vpt_index.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/EdoardoMorucci/Plant-Leaves-Search-Engine---MIRCV/blob/main/vpt_index.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ObI9JTVzT0gi"
      },
      "source": [
        "# Vantage Point Tree Index"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VKxdBA_GUEJC"
      },
      "source": [
        "Useful import"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Ftjnvkdwnxjr"
      },
      "outputs": [],
      "source": [
        "from statistics import median\n",
        "from sklearn.metrics.pairwise import cosine_similarity\n",
        "import numpy as np\n",
        "from numpy import dot\n",
        "from numpy.linalg import norm\n",
        "import random\n",
        "import math\n",
        "import pandas as pd\n",
        "import pickle\n",
        "import os\n",
        "import time"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XFVX6v0hUKFd"
      },
      "source": [
        "The **Object** is the data structure that contains the informations related to one image:\n",
        "* **Features**  is the numpy vector extracted using the CNN model\n",
        "* **Id** is the identifier used to retrieve the image from the dataframe\n",
        "\n",
        "![ExampleVPT_Object.png](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAA44AAAE4CAIAAACbmTqCAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAAFiUAABYlAUlSJPAAAC9PSURBVHhe7d1BiyRHn9/xvvjkV1AHG5sBw+Nn/Mj7DLotbB1MX3To5yJ4VuBiGQYEFuYBQRf0wVjgZ5BxQ7O7o8sKCnp0emBIELusrRkonmXpxW4oGIMOTYEPQjPURQyiaZAYRCH/KyMyK6sqKzMyIyMqMvP7oR892d1VNZHRkZG/jIzMPPoZAAAACBJRFQAAAIEiqgIAACBQRFUAAAAEiqgKAACAQBFVAQAAECiiKgAAAAJFVAUAAECgiKoAAAAIFFEVAAAAgSKqAgAAIFBEVQAAAASKqAoAAIBAEVUBAAAQKKIqAAAAAkVUBQAAQKCIqgAAAAgUURUAAACBIqoCgK2rq6sHv37n1atX+nsAQEOIqgA6ZHkzOR4cHQ2OJzdL+W5xfTk+PloZDMeffzlbyA8bJzlV/oF/+6+O/uRXv2g0rS5vp2eyMkdH70/mP/788+18+ofz0f3VD47uj86j2eJt8sLF7MvPx8P4tbKqo4sX81v9KwBoOaIqgA65nY5Xge3eKPrm7uZypMNb6vhs+rrZtKpy6vi3R//02dFv/rTZtPrjfPL+qtSDs+n3307PVObOGF7M7pbLxdWFzq8Zg4+i10mQBYA2I6oC6I6fZuf3Vklt+OmzycPtnKqoEcpmpDl19jerr6bT6rfRKF6bDz6d7ObUlQcfTy7PksHUTXpcGQDajqgKoDN+WkQf6qgmhuNLfcZ/eTf/Kjl1fnTvfPZT/GpLWzm1+bSqR4iV7ASG25uNHJ791dvF9JOh+ul4yiQAAB1AVAXQGd9Nxw/inHY0GF3e3G2OKt5dn6sByOPJ3Hq8UeXUyXgjp6qvptLqcj5JhlLvjyZf3+kfxxbRaN+vkoHlphI5ABwWURVAV+hrqiSo5s7UvJudxwOO1iGuIKeqrybSajpCPBieX2+E0UyKzRk6Xc/W/Vb/BADajKgKoCt0SsvJdrEk/NlF1dKcqr6s02oyQpwTu7fuDLAhGVRtckouABwQURVAR5SltAZGVf/xH6byAaU5VX1ZpdVkhDhvymmSYnNmMmRuGnBrPcsBAAJAVAXQDWWDpun0gFG00D/a8vZ19NFg/0zWSjlVfdVPq3o2at55/GRF8lZUp9j8a6pWs3XvcWcAAO1CVAXQDclY454kmszv3HcXJ33tfMGF83/9lxfy/kpRVb7Gv139qy9fvtSfYqToFH+SYh+Mp9/pn6SSKRA567h8Hd+ZlZtYAWgZoiqATkgHTXOHRZffRA/Vzarywt9ycX2hHheQl/8yqqZVlVOvrq70+00VnMcvSrFJHB+ezzYn697dRMlTu4iqANqFqAqgE9K7kOZchxSf2Ve/3B40vZ1PJ+kjSU2uRjJPq5JTf/WLf1k9p4rk5v85I8TJjFvTiarpCh5/PP5gQFQF0DZEVQBdkFxTFRuOJ9O5Hle8m784Tx6wup1i0xHKwXD8V6tnBJhdjWSSVlVOrXn5f9F5/IqXW8WvH4wuXsy/j1eWqAqgZYiqADogGVC897vz37+3WshxfDZ9vZnS5F0fjyfRdH6rI+D+a6q2FKdVq5y6jt15sxEKLrfKD7i389n/i1O7yuVEVQAtQ1QF0AGZa6ruvp4kz1BdG4wurtWjR/eIc17BNVW79qVVy5y6jt1HH0aLrUv8TSaq7ptuS1QF0EpEVQDtp0+LJzlsuZhF6Vn/4/Hk72aL3YdXZakYV3JN1a7dtCo59d//u39jkVNFvdumpk+32g24ClEVQCsRVQG0X8H9m4yoCFh+TdWubFqVnGr/6H9niKoAWomoCqD1rJ8mGg9kll1T9ebNG720SaXV0fHenPpDTH9zMERVAK1EVAXQdgWnxc0UXlMlCfX58+ePHj2Sf6Egrf76nV/uG0+Vt8t7Hz9+fHV1dbjMSlQF0EpEVQBtV/KcqlLxBUnbGU4ypSRLlVDffffdJ0+eFJ/Z35dihfooiaqrQh4ssxJVAbQSURVAyyW3Gt338P8yKsPpea7ZWKkSasVnohY5aGYlqgJoJaIqgJZr6Jqq//rl/8mGyAYT6i6ngXgPoiqAViKqAui1ly//+J//w784+mercVm/w5wrHjMrURVAKxFVAfTRq1evJBdKOpSM+OjRI88JddchxlkBoAWIqgB6RBLq06dPT05OVEJ9/vx5weVQB6Eya/ZyLjIrgD4jqgLoPsmjURSphCr/lbQaWkLdJSVMb5JFZgXQW0RVAJ2VTXsqoRbfcCpMZFYAfUZUBdA16hz66elpmu3m87n+XZvtZtY2Jm8AqISoCqAj+nNlUjdGiwHABFEVQOtJJJVgKrlNqBtO6V90HZkVQOcRVQG0lUqo78Y3nPJ/S9SgkFkBdBVRFUDLSAiTKKYSqoQziWgS1PTvek9VjqRVMiuAbiCqAmiHbAgjoZYiswLoBqIqgKBxatsSmRVAqxFVAYSIhNq4bGZlWBpAWxBVAQSER+F7QGYF0CJEVQCHl02ogoTqB5kVQPiIqgAOiRtOhUAya/pXILMCCApRFcABzOfzNBudnp6SUAORPXIgswIIAVEVgD+ccW4LMiuAQBBVATgnKSdNqPJfck+LbGVWxr8BeEZUBeCK5FFJpZJvVEKVtPqKG061FrOKARwEURVAwyTBpAlVko3kGxJql5BZAfhEVAXQDMkrklq4JWp/kFkBeEBUBWBLIotKqCqykFB7JXuIohoAmRVAg4iqAGpiUA1ZZFYALhBVAVSzdbt44gi2kFkBNIioCsAIt0RFVdnMyvRlAPUQVQEUkTwaRVF6S1RJqyRUVEVmBVAbURVADm6JChfIrACqIqoCWFNJ4vT0NE0S8/lc/w5ojrS0rZvvklkB5CKqAmCsCweTHb+n7QHYRVQFek1igYQDSQlCXamtfwH4RWYFkIuoCvSRSqgSCNKE+gP3EkIYtjIr86SBniOqAj2ibjilEqpEAQkEJFQEi2v7AAiiKtB93BIVrUZmBfqMqAp0Fjt4dIxq0uqgiyYN9ARRFegaEio6L3uigEYOdBtRFegIbjiFHiKzAp1HVAXajYQKiN3MyoRsoBuIqkBbccMpYFc2s3IRIdABRFWgZebzeZpQT09PSahALjIr0A1EVaAd2O8C9bDtAK1GVAWCJvvUdC8r/2UvC9SWPSNBZgXagqgKhEj2oLIflb2pSqiSVl9xXTPQkOw8bzIrEDiiKhCQH374IU2osh8loQJOkVmB8BFVgcPjhlPAYWUzK1crAkEhqgKHJDtIlVCFLJBQgcPKZlbuAQeEgKgKHAC7QyBwbKRAIIiqgD+vXr1Kd36PHj1i5weET2VW2WbJrMBBEFUB57itI9B2Ek8lpEpUJbMCnhFVAVckj0ZRlN4SVZZJqEDbkVkBz4iqQMMkj3JLVKDzcjOr/h2A5hBVgWao/VZ6S9QnT57M53P9OwDdlc2satvnVh5Ag4iqgBX2UgAUegPABaIqUNPudcH6FwD6jcwKNIioClSjEqrsftKEKrsl/TsAyJDOIfuoZDIrUANRFTCibjilEqq64RQJFYCh7NWWZFagEqIqUIRbogJoEJkVqIqoCuRQu5P0lqjccApAs7YyK50MsA9RFVjL7jxIqAA8oNsBihFVAS7XBXB4ZFYgF1EV/UVCBRAgyazZZzKTWdFzRFX0kURSCaYST2VPwA2nAIRJEqrkVDIreo6oih7JJtTT01MSKoBWILOiz4iq6L5sL/+IG04BaK2tzBpFEb0ZOo+ois6SHjzbp5NQAXQGR+DoD6Iqukb6a66iBdATZFZ0HlEVHfHD5rO2SagAeoXMiq4iqqILpINWCZUbTgHoua3rR/VPgdYiqqIL5vM5CRUAsqRXvLq60t8ArUVUBQAAQKCIqgAAAAgUURVt9Y//MP31O7/k2ikAKHbxP/7bX/zHP+eJJ2gpoiqsLW8mx4Ojo8Hx5GYp3y2uL8fHRyuD4fjzL2cL+WHjJKfKP/Bn7xz9ya9+4T2tLm+nZ7LCR0fvT+Y//vzz7Xz6h/PR/dUPju6PzqPZ4m3ywsXsy8/Hw/i1Uh2jixfzW/0rAP2znE/izlF1HW8Xsy+S/uF4PPm7ddfRKMmpv/zX/1y+HKTV76bjB3HxJ3Pp6O/m02fnI7VCg7gvTHr/VV84GQ/j38T95FfzOxd7BnQTURXWbqfjVd90bxR9c3dzqfupteOz6etm+ySVUyfjo3/67Og3f+o/rf44n7y/WrPB2fT7b6dnKpdnDC9md8vl4upC59eMwUfRayd7IwDBS49yP4wWb24mD7c7y+En06bTqsqp//O/H8lX82lVj1McDcbT7xcvzpLD8sRgeH59J4n8+rOd/cLR4GHU8I4B3UVUha2fZuf3Vj3P8NNnu12vooYQmvG//v5v5RMlp87+ZvV1iLT6bTSK1/iDTye7OXXlwceTy51eW9FjzwD65252Hg8s3vvk2R8+yu8s1fBkQ9KcqnrL5tPqIhqtCn3vg/PP8nu8we8mz/5LMpi6pcn9ArqNqApLPy2iD3XPI4bjS33OZ3k3/yo5LX5073z2U/xqS3/9lxfyaWlOVV++06oeRVaykxxuN4dJsr96u5h+ovrrwXjKJACgl5Kj3BXpH75Izvjfzl9cJOOOw/PZXfxDW1s5VX01mlbTQWIlM4fh7uvJxjmlzK+Wr5MzUQ/G0+9WPwHKEFVhKZmrJF3v6PJma/rR3fW5OtRuYqggN6eqL59pNZltJu6PJl9v7FX0GEPer5LB56ZSO4CWWR/l7vQPcmw/u4iPZps58ZKbU9VXc2k1mQq1KvXDyU32GDwzhLH9q/WJuKZCOTqPqAo7yVylPbMw0xNetgGtIKeqL19pNe2C1TSsDWmKzRk6Xc/o/Vb/BECfrPuH3GmazR3NFuRU9dVQWk0Hid87n32vf6alKXZ36DQ7YZfDdhghqsKOTmA5uS2WBDu73rc0p6ovL2k1GUXOieZbdwbYkOyGmJ4F9FPaP+wGO0UnP8uoWppT1VcDaTUZJM5L3pt3BtiQjF80OisX3UZUhZWyBNbAqKphTlVfztNq5orXnSmnBb1z5qYBt3TPQA+VRbQmRlUNc6r6skyrySBx3pTTZAgjZzJDURcK5COqwkbZoGk6PWAULfSPYnfzaXqPvc3b722plFPVl9u0mlzxmnMeP1nZvMrQKTbbOy8Xsyi5BaHsvtzdVRFAAEoGTZPkt923ZDuKws6yWk5VXxZpNZ0KlXMeP1mXvNmoOsVmA272GtzBcDyZcv9pbCKqwkYyjriVRBNJh7V5bL19cajYN3+gTlSVr/FvHUXVolP8SYo1GmNYvo5ybuzl4K6KAIKgO4F9s9XTyZ3ZvmWZd6fq/PkDkjUlcXqMqgUnkZIUm3MSabcLTa8ny9o3RwI9RVSFhXTQNPeU1vKb6KGKpNnOV/fIg9Fn16tYJsfTUfy8ln1TCCpPAPhPv3E3AaDgPH5Rit0ZY1C9/PH48joZIVH7pL2RHUCr5R+3J9bHrtm+VHewx+PoJu4WbufR2SrV7ZlCUDWtWuTUtGx1p0KlY8vqcwajC90Xlqwj+omoCgvJtPq8a4zevo70Pa43+jLdMWWjngp5RbdoCeayquSK15xR5IKJaDsBN6637S5e1QwdNNBB6aFs3kVI66P6jXMycbrd6hhVCtx7YG+eVq1yqiiYCqUn3eZ16TsBt8Y6ooeIqqgvuQwgFs8w0iOCd/MX6SzMrRQbz1I93kxpeb3VttK06uPy/53z+Gs1xxgyckI8gG5IDmVXstMxNx6VYvCs0bgzKewlTNKqbU41OolU8XKrtfJ1RN8QVVFbeirnd+e/f2+1kOP4bFr6nGc1/lp+DF2QVn3k1HU0z+uCC8YYjHrnPUOtADogOZS9N/709/mPXDaYqr5cXK+eaVU+Tag4rVrnVJEk75xAWXC5VVHA1ZaL2eV4aLCO6BWiKmpLBgtH0SLnSinpxdLpRwX0dQMGwwkruWnVT05dR/OKXXDRGMOayuvFrwHQTvp4VQ5lv8m7Uiqdu59rPXlg9Ziri6vSXlXsS6tN5FQpkU7eeVOhCk4iFcz1z3zmxiR+YIWoirp0z5IMFm7ce8nw1ktvF9efrd5S5cr3rbTqK6eKel1w0S1dEsk1VWcv6KCB7kmOV/Wh7EZnORxPvtx/A6qVTFTdeUhpgd202kxOFTWnQhXM9V+/MWaayNETRFXUVXBvJiP6Ss/B6PLmrlqflKZVjznVnWRcuXo9AGiDgps3mXu7mH2xullKlQ/JptXGcqprdzfRWIL9/YfRN3SIUIiqqKnsOVWFks6o9qGzSqt/9g45FUDgyp5TZUoNr1YbHUjTajtyqqJGbbkdChJEVdRTOOuo0HJxdbGa2Fp+xZVk0JOTkzdv3ujvN0la/fU7v9yXU588eXJ1daW/CZQaVx4Mx9GcnAp0VdE58UqKoqp0d6enp7lJVKXVfTlVOljpZsM64CeqYhNRFfVkrqnSPzGjLsAymHE1n8/ffffdR48eFQwD7Eux4vnz51K6KIr096FZvp6eWY0rA2iH9TVVuc+pyqPS7XZW+352/l7uiSzV3cnxuf5+h/Si+zpS+bl0s9LZHiKtqvC9c64/rjFuh4IUURW1JOME+55nvYfqassfmnd1dVXc85po5EPcUPXADVmA7kuuqcp7IP5e6rRV5lA2uVn17s1SpIuTT5e0qr+v7pBpVeX44VmUPPd/ubi+XE0P49mqWCOqopZ611Tp0YVdG+MEDUbMQNPq3noQteb+AghU3Wuqcu8AOLyYZSYLpRHz5cuX+kd1HS6tvl1MP0mfjpDgMB4biKrwJnt3wE2ZTtx+hGCLdOLS/8rH7jv/5d3+elghqgKIxc/2S2Lccfw8wHVOlUzZbLg8ZFpd3bwreWTX6PxZ+uBDIEZURUBUTr1q+nIo6Xml/5VeOJi0CgD1mUzlr+FwaRUoQlRFEKSLPD09lS7S/kxWLtIqgG5I5zW56M1IqwgQURWH56dzlA8/OTmRf6jgvgEAELKnT59KTpX/6u8dIK0iNERVHFiaID10i3TBAFpKuq/Hjx+7mCK1i64SQSGq4pCkH5TeUPpE6Rn1jxyjCwbQOv47LrpKhIOoioNR1+bve8KKO3TBAFokPaT332U9efKErhIHR1TFYRz8jqeO7jYAAA2SPkrlVM+H9CnSKg6OqIoDKH0MoB+kVQAhC6erJK3igIiq8C2ogEhaBRAm1Ts1+DwUG6RVHBBRFV4FGA3VuIXTm78AgLkfkvtMB9VVklZxKERVeJJezDSfz/WPgiH7A0mr0hHr7wHgQCQLBnvdp0qrnIaCZ0RV+BD+RfekVQAHJz2k9JMHvIiqVIBnxtB5RFU4l3a+gT8mSj1W+/Hjx8HuJAB0mDpgDr8LIq3CM6Iq3Ap/kCCrXaUF0BkenpjaINIqfCKqwiHpyFo3TklaBeCTdDVtTH6kVXhDVIUr0oVJRybdmf6+PSStSlQVgc9YANB2klOlq5HD4wCvNy1FWoUfRFU4EUWRdGHtvQNUuv+Q2Kp/BACNSs/htLefIa3CA6IqmteNzou0CsCdly9fdmOuEWkVrhFV0SQ16Ur63250W7I66kbcpFUADQrkialNIa3CKaIqGtPVYUh6YQANUl1KIE9MbQr9JNwhqqIZb9686fDpcnphAPbSEzWd7EzoJ+EIURUNkHgqnW8HJl0VoBcGYEP6yc5Pf6efhAtEVdjqQ05VpP+VXlj6Yv09AJjpTz9JWkXjiKqwkqa3zve/CmkVQFWq3+jPQ5vVRWOkVTSFqIr6+pnbSKsAzLXrialNUf0kaRWNIKqiJtX/RlGkv++T+Xz+7rvvnp6e9mSMBEAN0j/0+Ww4aRVNIaqijj73v0p/Zp4BqEF6BnURVRufmNoU0ioaQVRFNdL/qputvHz5Uv+or0irAHKlnYMs6B/1FWkV9oiqqCAdJ6D/VaQepELYIQFIdeaJqU1RabWfs8XQCKIqTKlYdnJyQizLIr4DSHXsialNUWmVakE9RFUYkRzGOME+pFUAQk3i79gTU5tCWkVtRFWUUxe8k1MLSM08fvxYaqnPl1AAvSU9QIefmNoU0irqIaqiBJ2LOTWmwr4K6BU1OYrzKibYoaAGoiqK0K1URVoFeoXJUVWxW0FVRFXsReqqRz0cgXoDOk+lrv48MbUppFVUQlRFPnKqDTpioPP6+cTUptBJwhxRFdt+4CErTaAjBrpKOkkO5u3RScIQURUb0pzK9QH26IiB7uFgvkF0kjBBVMWaxNOTkxPphcmpTVGXXJyenjKVDeiA9CIqOsmmkFZRiqgKLe2CCVXNomKBbuCJqY6QVlGMqIoV1QUz+OcIaRVoO56Y6hRpFQWIqqCP8OHNmzcSVU9OTjhvCLSOdI/SSUZRpL+HA2rEhD0RdhFV+046X+mCud+KBz9wyRrQNrLZ8sRUb9QJKNIqthBVe00NFdAFe0NaBVpEnQxhg/WJtIpdRNWeksxETj0IqfnHjx9LX/zy5Uv9IwDhUZlJoqoEVv0jeEFaxRaiah8xtndwHCcAIVMz+Hli6qGQVpFFVO0dcmogSKtAmNQMfnLSYaVplaMFEFX7RW38nNIKhNojPn/+XH8P4KAkFXEMGY50h0Va7Tmiao+w2QdInWdk/AY4uPSME09MDQe7LQiial9IJJINnqlXASKtAgcnkegkJgv6RwgDaRVE1V4gDAVOHUjwBwIOgiemBo602nNE1e57+vSp5FSesxI4+mLgIDiSbwV6yD4jqnac9L/SC0tfrL9HwOiLAc9UD8mRfCvQQ/YWUbWzZGNWt5onp7YIfTHgh2xiPDG1degh+4mo2k2yGcvGLJu0bNj6R2gJ9bfj8g7AHZ6Y2l6k1R4iqnYQvXDbcaQBuJNmHW4v3VKk1b4hqnYN23A3kFYBF9RFVNy2r+3Y0/UKUbVT2Hq7RP6IT548kT8oc+mARvDE1C5hf9cfRNXuUKMF9MIdwz0cAHvqwI9NqWNIqz1BVO0IcmqHsYsFbEiOUdNpeGJq90halT8uabXbiKpdoKLM8+fP9ffoHHXikrs/AlVJlOGJqd2mDkVIqx1GVG09htx6goFzoCqemNoTpNVuI6q2mGyT6hbW0h3rH6HTSKuAObaXXiGtdhhRta3UZik5lbNavSJ7X/mjy96X7hgooE43MWemV0irXUVUbSU1kZzZV/0kf3TOaQL7yHbBE1N7K02rPN+hS4iq7UNSAW0AyMWz+qDSKm2gS4iqLaOuEjg9PSWj9Jz0wicnJ6RVIJUewjGi1nOk1Y4hqrYJVwkgi+4YSKnukSemQqF77BKiams8f/6cnIotdMeA4Imp2EX32BlE1XZQV7NylQB20R2jz6T90z1iH7rHbiCqtgAdMUpJI5HumEaCXkmDCE9MxT6k1Q4gqgaNjhjmOKRBr0jyiB+Yyj37UIK02nZE1XCxdaEq0ip6giemohL2p61GVA2UGjCQTYu7rqASdfkdD+lBh8nBmDRyOTDT3wMGSKvtRVQNkWxIDBigNnbk6DB16oCDMdRAWm0pompwJGfIhsTdAWGDtIrukS6RJ6bCEmm1jYiqYSFhoClqMh/HPOgGnpiKppBWW4eoGhB1F+unT5/q7wE7zCRBN6Qtmbn7aEQ6Qk9abQWiaijUBCxObKFZpFW0nTrXJMGCNoxmyW6XtNoKRNXDk/6XnAp3pCPmbhJoKZ6YCqdIq61AVD0wyalMmoFrNDO0Ecfw8IC0Gj6i6oExXQZ+pGlVfw+E7fHjx9JcX758qb8HnFFplRkmwSKqHpiEVDYP+CEtjR0/2kL6Ro7h4Q1PLw8ZURUAAACBIqoCAAAgUERVAAAABIqoCgAAgEARVQEAABAooioAAAACRVQFAABAoIiqAAAACJSrqHoENE23rer0+4Hm6LZVnX4/0BzdtqrT7weao9tWoxxGVb0UjACLJCiVIZsiUcmGqChDtEYPqChDtEYPqChDjorkaj1paoYolSGbIlHJhqgoQ7RGD6goQ7RGD6goQ46K5Go9aWqGKJUhmyJRyYaoKEO0Rg+oKEO0Rg+oKEOOiuRqPWlqhiiVIZsiUcmGqChDtEYPqChDtEYPqChDjorkaj1paoYolSGbIlHJhqgoQ7RGD6goQ7RGD6goQ46K5Go9aWqGKJUhmyJRyYaoKEO0Rg+oKEO0Rg+oKEOOiuRqPWlqhiiVIZsiUcmGqChDtEYPqChDtEYPqChDjorkaj1paoYolSGbIlHJhqgoQ7RGD6goQ7RGD6goQ46K5Go9aWqGKJUhmyJRyYaoKEO0Rg+oKEO0Rg+oKEOOiuRqPWlqhiiVIZsiUcmGqChDtEYPqChDtEYPqChDjorkaj1paoYolSGbIlHJhqgoQ7RGD6goQ7RGD6goQ46K5Go9aWqGKJUhmyJRyYaoKEO0Rg+oKEO0Rg+oKEOOiuRqPWlqhiiVIZsiUcmGqChDtEYPqChDtEYPqChDjorkaj1paoYolSGbIlHJhqgoQ7RGD6goQ7RGD6goQ46K5Go9aWqGKJUhmyJRyYaoKEO0Rg+oKEO0Rg+oKEOOiuRqPWlqhiiVIZsiUcmGqChDtEYPqChDtEYPqChDjorkaj1paoYolSGbIlHJhqgoQ7RGD6goQ7RGD6goQ46K5Go9aWqGKJUhmyJRyYaoKEO0Rg+oKEO0Rg+oKEOOiuRqPWlqhiiVIZsiUcmGqChDtEYPqChDtEYPqChDjorkaj3rFXe5mH0ZfT4eDuTtsfuj8z9M57f613bk4/RSNW8Xs7+PJuOhKpEYjM6f/XF+t9S/tyOfp5eqcFpRQj5RLwXDpkj13htkJdMag2BTpHrvpTWaWtXUs8n4WJVIrAo1nd/pX9uSD9RLwbApUr330hpN0Rob4mo9qxf3dh6drRvZhvujydf2f1r5IL1k7u4myjSyDYOHk5sGtkz5JL1kynlFCfksvRQMmyJVf2+QlUxrDIZNkaq/l9ZoaHk3jzL5acNgdHnTRGqRj9JLwbApUvX30hoN0Rqb5Go9Kxb39mbyMP9Pqt1/GH1j+YeVT9FLhu6+nozuq38+3+Cj6PVb/eK65GP0khEfFSXkg/RSMGyKVPG9QVYyrTEkNkWq+F5ao6Hl3c3lqLCmBg+j19Y1JZ+jl4JhU6SK76U1GqI1NszVelYp7vJudpEcpW2cR1guri/TQ6XhxczuKEQ+Qy8Z+X52/p76lzfPI7xdzL5IDpUGw/Nry4NI+RS9VM5TRQn5GL0UDJsiVXlvmJVMawyLTZGqvJfWaOzu+jwZwdo4x7pczC7Tk8Lvnc++Vz+uTT5FLwXDpkhV3ktrNEZrbJqr9axQ3PUf9fhsunuYkTbE4fnMqrHJR+ilcpltcvjJdLFzQJaW+d757Cf9s3rkM/RSKV8VJeRT9FIwbIpU4b0hVjKtkdZIayyWVsVgePZisV1T6zJbF4rWKGiNxWiNzXO1nsbFXd5Oz+KmtPe4ZzmfxMdr90bRt/pHtRgXSXw3HT9Y/Zt7j3t+nE/ej1/wYbSwamzyEXqphL+KEsal8semSMbvDbOSaY20RlpjodvpOK6pvUN6y5vJcfyKUbTQP6pJPkMvBcOmSMbvpTXSGo04KpKr9TQubtLUBmfT27w/qlhEo9UrbDcA4yKtm9pgPNVnOLb9tIg+XL3C3wbgr6KEcan8sSmS8XuDrGRaI62R1lgkTVEPxtPv9M+2fRuN7q1eQjjYZPxeWiOt0YijIrlaT9Pi/jQ7j/9k+5taYxuAaZHWhSpoat43AI8VJUxL5ZFNkUzfG2Ql0xpNS+WRTZFM30trNK3ku9l5fEK1IEURDvYwfS+tkdZoxlGRXK2naXHLG3d6jFIwA+bt6+ijQVF7XTEtklHjTg4x9042iYt0PJnva6sJ+Qy9VMyiopaLWXSuL0YcjM6j2c7kmR3ySr0UDJsimb63fiW/jetYXYU6GI4n6QUHBeSleqmIRWu8m79Y/90vXjRWpIY22+U30cMHx5Ob3Na4fB09HLw/mf8oy6al8simSKbvrVPJ6U/yFHZH8nu9VMSqNU7Te16adUPyQr1UwmDHnwy/7XTYy7v5V8mWe390cdVcqfyxKZLpe+tv8kl72KA37X3kFXqpiOM99br/lC79C/k//fMSNq0xkd83SluVbSieZJFsQ7KgfxkMR0VytZ6mxS3fAJKmtvcY5e1i+kncAzbS+oXBBlBy3kEXqegANCEfopeK1ayo3FtmlF94KC/SS8GwKZLpe2tWctoCMwxu5iev0ktFarbG5eLFmb4GItXc391+s12+np5Jn5t/eKkLn7zXtFQe2RTJ9L11KjmdmZejuDuSF+ilInX7xpzbCe2d8piSF+mlEqXhIE1RW+1td8ttsFT+2BTJ9L21N/mkPWzY1y0k5CV6qYjDPXVe/3mUc9lWjtqtMZHfN+bvyuV/+vfBcFQkV+tpWly9AchRTe7gyvpauT1NLXMBYDOtX6QbwL7sm17fl9fUlovrC9Wi9jTETfI6vVSsXkXp6dvH4+gm7n+TuzeXDffKS/RSMGyKZPreepWsesPB6OJajciYHqjI5+ilIrVa4+qgXJLB/dH5V/GtW94urj9bNcqm/u52m+1ycXWhgkvONpsUNfNeWY7/PyA2RTJ9r23fmFAxMff66Az5HL1UpF7fqAP0YPTZ9aoM6a3RmxpcSMLBvuadXga+0d6Sff9gdP4ivpeQqqjG9iP+2BTJ9L11W2N8rZXRrjBLPkcvFXG2p077Tz3Kvtpvyuv2rPuWeq1R29s36l35RpFUhRd36f5JkfRSo1xtdabFTSab5F0rlz2MyB0QUi+4P/r0E3lZQ8lgJZ2Wk3eEnbkH8naZb+NTXPqXpR2xIq/TS8VqVVTcTWx1LurYt6mdhD82RTJ9b51KVofIm52d6lYa2ufVaI3q7775ehUXGvq7195ss2eBxUZvvnF6S9Y3bbfyTfz/AbEpkul7a1dylhqhMbgFunyQXipUozXmbQ5qq9mXezT5GL1UIpkdmFsV6wHdzTLrOJK971LetrxDPkgvBcOmSKbvrdka426nrCfcJR+klwrVaY0rxXtq3Tg3W8vN6oVlh/qxWq1RFPWN+u4KmyFHD2ObxAyfpEh6qVGutjrj4qbHPZvzlzb/bLnPdYhns63uW/ZaesKyXk/I5+ilUusbyN2PC6V6+a1d6dZjOdJR/cFw/FeryU9m26e8QS+VqF9Rm+L23VCK8smmSMbvrVHJ+6NqWb8mH6WXilVujbmptNndcL3WmJwiPDoef/6p7Ns2et70ROFw/Plqiti6qPIztRAOmyIZv9d+k1eT+AuzbEI+Si8Vq9E3qt/lDLY1FVXXQ3qbNbWZSDbzut73l3eY2+ST9FIwbIpk/N5arTHuCeX1z/RrVpM+kzZTRF6ql4q52FPnDzR8F7/DZJ9epzWW9I16jT7Y7L31yQqiqhXz4saJc/Un2if3ablqKkm8YRjtg4V8lF4qp7r4ArsPO5Z28/F4Eq2upzFLKop8ll4qU6+iNuhTHrnHoBvk0/RSMGyKZP7eOpUcZ6zk5Oaq744n45c/YFA+TS+VqNoacwfOVb/W2IhRnYqS7eLh2SRaPU5mN6ks55cPx5/L9nO3E7Xl09RCOGyKZP5ey00+fnv5xq7Ip+mlEjX6xl3qQxoa4xd6iHS/7bnjyebw4v8mTw9KZ8uUkJfqpWDYFMn8vTVaozoe2FY2F0XIq/RSieb31Hnjl/LTeFTVbPipemtcfX5B35gv+VdMYoZPUiS91ChXW12V4mZPH2zZ033Eo+jJhrG9Y9tHPk4vGdn/sGM5VFJzm/ZR2WWrre8hn6eXylWvKC09joxfyVWuRWpUshzyqrl3qXRycBF5nV4qV6k15kVVPfzQWFS1aI2i+PBye+BfPlEthMOmSFXea1HJak+Wc7o2n3yiXipn0Teu6JUqHdGUz9NLJtanVrfl3P5CZZSj4WiUDgiuFEd/RV6ml4JhU6Qq763aGtWu+Xh1QxT1q7ubaDXY2egp0Ib31MkxzFbXVGECQKxSa9xgOPSm1nr1TxiWyBspkl5qlKutrnJx7+bT6PPM/l7ad3zcs0s1grQLNh7ClA/VS6YkgvwxypzdOBpKodJHDO9jOsqryKfqJUPmFbWWiaoGV6YLeaFeCoZNkSq/t0Il53XfBsMGQl6ol4yYt0b9585cxZLejqe5cSylTmsU22F0w87+Qz5XLwXDpkiV31trk4/PQpYP7afkc/WSkXp9o0gum2tyaC11KzWVOfM7GOpx+m3paF+aG5LLWcr7bXmXXgqGTZEqv7fmJp9Q83yamhylNbinzj0ltSq2fKrh8FPCtDVuKuwblfTs6NkL+Vz9w2A4KpKr9XRVg+oqgWw3ZzyE6euPajrKq3hsam8Xsy9WXYzBWYyObQDuVkefFFsfvpteay8cVvL2GajBcPTBqh8v+9PLS/SSU4WHl7vnvzyVqgqbIvlYHdUAzAeBPFWyvmzZZPBSuCuSjqqbQ875Z353eKmoamyK5Ht11LYfREeUt6fO75pWoVaKVH5S3l7p0JsemdYTGzrWGgu4Wk9HxU2PhvM0PWJUk8FRUYavUimmI75+S2XEpkjOVkd1dnkXvRocq7it5PX9q4/Hl//75kU8zhrIbrjo8DKniXoqVRU2RXK/OpWHVIXzUqW7WIMJSIqzIqk2tnMa2mzUg9ZoxewsqJdS5e2p84ununQvFzAV9o16ptn6xohda40FXK2nm+KqLmaPNowY7fJUKo2o2ij1t95ueGFE1Sw9yBrK33133DQjp/ZojRVVO1pWnJYqOb2evTNUOWdFyo+qhc1yjdZoI6Ch69w9de4Pk/sMGO7TbexvhPkzZzrWGgu4Wk9fNVihU/ZTJMP+LuWqVPmJWd1wJKQUZcymSG4reav5qX7NoE26KdXu0UjySB6Dwycvf/fCKJ/Xbr2UqhqbIjlfndXAjOmF/ymHpVJXF5jNks9yV6S8Xpq+sVl5m7k+Zi6/e5qHSt6zp44TxUb/oxrGaj5VWfdpb1/fmFyJuDNzpmOtsYCr9fRUg/mBLJ+XIpkOW6aclUo1+szptuSMsMmtBDu2ATiv5OTq1+Xi+tLsElfhqlTqFJK+pup2/kI9kqXRm2taKTy8zDv/5aVU1dgUyfHqqC6oPHJtcVYqtac3an5bHFaU2nEcJXfqoG9snh66Tm+kmvSNgVTyvj21uvtVst9Mn2g1vHBfJLGnb1TDH3l38/BSqmocFcnVenqqQbPZRYqXIhWOGOVxWKrc+2WY3bxGXqiXgmFTJIers74H9ZpJXyzklXqpYeubdSdMbnW5Ii/VS+4UHl7mDnX4KFVFNkVyvDp1zv4LV6WKu+g8hx2/9HbjDh9siuRwdbYv7oyFUsn799S7XXpcZvl//QJ38vtGlarzHE/kP/pVwXBUJFfr6aUGqw1heilS5f2E21LdZR8lcry+v10ZebVeCoZNkdyuzvoCJkmp2ceTlHBYquUiubF5pRJ5+bsXHV7mb9E+SlWRTZHcrk6Vo/csN6Xav5c92AyZVPYmbvczzzoq4bhUddgUye3qZHdA0hM9M7md2YrbUq0U7aml+4x0l75uGO6LtG/jjYuaR14p/9WvCoajIrlaz/7UoCVKZcimSFSyISrKEK3RAyrKEK3RAyrKkKMiuVpPmpohSmXIpkhUsiEqyhCt0QMqyhCt0QMqypCjIrlaT5qaIUplyKZIVLIhKsoQrdEDKsoQrdEDKsqQoyK5Wk+amiFKZcimSFSyISrKEK3RAyrKEK3RAyrKkKMiuVpPmpohSmXIpkhUsiEqyhCt0QMqyhCt0QMqypCjIrlaT5qaIUplyKZIVLIhKsoQrdEDKsoQrdEDKsqQoyK5Wk+amiFKZcimSFSyISrKEK3RAyrKEK3RAyrKkKMiuVpPKS7QLN22qtPvB5qj21Z1+v1Ac3Tbqk6/H2iObluNchVVAQAAAEtEVQAAAASKqAoAAIBAEVUBAAAQKKIqAAAAAkVUBQAAQKCIqgAAAAgUURUAAACBIqoCAAAgUERVAAAABIqoCgAAgEARVQEAABAooioAAAACRVQFAABAoIiqAAAACBRRFQAAAIEiqgIAACBQRFUAAAAEiqgKAACAQBFVAQAAECiiKgAAAAJFVAUAAECgiKoAAAAIFFEVAAAAgSKqAgAAIFBEVQAAAASKqAoAAIBAEVUBAAAQKKIqAAAAAkVUBQAAQKCIqgAAAAgUURUAAACBIqoCAAAgUERVAAAABOnnn/8/Zy70/14j24EAAAAASUVORK5CYII=)\n",
        "\n",
        "\n",
        "It is like the Object **O<sub>1</sub>** or **O<sub>2</sub>** or also the Pivot **p<sub>1</sub>** present in this example of VPT."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "x3ahzw9LTmiZ"
      },
      "outputs": [],
      "source": [
        "class Object:\n",
        "  ''' Class containing information about an Image\n",
        "      Attributes:\n",
        "        - features (dtype): vector of features of 1024\n",
        "        - id (string): id of the image\n",
        "  '''\n",
        "  def __init__(self, features, id):\n",
        "    self.features = features\n",
        "    self.id = id\n",
        "\n",
        "  def __str__(self):\n",
        "    return (f\"Object-> Path:{self.id} Features:{self.features}\")\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "c_iraWZOWnWV"
      },
      "source": [
        "The **Node** is the data structure that will act as the building block for the tree, we differentiate as *intern node* and *leaf node*:\n",
        "* **Intern Node** has the Pivot (that is an Object) and the Median that is the distance that allow to split the received Objects in 2 set of equal number of objects\n",
        "* **Leaf Node** has a list of Objects, the number is parameterizable (in figure above we have 4)\n",
        "\n",
        "![Immagine.png](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAXgAAAE4CAIAAADep3+dAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAAFiUAABYlAUlSJPAAACO0SURBVHhe7Z1faBxJfsf1GMg9GIPFyQRfnJVOliJr7Cz2+mLjs0HYshWQ43DGjmx5WUZcTPDYu0GSDYvl9UU4WMkIofNDzpJY2QR2FSZ3JhA8C87mgu/hQKCHPCx6O06HXw5xLAYdx2I2X82vpnfc8697pqunuur7oRDqnpmWprrqU7/6091tXxNCiGYoGkKIdigaQoh2KBpCiHYoGkKIdigaQoh2KBpCiHYoGkKIdigaQoh2KBpCiHYoGkKIdigaQoh2KBpCiHYoGkKIdigaQoh2KBpCiHYoGkKIdigaQoh2KBpCiHYoGkKIdigaQoh2KBpCiHYoGkKIdigaQoh2KBpCiHYoGkKIdigaQoh2KBpCiHYoGkKIdigaQoh2KBpCiHYoGkKIdigaV1hfX19aWrieGTs9eBwJv2RnH6ytramXidlsbW29ePHi7kcf4sT1p7pHLp/HL7lcbmNjQ73DbCga+4Fizp4daGtrGxhqn7zXjTQ104Of5y7uxk5Ih7oxHAgFcsHJGknvwYm7P9+Hn5lbnYeP7sTO9z+4vrm5qd5qKhSN5aysfIKyCKc8fnrop59/z5ewcyyzF2+Ym5tVHyAmgUDmxs1rOEEwy6fP3vGdPqSHTw6i/dif6kK8oz5jJBSNzYhlEL/4SqcvoYXc1/ttusY0YJmrVy917duxsPK275T5krQWJruGorEW9JhQ+CARX6GsmLKP+vHmfD6vPkwMYGlpIYhlJME1iGuM7UNRNNZy9uwAuvS+4lgjIThHSUUrqj5PWoq0E2gAfKepRjp8dGd29oH6vGFQNHaytraGYlpxXKZa+vTZO2g/GdQYApQxMNTuO0e1E6JXnHQzgxqKxk5QTEOFM5IQfl8ZvaAOQVpKf2p7dsl3guomY5sKisZORi6fR1fIVwrrJhmpUYcgrWNjYyNsQCoJrcudqUl1FJNgqbITFNOHTw76SmHdhI9QNCYgAzS+sxMkoXW5nhlTRzEJlio7oWgSDUVDkkHqQG/d5TPliaIxBBFNxRV6tVPmVidFQ+IDHfWxzF5fKayb0B6eHjyuDkFax9bWFkQTam5b0sBQey6XU0cxCYrGTvL5fHfPrrBN4uGjO5eWFtQhSEu5evVS2Kbi8dND0JOZl1lSNHaCJnF/qivUxJPJqzAc5MWLFzgdAZcFSxpJ7zl7dkB93jAoGmuRC50CllRZrcfLnYziyugFdIUChqXSTqyvr6sPGwZFYzM3bl4LcrEMijIK9Mjl87z+wCjQCUod6EUHqq5rxDImtxMUjc3I5b/dPbtqzEBlH/VDRrBMUm6h5BTiGjQD1VoLOAgdZMMtAyga+1laWkBBPHx0J3TjLa7BL9hECcZLdz/6kLGMsWxubsotaUbSexC5iHHgF5zBzK1ONBL7U13mX6FG0TgBCitavNODx1FePfpT3dnZB8b26kkpa2trd6Ym1ZkrMnjmZC6XS0QjQdG4BQolzAI4u5RQcOLkDKrthEDREEK0Q9EQQrRD0RBCtEPREEK0Q9EQQrRD0RBCtEPREEK0Q9EQQrRD0RBCtEPREEK0Q9EQQrRD0RBCtEPREEK0Q9EQQrRD0RBCtEPREEK0Q9GQ6PFur1UO70zsJhQNaQQoY21tLVdgvEA6nVY3mAzMoUOH5LPz8/M4Tj6fx2F56z8roWhIfRCGvHjxQpwyPDysPNHWBrlgz/LyckE4uULIolCfLMO7EyWQY4Lp6WkcB95Rx21r8+yDt/HG6RZA0ZDKoIajnqPCq6pfqPxwisQd+io/pCaxEuzjSQ1Gg3cgJsY7CYWiId+ASl4qF1RvmAXVu4UDKzLcI96RkAf2Eekw0kkQFA3ZfpQHqq5XjSEX7DGzGkN5CKkgnYIJt1WITYY55kPRuEupX5JYY5P+/zsFReMcCAoQs0j9RC/Jgj4IvpFnHPlG6gViDBSNQ6AGouVHbUT/yMr2X2IcfEFIBzJlgGMOFI39oL7lcjlp8FEP121/Bi4CNGhUZqwQ4Fj/fRMBRWMzUIzXwsM1rk3TIMCRGTRIh/2p1kLR2ImnGNYxZoUJUDS2wXpVEWZLa6Fo7AE9I9al2pTqhmM3cULRWIIM9wIqpi7QjSz5Gx8fb+GiZ6egaBIPWma0z24O9zYD8k0m+5eXl5lvuqFoEgyqh7TM+IlWWu0lYUAAKJHg2tqa2kU0QNEklXw+j+qBWIY1pEm8sS36Wh8UTfJAZZDlIYz5I8TrgXKQSwcUTcJA/CKBDCdNfMC5yJxcCWGzCEeAuyW0ocGjhaJJDF6Ez0DGB0K87OwD5Aw4d3G3pMNHd2Lz9OBxGEe9LxheaEOVRwhFkww2NjbS6TTHLMtBTwdCgVbuz/f99PPvlabHTw9N3uvu7tl1ZfRCqGlseFxG2cNKilSDokkAMjMC0XCo0sfKyifQAWziU0xpgm4GhtpTB3rDLpnJ5/M4+Pj4OOPH5qFoTMfrLqltUgTBHXKmPJApT58+eweuGTxzMqwy4CbpRnFdX5NQNOaCWiHdJc6DlIPMQZAyltnrc0q1BNd07duxtLSgPh8Y/CGZ4+NZaAaKxlCkLQVsSyuCfk13zy7owyeUGgmxD3zRWPeTcWWTUDQmArnIoAxHB6oxcvl85lanTyV1E9wEQ6lDhERGnWEctU3CQNEYh1egaZlqIGeQRQ+fHPR5pG5CV+vO1KQ6SnhkERMbgAagaMyCzWYQ1tfXkUuh+k2SJu91X8+MqaM0BIPNxqBotkGhQUSNIoji64FN7IyzPIlluHajLiIan0SCpOZFA2T4jK4JBUWzPay4P9WF3jvi6uyjfgTkSPglc6uza98OvLSy8ol6q07wb6DycGojCC2MaAQoBqKha4Ljumjm5mZRZFH+qpVavIQ33Lh5TWuRkktsaJngILvQGPhOVt00kt5z96MP1SGag64JhdOigWUQs9QdU1xYeRtvg2vUx6JGeky0TChGLp8PvohGEtoSxK0R5jNdExx3RSPVO2CrCNfgzTpGT2iZxkCOhV1Hg+AUHeFopUDXBMRd0ZwePB6qSdRRTMUyDa/scBmciMEzJ9EV8p2maunx00MIS3UMt+E/4TxUXRwVjdRwFD5fcayRJPCOUAoyosmZ7IaRDAyybA/nbmCo/croBU0ukDnv8fFxtU3KcFQ02dkHwRtDLyECimqkRoomLdMk0mDgvNToQ6Hb29jV26HgCa2No6K5nhlDV8hXIuum+/N9/aludYgm8IJttU2aYG1tDSflyLGOqZkeX4gKxcBBMJHuSUOBHeEaOCoaFM0gtxfwpYdPDqIkqUM0Ckp8YfSQXfrIQE7Ozc3inOLswDhyhz30c7E5eOYk6r96n35kMRRvTlaOu6JBA+jzSN0UiWgQXSOc0RrGO8v6+nquCPzSkkzm+a0Iu04hEtx0evC4OkRDsMVzAYSrw8PDjFhLcVQ0S0sLA0PtPo/UTU2uK0UrB8ugsVXbxFKgGAQ109PTaps4KxqZGa27Jrg0PX56CB9puMOPwodWjjOgjiAFjAPDHo6KBqD3dO7ibp9NaiSEM4NnTqoPhwftG1o5htPugNAVruFgjeCuaKQjE3CkRu4C2fDYigzNoJVT28QNEMBysEZwVzRAFj7Udc3UTA/e1sB9rQUYDbEMh2YcZHNzE6eedxoGTosGiGvQh6o4XrOw8jZewhuauUZGVs2oDeIYiIIZzALXRQMQcVwv3Fvv8NGdmVudCHCQ8MvAUDt24qVmSgk76mR6epodKIpGARdACtCKl7DZpCAQOcMy7DS5A9okgDMOxgvAMjLb7XgHiqLRCMoZO012g6ZIhIIWpSLyGCl2oCgaXcjoj8tlywVkeVRBKRUojWIgI7xTbbgHRaMFRsvugLZEeeVNfMumHO9HUzRagGJ85YxYDE63yKWU8mXBsIyzpYKiiR5pu7j83BE2NjbeffddkYtHxV6S9LPcvDkWRRM9Mp2pNojVIEgRs6TTaflFqDY2JyN3Di53oGgiRnrsHAO2HshC5ILekESvXgdqvOals4VJKueuraVoIsbNYuQaXiCDcy0T2EB6Rtjp7amIm00RRRMl9pUhfJfs7AO5S6bHnanJhm+XkXTKA5lSkF21pxrhoKWlhb1/tkdyUhi5fB7msnuQmKKJEpvCGVSJGzevoRqcu7h7aqbnYeGR5Ej35/tG0tv15OzZAdea5YqBTEDgESgGnz18dOfYje1bpk/N9CI/S5/yjuOrd1sHRRMZNoUzaLdTB3oHhtorXmuK9PjpIbnc1JHQpnYgUxdY5urVS7CJd0t85B6Sl5+fPntnsvCUd0SLVoY2FE1kWBPOiGVQDeo+cFYeZmL9LZCbCWSAWObUX32n9GkwMDgO6PO4POUdfVX1SYugaKIBlRPlxo5w5sroBcQydS0jCa7pT3XbOr7QZCAjoMcEfZQ/FhUqL3+KoQjIvkVYFE00zM/Po0SqjSQjCz3QtPoqQLUEHx051jE3N6s+bxFNBjICPogjVHyImNy2sVxAmVudiCgtczdFEwFSmOwYrUA4gyDFV/RrJ1QYBDXq81YQSSAjIJw5fHSnL8e8tD0wXJbbcLc1xcmDookANH12LAVGK4oinn3U7yv6tZNUDGtmoCIJZDxODx6vca/YqZmezn3fKu+lokt1Z2pSHcIKKJoIgGXsmJiUiTNfoQ+SBobaLciBCAMZDxyt2swdEhQD0ZR3rOCmZh65YSAUTbPIPY2ab/pMoGHRnLu4O+miiTaQEWSKoHwUpjSh61T+LEMZElZHsQKKplmmC6iNhOOmaHQEMoIM3tUeWcer5e+haMgbSEmyZiGJiKZ8yKBuOnKsI6Gi0RHIlIIj1+g6SZK74pfuQddp5PJ5dQgroGiaAg0gmkG1YQWoGGEHg9E1wKcSNxisL5ApBb7wSaQ8yZBw6Z6R9B7Llu1RNE2BkmrZfYzuTE2WLo0PktD8pg70qs8nBN2BjAf+EMI9X475kpja87tsWrbemqJpHOk3Ja4lr430nupG+15CP6tr345mHrAXM/EEMh5SSGrMcEsaGGr3FtQ0+ZR3M6FoGgfF1Mo76b3/wXU0wgFHahD+oFYkZRlrbIFMKbAw/mLtIWGv9yTLhe27fIyiaRz7+k0CrHF68Dja2NrzsjARGuG+/rcQI6hPGkzMgYyPGzevIe6r4RrpLmUmO/Gz4ae8mwxF0yASEtt64TK+3ZXRC6W3NfAl9K0OH93Zn+pOhGVaEsiUAnffmZrEP4A+VMVQEaLp7P4W3mClZQBF0yAvXrywbL7JB+qG3KgJ3ajMrU4YB3LJPupHVYFisB89rJZU2lC0NpDxgX8gdaC3u2cXIkHvXmLbM9mFG4kd/Iu+EydOqLdaB0XTIDat06sBVILqcT0z5t3NE79DQLYFMl8+n+jAGztOLX7x+uvXr9Y///eZ0e0d2DU6k1t9+Vq97w8vV/9zceJU4ZXCa5+tv1IvBQL6RhOF6AadUznGyOXz2dkH2Iksxab57m4MiqZBTGghSTXCBjKv1xcL8nh74vlvXj6/e2L791KGZlZ/9/Xrl7/MKvuU0Pde7ldFDTWLxYWKomkEuxufpBN+ROarl7kfFj7xtzOLt8sss03HBz/599vFQMbHqcX1iEwzPz9va5hM0TQCmh0+Is5AGh2R+e3zie0LjhQnJhZ/Jp2l16+++PiNGOablxDffHb7ROG1jtvPv4zGNBYP/FE0jYBmx80Hm5pM41NLr79YPKV00jH68RevSq3x69zoW1VeerU6U4h+3ppZ/UrtahL82zheIsa/wkLRNAKaHctugJZoGg1kirzMjW4LAwFLdvUNlZQ4qELYUoyDRnMv1Z4IsHWYhqIJjcXNThJpeo3M6y+f3y64pNKw7huzUW/y1erMdqxT6aUmsDVYpmhCg1gG5UttkNbRbCCj+P364g9wkEoxi+egHyyu/17tK1IyUfVbtSsK4E18KbVhEawwoVleXkbjqTZIi2g6kPEojsJU6AEVHVRhFKbooDf1VLBPUzGOXNSqNiyCogkNSnbt5ysTrUQUyBSp0TkqOqhj4vmXao9HcYDmjbltsU9TMc5W4f7wlt0SAFA0oeFIcAuJLpBR1OoB1XBQcZA4uhmnb7ByPJiiCYetDY75RBzIKLylej/MvfQbQ432xjhAI1gZMlM04bC1C204kQcyRSr2gITwg8SFCKhSPysc+LL4mmrDFlhnwoG2FC2q2iD60RPIFCkGLZXsUGOQuLKemh8JFvA17Vt3TtGEw8rWxli0BTKKYg/ordHcr9UujwADNG/qKYKRYMHKqJmiCQcvPogHvYGMokoPqECtURi1ktinJ+lqVThUWKBUHB05oLatgKIJB5pWNLNqg+hBdyCjh0J/KqILLPHdLZtwoGjCgQaWc9v6iCWQ0UNEI8GCfcWMogmHfU2NbuCOH927uxXgMQnJDGQUUY0EC/YFzhRNOCiaUMAyB/t7kGnvXrlUwzUJDmQUkY0ECxSN08h0QJDGmQCxzLljbf9xr+3P9/5xNdckOpApEtlIsGDfrfYomhBYOe+oCbHMxMW2X/y4bfVf2/7rnyq4JvmBjEeUI8EA8oV21YYVsNqEgKIJiGcZKMZLPtdYEcgUiXQkGFA0TkPRBKGiZSSJa37wN8PvvvsucjL5gYwuKBqnwennPclrA8sc2P/dipaR9OHlQhjT1vb+++8nPpDRBvxrWUmjaEJgXzsTLbBMf8+eapZBOHPu2LZivvsnbd/59h/VnodyHPtiZ4omBBRNDWpb5sHfbSsGjJ5qe56tPDZMPCgap6FoqlHDMtCKBDK9f9r24xvf7Idr/vr7u+iailA0TkPRVOMfbl5HxYA7PI946Rc/bvt+SgUyvpfgHcDx4HIoGqehaKqBqASxCXpDFV1TrhikxYlty/zv/zxXhyAlUDROQ9HUoLZrfImWqQ1F4zQUTW0CuoaWqQtF4zT5fD5t48O9IqSua2iZIHAdjdPY187ooIZrxDK8oU9d7IudWW1CQNEEpKJraJngUDROQ9EEB67JPviR5xpaJhQUjdOIaFCF1Daph7hm4iItEw7ej8Z1UGGgG7VBAgDX0DJhQTiDoEZtWAFFEw6KpgGYY2GhaFzHvtvTx07xUbPymMfXL1c/njixvd3WdmJi8WerL6O5R12y4VMQXMe+piZ2is+THc29fPV/i6N9Bcd4dJy4/Rldg4ywLAykaMLBJ1U2S/Fx12/d/7dP3vNZRojsoSUJZZNPqiT2zTvGjXqerHBq4uNfqvjl1fpnM6OFB9RCQjOrXxV2OolMbqoNW6BowpHP59F/VhskNK+Lj7tG4PLe4he+m3n/bnVmqPBaZM8tSSL2XX8AKJpwWNnaxEhxJLit773cr8r7R8V+1YmZ1Vdql3ssLy/bFzWzzoRja2sL9YDztY1SHAk+kV19VWkcRnWsnBYNLAPXqA1boGhC0/Kpx83NTfwDuSJJsp6KWKoO9zKiAVY+hYaiCU0LGxz4ZeTyeVTE7p5d5y7uRhoYasdmf6p7bm42AU8vqROweB2rH+ZeOjoabGvITNGEBkFE/F1olL8bN6+hCI5l9i6svP3Tz7/npU+fvXN/vu/IsY79qS6zV3l5I8FVPPL6i8VThddlLZ8gO0v3WI2tg4AUTWhQmWMuCghVUgd6Ebz4FONLmVud+MdWVj5RHzMOL2CpOKn0h9/k/r6gmTc7VlE/bdZw0IxZeXM1iiY0Ma+nQixzZfQCLIPIxWeW8oTQBv/b2tqa+rBZFEeCK005vf5N7j2Z947uUflJxNYVoRRNI8Q5XIcIpbtn1+Onh3xOqZYQ1/Snuk28l0VxpLfAqYnF5+tq4unL9c+yxbV6lae93cHKkWBA0TRCbM0OfLE/1TV5r9tnkxoJgU/Xvh2IwNUhjOH1+uKpbZX85cTMbXUVpZ/yC50KQZAzMQ7CZOSCZRcfCBRNI8S2dlPGg4J0mkoTgprTg8fVIUyhdCR484tF1U8qoW80+8J/OaVjI8EoV7auO6doGkFanhimk7OzD0bSe3weqZsePjkYz78XhjfvDvH1H16u5mbUpdsdJyZ+Uvn+EI6NBCNSBmrDLiiaBomnL309Mxaq3+QlVF/D1mL8OjdaWKsXxhqF3lZMF3Oj8UCOtbbbYusADaBoGiSexsce0dRbE1wJ6W29PfH8t2qHBtA5vTM1if+slBs3r8W/Iim2MLklUDQNEs9qGmtEUxwJDmUNvSPBqNhnzw7gfxrL7M0+6pd5PfzE79iD/YNnTsaZh7lczr6Ltj0omgaRpeK6V6zMzc2eu7i71CBBkozRmDTDXW9NcEV0jgRLO4G8rbZuAPtH0nvwnthCm3Q6bd+1lB4UTeOgZOie5Jb60MCs08jl8+oQRlAcCQ51RyttI8HSSUHY4su38iShTQwLIGUVqKkrLSOAommceCYjUwd6w66j6e7ZZdiYokEjwQj00CcKPpcH18SwANLiiW2BommceFohFEH8ldpXOZUmVCFUJJP6TY2hayQ4l8tBxMGDRFkAqfsKshii49ZC0TRFPOXjxs1rKOtBXCOhvmET242hayT49OBxdC19+VY7IaJEXKk+rwHr+02AommKeCJehCdXr16Ca7KP+n11wEtoeGMevEwiUqWDh4eSHj89pFXf1vebAEXTFFBAPHUbf+juRx/ib527uPv+fF9p5I9qgyYa3YEDB/usiGU0gvxBHnpZFzwdOdahb9hreHjY4vkmgaJplnhW7gmoJ6IbH+gO5HK55I/LaAe5NDDU7pNIkAS/a7pOVdzX2hXJMUDRNAu61igoMS/oROkEiKTwM+Y/nWgQlSA28UkkSNInmvn5eSvvdOWDookAhL6aSiGJFngZrYJPIkESPqWjgxxb17vlUDQRAMtYP5hnB1Kxa4ypV0wLK9s3BtQROcowsAt9XoomAmQug9M9ieDGzWtB1gSXJrx/8MxJ9flIcWEYWKBoosGRnrYFyJjawycHfTapliSc0dGK4JiaAiUDoWiiQS6fWefschJAUHPkWEeQxcF4z8BQ+9Wrl9QnI2V8fNzu1cClUDSRgXIT//OeSANsbW2dHjwOg1S7dFuSWCZ1oFdH0CHD0u60TBRNZLhWdBIN3HFl9ELXvh1TMz0+v0i6P9+HVwfPnNS0wsW1ZomiiRLXSk+iQVyztLSAtgFCGcvsnbzXnX3Uj5/4HXuwf25uVtN8kINtEkUTJQxqEgdCm3w+f2dqUh5qjp83bl7DHq1jtA42SBRNxDhYhkgo3GyNKJqIYVBDapNOpx1siiia6Jmenrb4LtOkGZxaO1MKRRM9KEYoTPruKkASytbWFlogd9bOlELRaEGufnLhGhYSHJdLBUWjBRQmFCk32y5SEcfjXIpGF9Ib56gwEcbHx12+Go6i0YjjZYt4sNWhaDSCaBkdKN4Ty3GkH+3I7SCqQdHoBX1yNGXW3xGW1ECWOzg+M0DRaIcdKJeR299wqI6i0Y50oByPnN2Ep96DookD6UCxWXMNCWa5nApQNDGBjjoaN5Y5d8jlchye86BoYgKKGR4edvBqOjdB9ArL8DIUD4omPuS+wpztth4Zmont+aWJgKKJFVm4tba2praJdSB0TRdgN7kUt0SDgBYBxY2b165nxpCWl5dR82MuEPPz82jurO+6I1eRt0tLC5LVd6YmkfMuDFg4cn7D4opoUOhPDx5HNDEw1C43iM3c6jx3cTf29Ke6V1Y+iVM3aO4sXsGF74X8RK4ib5HDyGe5ES9yHntwFiwO6GR6kRFrOfaLBuX+7kcf4vSjrJc/XuPTZ++gGnT37LoyeiG2Vgj/EkRjZXSNPBw8c7Jr3w7kavmDk5D/OAs4F9nZB/Z9d+kXcwC4IpaLBqX56tVLKPe1n0yICiBP8InNNfhDCLAtu48EvhTysO7zknAucEY0PZWtVVh5QiPEctEsLS2gTC+svO0r6+VJnhaGuCa2lhZFEw2gNUUT+YZYBnlYHsiUJ5wRRJE4O+rDCUcsw2mmGtgsGlnLkH3U7yvl1RLaYZT+OKefJdi2Y4n6ysoncHrtWKY0Tc304LtbsFpaLMNpptrYLJq7H3147uJuX/munSbvdSP4V5+PBXENfqrtZII61p/qRu758rN2wtnJzj5Qh0gm+OLbU9m0TD2sFQ1OPCrw/fk+X+GunRD241MxzxpY4Bq5RjlIp6k04ezgU+oQCYSWCY61opF+U9iijzQw1B7/4t2kuwY5FjZ4RBKtJ7T3RMuEwlrR5PP5rn07fCU7SBrL7L0zNamOEiOJds31zFjmVqcvJ4MkfOUkrjrZ3NxslWU2NjagZpAswVkrmsbaWKTJe92oNuoo8SKuSeI8FHIs7ACNpCPHOhK38KQlo7/QMdo/FI9SBs+cjHmtacNYKxoZNfAV6yAJepqbm1VHiZ2Eumb7IfnpPb6cDJLwZZPVdYrfMviLN25eQ0Yhh+/P98laDfQ6Hz45iCgSYfv+VJf5srZWNDg9ODfBZ1u91PI2Fq6RRRkJio0RPx4+utOXk3UT6gzOEc6UOorxoPXCqRkfH4/TMrIGstpaMBgHsSSysYWtYxCsFQ3AGQobz6OVMKHo4x9I1tIM0XqQhZGlCWfn9OBxdQjjiT/YFMuMZfbWndPIPuo33DU2i0aWkIWaeEK/6croBfX5loJCBtFANy23XkDOnh0I1XvCecHZwTlSnzcb+AU1OebpSBRFxDK+fKuWZK2AsSPrNosG4UB/avu6Yd8pqZbkVJkzZID/H1E6XJOIqSgZFAu+DhvnBWfH/JAN/6EYP+azIAFUqL4/RA/dq88bhs2iAVL6gyzbk6tvDAw+l5eX8RUScZkCcg9BSpAOlAwrGNv8ekgfdnh4OP648urVS8HbSEmwEnLVzBDYctGAn//8v5H7tTu6ct2NscvhZXgY7erm5qbaZSr//C//uK/328hPXw57CWcB5wK5bX6Yli/cXCbOoV8P/MXtAhk4PPRSS5abBsF+0QC0nIjS0diiIS1tb9ECINg5fHQnTqrhgwXekI35UcDS0gLyE7mKvC2N/JHzMh2bOtBr+LdAPZ+ensa3aFWlRf8dfz3U8KIk5HCrVoHVxgnRABQdqERuslcKBIRAxvxIAeAryJAkfsbfxoYC+YlcRd5KJnsg/1F1Df/nUcmlu9TC0ToRjU8iQRKaUorGCBAa4Cx6qL3JAbFAy6tBcCSTBfNtDgPKiFjLFzEhuyga0mJQBySwR60wPDpIEKjb0LchnVM0hzi/DSw3HUnvacmVenWhaJKKF9qYP2pjOJ64jVqNjY5nkNlSX+rat8PMyxEomgSDWiGjNuPj44kYZjIQVEszfZ2dfRB8tZ4kWQhmZkmgaBIPYv50Oo0SZv44q1EYnm8yTBN8hvvTZ+8cPrrT2CUaFI0lSMsMzIycjQJtPmJA8yPB4LfWRxrL7N2f6jL261A09oBmGY0z6g86Aom4aiF+UA+ls4lYBiGD2msqOKHysKC6rpE1kCaP1lE0tuHVJeqmlIRmC1wjN6OZrPRAPqSHTw4ODLUjljH8S1E0duKrVy6P3WxsbCTdvAhUUwd68RVG0ntgHEmZW52yqP39D64b22PyoGhsRnQjYzcorOYXx2hBV0LGYtBRSnpwh6YCXyE7++B6ZsxLOKdmXkJZDkVjPzJ2g/YcVW56etr6dTfwaen3NX8sxgUoGodAkygtPCqhlQEOHCpL7xDBLS8vuxbBmQxF4xyofqiE0uCjT5HP55NeIeEX6SFKCJP0XpKVUDTuUlo/xThJ6fAD9AfL/3+Xx7wNh6IhyjgS4+AnfkdQYGaYs76+jk6fdAAB4hcLIjIXoGjINyCiQb31qrEnnRZGOghSfHKR/wpyZPySICgaUhmvekvfBOB31HDsxEv6gggcHGqTPy1BFkDPaHl52dg4i9SFoiH1QfVGBOGr/AC/e/YBeA80IVQMgiQ88UD0JB/EQYA6aAE5LN6At6kPkyRD0ZBGgEegANHE9PR0uSmCIJ4CiFZwHAQsOCY7RFZC0RAtIAjaDlrKUC8Tx6BoCCHaoWgIIdqhaAgh2qFoCCHaoWgIIdqhaAgh2qFoCCHaoWgIIdqhaAgh2qFoCCHaoWgIIdqhaAgh2qFoCCHaoWgIIdqhaAgh2qFoCCHaoWgIIdqhaAgh2qFoCCHaoWgIIdqhaAgh2qFoCCHaoWgIIdqhaAgh2qFoCCHaoWgIIdqhaAgh2qFoCCHaoWgIIdqhaAgh2qFoCCHaoWgIIdqhaAgh2qFoCCGa+frr/wclAmH0DY7m+AAAAABJRU5ErkJggg==)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Hrnq8f8DSZP-"
      },
      "outputs": [],
      "source": [
        "class Node:\n",
        "  ''' Generic Node in Vantage Point Tree Index.\n",
        "      Attributes:\n",
        "        - pivot (Object)\n",
        "        - is_leaf (Bool)\n",
        "        - right (Node): right child of the node\n",
        "        - left (Node): left child of the node\n",
        "        - median (Float): distance that divides objects in 2 set with equal cardinality\n",
        "        - Objects (List of Objects): objects that must be stored in leaf node\n",
        "      Methods:\n",
        "        - to_dict: serialize Tree in Pickle\n",
        "        - from_dict: recreates the Tree from Pickle\n",
        "  '''\n",
        "  \n",
        "  def __init__(self, is_leaf=False, **kwargs):\n",
        "    self.right = kwargs.get(\"right\", None)\n",
        "    self.left = kwargs.get(\"left\", None)\n",
        "    self.is_leaf = is_leaf\n",
        "    if is_leaf:\n",
        "      self.objects = kwargs.get(\"objects\", [])\n",
        "    else:\n",
        "      self.pivot = kwargs.get(\"pivot\", None)\n",
        "      self.median = kwargs.get(\"median\", None)\n",
        "\n",
        "\n",
        "  def __str__(self, level=0, side=\"ROOT\"):\n",
        "    if self.is_leaf:\n",
        "      ret = \"\"\n",
        "      for obj in self.objects:\n",
        "        ret += \"\\t\"*level+ side + \" \" + str(obj)+\"\\n\"\n",
        "      return ret\n",
        "    else:\n",
        "      ret = \"\\t\"*level+ \"Pivot \" + side + \" \" +str(self.pivot) +\"\\n\"\n",
        "      ret += self.left.__str__(level+1, \"left\")\n",
        "      ret += self.right.__str__(level+1, \"right\")\n",
        "      return ret\n",
        "\n",
        "\n",
        "  def to_dict(self):\n",
        "    if self.is_leaf:\n",
        "      objects = self.objects\n",
        "    else:\n",
        "      pivot = self.pivot\n",
        "      median = self.median\n",
        "\n",
        "    left = self.left\n",
        "    if left is not None:\n",
        "      left = left.to_dict()\n",
        "    right = self.right\n",
        "    if right is not None:\n",
        "      right = right.to_dict()\n",
        "    if self.is_leaf:\n",
        "      return {'objects':objects, 'left':left, 'right':right}\n",
        "    else:\n",
        "      return {'pivot':pivot, 'median': median, 'left':left, 'right':right}\n",
        "\n",
        "  @classmethod\n",
        "  def from_dict(cls, D):\n",
        "   left = D['left']\n",
        "   right = D['right']\n",
        "\n",
        "   if left is None and right is None:\n",
        "     objects = D['objects']\n",
        "   else:\n",
        "     pivot = D['pivot']\n",
        "     median = D['median']\n",
        "   \n",
        "   if left is not None:\n",
        "     left = cls.from_dict(left)\n",
        "\n",
        "   if right is not None:\n",
        "     right = cls.from_dict(right)\n",
        "\n",
        "   if left is None and right is None:\n",
        "     tmp_node = cls(is_leaf=True, objects=objects, left=left, right=right)\n",
        "   else:\n",
        "     tmp_node = cls(is_leaf=False, pivot=pivot, median=median, left=left, right=right)\n",
        "\n",
        "   return tmp_node\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "id": "lkHhNziEe5i3"
      },
      "outputs": [],
      "source": [
        "class VantagePointTree:\n",
        "  ''' Class Vantage Point Tree.\n",
        "      Attributes:\n",
        "        - root (Node)\n",
        "        - distance_measure (String): euclidean or manhattan\n",
        "        - size (Integer): total number of objects inside the tree\n",
        "        - mode_pivot_choice (String): random or outlier heuristic\n",
        "        - from_disk (Boolean): True if the tree is restored from disk\n",
        "      Methods:\n",
        "        - insert: methods to create the tree given the dataset\n",
        "        - search_kNN: search for the k-NN given a query\n",
        "  '''\n",
        "\n",
        "  def __init__(self, features=None, size=None, from_disk=False, root=None, distance_measure=\"euclidean\", mode_pivot_choice=\"Random\"):\n",
        "    self.root = Node()\n",
        "    self.distance_measure = distance_measure\n",
        "    self.size = size\n",
        "    self.mode_pivot_choice = mode_pivot_choice\n",
        "    print(f\"Distance measure: {distance_measure}\")\n",
        "    print(f\"Pivot choice: {mode_pivot_choice}\")\n",
        "    start_time = time.time()\n",
        "    if from_disk:\n",
        "      print(f\"Tree retrieved from disk\")\n",
        "      self.root = root\n",
        "    else:\n",
        "      print(f\"Vantage Point Tree index in construction...\")\n",
        "      self.insert(self.root, self.append_id(features))\n",
        "    end_time = time.time()\n",
        "    print(f\"Building time: {(end_time-start_time):.2f} sec\")\n",
        "\n",
        "  def __str__(self):\n",
        "    return str(self.root)\n",
        "\n",
        "  def append_id(self, features):\n",
        "    features_and_ids = []\n",
        "    for i in range(len(features)):\n",
        "      features_and_ids.append(Object(features[i],str(i)))\n",
        "    return features_and_ids\n",
        "        \n",
        "        \n",
        "  def outlier_heuristic(self,set):\n",
        "    # 1. Choose a random object\n",
        "    base_node = random.choice(set)\n",
        "    \n",
        "    # 2. Compute distances from this object to all others \n",
        "    distances = []\n",
        "    for x in set:\n",
        "      dist = self.compute_distance(base_node.features, x.features)\n",
        "      distances.append(dist)\n",
        "\n",
        "    tmp = list(zip(set,distances))\n",
        "    # use distance to sort objects\n",
        "    tmp.sort(key=lambda x: -x[1])\n",
        "\n",
        "    # 3. Pick the furthest object as pivot\n",
        "    return tmp[0][0]\n",
        "\n",
        "  def insert(self,node,set):\n",
        "      \"\"\" Recursive function that creates the VPT Index from a set of Objects.\n",
        "      Args:\n",
        "        - set (List of Object): the set of Object(s) from which create the VPT.\n",
        "      Returns:\n",
        "        - Doesn't return anything because It sets the Tree Data Structure in the\n",
        "          proper way.\n",
        "      \"\"\"\n",
        "      \n",
        "      if node.is_leaf:\n",
        "        node.objects = set\n",
        "        return\n",
        "      else:\n",
        "        node.objects = None\n",
        "\n",
        "      if self.mode_pivot_choice == \"Random\":\n",
        "        # randomly select Pivot\n",
        "        node.pivot = random.choice(set)\n",
        "      elif self.mode_pivot_choice == \"OutlierHeuristic\":\n",
        "        # select Pivot as the outlier in an heuristic fashion\n",
        "        node.pivot = self.outlier_heuristic(set)\n",
        "\n",
        "      # partition the set and find the median\n",
        "      set1, set2, median = self.partition_set_by_median(node.pivot,set)\n",
        "\n",
        "      # assign the medin to the current node\n",
        "      node.median = median\n",
        "\n",
        "      # set if the next Node will be Leaf or Internal Node according to the number\n",
        "      # of Object remaining in the set1 and set2\n",
        "      if len(set1) <= 4:\n",
        "        node.left = Node(is_leaf=True)\n",
        "      else:\n",
        "        node.left = Node(is_leaf=False)\n",
        "\n",
        "      if len(set2) <= 4:\n",
        "        node.right = Node(is_leaf=True)\n",
        "      else:\n",
        "        node.right = Node(is_leaf=False)\n",
        "\n",
        "      self.insert(node.left, set1)\n",
        "      self.insert(node.right, set2)\n",
        "  \n",
        "  def partition_set_by_median(self, pivot, set):\n",
        "    \"\"\" Partition in two set using the median.\n",
        "    Args:\n",
        "      - pivot (Object): the choosen Pivot.\n",
        "      - set (List of Object): the set of Object(s) to be partitioned.\n",
        "    Returns:\n",
        "      - set1 (List of Object): the Object(s) that are inside the ball with center\n",
        "                              the Pivot and radius the median.\n",
        "      - set1 (List of Object): the Object(s) that are outside the ball with center\n",
        "                              the Pivot and radius the median.\n",
        "      - median (Float): the median distance between Pivot and all the set of \n",
        "                        Object(s) that allows to split in 2 similar part the set.\n",
        "    \"\"\"\n",
        "\n",
        "    set1 = []\n",
        "    set2 = []\n",
        "    median = None\n",
        "\n",
        "    distances = []\n",
        "\n",
        "    # compute the distances between Pivot and all Object(s)\n",
        "    for x in set:\n",
        "      dist = self.compute_distance(pivot.features, x.features)\n",
        "      distances.append(dist)\n",
        "\n",
        "    # compute the median\n",
        "    median = np.percentile(distances, 50)\n",
        "    tmp = list(zip(set,distances))\n",
        "\n",
        "    # use the distance to sort the Object(s)\n",
        "    tmp.sort(key=lambda x: x[1])\n",
        "\n",
        "    # put in the right set all the Object(s) according to their distance wrt Pivot\n",
        "    for x in tmp:\n",
        "      if x[1] == 0:\n",
        "        continue\n",
        "      if x[1] <= median:\n",
        "        set1.append(x[0])\n",
        "      else:\n",
        "        set2.append(x[0])\n",
        "\n",
        "    return set1, set2, median\n",
        "\n",
        "\n",
        "  def search_kNN(self, query, k):\n",
        "    start_time = time.time()\n",
        "    # initialization of the vector containing the distances and the Objects\n",
        "    kNN = np.zeros(k)\n",
        "    dNN = np.zeros(k)\n",
        "    for i in range(k):\n",
        "      kNN[i] = None\n",
        "      dNN[i] = math.inf\n",
        "\n",
        "    distance_computations = 0\n",
        "    kNN, dNN, distance_computations = self.search_tree(self.root, kNN, dNN, query, distance_computations, k)\n",
        "\n",
        "    time_kNN = time.time() - start_time\n",
        "    return kNN, dNN, distance_computations, time_kNN\n",
        "\n",
        "  def search_leaf(self, node, kNN, dNN, query, distance_computations,k):\n",
        "    for obj in node.objects:\n",
        "      distance_query_obj = self.compute_distance(query.features, obj.features)\n",
        "      distance_computations = distance_computations + 1\n",
        "      if distance_query_obj < dNN[k-1]:\n",
        "        kNN, dNN = self.reorder_array(distance_query_obj, dNN, obj, kNN, k)\n",
        "        \n",
        "    return kNN, dNN, distance_computations\n",
        "\n",
        "  def search_tree(self, node, kNN, dNN, query, distance_computations, k):\n",
        "    \"\"\" Search in the VPT k Objects closest to the Query.\n",
        "    Args:\n",
        "      - Query (Object)\n",
        "      - k (Int)\n",
        "      - node (Node)\n",
        "      [...]\n",
        "    Returns:\n",
        "      - kNN (List of Object): current best k Nearest Neighbour wrt Query Object.\n",
        "      - dNN (List of Float): current best k Distances from Query to NNs.\n",
        "      - distance_computations (Int): Number of Distance Computations done so far.\n",
        "    \"\"\"\n",
        "    if not node.is_leaf:\n",
        "      distance_query_pivot = self.compute_distance(query.features, node.pivot.features)\n",
        "      distance_computations = distance_computations + 1\n",
        "\n",
        "      # if the distance is less than the greater distance found so far\n",
        "      if distance_query_pivot < dNN[k-1]:\n",
        "        kNN, dNN = self.reorder_array(distance_query_pivot, dNN, node.pivot, kNN, k)\n",
        "          \n",
        "      if distance_query_pivot - dNN[k-1] <= node.median:\n",
        "        kNN, dNN, distance_computations = self.search_tree(node.left, kNN, dNN, query,distance_computations,k)\n",
        "\n",
        "      if distance_query_pivot + dNN[k-1] >= node.median:\n",
        "        kNN, dNN, distance_computations = self.search_tree(node.right, kNN, dNN, query, distance_computations,k)\n",
        "      \n",
        "    else:\n",
        "      kNN, dNN, distance_computations = self.search_leaf(node, kNN, dNN, query, distance_computations,k)\n",
        "\n",
        "    return kNN, dNN, distance_computations\n",
        "\n",
        "\n",
        "  def reorder_array(self, distance, dNN, node, kNN, k):\n",
        "    \"\"\" Reorder the kNN, dNN using the new found Object.\n",
        "    Args:\n",
        "      - Distance (Int): Distance to be added in the dNN\n",
        "      - node (Node): Node to be added in the kNN\n",
        "      [...]\n",
        "    Returns:\n",
        "      - kNN (List of Object): ordered using also the added Object.\n",
        "      - dNN (List of Float): ordered using also the added Distance.\n",
        "    \"\"\"\n",
        "    # pair Distances with the respective Objects\n",
        "    tmp = list(zip(dNN,kNN))\n",
        "    tmp.append((distance,node))\n",
        "    # sort using as key the distances\n",
        "    tmp.sort(key=lambda x: x[0])\n",
        "    # cut off the farthest object from query\n",
        "    tmp = tmp[0:k]\n",
        "    res = list(zip(*tmp))\n",
        "    dNN = res[0]\n",
        "    kNN = res[1]\n",
        "    return kNN, dNN\n",
        "\n",
        "  def compute_distance(self, features1, features2):\n",
        "    if self.distance_measure == \"manhattan\":\n",
        "      return np.sum(abs(features1-features2))\n",
        "    else:\n",
        "      # Euclidean distance\n",
        "      return np.sqrt(np.sum(np.square(features1-features2)))\n",
        "\n",
        "  def save_on_disk(self, tree_file_name):\n",
        "    dict_tree = Node.to_dict(self.root)\n",
        "    with open(tree_file_name, 'wb') as f:\n",
        "      pickle.dump(dict_tree, f)\n",
        "    return\n",
        "  "
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [],
      "name": "vpt_index.ipynb",
      "provenance": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}