part3_similarity_search.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.6.8"
    },
    "toc": {
      "base_numbering": 1,
      "nav_menu": {},
      "number_sections": true,
      "sideBar": true,
      "skip_h1_title": false,
      "title_cell": "Table of Contents",
      "title_sidebar": "Contents",
      "toc_cell": false,
      "toc_position": {},
      "toc_section_display": true,
      "toc_window_display": false
    },
    "colab": {
      "name": "part3-similarity-search.ipynb",
      "provenance": [],
      "collapsed_sections": [
        "WTxKQVXeS8hN",
        "h331lRmtS8hO",
        "ktTi4DJBS8hO",
        "i5TVhNKFS8hO",
        "CpyEuCIoS8hO",
        "CWsd7Vr0S8hO",
        "E2ePDt-RS8hO",
        "jOGrNx7SS8hO",
        "-YvB3bpGS8hO",
        "EQcUxvzKS8hO",
        "SyGE3NCsS8hO",
        "zq3FLob5S8hO",
        "TMyQJWJ8S8hO",
        "6L-IRKl9S8hO",
        "ZwWB67L-S8hO",
        "1S2m2SgnS8hP",
        "PHA9pwlPS8hP",
        "Sby7N9dAS8hP",
        "n24cywM2S8hP",
        "8UakUnRQS8hP",
        "tTFG_gtjS8hP",
        "VasjWaSrS8hP",
        "aMApJHWRS8hP"
      ],
      "include_colab_link": true
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/xiaoya27/ANN-CBIR/blob/main/part3_similarity_search.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JxVpNeFsS8hM"
      },
      "source": [
        "# Similarity Search\n",
        "\n",
        "## part3\n",
        "\n",
        "We benchmark the algorithms based on the time it takes to index images and locate the most similar image based on its features using the Caltech-101 dataset. We also experiment with t-SNE and PCA.\n",
        "\n",
        "### Understanding the time it takes to index images and locate the most similar image based on its features\n",
        "\n",
        "For these experiments we will use the features of the Caltech101 dataset that we read above.\n",
        "\n",
        "First, let's choose a random image to experiment with. We will be using the same image for all the following experiments. Note: the results may change if the image is changed."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zcD3JFhaS8hN"
      },
      "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": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9_VGDEpVdBRF"
      },
      "source": [
        "from google.colab import drive\n",
        "drive.mount('/content/drive')\n",
        "%cd /content/drive/MyDrive/pipline-data\n",
        "!pwd"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cgepC7AIS8hN"
      },
      "source": [
        "filenames = pickle.load(open('filenames-caltech101.pickle', 'rb'))\n",
        "feature_list = pickle.load(open('features-caltech101-resnet.pickle',\n",
        "                                'rb'))\n",
        "class_ids = pickle.load(open('class_ids-caltech101.pickle', 'rb'))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6eCE2S0OS8hN"
      },
      "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": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0NdhIXxOS8hN"
      },
      "source": [
        "random_image_index = random.randint(0, num_images)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Jwy2EuyAS8hN"
      },
      "source": [
        "### Standard features\n",
        "\n",
        "The following experiments are based on the ResNet-50 features derived from the images of the Caltech101 dataset. \n",
        "\n",
        "### Standard features + Brute Force Algorithm on one image\n",
        "\n",
        "We will be timing the indexing for various Nearest Neighbors algorithms, so let's start with timing the indexing for the Brute force algorithm. While running terminal commands in iPython like the `timeit` command, the variables are not stored in memory, so we need to rerun the same command to compute and store the results in the variable. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aD-goooFS8hN"
      },
      "source": [
        "%timeit NearestNeighbors(n_neighbors=5, algorithm='brute', metric='euclidean').fit(feature_list)\n",
        "neighbors = NearestNeighbors(n_neighbors=5,\n",
        "                             algorithm='brute',\n",
        "                             metric='euclidean').fit(feature_list)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Rnr4xJHZS8hN"
      },
      "source": [
        "Now, let's look at the time it takes to search for the nearest neighbors for the selected random image using the trained model with the Brute force algorithm."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HNve6GBAS8hN"
      },
      "source": [
        "%timeit neighbors.kneighbors([feature_list[random_image_index]])"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "950KM2SSS8hN"
      },
      "source": [
        "###  Standard features + k-d Tree Algorithm  on one image\n",
        "\n",
        "Now let's turn our attention to the next nearest neighbors algorithm, the k-d tree. Let's time the indexing for the k-d tree algorithm."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FcTJ6DEyS8hN"
      },
      "source": [
        "%timeit NearestNeighbors(n_neighbors=5, algorithm='kd_tree').fit(feature_list)\n",
        "neighbors = NearestNeighbors(n_neighbors=5,\n",
        "                             algorithm='kd_tree').fit(feature_list)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xW_20IrES8hN"
      },
      "source": [
        "Now, time the search for the same random image using the k-d tree trained model."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "t4cSUbCPS8hN"
      },
      "source": [
        "%timeit neighbors.kneighbors([feature_list[random_image_index]])"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ypR2bUh5S8hN"
      },
      "source": [
        "###  Standard features + Ball Tree Algorithm  on one image\n",
        "\n",
        "Finally, its time for our last nearest neighbors algorithm - the Ball Tree algorithm. As before, let's calculate the time it takes to train the model."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MG7RWpDHS8hN"
      },
      "source": [
        "%timeit NearestNeighbors(n_neighbors=5, algorithm='ball_tree').fit(feature_list)\n",
        "neighbors = NearestNeighbors(n_neighbors=5,\n",
        "                             algorithm='ball_tree').fit(feature_list)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eEkuuvfuS8hN"
      },
      "source": [
        "As before, let's time the search for the Ball Tree model."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0UowcibGS8hN"
      },
      "source": [
        "%timeit neighbors.kneighbors([feature_list[random_image_index]])"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8aOJCe7zS8hN"
      },
      "source": [
        "We will increase the number of our test images so that we can experiment with how the scalability of different nearest neighbors algorithms change. Let's choose a random set of 100 or 1000 images to experiment. \n",
        "\n",
        "Note: the results may change if any of the images are changed"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cOnS_8T0S8hN"
      },
      "source": [
        "Generate a list of images to do the next set of experiments on."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "IH2mxaknS8hN"
      },
      "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\n",
        "]"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WTxKQVXeS8hN"
      },
      "source": [
        "### Standard features + Brute Force Algorithm on a set of images\n",
        "\n",
        "Time the search for the Brute force algorithm."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "K4-t8E_DS8hO"
      },
      "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": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "h331lRmtS8hO"
      },
      "source": [
        "### Standard features +  k-d Tree Algorithm on a set of images\n",
        "\n",
        "Time the search for the k-d tree algorithm."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9ycPxx5uS8hO"
      },
      "source": [
        "neighbors = NearestNeighbors(n_neighbors=5,\n",
        "                             algorithm='kd_tree').fit(feature_list)\n",
        "%timeit neighbors.kneighbors(random_feature_list)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ktTi4DJBS8hO"
      },
      "source": [
        "### Standard features +  Ball Tree Algorithm on a set of images\n",
        "\n",
        "Time the search for the Ball Tree algorithm."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "U9Y4ht7IS8hO"
      },
      "source": [
        "neighbors = NearestNeighbors(n_neighbors=5,\n",
        "                             algorithm='ball_tree').fit(feature_list)\n",
        "%timeit neighbors.kneighbors(random_feature_list)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "i5TVhNKFS8hO"
      },
      "source": [
        "### PCA\n",
        "\n",
        "Now we have seen the time it takes to index and search using nearest neighbor algorithms on the full feature length. We can use PCA to compress the features and reduce the time. As before we set the number of features intended."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-G6KUTV1S8hO"
      },
      "source": [
        "num_feature_dimensions = 100\n",
        "num_feature_dimensions = min(num_images, num_feature_dimensions,\n",
        "                             len(feature_list[0]))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YnNx7vYjS8hO"
      },
      "source": [
        "Train the PCA model with the number of desired feature dimensions."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dj6BJRXVS8hO"
      },
      "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()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ewD0ZCC8S8hO"
      },
      "source": [
        "Let's try to understand the importance of each of the resultant features. The numbers displayed below show the relative importance of the first 20 features."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "G790_g5-S8hO"
      },
      "source": [
        "print(pca.explained_variance_ratio_[0:20])"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "efVtY-6QS8hO"
      },
      "source": [
        "Repeat the timing experiments. We use the same random image to experiment.\n",
        "Note: the results may change if the image is changed."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CpyEuCIoS8hO"
      },
      "source": [
        "### PCA + Brute Force Algorithm on one image\n",
        "\n",
        "Let's time the indexing for the brute force algorithm."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "m14Kbl01S8hO"
      },
      "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": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Kt8p_yt0S8hO"
      },
      "source": [
        "We will now time the search for the brute force algorithm."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "scrolled": false,
        "id": "Wu39G4MRS8hO"
      },
      "source": [
        "%timeit neighbors.kneighbors([feature_list_compressed[random_image_index]])"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CWsd7Vr0S8hO"
      },
      "source": [
        "###  PCA + k-d Tree Algorithm  on one image\n",
        "\n",
        "Time the indexing for the k-d tree algorithm."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Xm2j-Pq5S8hO"
      },
      "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": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8D0NPbq9S8hO"
      },
      "source": [
        "Time the search for the k-d tree algorithm."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0Wuf5zCeS8hO"
      },
      "source": [
        "%timeit neighbors.kneighbors([feature_list_compressed[random_image_index]])"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "E2ePDt-RS8hO"
      },
      "source": [
        "###  PCA + Ball Tree Algorithm  on one image\n",
        "\n",
        "Time the indexing for the ball tree algorithm."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1utq7C5yS8hO"
      },
      "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": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RHaEJeiiS8hO"
      },
      "source": [
        "Time the search for the ball tree algorithm."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hZ-F9VV6S8hO"
      },
      "source": [
        "%timeit neighbors.kneighbors([feature_list_compressed[random_image_index]])"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DdVzK610S8hO"
      },
      "source": [
        "We use the same random indices to experiment. Note: the results may change if any of the images are changed.\n",
        "\n",
        "Generate a list of images to do the next set of experiments on."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XKXh5deKS8hO"
      },
      "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": "jOGrNx7SS8hO"
      },
      "source": [
        "### PCA + Brute Force Algorithm on a set of images\n",
        "\n",
        "Time the search for the brute force algorithm."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9Hz2dI6_S8hO"
      },
      "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": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-YvB3bpGS8hO"
      },
      "source": [
        "### PCA + k-d Tree Algorithm on a set of images\n",
        "\n",
        "Time the search for the k-d tree algorithm."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qH41sDkTS8hO"
      },
      "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": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EQcUxvzKS8hO"
      },
      "source": [
        "### PCA + Ball Tree Algorithm on a set of images\n",
        "\n",
        "Time the search for the Ball Tree algorithm."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mhezP6uHS8hO"
      },
      "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": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SyGE3NCsS8hO"
      },
      "source": [
        "### Annoy \n",
        "\n",
        "Make sure you have `annoy` installed. You can install it using pip, `pip3 install annoy`."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "r14OGhbBS8hO"
      },
      "source": [
        "from annoy import AnnoyIndex"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "IKvwnzx0S8hO"
      },
      "source": [
        "# Time the indexing for Annoy\n",
        "t = AnnoyIndex(2048)  # Length of item vector that will 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(40)  # 50 trees\n",
        "t.save('data/caltech101index.ann')"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zq3FLob5S8hO"
      },
      "source": [
        "### Annoy on one image \n",
        "\n",
        "Time the search for one image for Annoy."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sDfGn9QOS8hO"
      },
      "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],\n",
        "                              5,\n",
        "                              include_distances=True)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tuyZhcOBS8hO"
      },
      "source": [
        "Helper function to time the search for multiple images for Annoy. Perform the search for the same image multiple times to get an average value.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dN-r-4hcS8hO"
      },
      "source": [
        "def calculate_annoy_time():\n",
        "    for i in range(0, 100):\n",
        "        indexes = u.get_nns_by_vector(feature_list[random_image_index],\n",
        "                                      5,\n",
        "                                      include_distances=True)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TMyQJWJ8S8hO"
      },
      "source": [
        "### Annoy on a set of images\n",
        "\n",
        "Time the search for multiple images for Annoy."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1yPXkZsCS8hO"
      },
      "source": [
        "%time calculate_annoy_time()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6L-IRKl9S8hO"
      },
      "source": [
        "### PCA + Annoy\n",
        "\n",
        "Now, let's time the indexing for Annoy for the PCA generated features."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "L34MWP6JS8hO"
      },
      "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(40)  # 50 trees\n",
        "t.save('data/caltech101index.ann')"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZwWB67L-S8hO"
      },
      "source": [
        "### PCA + Annoy for one image\n",
        "\n",
        "Time the search for one image for Annoy."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "59Aws_bFS8hO"
      },
      "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],\n",
        "                              5,\n",
        "                              include_distances=True)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "AKEdJl3vS8hP"
      },
      "source": [
        "Helper function to time the search for multiple images for Annoy. Perform the search for the same image multiple times to get an average value.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "imYf7iCkS8hP"
      },
      "source": [
        "def calculate_annoy_time():\n",
        "    for i in range(0, 100):\n",
        "        indexes = u.get_nns_by_vector(\n",
        "            feature_list_compressed[random_image_index],\n",
        "            5,\n",
        "            include_distances=True)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1S2m2SgnS8hP"
      },
      "source": [
        "### PCA + Annoy on a set of images\n",
        "\n",
        "Time the search for multiple images for Annoy."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "F30gchizS8hP"
      },
      "source": [
        "%time calculate_annoy_time()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PHA9pwlPS8hP"
      },
      "source": [
        "### NMS Lib"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wTuGAk-vS8hP"
      },
      "source": [
        "import nmslib"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9XZvkZI5S8hP"
      },
      "source": [
        "index = nmslib.init(method='hnsw', space='cosinesimil')\n",
        "index.addDataPointBatch(feature_list_compressed)\n",
        "index.createIndex({'post': 2}, print_progress=True)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Sby7N9dAS8hP"
      },
      "source": [
        "### NMS Lib on one image"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yytCjZrcS8hP"
      },
      "source": [
        "# Query for the nearest neighbors of the first datapoint\n",
        "%timeit index.knnQuery(feature_list_compressed[random_image_index], k=5)\n",
        "ids, distances = index.knnQuery(feature_list_compressed[random_image_index],\n",
        "                                k=5)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "n24cywM2S8hP"
      },
      "source": [
        "### NMS Lib on a set of images"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pAQImcTjS8hP"
      },
      "source": [
        "# Get all nearest neighbors for all the datapoint\n",
        "# using a pool of 4 threads to compute\n",
        "%timeit index.knnQueryBatch(feature_list_compressed, k=5, num_threads=16)\n",
        "neighbors = index.knnQueryBatch(feature_list_compressed, k=5, num_threads=16)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8UakUnRQS8hP"
      },
      "source": [
        "### Falconn\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jl_saYaMS8hP"
      },
      "source": [
        "import falconn"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0UhSAwXUS8hP"
      },
      "source": [
        "# Setup different parameters for Falonn\n",
        "parameters = falconn.LSHConstructionParameters()\n",
        "num_tables = 1\n",
        "parameters.l = num_tables\n",
        "parameters.dimension = num_feature_dimensions\n",
        "parameters.distance_function = falconn.DistanceFunction.EuclideanSquared\n",
        "parameters.lsh_family = falconn.LSHFamily.CrossPolytope\n",
        "parameters.num_rotations = 1\n",
        "parameters.num_setup_threads = 1\n",
        "parameters.storage_hash_table = falconn.StorageHashTable.BitPackedFlatHashTable\n",
        "\n",
        "# Train the Falconn model\n",
        "falconn.compute_number_of_hash_functions(16, parameters)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tTFG_gtjS8hP"
      },
      "source": [
        "### Falconn on a set of images"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xr1fsDNFS8hP"
      },
      "source": [
        "dataset = np.array(feature_list_compressed)\n",
        "a = np.random.randn(8677, 100)\n",
        "a /= np.linalg.norm(a, axis=1).reshape(-1, 1)\n",
        "dataset = a\n",
        "\n",
        "index = falconn.LSHIndex(parameters)\n",
        "%time index.setup(dataset)\n",
        "\n",
        "query_object = index.construct_query_object()\n",
        "num_probes = 1\n",
        "query_object.set_num_probes(num_probes)\n",
        "\n",
        "searchQuery = np.array(feature_list_compressed[random_image_index])\n",
        "searchQuery = a[0]\n",
        "%timeit query_object.find_k_nearest_neighbors(searchQuery, 5)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VasjWaSrS8hP"
      },
      "source": [
        "### PCA + Annoy"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tbUFqdK6S8hP"
      },
      "source": [
        "# Time the indexing for Annoy for the PCA generated features\n",
        "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 = dataset[i]\n",
        "    t.add_item(i, feature)\n",
        "endtime = time.time()\n",
        "print(endtime - starttime)\n",
        "t.build(40)  # 50 trees\n",
        "t.save('data/caltech101index.ann')"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mHxwGoImS8hP"
      },
      "source": [
        "u = AnnoyIndex(num_feature_dimensions)\n",
        "# Time the search for one image for Annoy\n",
        "%timeit u.get_nns_by_vector(dataset[random_image_index], 5, include_distances=True)\n",
        "indexes = u.get_nns_by_vector(dataset[random_image_index],\n",
        "                              5,\n",
        "                              include_distances=True)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aMApJHWRS8hP"
      },
      "source": [
        "### Some benchmarks on different algorithms to see relative speeds\n",
        "\n",
        "These results lead to the benchmarking of time for indexing and searching on Caltech101. Repeating Level 2 on the Caltech256 features we can benchmark that as well. \n",
        "\n",
        "Benchmarking the different models on Caltech101. (Rounded to nearest integer)\n",
        "\n",
        "| Algorithm | Number of features indexed | Time to search 1 image (ms) | Time to search 100 images (ms)  | Time to search 1000 images (ms)  | Time to index (ms)    |\n",
        "|-------------|----------------------------|------------------------|---------------------------|---|---|\n",
        "| Brute force | 2048 | 14 | 38 | 240 | 22 | \n",
        "| k-d tree | 2048 | 16 | 2270 | 24100 | 1020    |\n",
        "| Ball tree | 2048 | 15 | 1690 | 17000 | 1090   |\n",
        "| PCA + brute force | 100 | 1 | 13 | 135 | 0.334   |\n",
        "| PCA + k-d tree | 100 | 1 | 77 | 801 | 20   |\n",
        "| PCA + ball tree | 100 | 1 | 80 | 761 |  23   |\n",
        "| Annoy | 2048 | 0.16 | 40    | 146 | 1420 |\n",
        "| PCA + Annoy | 100 | **.008** | **2.3**   | **20.3** | 109 | \n",
        "\n",
        "\n",
        "Benchmarking the different models on Caltech256. (Rounded to nearest integer)\n",
        "\n",
        "\n",
        "| Algorithm | Number of features indexed | Time to search 1 image (ms) | Time to search 100 images (ms)  | Time to search 1000 images (ms)  | Time to index (ms)    |\n",
        "|-------------|----------------------------|------------------------|---------------------------|---|---|\n",
        "| Brute force | 2048 |  16 | 135 |  747  | 23  | \n",
        "| k-d tree | 2048 |  15  | 7400  | 73000 |    4580 |\n",
        "| Ball tree | 2048 | 15 | 5940  | 59700 |   4750  |\n",
        "| PCA + brute force | 100 | 6.42  | 43.8  | 398  |  1.06   |\n",
        "| PCA + k-d tree | 100 |  6.46  | 530  | 5200  |  89.6  |\n",
        "| PCA + ball tree | 100 | 6.43  |  601 |  6000 |   104  |\n",
        "| Annoy | 2048 | .156  |  41.6  | 166  | 4642  |\n",
        "| PCA + Annoy | 100 | **.0076**  |   **2.68** | **23.8**  |  296 | "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HlaQNam1TLbW"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}