3-improve_search_time.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "improve_search_time.ipynb",
      "provenance": [],
      "mount_file_id": "1L3ydSUTWTwULipyV3XU-Gt5eMboUyv7W",
      "authorship_tag": "ABX9TyM1Pl5mBMSlwbG0mnnfDNsO",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/AbdullahMakhdoom/Image-Search-Engine/blob/main/improve_search_time.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VkYF4lKDvul6"
      },
      "source": [
        "**Objective** : In this notebook, we will benchmark various Nearest Neighbors algorithms based on the time it takes to index and locate the most similar image based on the features of Caltech101.\n",
        "We will also see the improvement in search time when features are reduced by PCA. Aditionally, we will use a C++ library with python binding called Annoy and observe it's effect in speeding up the query time."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0lNlXZvIvuIm"
      },
      "source": [
        "import numpy as np\n",
        "import pickle\n",
        "from tqdm import tqdm, tqdm_notebook\n",
        "import random\n",
        "import time\n",
        "from sklearn.manifold import TSNE\n",
        "from sklearn.decomposition import PCA\n",
        "import PIL\n",
        "from PIL import Image\n",
        "from sklearn.neighbors import NearestNeighbors\n",
        "\n",
        "import glob\n",
        "import matplotlib\n",
        "import matplotlib.pyplot as plt\n",
        "import matplotlib.image as mpimg\n",
        "%matplotlib inline"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "l5vJdYEVw1RJ"
      },
      "source": [
        "## Standard Features\n",
        "\n",
        "Experimentation will be done on standard ResNet-50 features from the images of Caltech101 dataset. (extracted in `feature_extraction.ipynb`)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Vyk6VAPeh71k"
      },
      "source": [
        "filenames = pickle.load(open('/content/drive/MyDrive/Caltech101-features/filenames-caltech101.pickle', 'rb'))\n",
        "feature_list = pickle.load(open('/content/drive/MyDrive/Caltech101-features/features-caltech101-resnet.pickle',\n",
        "                                'rb'))\n",
        "class_ids = pickle.load(open('/content/drive/MyDrive/Caltech101-features/class_ids-caltech101.pickle', 'rb'))"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "MrpDN_jaxSWT",
        "outputId": "dbdb2117-7cb7-4568-e79e-8f2e3180098a"
      },
      "source": [
        "num_images = len(filenames)\n",
        "num_features_per_image = len(feature_list[0])\n",
        "print(\"Number of images = \", num_images)\n",
        "print(\"Number of features per image = \", num_features_per_image)"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Number of images =  8677\n",
            "Number of features per image =  2048\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ashgV6mNwr_l"
      },
      "source": [
        "random_image_index = random.randint(0, num_images)"
      ],
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wW1vuFczlzsN"
      },
      "source": [
        "### Standard Features + Brute Force on one image"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "H9GnUPBMwxqH",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "9c17c1a6-a66c-49a5-cafa-c6418622fec6"
      },
      "source": [
        "%timeit NearestNeighbors(n_neighbors = 5, algorithm='brute', metric='euclidean')\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "The slowest run took 6.22 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
            "100000 loops, best of 5: 3.44 µs per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vLgWgW2qlf0g"
      },
      "source": [
        "# timit command does not store variable in memory\n",
        "# so we need to re-run the same command and store the results\n",
        "neighbors = NearestNeighbors(n_neighbors=5,\n",
        "                             algorithm='brute',\n",
        "                             metric='euclidean').fit(feature_list)\n",
        "                             "
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "J0cqkxzQmpoi",
        "outputId": "b278910f-9cec-4f7c-c513-116f475743c4"
      },
      "source": [
        "%timeit neighbors.kneighbors([feature_list[random_image_index]])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "10 loops, best of 5: 82.6 ms per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Pf1T8K5zl7nY"
      },
      "source": [
        "### Standard Features + k-d Tree Algorithm on one image"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "AbPG9PPwl78w",
        "outputId": "a6e014b9-759c-404d-8d94-15b87ac7c265"
      },
      "source": [
        "%timeit NearestNeighbors(n_neighbors=5, algorithm='kd_tree').fit(feature_list)\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1 loop, best of 5: 2.74 s per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CvvJtSkEl8Tn"
      },
      "source": [
        "neighbors = NearestNeighbors(n_neighbors=5, algorithm='kd_tree').fit(feature_list)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "v9eiQGMYnCUd",
        "outputId": "fc0cb0b1-26d2-475e-90ca-85e4658110b3"
      },
      "source": [
        "%timeit neighbors.kneighbors([feature_list[random_image_index]])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "10 loops, best of 5: 37.4 ms per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "r5eRTLElnFKF"
      },
      "source": [
        "### Standard Features + Ball Tree Algorithm on one image"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ir4_2VhOnD6O",
        "outputId": "d94f1c7c-487f-4992-f8f2-69126f2acb73"
      },
      "source": [
        "%timeit NearestNeighbors(n_neighbors=5, algorithm='ball_tree').fit(feature_list)\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1 loop, best of 5: 2.17 s per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Om78bO09nM2m"
      },
      "source": [
        "neighbors = NearestNeighbors(n_neighbors=5,\n",
        "                             algorithm='ball_tree').fit(feature_list)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "FmfVLBrjnNuJ",
        "outputId": "edaf3770-aa45-4442-f8ec-1c74960e259f"
      },
      "source": [
        "%timeit neighbors.kneighbors([feature_list[random_image_index]])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "10 loops, best of 5: 25.4 ms per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zuvLxAVznVxw"
      },
      "source": [
        "Let's experiment on a random set of 1000 images."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ncMxOeRenQ9b"
      },
      "source": [
        "random_image_indices = random.sample(range(0, num_images), 1000)\n",
        "random_feature_list = [\n",
        "    feature_list[each_index] for each_index in random_image_indices]"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xSMtw6HvntFJ"
      },
      "source": [
        "### Standard features + Brute Force on 1000 images\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "irdVCpCZnsot",
        "outputId": "4d198858-048c-4262-9df6-774aa1fbdeff"
      },
      "source": [
        "neighbors = NearestNeighbors(n_neighbors=5,\n",
        "                             algorithm='brute',\n",
        "                             metric='euclidean').fit(feature_list)\n",
        "%timeit neighbors.kneighbors(random_feature_list)                             "
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1 loop, best of 5: 1.47 s per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jUq-sfIkoIDj"
      },
      "source": [
        "### Standard features +  k-d Tree  on 1000 images"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "qjcfvmLHnc5X",
        "outputId": "2de063a9-c224-4d83-db56-2006be8ae6ac"
      },
      "source": [
        "neighbors = NearestNeighbors(n_neighbors=5,\n",
        "                             algorithm='kd_tree').fit(feature_list)\n",
        "%timeit neighbors.kneighbors(random_feature_list)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1 loop, best of 5: 36.7 s per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qe_SQg3ooV1d"
      },
      "source": [
        "### Standard features +  Ball Tree on 1000 images"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "2qr4lcFsoTOK",
        "outputId": "f60689ab-9443-492b-d945-ff78f72ff3f4"
      },
      "source": [
        "neighbors = NearestNeighbors(n_neighbors=5,\n",
        "                             algorithm='ball_tree').fit(feature_list)\n",
        "%timeit neighbors.kneighbors(random_feature_list)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1 loop, best of 5: 24.7 s per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LEsM4DrNok20"
      },
      "source": [
        "## Dimensionality Reduction using PCA\n",
        " Using Principle Component Analysis(PCA), we reduce the feature size to 100, and thus further speed up search query time.\n",
        " "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "y7UoV5PvoaN-"
      },
      "source": [
        "num_feature_dimensions = 100"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MCSfEUO7w-iy"
      },
      "source": [
        "pca = PCA(n_components=num_feature_dimensions)\n",
        "pca.fit(feature_list)\n",
        "feature_list_compressed = pca.transform(feature_list)\n",
        "feature_list_compressed = feature_list_compressed.tolist()\n"
      ],
      "execution_count": 15,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8UtokP20xEfv",
        "outputId": "3b05befc-1a77-4e36-89df-c1fb350ee112"
      },
      "source": [
        "print(pca.explained_variance_ratio_[0:20])\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[0.06110197 0.04382468 0.04060568 0.03228543 0.02124298 0.01967341\n",
            " 0.01750924 0.01519272 0.01506694 0.01313028 0.01261717 0.01226299\n",
            " 0.01129626 0.01055883 0.00959002 0.0093974  0.00869048 0.00849483\n",
            " 0.008367   0.00772746]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cugt46RS0tF5"
      },
      "source": [
        "The numbers displayed above show the relative importance of the first 20 features."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oUecs3QZ00oR"
      },
      "source": [
        "### PCA + Brute Force Algorithm on one image"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "naCsRhtH0d0B",
        "outputId": "a5c8d6e1-f822-4061-e8e7-78c2fb8e6208"
      },
      "source": [
        "%timeit NearestNeighbors(n_neighbors=5, algorithm='brute', metric='euclidean').fit(feature_list_compressed)\n",
        "neighbors = NearestNeighbors(n_neighbors=5,\n",
        "                             algorithm='brute',\n",
        "                             metric='euclidean').fit(feature_list_compressed)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "10 loops, best of 5: 41 ms per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "IFgKLvoK07zg",
        "outputId": "622d3b9d-2357-416b-b608-9065d27e438f"
      },
      "source": [
        "%timeit neighbors.kneighbors([feature_list_compressed[random_image_index]])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "100 loops, best of 5: 2.09 ms per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FIhltSBg1NfT"
      },
      "source": [
        "###  PCA + k-d Tree Algorithm  on one image"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "vOUcVd4M1LEE",
        "outputId": "4639abf3-aa08-4fdb-8d66-153d56df6e68"
      },
      "source": [
        "%timeit NearestNeighbors(n_neighbors=5, algorithm='kd_tree').fit(feature_list_compressed)\n",
        "neighbors = NearestNeighbors(n_neighbors=5,\n",
        "                             algorithm='kd_tree').fit(feature_list_compressed)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "10 loops, best of 5: 130 ms per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "xDYx-Mtz1Vym",
        "outputId": "64c69269-6f33-450a-fe5c-0cc197222229"
      },
      "source": [
        "%timeit neighbors.kneighbors([feature_list_compressed[random_image_index]])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "100 loops, best of 5: 2.72 ms per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PXCBYqqK1b3b"
      },
      "source": [
        "###  PCA + Ball Tree Algorithm  on one image\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "kT6FOTGD1X5t",
        "outputId": "53df574e-f1a9-4f86-cbb8-1a162455b81b"
      },
      "source": [
        "%timeit NearestNeighbors(n_neighbors=5, algorithm='ball_tree').fit(feature_list_compressed)\n",
        "neighbors = NearestNeighbors(\n",
        "    n_neighbors=5, algorithm='ball_tree').fit(feature_list_compressed)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "10 loops, best of 5: 102 ms per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "JvNqGs7m1her",
        "outputId": "5c988e01-2d0f-4a5f-acb4-c91a13739731"
      },
      "source": [
        "%timeit neighbors.kneighbors([feature_list_compressed[random_image_index]])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1000 loops, best of 5: 1.87 ms per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nbzyBy0F1jnd"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "U6uJobQv1mah"
      },
      "source": [
        "Using the same random indices to experiment with 1000 set of images."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9cs0inKt1y-m"
      },
      "source": [
        "random_feature_list_compressed = [\n",
        "    feature_list_compressed[each_index] for each_index in random_image_indices\n",
        "]"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "AnoPyvFG112Z"
      },
      "source": [
        "### PCA + Brute Force on 1000 images"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "wpMcjCOQ10nZ",
        "outputId": "302e18b9-a403-40e0-9f0c-b797b0008be2"
      },
      "source": [
        "neighbors = NearestNeighbors(n_neighbors=5,\n",
        "                             algorithm='brute',\n",
        "                             metric='euclidean').fit(feature_list_compressed)\n",
        "%timeit neighbors.kneighbors(random_feature_list_compressed)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1 loop, best of 5: 205 ms per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dKIOZq512BJt"
      },
      "source": [
        "### PCA + k-d Tree Algorithm on 1000 images\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Y-iMRb60170O",
        "outputId": "8910d17d-c06f-4f1c-b5b9-7d11c6321cef"
      },
      "source": [
        "neighbors = NearestNeighbors(n_neighbors=5,\n",
        "                             algorithm='kd_tree').fit(feature_list_compressed)\n",
        "%timeit neighbors.kneighbors(random_feature_list_compressed)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1 loop, best of 5: 1.34 s per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ay6M8m-L2W33"
      },
      "source": [
        "### PCA + Ball Tree on 1000 images\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "wwNI4zWA19nV",
        "outputId": "2ce3b10d-9af6-402a-b44d-59d4e22f9a27"
      },
      "source": [
        "neighbors = NearestNeighbors(\n",
        "    n_neighbors=5, algorithm='ball_tree').fit(feature_list_compressed)\n",
        "%timeit neighbors.kneighbors(random_feature_list_compressed)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1 loop, best of 5: 1.1 s per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZMFefkmk2f1P"
      },
      "source": [
        "### Annoy\n",
        "Annoy (Approximate Nearest Neighbors Oh Yeah) is a C++ library with Python bindings for searching nearest neighbors. Synonymous with speed, it was released by Spotify and is used in production to serve its music recommendations."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "pvj34HT92j9n",
        "outputId": "f5bc8bc9-0017-4b02-df94-0a795e3ab93e"
      },
      "source": [
        "# installing annoy\n",
        "!pip3 install annoy"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Collecting annoy\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/a1/5b/1c22129f608b3f438713b91cd880dc681d747a860afe3e8e0af86e921942/annoy-1.17.0.tar.gz (646kB)\n",
            "\r\u001b[K     |▌                               | 10kB 16.7MB/s eta 0:00:01\r\u001b[K     |█                               | 20kB 24.2MB/s eta 0:00:01\r\u001b[K     |█▌                              | 30kB 21.4MB/s eta 0:00:01\r\u001b[K     |██                              | 40kB 15.3MB/s eta 0:00:01\r\u001b[K     |██▌                             | 51kB 16.8MB/s eta 0:00:01\r\u001b[K     |███                             | 61kB 15.4MB/s eta 0:00:01\r\u001b[K     |███▌                            | 71kB 12.4MB/s eta 0:00:01\r\u001b[K     |████                            | 81kB 13.4MB/s eta 0:00:01\r\u001b[K     |████▋                           | 92kB 13.1MB/s eta 0:00:01\r\u001b[K     |█████                           | 102kB 12.5MB/s eta 0:00:01\r\u001b[K     |█████▋                          | 112kB 12.5MB/s eta 0:00:01\r\u001b[K     |██████                          | 122kB 12.5MB/s eta 0:00:01\r\u001b[K     |██████▋                         | 133kB 12.5MB/s eta 0:00:01\r\u001b[K     |███████                         | 143kB 12.5MB/s eta 0:00:01\r\u001b[K     |███████▋                        | 153kB 12.5MB/s eta 0:00:01\r\u001b[K     |████████▏                       | 163kB 12.5MB/s eta 0:00:01\r\u001b[K     |████████▋                       | 174kB 12.5MB/s eta 0:00:01\r\u001b[K     |█████████▏                      | 184kB 12.5MB/s eta 0:00:01\r\u001b[K     |█████████▋                      | 194kB 12.5MB/s eta 0:00:01\r\u001b[K     |██████████▏                     | 204kB 12.5MB/s eta 0:00:01\r\u001b[K     |██████████▋                     | 215kB 12.5MB/s eta 0:00:01\r\u001b[K     |███████████▏                    | 225kB 12.5MB/s eta 0:00:01\r\u001b[K     |███████████▋                    | 235kB 12.5MB/s eta 0:00:01\r\u001b[K     |████████████▏                   | 245kB 12.5MB/s eta 0:00:01\r\u001b[K     |████████████▊                   | 256kB 12.5MB/s eta 0:00:01\r\u001b[K     |█████████████▏                  | 266kB 12.5MB/s eta 0:00:01\r\u001b[K     |█████████████▊                  | 276kB 12.5MB/s eta 0:00:01\r\u001b[K     |██████████████▏                 | 286kB 12.5MB/s eta 0:00:01\r\u001b[K     |██████████████▊                 | 296kB 12.5MB/s eta 0:00:01\r\u001b[K     |███████████████▏                | 307kB 12.5MB/s eta 0:00:01\r\u001b[K     |███████████████▊                | 317kB 12.5MB/s eta 0:00:01\r\u001b[K     |████████████████▎               | 327kB 12.5MB/s eta 0:00:01\r\u001b[K     |████████████████▊               | 337kB 12.5MB/s eta 0:00:01\r\u001b[K     |█████████████████▎              | 348kB 12.5MB/s eta 0:00:01\r\u001b[K     |█████████████████▊              | 358kB 12.5MB/s eta 0:00:01\r\u001b[K     |██████████████████▎             | 368kB 12.5MB/s eta 0:00:01\r\u001b[K     |██████████████████▊             | 378kB 12.5MB/s eta 0:00:01\r\u001b[K     |███████████████████▎            | 389kB 12.5MB/s eta 0:00:01\r\u001b[K     |███████████████████▊            | 399kB 12.5MB/s eta 0:00:01\r\u001b[K     |████████████████████▎           | 409kB 12.5MB/s eta 0:00:01\r\u001b[K     |████████████████████▉           | 419kB 12.5MB/s eta 0:00:01\r\u001b[K     |█████████████████████▎          | 430kB 12.5MB/s eta 0:00:01\r\u001b[K     |█████████████████████▉          | 440kB 12.5MB/s eta 0:00:01\r\u001b[K     |██████████████████████▎         | 450kB 12.5MB/s eta 0:00:01\r\u001b[K     |██████████████████████▉         | 460kB 12.5MB/s eta 0:00:01\r\u001b[K     |███████████████████████▎        | 471kB 12.5MB/s eta 0:00:01\r\u001b[K     |███████████████████████▉        | 481kB 12.5MB/s eta 0:00:01\r\u001b[K     |████████████████████████▍       | 491kB 12.5MB/s eta 0:00:01\r\u001b[K     |████████████████████████▉       | 501kB 12.5MB/s eta 0:00:01\r\u001b[K     |█████████████████████████▍      | 512kB 12.5MB/s eta 0:00:01\r\u001b[K     |█████████████████████████▉      | 522kB 12.5MB/s eta 0:00:01\r\u001b[K     |██████████████████████████▍     | 532kB 12.5MB/s eta 0:00:01\r\u001b[K     |██████████████████████████▉     | 542kB 12.5MB/s eta 0:00:01\r\u001b[K     |███████████████████████████▍    | 552kB 12.5MB/s eta 0:00:01\r\u001b[K     |███████████████████████████▉    | 563kB 12.5MB/s eta 0:00:01\r\u001b[K     |████████████████████████████▍   | 573kB 12.5MB/s eta 0:00:01\r\u001b[K     |█████████████████████████████   | 583kB 12.5MB/s eta 0:00:01\r\u001b[K     |█████████████████████████████▍  | 593kB 12.5MB/s eta 0:00:01\r\u001b[K     |██████████████████████████████  | 604kB 12.5MB/s eta 0:00:01\r\u001b[K     |██████████████████████████████▍ | 614kB 12.5MB/s eta 0:00:01\r\u001b[K     |███████████████████████████████ | 624kB 12.5MB/s eta 0:00:01\r\u001b[K     |███████████████████████████████▍| 634kB 12.5MB/s eta 0:00:01\r\u001b[K     |████████████████████████████████| 645kB 12.5MB/s eta 0:00:01\r\u001b[K     |████████████████████████████████| 655kB 12.5MB/s \n",
            "\u001b[?25hBuilding wheels for collected packages: annoy\n",
            "  Building wheel for annoy (setup.py) ... \u001b[?25l\u001b[?25hdone\n",
            "  Created wheel for annoy: filename=annoy-1.17.0-cp37-cp37m-linux_x86_64.whl size=386982 sha256=92acdda9e1d72ce1b08987796ab83e271f79049e78369e64add7fc3091c5ac2a\n",
            "  Stored in directory: /root/.cache/pip/wheels/3a/c5/59/cce7e67b52c8e987389e53f917b6bb2a9d904a03246fadcb1e\n",
            "Successfully built annoy\n",
            "Installing collected packages: annoy\n",
            "Successfully installed annoy-1.17.0\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rgqaI1dJ2eQR"
      },
      "source": [
        "from annoy import AnnoyIndex"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "83dvmwXK2wAK",
        "outputId": "b1678743-dda1-40ce-c58b-918e7a743d43"
      },
      "source": [
        "# Time the indexing for Annoy\n",
        "t = AnnoyIndex(2048) # Length of feature vector that is to be indexed\n",
        "starttime = time.time()\n",
        "for i in range(num_images):\n",
        "  feature = feature_list[i]\n",
        "  t.add_item(i, feature)\n",
        "endtime = time.time()\n",
        "print(endtime - starttime)\n",
        "t.build(50) # 50 trees to build\n",
        "t.save('/caltech101index.ann')"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "/usr/local/lib/python3.7/dist-packages/ipykernel_launcher.py:2: FutureWarning: The default argument for metric will be removed in future version of Annoy. Please pass metric='angular' explicitly.\n",
            "  \n"
          ],
          "name": "stderr"
        },
        {
          "output_type": "stream",
          "text": [
            "4.00521445274353\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 9
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FIQlqf8A5ScK"
      },
      "source": [
        "### Annoy on one image"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "SQoLnc-t5E35",
        "outputId": "149a382f-e3c3-445c-d211-d9a894bc8981"
      },
      "source": [
        "u = AnnoyIndex(2048)\n",
        "%timeit u.get_nns_by_vector(feature_list[random_image_index], 5, include_distances = True)\n",
        "indexes = u.get_nns_by_vector(feature_list[random_image_index], 5,\n",
        "                            include_distances = True)"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "/usr/local/lib/python3.7/dist-packages/ipykernel_launcher.py:1: FutureWarning: The default argument for metric will be removed in future version of Annoy. Please pass metric='angular' explicitly.\n",
            "  \"\"\"Entry point for launching an IPython kernel.\n"
          ],
          "name": "stderr"
        },
        {
          "output_type": "stream",
          "text": [
            "1000 loops, best of 5: 460 µs per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7xR3eaX658Li"
      },
      "source": [
        "Helper function to time the search for multiple images for Annoy. Perform the search for the same images multiple times to get an average value."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "K4JM0u9bqCxe"
      },
      "source": [
        "def calculate_annoy_time():\n",
        "    for i in range(0, 1000):\n",
        "        indexes = u.get_nns_by_vector(feature_list[random_image_index],\n",
        "                                      5,\n",
        "                                      include_distances=True)"
      ],
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1R5pkf0W52dJ"
      },
      "source": [
        "### Annoy on 1000 images"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hzLPBqAT5zmd",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "6fda4b58-d52d-41cd-afc2-9b8512a77212"
      },
      "source": [
        "%timeit calculate_annoy_time()"
      ],
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1 loop, best of 5: 454 ms per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qM82oRo56A80"
      },
      "source": [
        "### PCA + Annoy"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "wfppcYj65_N_",
        "outputId": "a00907c2-839e-48af-9ab3-402eb28c3b22"
      },
      "source": [
        "starttime = time.time()\n",
        "# Length of item vector that will be indexed\n",
        "t = AnnoyIndex(num_feature_dimensions)\n",
        "\n",
        "for i in range(num_images):\n",
        "  feature = feature_list_compressed[i]\n",
        "  t.add_item(i, feature)\n",
        "endtime = time.time()\n",
        "print(endtime - starttime)\n",
        "t.build(50) # 50 trees\n",
        "t.save('/caltech101index-pca.ann')"
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "/usr/local/lib/python3.7/dist-packages/ipykernel_launcher.py:3: FutureWarning: The default argument for metric will be removed in future version of Annoy. Please pass metric='angular' explicitly.\n",
            "  This is separate from the ipykernel package so we can avoid doing imports until\n"
          ],
          "name": "stderr"
        },
        {
          "output_type": "stream",
          "text": [
            "0.0298306941986084\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 17
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eSt7Kj1z7yZj"
      },
      "source": [
        "### PCA + Annoy for one image"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "mOj1Pu_m7nHS",
        "outputId": "6077fde2-77b2-447a-c73b-f4378cdabc33"
      },
      "source": [
        "u = AnnoyIndex(num_feature_dimensions)\n",
        "%timeit u.get_nns_by_vector(feature_list_compressed[random_image_index], 5, include_distances=True)\n",
        "indexes = u.get_nns_by_vector(feature_list_compressed[random_image_index], 5,\n",
        "                            include_distances=True)"
      ],
      "execution_count": 19,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "/usr/local/lib/python3.7/dist-packages/ipykernel_launcher.py:1: FutureWarning: The default argument for metric will be removed in future version of Annoy. Please pass metric='angular' explicitly.\n",
            "  \"\"\"Entry point for launching an IPython kernel.\n"
          ],
          "name": "stderr"
        },
        {
          "output_type": "stream",
          "text": [
            "The slowest run took 20.73 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
            "100000 loops, best of 5: 2.21 µs per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RtLw-s1v8Y7T"
      },
      "source": [
        "Again, writing a helper function to get an average time to perform search for the same image, 1000 times."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jE5Z-2S68Kcg"
      },
      "source": [
        "def calculate_annoy_time():\n",
        "    for i in range(0, 1000):\n",
        "        indexes = u.get_nns_by_vector(feature_list_compressed[random_image_index],\n",
        "                                      5,\n",
        "                                      include_distances=True)"
      ],
      "execution_count": 20,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NBdX16t28xCH"
      },
      "source": [
        "### PCA + Annoy on 1000 images"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ySCtd-Gz8vyz",
        "outputId": "4c88b0bb-88ab-497d-b1ff-d694bfbf0107"
      },
      "source": [
        "%timeit calculate_annoy_time()"
      ],
      "execution_count": 21,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "100 loops, best of 5: 2.42 ms per loop\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}