task_01_duplicate_detection_done.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Project task 01: Near duplicate detection with LSH"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 186,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gzip\n",
    "import tarfile\n",
    "\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import time\n",
    "import itertools as it \n",
    "\n",
    "from sklearn import preprocessing\n",
    "from collections import defaultdict\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To goal of this task is to find near duplicate songs in the Million Song dataset. You can imagine a scenario were the same song appears on multiple different releases with only small feature variation (e.g. duration or loudness)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Load data and extract the data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll be working with the Million Songs Dataset, a freely-available collection of audio features and metadata for a million contemporary popular music tracks.\n",
    "\n",
    "Specifically, we will work with a smaller subset of 10 000 songs ([download link](http://static.echonest.com/millionsongsubset_full.tar.gz))."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 187,
   "metadata": {},
   "outputs": [],
   "source": [
    "tar = tarfile.open('millionsongsubset_full.tar.gz', 'r')\n",
    "members = tar.getmembers()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 188,
   "metadata": {},
   "outputs": [],
   "source": [
    "tar.extract(members[5])\n",
    "summary = pd.HDFStore(members[5].name)\n",
    "songs = summary['/analysis/songs']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Show a snippet of how the data looks like:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 189,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>analysis_sample_rate</th>\n",
       "      <th>audio_md5</th>\n",
       "      <th>danceability</th>\n",
       "      <th>duration</th>\n",
       "      <th>end_of_fade_in</th>\n",
       "      <th>energy</th>\n",
       "      <th>idx_bars_confidence</th>\n",
       "      <th>idx_bars_start</th>\n",
       "      <th>idx_beats_confidence</th>\n",
       "      <th>idx_beats_start</th>\n",
       "      <th>...</th>\n",
       "      <th>key</th>\n",
       "      <th>key_confidence</th>\n",
       "      <th>loudness</th>\n",
       "      <th>mode</th>\n",
       "      <th>mode_confidence</th>\n",
       "      <th>start_of_fade_out</th>\n",
       "      <th>tempo</th>\n",
       "      <th>time_signature</th>\n",
       "      <th>time_signature_confidence</th>\n",
       "      <th>track_id</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>22050</td>\n",
       "      <td>a600d65cf157a306be60f26ecbf218f4</td>\n",
       "      <td>0.0</td>\n",
       "      <td>280.21506</td>\n",
       "      <td>0.238</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>...</td>\n",
       "      <td>5</td>\n",
       "      <td>0.555</td>\n",
       "      <td>-3.306</td>\n",
       "      <td>1</td>\n",
       "      <td>0.500</td>\n",
       "      <td>275.528</td>\n",
       "      <td>173.205</td>\n",
       "      <td>5</td>\n",
       "      <td>0.120</td>\n",
       "      <td>TRACCVZ128F4291A8A</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>22050</td>\n",
       "      <td>c64d75b0588e5ab552ee94548b50a4fa</td>\n",
       "      <td>0.0</td>\n",
       "      <td>191.68608</td>\n",
       "      <td>0.000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>...</td>\n",
       "      <td>0</td>\n",
       "      <td>0.501</td>\n",
       "      <td>-10.764</td>\n",
       "      <td>1</td>\n",
       "      <td>0.710</td>\n",
       "      <td>184.128</td>\n",
       "      <td>150.955</td>\n",
       "      <td>4</td>\n",
       "      <td>0.600</td>\n",
       "      <td>TRACCMH128F428E4CD</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>22050</td>\n",
       "      <td>0cadd310865701bb93ced1cd78e8910a</td>\n",
       "      <td>0.0</td>\n",
       "      <td>222.92853</td>\n",
       "      <td>0.000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>...</td>\n",
       "      <td>1</td>\n",
       "      <td>0.329</td>\n",
       "      <td>-9.035</td>\n",
       "      <td>1</td>\n",
       "      <td>0.407</td>\n",
       "      <td>216.300</td>\n",
       "      <td>93.056</td>\n",
       "      <td>4</td>\n",
       "      <td>1.000</td>\n",
       "      <td>TRACCSW128F148C7C3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>22050</td>\n",
       "      <td>14be4fc1170152c445b3be7b8d18dfec</td>\n",
       "      <td>0.0</td>\n",
       "      <td>278.38649</td>\n",
       "      <td>0.496</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>...</td>\n",
       "      <td>7</td>\n",
       "      <td>0.313</td>\n",
       "      <td>-23.095</td>\n",
       "      <td>1</td>\n",
       "      <td>0.387</td>\n",
       "      <td>278.386</td>\n",
       "      <td>127.113</td>\n",
       "      <td>1</td>\n",
       "      <td>0.446</td>\n",
       "      <td>TRACCXJ128F428F0CF</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>22050</td>\n",
       "      <td>1def5d8298e8cb29a188a5a7c0e9429a</td>\n",
       "      <td>0.0</td>\n",
       "      <td>89.15546</td>\n",
       "      <td>4.847</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>...</td>\n",
       "      <td>2</td>\n",
       "      <td>0.000</td>\n",
       "      <td>-20.359</td>\n",
       "      <td>1</td>\n",
       "      <td>0.000</td>\n",
       "      <td>79.203</td>\n",
       "      <td>90.660</td>\n",
       "      <td>3</td>\n",
       "      <td>0.524</td>\n",
       "      <td>TRACCVS12903D014F8</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>5 rows × 31 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "   analysis_sample_rate                         audio_md5  danceability  \\\n",
       "0                 22050  a600d65cf157a306be60f26ecbf218f4           0.0   \n",
       "1                 22050  c64d75b0588e5ab552ee94548b50a4fa           0.0   \n",
       "2                 22050  0cadd310865701bb93ced1cd78e8910a           0.0   \n",
       "3                 22050  14be4fc1170152c445b3be7b8d18dfec           0.0   \n",
       "4                 22050  1def5d8298e8cb29a188a5a7c0e9429a           0.0   \n",
       "\n",
       "    duration  end_of_fade_in  energy  idx_bars_confidence  idx_bars_start  \\\n",
       "0  280.21506           0.238     0.0                    0               0   \n",
       "1  191.68608           0.000     0.0                    0               0   \n",
       "2  222.92853           0.000     0.0                    0               0   \n",
       "3  278.38649           0.496     0.0                    0               0   \n",
       "4   89.15546           4.847     0.0                    0               0   \n",
       "\n",
       "   idx_beats_confidence  idx_beats_start         ...          key  \\\n",
       "0                     0                0         ...            5   \n",
       "1                     0                0         ...            0   \n",
       "2                     0                0         ...            1   \n",
       "3                     0                0         ...            7   \n",
       "4                     0                0         ...            2   \n",
       "\n",
       "   key_confidence  loudness  mode  mode_confidence  start_of_fade_out  \\\n",
       "0           0.555    -3.306     1            0.500            275.528   \n",
       "1           0.501   -10.764     1            0.710            184.128   \n",
       "2           0.329    -9.035     1            0.407            216.300   \n",
       "3           0.313   -23.095     1            0.387            278.386   \n",
       "4           0.000   -20.359     1            0.000             79.203   \n",
       "\n",
       "     tempo  time_signature  time_signature_confidence            track_id  \n",
       "0  173.205               5                      0.120  TRACCVZ128F4291A8A  \n",
       "1  150.955               4                      0.600  TRACCMH128F428E4CD  \n",
       "2   93.056               4                      1.000  TRACCSW128F148C7C3  \n",
       "3  127.113               1                      0.446  TRACCXJ128F428F0CF  \n",
       "4   90.660               3                      0.524  TRACCVS12903D014F8  \n",
       "\n",
       "[5 rows x 31 columns]"
      ]
     },
     "execution_count": 189,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "songs.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "We should have $31$ columns and $10~000$ rows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 190,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10000\n"
     ]
    }
   ],
   "source": [
    "songs_all = songs\n",
    "print(len(songs))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since not all features are important we are going to consider a subset of features (columns) that are relevant for duplicate detection.\n",
    "\n",
    "We will also convert the pandas dataframe into a numpy array so it is easier to work with."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 204,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10000, 8)"
      ]
     },
     "execution_count": 204,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "subset = songs[['duration', 'end_of_fade_in', 'key', 'loudness',\n",
    "                'mode', 'start_of_fade_out', 'tempo', 'time_signature',]]\n",
    "\n",
    "data_matrix = subset.values\n",
    "\n",
    "#data_matrix = data_matrix [:500,:]\n",
    "data_matrix.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Additionally we will standardize the data to have zero mean and unit variance as a preprocessing step."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 205,
   "metadata": {},
   "outputs": [],
   "source": [
    "scaled_data = preprocessing.scale(data_matrix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Implementaion\n",
    "\n",
    "Your task is to implement near duplicate detection using LSH with cosine similarity.\n",
    "More specifically you have to:\n",
    "* Generate duplicate **candidates** based on LSH with $b$ bands and $r$ rows per band\n",
    "* Refine the candidates by computing the exact cosine distance\n",
    "* Report all pairs/duplicates with cosine distance < $d$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implement a function that computes the cosine distance between two rows (instances) in the data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 207,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cosine_distance(X, i, j):\n",
    "    \"\"\"Compute cosine distance between two rows of a data matrix.\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    X : np.array, shape [N, D]\n",
    "        Data matrix.\n",
    "    i : int\n",
    "        Index of the first row.\n",
    "    j : int\n",
    "        Index of the second row.\n",
    "        \n",
    "    Returns\n",
    "    -------\n",
    "    d : float\n",
    "        Cosine distance between the two rows of the data matrix.\n",
    "        \n",
    "    NOTE: this function is actually not used due to the way we wrote the other functions\n",
    "    (IE stored referenced to actual data not indexes in initial matrix) \n",
    "    This function is provided just to complete all the tasks. \n",
    "    See cosine_distance_alternative function for the alternative used in the code.\n",
    "    \"\"\"\n",
    "    d = 1.0 - np.dot(X[i,:],X[j,:])/(np.linalg.norm(X[i,:])*np.linalg.norm(X[j,:]))\n",
    "    return d\n",
    "\n",
    "def cosine_distance_alternative(v1,v2):\n",
    "    \"\"\"\n",
    "    TODO: documentation\n",
    "    \"\"\"\n",
    "    d = np.dot(v1,v2)/(np.linalg.norm(v1)*np.linalg.norm(v2))\n",
    "    return d\n",
    "               "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cosine distance between the 5-th and the 28-th instance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 208,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.7273\n"
     ]
    }
   ],
   "source": [
    "print('{:.4f}'.format(cosine_distance(scaled_data, 5, 28)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 209,
   "metadata": {},
   "outputs": [],
   "source": [
    "def batchGetCandidates(batchSize,X):\n",
    "    \"\"\"\n",
    "    Returns all Candidate pairs found during running a batch \n",
    "    \"\"\"\n",
    "    dictCandidates = {}\n",
    "    candidatePairs = set()\n",
    "    \n",
    "    randVects = np.random.rand(batchSize,X.shape[1])-0.5 #IE uniform distribution from -0.5 to 0.5\n",
    "    for i in range(X.shape[0]):\n",
    "        sig = batchGetSongSignature (X,i,randVects)\n",
    "        sig_string = str(sig) #as strings are hashable by default\n",
    "        if sig_string in dictCandidates:\n",
    "            dictCandidates[sig_string ].append(i)\n",
    "        else:\n",
    "            dictCandidates.update( {sig_string  : [i]} )\n",
    "    \n",
    "    for key, bucket in dictCandidates.items():\n",
    "        if len(bucket) > 1:\n",
    "            candidatePairs.update(tuple(x for x in it.combinations(bucket,2)))\n",
    "    \n",
    "    #print(\"debug. CandidatePairs is : \" + str (candidatePairs))\n",
    "    return candidatePairs\n",
    "    \n",
    "\n",
    "def batchGetSongSignature(X ,i ,rand_vects):\n",
    "    \"\"\"\n",
    "    returns the data's signature(IE a column of the sketch) based on the data (np.array)\n",
    "    and a matrix containing random vectors (number of vectors depends on size of batch)\n",
    "    to be used with random hyperplane hashing technique\n",
    "    \"\"\"\n",
    "    return [hyperplaneHash(X, i,rand_vect) for rand_vect in rand_vects]\n",
    "\n",
    "def hyperplaneHash(X, i, v2):\n",
    "    \"\"\"\n",
    "        returns +1 or -1, depending on v1*v2. v1 is line i of X\n",
    "        The basis of implementing LSH for cosine distance\n",
    "    \"\"\"\n",
    "    if (np.dot(X[i,:],v2) >= 0.0):\n",
    "        return 1\n",
    "    else:\n",
    "        return -1\n",
    "    \n",
    "def refineStep(candidates,d,X):\n",
    "    duplicates = set ()\n",
    "    for pair in candidates:\n",
    "        #print(\"debug. pair is: \" + str(pair))\n",
    "        dist = cosine_distance(X,pair[0],pair[1])\n",
    "        if dist <= d :\n",
    "            duplicates.add(pair + (dist,))\n",
    "    return duplicates\n",
    "\n",
    "\n",
    "def LSH(X, b=8, r=32, d=0.3):\n",
    "    \"\"\"Find candidate duplicate pairs using LSH and refine using exact cosine distance.\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    X : np.array shape [N, D]\n",
    "        Data matrix.\n",
    "    b : int\n",
    "        Number of bands.\n",
    "    r : int\n",
    "        Number of rows per band.\n",
    "    d : float\n",
    "        Distance treshold for reporting duplicates.\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    duplicates : {(ID1, ID2, d_{12}), ..., (IDX, IDY, d_{xy})}\n",
    "        A set of tuples indicating the detected duplicates.\n",
    "        Each tuple should have 3 elements:\n",
    "            * ID of the first song\n",
    "            * ID of the second song\n",
    "            * The cosine distance between them\n",
    "    \n",
    "    n_candidates : int\n",
    "        Number of detected candidate pairs.\n",
    "        \n",
    "    \"\"\"\n",
    "    np.random.seed(158)\n",
    "    n_candidates = 0\n",
    "    candidates = set()\n",
    "    \n",
    "    for _ in range(b):\n",
    "        batchCandidates = batchGetCandidates(r,X)\n",
    "        #now check if the batchCandidates are already in candidates. if not, add them:\n",
    "        candidates.update(batchCandidates) #luckiliy python sets are smart\n",
    "    \n",
    "    n_candidates = len(candidates)\n",
    "    duplicates = refineStep(candidates,d,X)\n",
    "                               \n",
    "    return duplicates, n_candidates\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 210,
   "metadata": {},
   "outputs": [],
   "source": [
    "duplicates, n_candidates = LSH(scaled_data, b=3, r=62, d=0.003)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 211,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "We detected 5149 candidates.\n"
     ]
    }
   ],
   "source": [
    "print('We detected {} candidates.'.format(n_candidates))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Show the duplicates we have found:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 212,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(70, 6427, 0.0002997386232330701),\n",
       " (86, 7833, 0.002924800787201476),\n",
       " (99, 9651, 0.0002776014724606979),\n",
       " (101, 2089, 0.002376150742492422),\n",
       " (101, 7977, 0.002063456165628086),\n",
       " (107, 275, 0.0020696581470437403),\n",
       " (107, 6529, 0.00276085809526716),\n",
       " (108, 7140, 0.0017469654048630767),\n",
       " (126, 233, 0.002944031033371375),\n",
       " (138, 3719, 0.0025105375101999172),\n",
       " (145, 7916, 0.0017291675133956907),\n",
       " (188, 4874, 0.001302503017804102),\n",
       " (195, 2171, 0.002289829934054799),\n",
       " (214, 8893, 0.0028689946442929104),\n",
       " (242, 3736, 0.0027545598012811423),\n",
       " (244, 9339, 0.0020226875950987155),\n",
       " (246, 1283, 0.0021377728346071434),\n",
       " (254, 7115, 0.0018791255290667719),\n",
       " (311, 2447, 0.0022723416075131064),\n",
       " (322, 484, 0.0017782599360433027),\n",
       " (326, 2325, 0.001803445802850856),\n",
       " (335, 2496, 0.002471706062440293),\n",
       " (352, 2931, 0.0017374523366251449),\n",
       " (408, 7569, 0.002386073152351398),\n",
       " (418, 8744, 0.0023935343915292284),\n",
       " (421, 2670, 0.001412615179239629),\n",
       " (422, 3351, 0.0013891604960050152),\n",
       " (437, 2747, 0.000391690332121164),\n",
       " (449, 2003, 0.0027188249562004607),\n",
       " (451, 5093, 0.002053938349191653),\n",
       " (488, 7336, 0.0009930556386562595),\n",
       " (497, 582, 0.0004003824704003067),\n",
       " (497, 4912, 0.0020127330473970195),\n",
       " (499, 5472, 0.0025677029645395644),\n",
       " (533, 9360, 0.0016630777962608478),\n",
       " (582, 4912, 0.002441568126509641),\n",
       " (585, 2035, 0.0005169436336629474),\n",
       " (612, 2569, 0.0),\n",
       " (615, 801, 0.000611047255939634),\n",
       " (615, 3504, 0.0005332220616117711),\n",
       " (674, 6859, 0.0016090704121383137),\n",
       " (687, 2458, 0.0018387919068351133),\n",
       " (727, 3056, 0.0022245476664773944),\n",
       " (800, 5636, 0.001941639647403015),\n",
       " (801, 3504, 0.001641467855162504),\n",
       " (821, 4252, 0.0007197402529764974),\n",
       " (835, 7203, 0.0018840410831685306),\n",
       " (837, 6916, 0.0015873072092236207),\n",
       " (848, 7665, 0.0019695070796984515),\n",
       " (908, 3742, 0.00030818307313895676),\n",
       " (915, 2810, 0.0007756545071601062),\n",
       " (939, 1595, 0.0029457769725710348),\n",
       " (991, 6760, 0.0028802270089171023),\n",
       " (1002, 4081, 0.002576372596040266),\n",
       " (1032, 3725, 0.0011439606361881571),\n",
       " (1063, 8948, 0.0005280193513251819),\n",
       " (1121, 4360, 0.0006368607295353934),\n",
       " (1149, 4965, 0.001086859042432109),\n",
       " (1149, 8664, 0.0016805726222116624),\n",
       " (1229, 1411, 0.002358109258962182),\n",
       " (1256, 9811, 0.0005833488611604043),\n",
       " (1285, 2172, 0.002908074401412497),\n",
       " (1288, 2361, 0.0012692269195423433),\n",
       " (1332, 1960, 0.0026076414582915097),\n",
       " (1343, 8183, 0.001597123268501477),\n",
       " (1346, 3323, 0.0008697827217429843),\n",
       " (1369, 2164, 0.0016162466136812048),\n",
       " (1396, 9099, 0.001646723802046779),\n",
       " (1418, 9642, 0.001719493190320498),\n",
       " (1440, 1652, 0.0026124647902118214),\n",
       " (1449, 6760, 0.0014792538489197815),\n",
       " (1451, 3222, 0.001989433572034627),\n",
       " (1465, 5574, 0.0008072015730189452),\n",
       " (1499, 8865, 0.002323059208490852),\n",
       " (1532, 2141, 0.0017157031276336943),\n",
       " (1540, 5157, 0.0019805215717701996),\n",
       " (1559, 2969, 0.0011958281618117406),\n",
       " (1565, 5633, 0.0009764631622721787),\n",
       " (1577, 7636, 0.0022684385308399113),\n",
       " (1636, 5623, 0.002026386719740536),\n",
       " (1640, 8657, 0.0020718118365895544),\n",
       " (1652, 3562, 0.00039341468445719396),\n",
       " (1652, 9749, 0.0026526094442801407),\n",
       " (1670, 7960, 0.0022356542934449664),\n",
       " (1679, 7098, 0.002509231418599267),\n",
       " (1683, 2907, 0.001280934731835326),\n",
       " (1694, 2992, 0.0017669029462052954),\n",
       " (1727, 4364, 0.0026955755919148006),\n",
       " (1732, 4875, 0.0021569574799271685),\n",
       " (1732, 7688, 0.0012938841493815856),\n",
       " (1736, 6319, 0.002717903530767507),\n",
       " (1762, 3158, 0.0008587437831150124),\n",
       " (1762, 9214, 0.0019196538337891145),\n",
       " (1795, 2824, 0.00248281012577678),\n",
       " (1864, 2996, 0.0011958796325441945),\n",
       " (1894, 9129, 0.0009531213686636564),\n",
       " (1910, 7155, 0.0010377257539565532),\n",
       " (1960, 2437, 0.00277900147247212),\n",
       " (1990, 5517, 0.0023569021432962023),\n",
       " (2062, 3354, 0.0021230821569920844),\n",
       " (2094, 4504, 0.002347242044567377),\n",
       " (2127, 8462, 0.0019096512469746196),\n",
       " (2134, 4459, 0.0025269505536344994),\n",
       " (2140, 5847, 0.002749584327678134),\n",
       " (2144, 4477, 0.0027084039735053578),\n",
       " (2155, 8077, 0.001816901090271772),\n",
       " (2174, 6410, 0.0014909707731198818),\n",
       " (2271, 4089, 0.002795829565091945),\n",
       " (2292, 6766, 0.002869044877257365),\n",
       " (2295, 4646, 0.0007188381530381927),\n",
       " (2310, 5316, 0.0020955958287169896),\n",
       " (2312, 5296, 0.001600680320127501),\n",
       " (2315, 4253, 0.0014161494111540884),\n",
       " (2323, 8996, 0.0023021181500860743),\n",
       " (2359, 6213, 0.0018166725719171994),\n",
       " (2361, 8286, 0.0005030136333263879),\n",
       " (2411, 2432, 0.0014448938976440173),\n",
       " (2411, 3920, 0.0025527691108171435),\n",
       " (2432, 3679, 0.0009566695344548348),\n",
       " (2437, 3636, 0.002981478753209532),\n",
       " (2443, 8194, 0.0007701436246723148),\n",
       " (2488, 3920, 0.001790251496409323),\n",
       " (2520, 4983, 0.0011672391002209848),\n",
       " (2532, 3702, 0.0017102503667210112),\n",
       " (2552, 7995, 0.0019515912412256808),\n",
       " (2593, 4442, 0.0024441325078210507),\n",
       " (2597, 2785, 0.0003505812872258707),\n",
       " (2628, 8617, 0.00046566435060835243),\n",
       " (2639, 8049, 0.002565948251651462),\n",
       " (2640, 3046, 0.0011691575640484508),\n",
       " (2654, 8333, 0.0010074400645491144),\n",
       " (2669, 3964, 0.00174747133232378),\n",
       " (2710, 6159, 0.0019004467798032776),\n",
       " (2744, 5316, 0.002303121282988818),\n",
       " (2750, 4177, 0.002590229581438175),\n",
       " (2777, 5985, 0.002578750972492161),\n",
       " (2858, 3323, 0.002999801887609621),\n",
       " (2859, 3554, 0.002348497318640841),\n",
       " (2863, 9360, 0.0015849630188796704),\n",
       " (2881, 6642, 0.0014639416654957937),\n",
       " (2885, 3333, 0.00172916938622103),\n",
       " (2885, 7268, 0.002589307970030319),\n",
       " (2892, 8563, 0.0016044975281733764),\n",
       " (2895, 6856, 0.0027349342087810147),\n",
       " (2898, 9227, 0.002011208845072665),\n",
       " (2925, 5634, 0.001313494032261886),\n",
       " (2998, 4302, 0.0006983689495111411),\n",
       " (3030, 3315, 0.0006938698027630918),\n",
       " (3067, 6071, 0.002563111209579194),\n",
       " (3075, 8025, 0.0027173355377642094),\n",
       " (3088, 5529, 0.00017364668134511874),\n",
       " (3089, 7520, 0.00249207358891812),\n",
       " (3106, 4479, 0.0011773630852988104),\n",
       " (3106, 8503, 0.00039429508753818787),\n",
       " (3128, 4652, 0.0013938170684050233),\n",
       " (3140, 3555, 0.002499763122682852),\n",
       " (3222, 9219, 0.0014869420625166496),\n",
       " (3257, 5276, 0.0027652673871114697),\n",
       " (3274, 6847, 0.0007272849616699606),\n",
       " (3319, 4561, 0.0012405786019581422),\n",
       " (3348, 6414, 0.0021447326331164307),\n",
       " (3372, 7614, 0.002581844323032878),\n",
       " (3379, 3482, 0.001284654966388632),\n",
       " (3386, 7346, 0.0028323280943348683),\n",
       " (3400, 5645, 0.0008573509961697923),\n",
       " (3401, 3837, 0.0011619818711453567),\n",
       " (3424, 5946, 0.0020729143625247692),\n",
       " (3455, 9713, 0.0020697537525340426),\n",
       " (3467, 6617, 0.0025118129004251255),\n",
       " (3469, 8270, 0.001700657670643202),\n",
       " (3470, 8470, 0.001431108941374326),\n",
       " (3485, 6987, 0.0021344383193405703),\n",
       " (3518, 4389, 0.0011646583183625436),\n",
       " (3522, 9737, 0.002848138349211271),\n",
       " (3562, 9749, 0.0018118841531380436),\n",
       " (3636, 4093, 0.0018395542186032676),\n",
       " (3641, 6298, 0.0019022921295213102),\n",
       " (3666, 7406, 0.0013034494665499219),\n",
       " (3669, 3698, 0.00044969782548254233),\n",
       " (3669, 9994, 0.002490040949538641),\n",
       " (3671, 7220, 0.0018525826609013807),\n",
       " (3673, 5141, 0.0027343405463999826),\n",
       " (3696, 7524, 0.0020773717822651916),\n",
       " (3698, 4459, 0.002894009030462996),\n",
       " (3698, 9994, 0.002785408086883323),\n",
       " (3742, 6693, 0.0013965359990784076),\n",
       " (3802, 4056, 0.0016382671052657116),\n",
       " (3867, 9382, 0.0015635391863754178),\n",
       " (3928, 8064, 0.0027717654409878945),\n",
       " (4027, 4512, 0.0017448253197056562),\n",
       " (4034, 5600, 0.0027255636494608604),\n",
       " (4043, 7072, 0.0006531415255929263),\n",
       " (4045, 8023, 0.0027342075297780433),\n",
       " (4046, 8940, 0.00210754117266454),\n",
       " (4076, 8632, 0.0004834341456750879),\n",
       " (4085, 7098, 0.0009191236433532257),\n",
       " (4093, 4232, 0.002193171984469555),\n",
       " (4116, 8585, 0.0017000134370966924),\n",
       " (4139, 4227, 0.0013724928111166212),\n",
       " (4139, 8761, 0.002029135053820963),\n",
       " (4150, 9526, 0.0027830489144282655),\n",
       " (4165, 7968, 0.0013085263450660634),\n",
       " (4208, 6396, 0.001222808175450174),\n",
       " (4227, 7204, 0.0027266618592732828),\n",
       " (4232, 5872, 0.0015188900515740178),\n",
       " (4271, 7136, 0.0029684369116216303),\n",
       " (4272, 5065, 0.0015330945901749216),\n",
       " (4317, 9854, 0.0024132163552662567),\n",
       " (4317, 9950, 0.00244380527013377),\n",
       " (4436, 5889, 0.001623056269980161),\n",
       " (4443, 9347, 0.002272031023689114),\n",
       " (4459, 9994, 0.002672582068108831),\n",
       " (4467, 8567, 0.0021515618265234293),\n",
       " (4479, 8503, 0.002210393588025439),\n",
       " (4494, 5475, 0.0020437783887502503),\n",
       " (4525, 9292, 0.0025526058657123762),\n",
       " (4551, 8655, 0.0009478841448981035),\n",
       " (4552, 8773, 0.002145680903473113),\n",
       " (4598, 6576, 0.0024286058503762975),\n",
       " (4598, 6721, 0.0023821413503959388),\n",
       " (4725, 5615, 0.002588184449481501),\n",
       " (4749, 6239, 0.001172607485894428),\n",
       " (4765, 7529, 0.0026185401857234947),\n",
       " (4799, 8199, 0.001089729314590504),\n",
       " (4810, 6330, 0.0029056611581217417),\n",
       " (4826, 5442, 0.0005099921279348996),\n",
       " (4915, 5998, 0.0014888430426408528),\n",
       " (4931, 9509, 0.002461204016735996),\n",
       " (4961, 8609, 0.00030459488119105593),\n",
       " (4965, 8664, 0.0010936593898056568),\n",
       " (5121, 6612, 0.0011219128635937548),\n",
       " (5146, 7919, 0.0008961442189971969),\n",
       " (5203, 8970, 0.0011920896238036827),\n",
       " (5324, 8563, 0.0009704308291833552),\n",
       " (5419, 7245, 0.0008022234882332224),\n",
       " (5424, 7480, 0.002856929901002614),\n",
       " (5451, 5612, 0.0027366501316155034),\n",
       " (5514, 6488, 0.002637916126570161),\n",
       " (5600, 9652, 0.0012800204913888669),\n",
       " (5614, 7178, 0.0013326489533239672),\n",
       " (5699, 6948, 0.0005690302518707169),\n",
       " (5701, 7144, 0.0007494097917237763),\n",
       " (5755, 9424, 0.0011935213186066163),\n",
       " (5845, 6870, 0.0018867561703179714),\n",
       " (5872, 6002, 0.0017292111953103317),\n",
       " (5970, 8978, 0.0005702860130146759),\n",
       " (5972, 6256, 0.0010598326533634017),\n",
       " (5975, 9046, 0.0015558100111970896),\n",
       " (6138, 8861, 0.0028981458669664617),\n",
       " (6151, 6394, 0.0028634015351650666),\n",
       " (6206, 7902, 0.0008444522696948731),\n",
       " (6236, 7673, 0.0025521023104587703),\n",
       " (6245, 9933, 0.0015242606033599726),\n",
       " (6263, 7497, 0.0011678128233640894),\n",
       " (6386, 9303, 0.0027777977085651218),\n",
       " (6395, 7292, 0.001690200803244224),\n",
       " (6400, 6568, 0.0008586376295079967),\n",
       " (6444, 7462, 0.0026243362651969804),\n",
       " (6570, 7442, 0.001985768362522511),\n",
       " (6676, 9440, 0.0020933122339023003),\n",
       " (6775, 9760, 0.0012040779343266417),\n",
       " (6786, 7779, 0.002992293973111626),\n",
       " (6932, 8834, 0.0028212803648607343),\n",
       " (6983, 8115, 0.0005955064722529269),\n",
       " (7031, 7934, 0.0016821977024025214),\n",
       " (7050, 8339, 0.0028492818010183996),\n",
       " (7103, 7258, 0.002118178389604375),\n",
       " (7131, 9481, 0.0021789407352388324),\n",
       " (7157, 9446, 0.0017183529144453313),\n",
       " (7294, 7824, 0.002032490059868719),\n",
       " (7497, 9996, 0.0028442316468837436),\n",
       " (7531, 9994, 0.001980665315147956),\n",
       " (7542, 8292, 0.0012992774597667678),\n",
       " (7561, 7660, 0.001305071982648287),\n",
       " (7564, 8323, 0.0024958341938391415),\n",
       " (7614, 7926, 0.0024923007543097286),\n",
       " (7702, 9543, 0.002664826689066091),\n",
       " (7711, 9463, 0.0025204841270365375),\n",
       " (7742, 8924, 0.0011564175853466807),\n",
       " (7930, 9654, 0.0012908668329002504),\n",
       " (7957, 8898, 0.0021434245706450916),\n",
       " (7967, 8666, 0.0022590088256283503),\n",
       " (8048, 9194, 0.001367232641210081),\n",
       " (8171, 8300, 0.002582297293632796),\n",
       " (8249, 9246, 0.0028092131132508857),\n",
       " (8267, 8330, 0.001950429401036402),\n",
       " (8391, 8578, 0.0008861602789796974),\n",
       " (8442, 9831, 0.002454954689817823),\n",
       " (8449, 8543, 0.00036371307470439707),\n",
       " (8563, 9624, 0.0015756966619815405),\n",
       " (8924, 9551, 0.0021841876339081523),\n",
       " (9051, 9624, 0.0025789483316709383),\n",
       " (9264, 9348, 0.00206577319379897),\n",
       " (9345, 9680, 0.001209204398131991),\n",
       " (9854, 9950, 0.0026623386850497255)}"
      ]
     },
     "execution_count": 212,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "duplicates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Show the metadata for the songs that were detected as duplicates:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 213,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Song ID 1: 1894\n",
      "Song ID 2: 9129\n",
      "Distance: 0.000953\n",
      "El Gallo Y La Vaca - Richie Ray & Bobby Cruz\n",
      "Destroy Everything (Album Version) - Hatebreed\n",
      "\n",
      "Song ID 1: 3088\n",
      "Song ID 2: 5529\n",
      "Distance: 0.000174\n",
      "Quiet Time - Regina Belle\n",
      "Quiet Time - Regina Belle\n",
      "\n",
      "Song ID 1: 4915\n",
      "Song ID 2: 5998\n",
      "Distance: 0.001489\n",
      "I Am Going (Album Version) - Randy Travis\n",
      "Bare As You Dare - Lady Saw\n",
      "\n",
      "Song ID 1: 2639\n",
      "Song ID 2: 8049\n",
      "Distance: 0.002566\n",
      "The Emperor Falls - John Wesley\n",
      "Messiaen : Et exspecto resurrectionem mortuorum : IV \"Ils ressusciteront_ glorieux_ avec un nom nouveau - Pierre Boulez\n",
      "\n",
      "Song ID 1: 3372\n",
      "Song ID 2: 7614\n",
      "Distance: 0.002582\n",
      "I'm On My Way Blues - Washboard Sam\n",
      "The Gal I Love - Washboard Sam\n",
      "\n",
      "Song ID 1: 5451\n",
      "Song ID 2: 5612\n",
      "Distance: 0.002737\n",
      "Whitfield - Atomship\n",
      "Mental Beat - Hanoi Rocks\n",
      "\n",
      "Song ID 1: 1256\n",
      "Song ID 2: 9811\n",
      "Distance: 0.000583\n",
      "Bye-Bye - Medley - Günter Noris\n",
      "Será cuando regreses - Noemí\n",
      "\n",
      "Song ID 1: 2593\n",
      "Song ID 2: 4442\n",
      "Distance: 0.002444\n",
      "Bonus Beats (2002 Digital Remaster) - N.W.A.\n",
      "La Copa Grande - Pablo Montero\n",
      "\n",
      "Song ID 1: 1732\n",
      "Song ID 2: 4875\n",
      "Distance: 0.002157\n",
      "Controlando El Area - Daddy Yankee / Bounty Killer\n",
      "Surfriendo El Castigo - Michael Salgado\n",
      "\n",
      "Song ID 1: 2744\n",
      "Song ID 2: 5316\n",
      "Distance: 0.002303\n",
      "Something Girls - Adam Ant\n",
      "Brampton Boogaloo - Mocambo Allstars\n",
      "\n",
      "Song ID 1: 6138\n",
      "Song ID 2: 8861\n",
      "Distance: 0.002898\n",
      "Mama Don't Know Love - Fred Locks\n",
      "Xue Hua Chao - Hins Cheung\n",
      "\n",
      "Song ID 1: 2443\n",
      "Song ID 2: 8194\n",
      "Distance: 0.000770\n",
      "Michaelangelo - 23rd Turnoff\n",
      "I Can Dig It - The Box Tops\n",
      "\n",
      "Song ID 1: 2312\n",
      "Song ID 2: 5296\n",
      "Distance: 0.001601\n",
      "Santa Barbara - Chaka Demus & Pliers\n",
      "Ine Mono Ekloges - Imiskoubria\n",
      "\n",
      "Song ID 1: 3518\n",
      "Song ID 2: 4389\n",
      "Distance: 0.001165\n",
      "Poem To A Horse - Shakira\n",
      "Money Make The World Go Around - G-Unit\n",
      "\n",
      "Song ID 1: 3928\n",
      "Song ID 2: 8064\n",
      "Distance: 0.002772\n",
      "If I Had Known - Tampa Red\n",
      "I Love The Life I'm Living - Slim Harpo\n",
      "\n",
      "Song ID 1: 2323\n",
      "Song ID 2: 8996\n",
      "Distance: 0.002302\n",
      "Caribou Lou - Tech N9ne\n",
      "Superstar (feat. J-Noxx) - Hollowtip\n",
      "\n",
      "Song ID 1: 1732\n",
      "Song ID 2: 7688\n",
      "Distance: 0.001294\n",
      "Controlando El Area - Daddy Yankee / Bounty Killer\n",
      "(I Used To Couldn't Dance) Tight Pants - Eagles Of Death Metal\n",
      "\n",
      "Song ID 1: 615\n",
      "Song ID 2: 801\n",
      "Distance: 0.000611\n",
      "Man  On The Side - Bill Perry\n",
      "da da Diamonds - Soul Ballet\n",
      "\n",
      "Song ID 1: 2174\n",
      "Song ID 2: 6410\n",
      "Distance: 0.001491\n",
      "Wot U Say - Various Production\n",
      "Dame Tu Carino - Ray Barretto\n",
      "\n"
     ]
    },
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-213-9d282a5d5723>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      3\u001b[0m           \u001b[0;34m'Song ID 2: {}'\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mj\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m           \u001b[0;34m'Distance: {:.6f}'\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0md\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m           \u001b[0msummary\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'/metadata/songs'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mloc\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'title'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'artist_name'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mstr\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcat\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msep\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;34m' - '\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m           summary['/metadata/songs'].loc[j][['title', 'artist_name']].str.cat(sep=' - '), sep='\\n')\n\u001b[1;32m      7\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/lib/python3.7/site-packages/pandas/io/pytables.py\u001b[0m in \u001b[0;36m__getitem__\u001b[0;34m(self, key)\u001b[0m\n\u001b[1;32m    505\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    506\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0m__getitem__\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 507\u001b[0;31m         \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mget\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mkey\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    508\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    509\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0m__setitem__\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/lib/python3.7/site-packages/pandas/io/pytables.py\u001b[0m in \u001b[0;36mget\u001b[0;34m(self, key)\u001b[0m\n\u001b[1;32m    693\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0mgroup\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    694\u001b[0m             \u001b[0;32mraise\u001b[0m \u001b[0mKeyError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'No object named %s in the file'\u001b[0m \u001b[0;34m%\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 695\u001b[0;31m         \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_read_group\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgroup\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    696\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    697\u001b[0m     def select(self, key, where=None, start=None, stop=None, columns=None,\n",
      "\u001b[0;32m~/anaconda3/lib/python3.7/site-packages/pandas/io/pytables.py\u001b[0m in \u001b[0;36m_read_group\u001b[0;34m(self, group, **kwargs)\u001b[0m\n\u001b[1;32m   1373\u001b[0m         \u001b[0ms\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_create_storer\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgroup\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1374\u001b[0m         \u001b[0ms\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0minfer_axes\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1375\u001b[0;31m         \u001b[0;32mreturn\u001b[0m \u001b[0ms\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mread\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m**\u001b[0m\u001b[0mkwargs\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   1376\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1377\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/lib/python3.7/site-packages/pandas/io/pytables.py\u001b[0m in \u001b[0;36mread\u001b[0;34m(self, where, columns, **kwargs)\u001b[0m\n\u001b[1;32m   4178\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mread\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mwhere\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mNone\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcolumns\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mNone\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0mkwargs\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   4179\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 4180\u001b[0;31m         \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mread_axes\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mwhere\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mwhere\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0mkwargs\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   4181\u001b[0m             \u001b[0;32mreturn\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   4182\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/lib/python3.7/site-packages/pandas/io/pytables.py\u001b[0m in \u001b[0;36mread_axes\u001b[0;34m(self, where, **kwargs)\u001b[0m\n\u001b[1;32m   3375\u001b[0m         \u001b[0;31m# create the selection\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   3376\u001b[0m         \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mselection\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mSelection\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mwhere\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mwhere\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0mkwargs\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 3377\u001b[0;31m         \u001b[0mvalues\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mselection\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mselect\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   3378\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   3379\u001b[0m         \u001b[0;31m# convert the data\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/lib/python3.7/site-packages/pandas/io/pytables.py\u001b[0m in \u001b[0;36mselect\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m   4777\u001b[0m         \u001b[0;32melif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcoordinates\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   4778\u001b[0m             \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtable\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtable\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mread_coordinates\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcoordinates\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 4779\u001b[0;31m         \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtable\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtable\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mread\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mstart\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mstart\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mstop\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mstop\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   4780\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   4781\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mselect_coords\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/lib/python3.7/site-packages/tables/table.py\u001b[0m in \u001b[0;36mread\u001b[0;34m(self, start, stop, step, field, out)\u001b[0m\n\u001b[1;32m   1932\u001b[0m                                                 warn_negstep=False)\n\u001b[1;32m   1933\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1934\u001b[0;31m         \u001b[0marr\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_read\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mstart\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mstop\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mstep\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mfield\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mout\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   1935\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0minternal_to_flavor\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0marr\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mflavor\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1936\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/lib/python3.7/site-packages/tables/table.py\u001b[0m in \u001b[0;36m_read\u001b[0;34m(self, start, stop, step, field, out)\u001b[0m\n\u001b[1;32m   1846\u001b[0m             \u001b[0;31m# This optimization works three times faster than\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1847\u001b[0m             \u001b[0;31m# the row._fill_col method (up to 170 MB/s on a pentium IV @ 2GHz)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1848\u001b[0;31m             \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_read_records\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mstart\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mstop\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0mstart\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   1849\u001b[0m         \u001b[0;31m# Warning!: _read_field_name should not be used until\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1850\u001b[0m         \u001b[0;31m# H5TBread_fields_name in tableextension will be finished\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "for i, j, d in duplicates:\n",
    "    print('Song ID 1: {}'.format(i),\n",
    "          'Song ID 2: {}'.format(j),\n",
    "          'Distance: {:.6f}'.format(d),\n",
    "          summary['/metadata/songs'].loc[i][['title', 'artist_name']].str.cat(sep=' - '),\n",
    "          summary['/metadata/songs'].loc[j][['title', 'artist_name']].str.cat(sep=' - '), sep='\\n')\n",
    "    print() "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Compare runtime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Your task is to implement code for runtime comparison between LSH and the naive nested for loop implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 200,
   "metadata": {},
   "outputs": [],
   "source": [
    "# naively compute the duplicates using a double for loop\n",
    "def naive_duplicates(X, d = 0.3):\n",
    "    \"\"\"\n",
    "    Parameters\n",
    "    ----------\n",
    "    X : np.array, shape [N, D]\n",
    "        Data matrix.\n",
    "    d : float\n",
    "        Distance treshold for reporting duplicates.\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    duplicates : {(ID1, ID2, d_{12}), ..., (IDX, IDY, d_{xy})}\n",
    "        A set of tuples indicating the detected duplicates.\n",
    "        Each tuple should have 3 elements:\n",
    "            * ID of the first song\n",
    "            * ID of the second song\n",
    "            * The cosine distance between them\n",
    "    \"\"\"\n",
    "    N = X.shape[0]\n",
    "    duplicates = set()\n",
    "    for i in range(N):\n",
    "        for j in range(N):\n",
    "            d_ij = cosine_distance(X, i, j)\n",
    "            if d_ij < d and i != j:\n",
    "                duplicates.add((i, j, d_ij))\n",
    "    return duplicates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 233,
   "metadata": {},
   "outputs": [],
   "source": [
    "def runtime_comparison():\n",
    "    \"\"\"\n",
    "    Compare the runtime between LSH and the naive approach.\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    trace : [(n1, lsh_dur, naive_dur), (n2, lsh_dur, naive_dur), ... ]\n",
    "            A list of tuples with execution times for different number of songs.\n",
    "            Each tuple should have 3 elements:\n",
    "                * number of songs considered\n",
    "                * duration of the LSH approach\n",
    "                * duration of the naive approach\n",
    "    s\"\"\"\n",
    "    trace = []\n",
    "    for n in np.arange(25, 351, 25):\n",
    "        print('Running comparison for {} songs.'.format(n))\n",
    "        \n",
    "        ### YOUR CODE HERE ###\n",
    "        start = time.time()\n",
    "        dupli_lsh,_ = LSH(scaled_data[0:n,:])\n",
    "        end = time.time()\n",
    "        lsh_dur = end-start\n",
    "        start = time.time()\n",
    "        dupli_naive = naive_duplicates(scaled_data[0:n,:])\n",
    "        end = time.time()\n",
    "        naive_dur = end-start\n",
    "        \n",
    "        if len(dupli_lsh) != len(dupli_naive):\n",
    "            print(\"Number of missed pairs! \" + str(len(dupli_naive)-len(dupli_lsh)))\n",
    "        \n",
    "        trace.append((n,lsh_dur,naive_dur))\n",
    "        \n",
    "        \n",
    "    return trace"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 234,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Running comparison for 25 songs.\n",
      "Number of missed pairs! 26\n",
      "Running comparison for 50 songs.\n",
      "Number of missed pairs! 111\n",
      "Running comparison for 75 songs.\n",
      "Number of missed pairs! 253\n",
      "Running comparison for 100 songs.\n",
      "Number of missed pairs! 431\n",
      "Running comparison for 125 songs.\n",
      "Number of missed pairs! 702\n",
      "Running comparison for 150 songs.\n",
      "Number of missed pairs! 1062\n",
      "Running comparison for 175 songs.\n",
      "Number of missed pairs! 1445\n",
      "Running comparison for 200 songs.\n",
      "Number of missed pairs! 1921\n",
      "Running comparison for 225 songs.\n",
      "Number of missed pairs! 2497\n",
      "Running comparison for 250 songs.\n",
      "Number of missed pairs! 3044\n",
      "Running comparison for 275 songs.\n",
      "Number of missed pairs! 3629\n",
      "Running comparison for 300 songs.\n",
      "Number of missed pairs! 4393\n",
      "Running comparison for 325 songs.\n",
      "Number of missed pairs! 5301\n",
      "Running comparison for 350 songs.\n",
      "Number of missed pairs! 6112\n"
     ]
    }
   ],
   "source": [
    "trace = runtime_comparison()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Plot the differecene in runtime. On the x-axis plot the number of songs processed and on the y-axis plot the runtime in seconds for both approaches. You should obtain a plot similar to the one shown below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 235,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<function matplotlib.pyplot.show(*args, **kw)>"
      ]
     },
     "execution_count": 235,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYUAAAEWCAYAAACJ0YulAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAIABJREFUeJzt3Xl8VNX5+PHPk50QIAIRgbCLCiig4AJuuKLWgruoVXGjtu5VW61Wrdb+6ldt1WpLcam7YnFDRcUNt6oIFBBEBFkkLBICZCF78vz+ODdhGLJMQm7uzOR5v17zmnvv3OWZS7jPnHPuPUdUFWOMMQYgIegAjDHGRA9LCsYYY2pZUjDGGFPLkoIxxphalhSMMcbUsqRgjDGmliUFE/NEZLKI/CHoOKKdiLwtIhcGHYeJbmLPKZiWJiKrgG5AFVAEvANcqapFLbDvicClqnrYru6rmcfvCNwJnAZ0BjYAbwJ/UtVNQcRkTEuykoLxy89VNQMYDuwP3BxwPLtMRFKAD4AhwAlAR2A0kAccFGBoDRLH/q+biNgfivGVqm4A3sUlBwBEZJaIXBoyP1FEPguZVxG5XESWicgWEXnEu7ANAiYDo0SkSES2eus/KSJ/8qbHiEiOiPxWRDaKyHoROUVEThKR70Vks4j8PuRYCSJyk4j8ICJ5IvKSiHSu5+tcAPQGTlXVb1W1WlU3qupdqjrD298g7/ttFZHFIjIu5FhPisg/vGqcIhH5XET2EJEHvO/5nYjsH7L+KhG5WUS+9T7/t4ikeZ/tJiJvikiu99mbIpIddo7vFpHPgWKgf+h5F5E9ReRjEckXkU0iMjVk29Ei8rX32dciMjpsv3d5sReKyEwR6RrRH4OJCZYUjK+8C9WJwPImbnoycCAwDDgLGKuqS4DLgS9UNUNVM+vZdg8gDegJ3AY8CvwCGAEcDtwmIv29da8GTgGOBHoAW4BH6tnvscA79VWDiUgy8AYwE9gduAp4TkT2DlntLOBWoCtQBnwBzPPmpwF/DdvtecBYYACwl7ctuP+7/wb64BJVCfBw2LbnA5OADsDqsM/u8uLcDcgG/u59h87AW8BDQBcvnrdEpEvItucCF3nfMQW4oa7zYWKTJQXjl9dEpBBYA2wEbm/i9n9R1a2q+iPwESEljQhUAHeragXwIu6C+6CqFqrqYmAxMNRb95fALaqao6plwB3AGSKSVMd+uwDrGzjuIUCGF3u5qn6Ia284J2SdV1V1rqqWAq8Cpar6tKpWAVNxVW2hHlbVNaq6Gbi7Zl+qmqeqL6tqsaoWep8dGbbtk6q6WFUrvXMRfo76AD1UtVRVa0pqPwOWqeoz3nYvAN8BPw/Z9t+q+r2qlgAv0bR/GxPlLCkYv5yiqh2AMcA+uAtzU2wImS7GXWwjleddZMH9ggb4KeTzkpD99QFe9ap7tgJLcA3k3eraL9C9geP2ANaoanXIstW4EkuN8Djqi6vGmrB99QAQkXQR+ZeIrBaRAuATIFNEEuvZNtxvAQFme9VcF4d8h/BSRfh32JV/GxPlLCkYX6nqx8CTwH0hi7cB6SHzezRlly0QVqg1wImqmhnySlPVtXWs+z4wVkTa17OvdUCvsEbd3kBd+4pUr7B9rfOmrwf2Bg5W1Y7AEd5yCVm/3nOlqhtU9TJV7YErLf1DRPb09t8nbPVd/Q4mhlhSMK3hAeA4EampZpgPnOb92t0TuKQJ+/oJyPbuBGoJk4G7RaQPgIhkicj4etZ9BpdEXhaRfbxG6i4i8nsROQn4CpfwfisiySIyBlft8uIuxHeFiGR7df2/x1UxgWsnKAG2ep81qXpORM4MaZjegksgVcAMYC8ROVdEkkTkbGAwrhrMtAGWFIzvVDUXeBqoecDsb0A57gL/FPBcE3b3Ia5NYIOItMRzAQ8C04GZXhvIl8DBda3otTkci6tjfw8oAGbjqsa+UtVyYByuYX0T8A/gAlX9bhfiex7XILzCe/3JW/4A0M47zpe4Z0Ga4kDgKxEpwn3/a1R1parm4Rr5r8dVl/0WONmewWg77OE1Y6KUuIcAL1XV94OOxbQdVlIwxhhTy5KCMcaYWlZ9ZIwxppaVFIwxxtSq66nNqNa1a1ft27dv0GEYY0xMmTt37iZVzWpsvZhLCn379mXOnDlBh2GMMTFFRMKfVK+TVR8ZY4ypZUnBGGNMLUsKxhhjasVcm0JdKioqyMnJobS0NOhQWl1aWhrZ2dkkJycHHYoxJg7ERVLIycmhQ4cO9O3bFxFpfIM4oark5eWRk5NDv379gg7HGBMH4qL6qLS0lC5durSphAAgInTp0qVNlpCMMf6Ii6QAtLmEUKOtfm9jjD/iJikYY0xcm/UX2PCN74expNBCMjJ2HpFw6dKljBkzhuHDhzNo0CAmTZoEwKxZszj55JN3WHfixIlMmzatVWI1xsSYuU/CrP8Hi17x/VBx0dAcra6++mquu+46xo93A3l9843/Wd4YE2fWzIa3boABR8PRt/p+OCsp+Gj9+vVkZ2fXzu+3334BRmOMiTkF62Hq+dCpJ5z+OCQk+n7IuCsp/PGNxXy7rqBF9zm4R0du//mQJm933XXXcfTRRzN69GiOP/54LrroIjIzMwH49NNPGT58eO26P/74405VSsaYNqyyDF66AMoK4PxXIL1zqxzWSgo+uuiii1iyZAlnnnkms2bN4pBDDqGsrAyAww8/nPnz59e+xo0bF3C0xpio8vZvIWc2nPIP6Nb0H6XNFXclheb8ovdTjx49uPjii7n44ovZd999WbRoUdAhGWOi3ZwnXOPyYdfBkFNb9dBWUvDRO++8Q0VFBQAbNmwgLy+Pnj17BhyVMSaq/fglzPgt7HksHP2HVj983JUUglJcXLxDo/JvfvMbcnJyuOaaa0hLSwPg3nvvZY899uC7774LKkxjTDQrWO/aETplw+mPtUrDcjjfxmgWkTTgEyAVl3ymqertYetMBO4F1nqLHlbVxxra78iRIzV8kJ0lS5YwaNCgFoo89rT1729MXKgsg3+fBBuXwKXvQ7fBLbp7EZmrqiMbW8/PkkIZcLSqFolIMvCZiLytql+GrTdVVa/0MQ5jjIluqvDW9bB2Dpz1dIsnhKbwLSmoK4IUebPJ3sufYokxxsSyOY/D/56Bw2+AweMDDcXXhmYRSRSR+cBG4D1V/aqO1U4XkYUiMk1EetWzn0kiMkdE5uTm5voZsjHGtK7VX8Dbv4OBx8NRvw86Gn+TgqpWqepwIBs4SET2DVvlDaCvqg4F3geeqmc/U1R1pKqOzMrK8jNkY4xpPflrXcNyZh847dFAGpbDtcotqaq6FZgFnBC2PE9Vy7zZR4ERrRGPMcYErqIUpv4CKophwvPQLjPoiAAfk4KIZIlIpjfdDjgW+C5sne4hs+OAJX7FY4wxUaOmYXndPDj1X7D7PkFHVMvPu4+6A0+JSCIu+bykqm+KyJ3AHFWdDlwtIuOASmAzMNHHeKLK5MmTSU9P54ILLgg6FGNMa/v6MZj/LBzxWxgUXX2e+Xn30UJg/zqW3xYyfTNws18xRLPLL7886BCMMUFY9Tm8cxPsdQKMib7Ln3Vz0UJWrVrFoEGDuOyyyxgyZAjHH388JSUlPProoxx44IEMGzaM008/neLiYgDuuOMO7rvvPpYsWcJBBx20w36GDh0KwNy5cznyyCMZMWIEY8eOZf369YF8N2NMC8nPcQ3Lu/WD06ZAQvRdguOvm4u3b2r5Iev22A9O/Eujqy1btowXXniBRx99lLPOOouXX36Z0047jcsuuwyAW2+9lccff5yrrrqqdptBgwZRXl7OihUr6N+/P1OnTuWss86ioqKCq666itdff52srCymTp3KLbfcwhNPPNGy380Y0zoqSlzDcmWZa1hO6xR0RHWKv6QQoH79+tWOkTBixAhWrVrFokWLuPXWW9m6dStFRUWMHTt2p+3OOussXnrpJW666SamTp3K1KlTWbp0KYsWLeK4444DoKqqiu7du++0rTEmBqjCm7+Bdf+DCS9A1l5BR1Sv+EsKEfyi90tqamrtdGJiIiUlJUycOJHXXnuNYcOG8eSTTzJr1qydtjv77LM588wzOe200xARBg4cyDfffMOQIUP44osvWvEbGGN8MXsKLHjetSHsc1LQ0TQo+iq04kxhYSHdu3enoqKC5557rs51BgwYQGJiInfddRdnn302AHvvvTe5ubm1SaGiooLFixe3WtzGxKUZv4WnxsHsR12PpK1h5afwzs2w98/c3UZRLv5KClHmrrvu4uCDD6ZPnz7st99+FBYW1rne2WefzY033sjKlSsBSElJYdq0aVx99dXk5+dTWVnJtddey5Ah0TWIkDExY/1CmP0vaNcZVn4MM26A7INg8DgY9HPYrW/LH3PrGvjPhdBlAJw6OSoblsP51nW2X6zr7J219e9vTEReuhB++BCu/QaKfoJvp8OS17ffmNJ9mEsOg8a3TJ1/RQk8MRY2r4TLPoSuA3d9n7sgGrrONsaY6JD7PXz7uhvesl2mex15o3ttXglL3oAl0+HDP7lX1729EsQ4d/ehSNOOpwpvXOtKJ+e8GHhCaApLCsaY+PfZXyEpDUZdsfNnnfvBoVe7V/5a+O4tlyA+vR8+uddVK9WUIHqOiKwK6KvJsPBFOOoW2PuExtePInGTFFQVaWo2jwOxVv1nTKvbsgoWvgQH/xLad2143U494eBJ7lWUC0tnuATx5WT479+hQw8vQfwc+oyuu1fTlZ/Au7fAPie78RFiTFwkhbS0NPLy8ujSpUubSgyqSl5eXu0Y0MaYOnz+oLt4j76q8XVDZWTBiAvdq2QrfP+Oq2aa95RrsE7vCvv8zFUx9TsCklJg64/wn4muuihGGpbDxUVSyM7OJicnh7Y4AE9aWhrZ2dlBh2FMdCpYB/97FoafBx17NH8/7TJh2AT3KiuC5e+5hupFL7skkdYJ9joRfloMVZXuieXUDi33PVpRXCSF5ORk+vXrF3QYxpho89+HoboKDru25faZmgFDTnWvilJY8ZFLEEtnQFkBnDPV3YIao+IiKRhjzE62bYI5T8DQs/x5BgEgOQ32PtG9qipgW+6ulUiiQOxVeBljTCS+/AdUlsJhv2md4yUmx3xCAEsKxph4VLLVdWUxuIUeRGtDLCkYY+LP7Edd/f7h1wcdScyxpGCMiS9lRa7qaK8ToPvQoKOJOb4lBRFJE5HZIrJARBaLyB/rWCdVRKaKyHIR+UpE+voVjzGmjZj7byjZHJMPjkUDP0sKZcDRqjoMGA6cICKHhK1zCbBFVfcE/gbc42M8xph4V1HqnjzudwT0OjDoaGKSb0lBnSJvNtl7hffJMB54ypueBhwjbemRZGNMy/rfM64H1CNuDDqSmOVrm4KIJIrIfGAj8J6qfhW2Sk9gDYCqVgL5QJc69jNJROaIyJy2+NSyMSYCVRXw+UNujIS+hwcdTczyNSmoapWqDgeygYNEZN+wVeoqFezUw5uqTlHVkao6Misry49QjTGxbuFLkP+jKyVYhUOztcrdR6q6FZgFhPchmwP0AhCRJKATsLk1YjLGxJHqKtfV9R5DYeBxQUcT0/y8+yhLRDK96XbAscB3YatNBy70ps8APlTrC9oY01Tfvgabf3DPJVgpYZf42fdRd+ApEUnEJZ+XVPVNEbkTmKOq04HHgWdEZDmuhDDBx3iMMfGouho+ud+NljZoXNDRxDzfkoKqLgT2r2P5bSHTpcCZfsVgjGkDvn8HNi6GU/8Vk+MXRBs7g8aY2KUKn94HmX1g3zOCjiYuWFIwxsSuFR/B2rlw2HWQaCMBtARLCsaY2PXJ/W7c5OHnBh1J3LCkYIyJTau/gNWfwaFXQ1Jq0NHEjUbLWyIyCvgFcDjujqISYBHwFvCsqub7GqExxtTl0/sgvSsccGHj65qINVhSEJG3gUuBd3EPnnUHBgO3AmnA6yJi94AZY1rX2nmw/H0YdQWkpAcdTVxprKRwvqpuCltWBMzzXveLSFdfIjPGmPp8ej+kdYIDLw06krjTYEmhJiGISHsRSfCm9xKRcSKSHLqOMca0io1L4Ls34eDLIa1j0NHEnUgbmj8B0kSkJ/ABcBHwpF9BGWNMvT69H5Lbu6RgWlykSUFUtRg4Dfi7qp6Ka1swxpjWk/cDLHoZDrwY0jsHHU1cijgpeHchnYe76wj87TfJGGN29tnfICEZRl0VdCRxK9KkcC1wM/Cqqi4Wkf7AR/6FZYwxYfJzYMGLcMAF0KFb0NHErYh+7avqx8DHIfMrgKv9CsoYY3by+UOAwqHXBB1JXGswKYjIG9QxEloNVbVnFIwx/ivaCPOegmETILNX0NHEtcZKCvd576cBewDPevPnAKt8iskYY3b0xcNQVQ6H/SboSOJeg0nBqzZCRO5S1SNCPnpDRD7xNTJjjAEo3gxfPw5DToMuA4KOJu5F2tCc5TUuAyAi/YAsf0IyxpgQX/0LyovcUJvGd5HeVnodMEtEVnjzfYFfNrSBiPQCnsZVO1UDU1T1wbB1xgCvAyu9Ra+o6p0RxmSMiXelBfDVP2Gfk6GbPRrVGiK9++gdERkI7OMt+k5VyxrZrBK4XlXniUgHYK6IvKeq34at96mqnty0sI0xbcKcx6E030oJragpD6CNwJUQkoBhIoKqPl3fyqq6HljvTReKyBKgJxCeFIwxZmflxfDFIzDgGOh5QNDRtBkRJQUReQYYAMwHqrzFiqseimT7vsD+wFd1fDxKRBYA64AbVHVxJPs0xsS5eU/Dtlw44oagI2lTIi0pjAQGq2q9zyzUR0QygJeBa1W1IOzjeUAfVS0SkZOA14CBdexjEjAJoHfv3k0NwRgTayrL4L8PQe/R0Gd00NG0KZHefbQI12DcJF732i8Dz6nqK+Gfq2qBqhZ50zOA5LrGZ1DVKao6UlVHZmXZTU/GxL0FL0DBWislBCDSkkJX4FsRmQ3UNjA39ESziAjwOLBEVf9azzp7AD+pqorIQbgklRdp8MaYOFRV6Tq+67E/DDg66GjanEiTwh3N2PehwPnANyIy31v2e6A3gKpOBs4AfiUilbixnyc0p4rKGBNHFr8CW1bB2D+DSNDRtDkRd4gnIt2AA71Fs1V1YyPbfAY0+C+qqg8DD0cSgzGmDaiucoPo7D4Y9jox6GjapIjaFETkLGA2cCZwFvCViJzhZ2DGmDYmfy08cwrkfufaEhIibfI0LSnS6qNbgANrSgcikgW8D0zzKzBjTBuy+FV441qoqoBxf3f9HJlARJoUEsKqi/KI/M4lY4ypW1khvP07mP8c9BwBpz1qnd4FLNKk8I6IvAu84M2fDbztT0jGmDZhzWx45TLY+iMccSMc+TtITA46qjYv0obmG0XkNOAwXOPxFFV91dfIjDHxqaoSPr0PPv4/6NgTJs6APqOCjsp4Iu3moh8wo+YBNBFpJyJ9VXWVn8EZY+LM5pXwyiTImQ1Dz4aT7oW0TkFHZUJE2i7wH1z31zWqvGXGGNM4VZj/PEw+DHKXwumPw2lTLCFEoUjbFJJUtbxmRlXLRSTFp5iMMfGkeDO8eR18+xr0ORRO/ZeNsxzFIk0KuSIyTlWnA4jIeGCTf2EZY+LCyk/glV/Cto1wzO1w6DWQkBh0VKYBkSaFy4HnROQRXJfZOcAFvkVljIltleXw4V3w37+7W0zPed/1ZWSiXqR3H/0AHOJ1gy2qWuhvWMaYmJW7FF6+FDYshBEXwdi7IaV90FGZCEV691E34M9AD1U9UUQGA6NU9XFfozPGxA5V+PoxmHmrSwITnod9fhZ0VKaJIr376EngXaCHN/89cK0fARljYlDRRnj+bJhxg2tM/tUXlhBiVKRJoauqvoR3W6qqVrJ9WE5jTFv2/Uz452hYMQtOuAfOmwYdugUdlWmmSBuat4lIF1wjMyJyCJDvW1TGmOhXXgzv/cFVGXXbFy6YDt0GBx2V2UWRJoXfANOBASLyOZCFGyDHGNMWrV/oGpM3LYVRV8LRf4DktKCjMi0g0ruP5onIkcDeuL6Plqpqha+RGWOijyp8NRlm/gHSu8D5r9qQmXEm0kF2zgTaqepi4BRgqogc4GtkxpjoUl7s+i165yYYeBz8+gtLCHEo0obmP6hqoYgcBowFngL+2dAGItJLRD4SkSUislhErqljHRGRh0RkuYgstERjTJTashqeOB6++Q8cfSuc/Rykdw46KuODSJNCzZ1GPwP+qaqvA431fVQJXK+qg4BDgCu85xtCnQgM9F6TaCTRGGMCsGIWTBkDW36Ec6e6sQ9sqMy4Fem/7FoR+RdufOYZIpLa2Laqul5V53nThcASoGfYauOBp9X5EsgUke5N+gbGGH+oum4qnjkVMnaHSR/BXmODjsr4LNKkcBbu4bUTVHUr0Bm4MdKDiEhfYH/gq7CPegJrQuZz2DlxICKTRGSOiMzJzc2N9LDGmOYqL3Z3F828FfY5GS5934bJbCMavPtIRDJUtUhVi4FXapar6npgfeg6De0DeBm4VlULwj+uYxPdaYHqFGAKwMiRI3f63BjTgrasghd/AT8tgmNug8N+A1LXf1UTjxq7JfV1EZkPvA7MVdVtACLSHzgKV4J4FJhW18YikoxLCM/VjNoWJgcI7Vg9G1jXpG9gjGk5P3wI0y4GrYbz/uPuMjJtSmPtAscAHwC/BBaLSL6I5AHPAnsAF6pqfQlBgMeBJar613oOMR24wLsL6RAg3yuFGGNakyp8/iA8ezp06A6XfWQJoY1q9OE1VZ0BzGjGvg8Fzge+8UobAL8Henv7nezt9yRgOVAMXNSM4xhjdkX5Nnj9Clj8Kgw+BcY/AqkZQUdlAhJpNxdNpqqfUXebQeg6ClzhVwzGmEZsXuHaD3KXwLF/dCOjWftBm+ZbUjDGRLnl78O0S9z0edNgz2OCjcdEBUsKxrQ1qvD5A/DBnZA1CCY8C537Bx2ViRIRJwURSQS6hW6jqj/6EZQxxidlRfD6r+Hb12HIaTD+YRsq0+wg0uE4rwJuB37CG2gH9zzBUJ/iMsa0tLwf4MXzXHfXx90Jo6+29gOzk0hLCtcAe6tqnp/BGGN8suw9ePkSkAT4xcvWu6mpV6RJYQ020poxsUcVPr0fPvyTGx1twrOwW9+gozJRLNKksAKYJSJvAWU1Cxt4KM0YE7SyQnjtV7DkDdj3DBj3d0hJDzoqE+UiTQo/eq8UGu8y2xgTtLwf4MVzYdP3cPzdMOoKaz8wEYl0OM4/AohI+5r+j4wxUWrtPHjmFJBEN1xm/zFBR2RiSKTDcY4SkW9xYyIgIsNE5B++RmaMabqahJDWyY1/0H9M0BGZGBPpeAoP4IbhzANQ1QXAEX4FZYxphtCEMPEta1A2zRLxmHqquiZsUVWdKxpjWl94QsjsHXREJkZFfEuqiIwGVERSgKvxqpKMMQFb9z9LCKbFRFpSuBzXm2lP3MA4w7HeTY0J3rr/wdPjLSGYFhNpSaFaVc8LXSAi/fDaGIwxAQhNCBe+aQnBtIhISwpviEjHmhkRGQS84U9IxphGhSeE3foEHZGJE5EmhT/jEkOGiIzAjcn8C//CMsbUyxKC8VGkD6+9JSLJwEygA3CKqi7zNTJjzM4sIRifNZgUROTvuC6ya3TE9YN0lYigqlc3sO0TwMnARlXdt47PxwCvAyu9Ra+o6p1NC9+YNmTdfHj6FEi1hGD801hJYU7Y/Nwm7PtJ4GHg6QbW+VRVT27CPo1pm9bNdyWE1I4w0RKC8U+DSUFVn2rujlX1ExHp29ztjTEeSwimFUXa99FAEZkmIt+KyIqaVwscf5SILBCRt0VkSAPHnyQic0RkTm5ubgsc1pgYYQnBtLJI7z76N/BPoBI4Clcl9MwuHnse0EdVhwF/B16rb0VVnaKqI1V1ZFZW1i4e1pgYYQnBBCDSpNBOVT8ARFVXq+odwC6N56eqBapa5E3PAJJFpOuu7NOYuGEJwQQk0ieaS0UkAVgmIlcCa4Hdd+XAIrIH8JOqqogchEtQ9oS0MZYQTIAiTQrXAum4jvDuwlUhXdDQBiLyAjAG6CoiOcDtQDKAqk4GzgB+JSKVQAkwQVW1nt0Z0zZYQjABizQp9FXVr4Ei4CIAETkT+Kq+DVT1nIZ2qKoP425ZNcaAJQQTFSJtU7g5wmXGmOZYv8BLCB0sIZhANfZE84nASUBPEXko5KOOuDuRjDG7av0CeGqcJQQTFRqrPlqHe6p5HDs+zVwIXOdXUMa0GTslhL5BR2TauMaeaF4ALBCR51W1opViMqZtsIRgolBEbQqWEIxpYcvft4RgolKkdx8ZY1rChkXw3h/ghw+h8wA4/xVLCCaqNCkpiEh7Vd3mVzDGxK2CdfDh3TD/OTcWwtg/w4GXQlJq0JEZs4OIkoKIjAYeAzKA3iIyDPilqv7az+CMiXllhfDZA/DFI6BVMPpKOPx6aLdb0JEZU6dISwp/A8YC08E1QIvIEb5FZUysq6qAeU/BrL/AtlzY9ww45g9WVWSiXsTVR6q6RkRCF1W1fDjGxDhVWPo2vHcb5C2DPofCuVOh54igIzMmIpEmhTVeFZKKSAquD6Ql/oVlTAxaOxdm/gFWfw5dBsKEF2DvE2HHH1PGRLVIk8LlwINATyAHmAlc4VdQxsSULavhgzth0TRI7wo/ux8OuBASk4OOzJgmiygpqOom4DyfYzEmtpRsgU/ug9lTQBLh8Bvg0GsgrWPQkRnTbJHefdQPuAroG7qNqo7zJyxjolhlGXz9GHz8f1CaD8PPg6N+D516Bh2ZMbss0uqj14DHgTeAav/CMSaKqcLiV+H9O2DrahhwNBx3J+yxX9CRGdNiIh55TVUfanw1Y+LU6i9g5q2wdg7sPgR+8TLseWzQURnT4iJNCg+KyO24BuaymoWqOs+XqIyJFpuWw/u3w3dvQofuMP4RGHYOJCQGHZkxvog0KewHnA8czfbqI/XmjYk/VZXwwR3w5T8hKQ2OuhVG/RpS2gcdmTG+ijQpnAr0V9XySHcsIk8AJwMbVXXfOj4X3G2uJwHFwEQreZioUFYI0y6GZTNh//PhmNsgY/egozKmVUQ6HOcCILOJ+34SOKGBz08EBnqvScA/m7h/Y1pewTr494mw/AM4+QEY/7D7RWaMAAAW/0lEQVQlBNOmRFpS6AZ8JyJfs2ObQr23pKrqJyLSt4F9jgeeVlUFvhSRTBHprqrrI4zJmJa1YRE8dyaUFcC5L8FAa0g2bU+kSeF2H47dE1gTMp/jLdspKYjIJFxpgt69e/sQimnzlr8PL010g95c/I7dZmrarEifaP7Yh2PX1SGM1nP8KcAUgJEjR9a5jjHNNuff8Nb1sPtg13mdPYRm2rAGk4KIfKaqh4lIITtesAVQVd2V5/lzgF4h89nAul3YnzFNU10NH94Jn/3NPXNw5pOupGBMG9ZYSaE9gKr68T9lOnCliLwIHAzkW3uCaTUVpfDar2DxKzDiIjjpPki00WmNaex/QbOrakTkBWAM0FVEcnDtEskAqjoZmIG7HXU57pbUi5p7LGOaZFsevHgurPnSdVMx+mrr3toYT2NJYXcR+U19H6rqXxv47JyGduzddWTdb5vWlfcDPHcG5K911UVDTg06ImOiSmNJIRE3LrP9jDKx78cv4QXvt8qFb0Dvg4ONx5go1FhSWK+qd7ZKJMb4adHL8OqvoFM2nPcf6DIg6IiMiUqNPdFsJQQT21Td3UXTLoaeB8Cl71tCMKYBjZUUjmmVKIzxQ1WFe/5g3lOw7+kw/h+QnBZ0VMZEtQaTgqpubq1AjGlRpQXwn4nwwwdw+PWul9OESLv6MqbtshuzTfzJXwvPnwUbl8DPH4IRFwYdkTExw5KCiS/rF7qEUFbkGpT3tBpQY5rCkoKJH8vec1VGaZlwybvQbUjQERkTc6yS1cSHrx+H58+Gzv3dHUaWEIxpFispmNhWXe3GUP7vQzBwLJzxBKRmBB2VMTHLkoKJTdXVsHExfHIvfPs6HHgpnHCPdWpnzC6y/0EmNqjCpmWw8mNY+Qms+gxKNgMCx98No66wTu2MaQGWFEz02rLaJYCaV9EGt7xTL9j7ROh3hHt17BFsnMbEEUsKJnoUboCVn24vDWxd7Za33317Auh3OOzWz0oFxvjEkoIJTvFmVw1UUxLYtNQtT+sEfQ+HUVe6RJC1tyUBY1qJJQXTesoKYfUX20sCG74BFJLbQ5/RsP8vXBLYYz9ISAw6WmPaJEsKxl8bl8A301wSWDsXtAoSU6HXQXDULS4J9DwAEpODjtQYgyUF45fSAvjozzB7ipvvOQIOu84lgV4HQXK7YOMzxtTJ16QgIicAD+JGcHtMVf8S9vlE4F5grbfoYVV9zM+YjM9UXclg5i1QtBFGXuR6KG3fJejIjDER8C0piEgi8AhwHJADfC0i01X127BVp6rqlX7FYVrRxu9gxg2w6lPosT+c84IrIRhjYoafJYWDgOWqugJARF4ExgPhScHEurIi+Pge+PIfkJIBJ/8NDrjQGouNiUF+JoWewJqQ+RygrpHSTxeRI4DvgetUdU34CiIyCZgE0Lt3bx9CNc2iCt++Bu/8HgrXwf7nw7F3QPuuQUdmjGkmP3tJrevGcg2bfwPoq6pDgfeBp+rakapOUdWRqjoyKyurhcM0zbJpGTxzquuqun0XuOQ9GP+wJQRjYpyfJYUcoFfIfDawLnQFVc0LmX0UuMfHeExLKC+GT++Dzx+C5HQ48V4YebF1RGdMnPDzf/LXwEAR6Ye7u2gCcG7oCiLSXVXXe7PjgCU+xmN2hSp89xa8cxPkr4GhE+D4uyBj96AjM8a0IN+SgqpWisiVwLu4W1KfUNXFInInMEdVpwNXi8g4oBLYDEz0Kx6zCzavgLd/B8tmwu6DYeIM6Hto0FEZY3wgquHV/NFt5MiROmfOnKDDaBsqSuCzB+Czv7knjsfcDAf/0p4+NiYGichcVR3Z2HpWEWzq9v1MePtG2LIK9j3djVnQsXvQURljfGZJwexoy2p452ZY+hZ03QsueB36jwk6KmNMK7GkYJzKMjfO8Sf3u26qj70DDrkCklKCjswY04osKbR11VWw/AN492bIWw6DxsHYP0Nmr8a3Nca0mOpqpbSyitKKakorqrxXtbesirKKanp1bseeu3fwNQ5LCm1R8Wb44UP4/l1Y/r4b67hzfzjvZRh4bNDRGRPVVJXCskryiyvYWlzB1pJythRXkF9cTkFpJSXl3gV9hwt8NWWVIRf6sM/LKqopr6pu9NiXHzmAm07cx9fvZ0mhLVCFnxa5W0q/nwk5s0GrIb0LDDwOBh4P+5wMyWlBR2pMq6mqVgpLay7sFWwpLvcu9OVsLXHL80u2z+d76+WXVFBVXf9dmwkCacmJ7pWUQFpyIqnJiaQlJ5CWlEjXjKTtnycnkJq0fTp0m9rPkxNJS0okNTmBHp3873LekkK8KityI5wtmwnL3oMCr3fy7sPg8BtcIuh5gHVaZ6JGdbWyrbySwtJKyirdL+uaX9Bl3i/t8srq2s+2T1dTVlFFWe161d5nVXVOF5VVsrW4goLSChq6I79DWhKZ6clktkshMz2ZnpntdpjPTE8hs12yN51Mp3YpdGyXREpiAhLDw8daUogneT94SWCmG/u4qhxSOsCAMe4Zgz2PtdtKA7axoJQFOfkszNnKms3FdGrnLi6d26ewW/sUdktPZrea+fQU2qXERtJWVUoqqigsraSwtIKC0koKSiq8+UoKSisoLA2Z9z4rKN3+XlRW2eBFujGpSQmkJLlf3qlJCdvnkxNJTUwgIzWJlPQEMtKSyGyXTKc6Luruop9Mp3bJJCX62TVc9LKkEMsqy2D1f7cngrzlbnnXveCgSa400HuU3UEUkPziChau3crCnHwWrHHvGwpKAUhMEPbomEZRWSX5JRX17iMtOYHO6TUJw713Tm96IqmuVsoqqympbcCs8qbdr+ySkLrumnXKKqt3qB8vKXeNnmUVVWwrq6KwrIKCksrai31lA1UqNd+5Q1oSHdKS6JiWTIe0JHp1Tq+d7piWRMd2yWSkuuqV1KQEUpMTSEl0VSfhF/2UkAt/rP86jyaWFGJNwTpXHbRsJqyYBeVFbszjfodvTwSd+wUdZZtTXF7J4nUFtRf/hTlbWZVXXPt5v67tObh/Z4ZlZzKsVycGd+9Ue/GurKr26rDL2bytgs3byt10cTlbtrllNfM5W4pdo2YjiWS39BSqVSmtcImgvLLxRsy6iEC70PrxFFe/nZ6SyO4d0hiQFXqR9y7u7UIu8iHL01MS7cIdAywpRLuKEsiZ4xLAsndhwzduecdsGHoWDBzrEkJK+0DDbEvKK6tZuqGQBTlbWZjjksD3PxVS80O5e6c0hmZ34syRvRiWncl+2Z3o1K7+rkGSEhPompFK14zUiGNoLJFsKa4gUcQ1XnoX8rTkRNolhzZibm/cbBc2XzNtv8DbHksK0aa0ANbMhtWfu6qhtXOhugIkEXof4h4qGzgWdh/kfsYZX1VXKys2FbFgTT4LcrayICefJesLan9575aezNDsTI4f3I2h2ZkM7dWJ3Tv4fxdXcxKJMZGwpBC04s3w4xew6nOXCDYsdLeLJiS5cY5H/Rr6HAq9DoZ2mUFHG1Mqq6rZVl7FtrJKissr2VbmpmuWbSuvdO9hy4vLKynylq/ctI2iskoA0lMS2bdnJyaO7svQ7E4My84ke7d29kvaxBVLCq2tcMP2UsDq/8JGb8jqpDTIPhCOuBH6jHbTbaBKqLra3bVSXF5FSXmVN10ZMl0VNl25w/Li8iq2lVe699oLvZsua0I9enpKIukpSWSkuvf2qYl0bp/C8F6ZLgH0ymRAVgaJCZYATHyzpOAnVdj6o5cAPnPvm1e4z1Iy3K//fU93JYGeB0BScFUB1dW6w/3gZSH3g7v7wMPv+95+H3n4veDhy0u8O1rcRbyS0opqir0LeVMu3DXaJbuGzjTvvX1qzUU8nYxU16Dp3t1y93kS7WvWDVveLjnRLvbGeCwptCRVN3ZxaEmgIMd9lpbpSgAjL3ZJYI+hDQ5hqapsLa4gt6iM3MIythSXU+5dZGsu3uVV2y+8bnlV7XRZ6Lo7rLP9Ah66rKJq18fVSE4UUpMSa28VTK25fTA5gXbJiXTNSCE9Jb32Yh56Yd8+nVTPcvdZalICCXYBN8Y3lhSaShVKtsDW1a4UsHWN977aNQpvy3Xrtd/djU7W51qXDLIGQUICxeWV5BaWkbumwL17F/3alze/qags4gt1SqJ3r7Z3v3bodKp3B0mHtKQd7umuud87JeR+750u6MlhDwF594fXPJofvp392jYm9llSCKcK2za5C33+j94F31381ZuWim07bFKdkkFlh2y2dT+MDbuNYEX6MFZW70FuUTm5y8rInZdPbuHH5BaWsa28aqdDJgh0yUglKyOVrA6p7NWtA1kdts9ndUhlt/SU7Rf10It7ov1yNsa0HF+TgoicADyIG6P5MVX9S9jnqcDTwAggDzhbVVf5EcvslZv5x6zlVFdVkV6RR+fyn+hc+RNdqzaQVfkTWVUb6Va9kW66kTTKd9g2X9uzVruyRrNYq4eTo1nkaFfWahZrtCsFpe2hQGBtzRaFQCEd05JqL+r7ZWfucJEPveh3bp9iv7KNMVHBt6QgIonAI8BxQA7wtYhMV9VvQ1a7BNiiqnuKyATgHuBsP+LJ+PED7l5zG1nVuaSw49OgRQkdyUvegy3J/VmZMpqtqd0pSO1OUVp3CtN6UJ3SgcQEISkxgeQEoWui0D0hgVGJQpK3PDFByGyXXHvB75qRSlpybPRbY4wxNfwsKRwELFfVFQAi8iIwHghNCuOBO7zpacDDIiKqu9ItVt0GD+gPGw+GTr0gs/f2V6deZKRmkAH0aemDGmNMjPEzKfQE1oTM5wAH17eOqlaKSD7QBdgUupKITAImAfTu3bt50WSPgDOfbN62xhjTRvjZN2xdleThJYBI1kFVp6jqSFUdmZWV1SLBGWOM2ZmfSSEHCB3oNxtYV986IpIEdAI2+xiTMcaYBviZFL4GBopIPxFJASYA08PWmQ5c6E2fAXzoR3uCMcaYyPjWpuC1EVwJvIu7JfUJVV0sIncCc1R1OvA48IyILMeVECb4FY8xxpjG+fqcgqrOAGaELbstZLoUONPPGIwxxkSubQ5Caowxpk6WFIwxxtSypGCMMaaWxNrNPiKSC6wOOo56dCXswbsYEquxx2rcYLEHpa3G3kdVG33QK+aSQjQTkTmqOjLoOJojVmOP1bjBYg+Kxd4wqz4yxhhTy5KCMcaYWpYUWtaUoAPYBbEae6zGDRZ7UCz2BlibgjHGmFpWUjDGGFPLkoIxxphalhSaSURWicg3IjJfROZ4yzqLyHsissx73y3oOAFE5AkR2Sgii0KW1RmrOA+JyHIRWSgiBwQXeb2x3yEia71zP19ETgr57GYv9qUiMjaYqGtj6SUiH4nIEhFZLCLXeMuj+tw3EHfUn3cRSROR2SKywIv9j97yfiLylXfOp3o9NyMiqd78cu/zvlEY+5MisjLkvA/3lvvz96Kq9mrGC1gFdA1b9n/ATd70TcA9QcfpxXIEcACwqLFYgZOAt3EDIB0CfBWFsd8B3FDHuoOBBUAq0A/4AUgMMPbuwAHedAfgey/GqD73DcQd9efdO3cZ3nQy8JV3Ll8CJnjLJwO/8qZ/DUz2picAUwP8e6kv9ieBM+pY35e/FysptKzxwFPe9FPAKQHGUktVP2HnwYvqi3U88LQ6XwKZItK9dSLdWT2x12c88KKqlqnqSmA5bqzwQKjqelWd500XAktwQ9BG9blvIO76RM15985dkTeb7L0UOBo3DjzsfM5r/i2mAceISF0jQvqugdjr48vfiyWF5lNgpojM9caQBuimquvB/ccCdg8susbVF2tdY2s3dEEIypVekfmJkGq6qI3dq5bYH/frL2bOfVjcEAPnXUQSRWQ+sBF4D1dy2aqqlXXEt8M48UDNOPGBCI9dVWvO+93eef+biKR6y3w575YUmu9QVT0AOBG4QkSOCDqgFhLRuNkB+ycwABgOrAfu95ZHZewikgG8DFyrqgUNrVrHssDiryPumDjvqlqlqsNxQwAfBAyqazXvPapjF5F9gZuBfYADgc7A77zVfYndkkIzqeo6730j8Cruj++nmuKb974xuAgbVV+skYytHShV/cn7z1MNPMr2qoqoi11EknEX1udU9RVvcdSf+7rijqXzDqCqW4FZuPr2THHjwMOO8UXlOPEhsZ/gVeepqpYB/8bn825JoRlEpL2IdKiZBo4HFrHjmNMXAq8HE2FE6ot1OnCBd2fDIUB+TVVHtAirNz0Vd+7BxT7Bu6OkHzAQmN3a8dXw6qYfB5ao6l9DPorqc19f3LFw3kUkS0Qyvel2wLG4NpGPcOPAw87nPCrGia8n9u9CfkAIri0k9Ly3/N9La7ewx8ML6I+722IBsBi4xVveBfgAWOa9dw46Vi+uF3DF/Qrcr4tL6osVVyR9BFcP+w0wMgpjf8aLbaH3H6N7yPq3eLEvBU4MOPbDcMX5hcB873VStJ/7BuKO+vMODAX+58W4CLjNW94fl6iWA/8BUr3lad78cu/z/lEY+4feeV8EPMv2O5R8+Xuxbi6MMcbUsuojY4wxtSwpGGOMqWVJwRhjTC1LCsYYY2pZUjDGGFPLkoLZZSKiInJ/yPwNInJHC+37SRE5o/E1d/k4Z3q9gn7k97GaQ0SmiUh/n4+xS+daRFJE5JOQh8RMDLKkYFpCGXCaiHQNOpBQIpLYhNUvAX6tqkf5FU9zicgQXK+jK4KOpT4ikqiq5bjnLs4OOh7TfJYUTEuoxI0de134B+G/PkWkyHsfIyIfi8hLIvK9iPxFRM7z+pP/RkQGhOzmWBH51FvvZG/7RBG5V0S+9joK+2XIfj8SkedxD/SEx3OOt/9FInKPt+w23ANbk0Xk3rD1u3u/fud72xxe335qvp+I3C2uT/wvRaSbt3yAN/+1iNwZch7q3H+Y8wh5Or6BY0TDuX7Ni9fEKEsKpqU8ApwnIp2asM0w4BpgP+B8YC9VPQh4DLgqZL2+wJHAz3AX7jTcL/t8VT0Q11HYZV4XC+D6hrlFVQeHHkxEegD34LpRHg4cKCKnqOqdwBzgPFW9MSzGc4F31XVSNgyYX99+vPXbA1+q6jDgE+Ayb/mDwINevOsa2n8d5+lQYG7IfH3HaEhrnetF3jomRllSMC1CXS+aTwNXN2Gzr9V19lWGe1R/prf8G9zFqcZLqlqtqsuAFbgeI4/H9fsyH9etcxdcnzsAs9X16x/uQGCWquaq6yb5OdwgPg3GCFzktZHsp258gYb2Uw686U3PDfkeo3DdKQA838j+w3UHckPm6ztGg9+jNc61qlYB5eL1DWZijyUF05IewP2qbB+yrBLv78zr0Csl5LOykOnqkPlqILSxMrwvFsX1+3KVqg73Xv1UteZCt62e+Jo8eIq6QX6OANYCz4jIBY3sp0K39x1TxY7fI9L9hyvB9dHT2DGi5VynAqV1LDcxwJKCaTGquhk37OElIYtXASO86fG40aSa6kwRSfDqvvvjOl17F/iVuC6eEZG9xPVY25CvgCNFpKvXCH0O8HFDG4hIH2Cjqj6K6zn0gObsB/gSON2bntDI/sMtAfZsZP8QBedaRLoAuapa0Yxjmyhgt46ZlnY/cGXI/KPA6yIyG3dnSn2/4huyFHfR7QZcrqqlIvIYrtpjnverOJdGhj9V1fUicjOuG2UBZqhqY92bjwFuFJEKoAi4oJn7uRZ4VkSuB97CjfBV5/7r2PYtb733GzlGNJzro4AZzTiuiRLWS6oxrUBE0oESVVURmQCco6rjI9y2HS4BHerV2UctEXkFuFlVlwYdi2keKykY0zpGAA97v7S3AhdHuqGqlojI7bjxd3/0Kb5dJiIpwGuWEGKblRSMMcbUsoZmY4wxtSwpGGOMqWVJwRhjTC1LCsYYY2pZUjDGGFPr/wMgM8vlZlkOHQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "trace\n",
    "x =[]\n",
    "y1=[]\n",
    "y2=[]\n",
    "for measure in trace:\n",
    "    x.append(measure[0])\n",
    "    y1.append(measure[1])\n",
    "    y2.append(measure[2])\n",
    "\n",
    "plt.figure()\n",
    "plt.plot(x,y1,label=\"LSH\")\n",
    "plt.plot(x,y2,label=\"naive\")\n",
    "\n",
    "plt.title(\"Runtime Comparison\")\n",
    "plt.xlabel(\"Number of songs (number)\")\n",
    "plt.ylabel(\"Time taken (seconds)\")\n",
    "plt.legend(loc='upper left')    \n",
    "\n",
    "\n",
    "plt.show"
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}