2014-Densifying One Permutation Hashing via Rotation for Fast Near Neighbor Search.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import math\n",
    "from hashlib import md5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "%store -r Datasets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "mnist = Datasets['MNIST-Hamming']\n",
    "\n",
    "train = mnist['train']\n",
    "test = mnist['test']\n",
    "k_near_neighbors = mnist['k_near_neighbors']\n",
    "nearest_neighbor = mnist['nearest_neighbor']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# One Permutation with Rotation(OPR)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_md5(H):\n",
    "    hmd5 = md5()\n",
    "    hmd5.update(str(H).encode(encoding='utf-8'))\n",
    "    return hmd5.hexdigest()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "def OPR(P, k, L, C):\n",
    "    \"\"\"\n",
    "    Desc:\n",
    "        One Permutation with Rotation\n",
    "    Args:\n",
    "        P: 点集\n",
    "        k: 分段数\n",
    "            sd: D / k 每段长度\n",
    "        L: 桶数\n",
    "        C: 防碰撞参数\n",
    "    \"\"\"\n",
    "    n = P.shape[0]\n",
    "    D = P.shape[1]\n",
    "    sd = int(D / k)\n",
    "\n",
    "    print('k = {}, L = {}'.format(k, L))\n",
    "    print('Every segament length is {}'.format(sd))\n",
    "    buckets = []\n",
    "    seeds = np.random.choice(np.arange(k * L * D), L, replace=False)\n",
    "\n",
    "    one_segament_vector = list(range(sd, 0, -1))\n",
    "    auxiliary_vector = np.array(one_segament_vector * k)\n",
    "\n",
    "    for i in range(L):\n",
    "\n",
    "        bucket = dict()\n",
    "        \n",
    "        # 1. 重排\n",
    "        P_ = []\n",
    "        for p in P:\n",
    "            np.random.seed(seeds[i])\n",
    "            P_.append(np.random.permutation(p))\n",
    "        \n",
    "        # 2. 计算哈希\n",
    "        for idx, p in enumerate(P_):\n",
    "            H = []\n",
    "            \n",
    "            H = -((auxiliary_vector * p).reshape(-1, sd).max(axis=1) - sd)\n",
    "            H[H == sd] = -1\n",
    "            for j, h in enumerate(H):\n",
    "                if h == -1:\n",
    "                    nj = j\n",
    "                    while H[nj] == -1:\n",
    "                        nj = (1 + nj) % k\n",
    "                    H[j] = H[nj] + C\n",
    "            bi = generate_md5(H)\n",
    "            if bi not in bucket:\n",
    "                bucket[bi] = [idx]\n",
    "            else:\n",
    "                bucket[bi].append(idx)\n",
    "        buckets.append(bucket)\n",
    "\n",
    "    return buckets, seeds, auxiliary_vector"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def OPR_query(args, q):\n",
    "    \"\"\"\n",
    "    Desc:\n",
    "        One Permutation with Rotation\n",
    "    Args:\n",
    "        args:\n",
    "            [0]: (D, k, L, C)\n",
    "            [1]: buckets\n",
    "            [2]: seeds\n",
    "            [3]: auxiliary_vector\n",
    "            \n",
    "    \"\"\"\n",
    "    D, k, L, C = args[0]\n",
    "    buckets = args[1]\n",
    "    seeds = args[2]\n",
    "    auxiliary_vector = args[3]\n",
    "\n",
    "    sd = int(D / k)\n",
    "\n",
    "    result = []\n",
    "    for i in range(L):\n",
    "        # 1. 重排\n",
    "        np.random.seed(seeds[i])\n",
    "        q_ = np.random.permutation(q)\n",
    "        \n",
    "        # 2. 计算哈希\n",
    "        H = -((auxiliary_vector * q_).reshape(-1, sd).max(axis=1) - sd)\n",
    "        H[H == sd] = -1\n",
    "\n",
    "        for j, h in enumerate(H):\n",
    "            if h == -1:\n",
    "                nj = j\n",
    "                while H[nj] == -1:\n",
    "                    nj = (1 + nj) % k\n",
    "                H[j] = H[nj] + C\n",
    "        \n",
    "        bi = generate_md5(H)\n",
    "        if bi in buckets[i]:\n",
    "            result.append(buckets[i][bi])\n",
    "\n",
    "    if len(result) != 0:\n",
    "        result = np.unique(np.concatenate(result))\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "def metrics(P, query_func, args, nearest_neighbor, test):\n",
    "    correct = 0\n",
    "    n = P.shape[0]\n",
    "    total = 0\n",
    "    selectivity = 0\n",
    "    for i, q in enumerate(test):\n",
    "        candidates = query_func(args, q)\n",
    "        if nearest_neighbor[i] in candidates:\n",
    "            correct += 1\n",
    "        selectivity += len(candidates) / n\n",
    "    \n",
    "    result = dict()\n",
    "    result['precision'] = correct / len(test)\n",
    "    result['selectivity'] = selectivity / len(test)\n",
    "    \n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "k = 8, L = 16\n",
      "Every segament length is 98\n",
      "CPU times: user 2min 10s, sys: 1.55 s, total: 2min 12s\n",
      "Wall time: 2min 11s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "k = 8\n",
    "L = 16\n",
    "\n",
    "D = train.shape[1]\n",
    "C = np.ceil(D / k + L)\n",
    "\n",
    "buckets, seeds, auxiliary_vector = OPR(train, k=k, L=L, C=C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1.18 s, sys: 3.22 ms, total: 1.18 s\n",
      "Wall time: 1.18 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'precision': 0.878, 'selectivity': 0.018446820143884907}"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "metrics(train, OPR_query, [(D, k, L, C), buckets, seeds, auxiliary_vector], nearest_neighbor, test)"
   ]
  }
 ],
 "metadata": {
  "hide_input": false,
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.6"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "334px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}