lattice_length_radius_tradeoffs.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import faiss\n",
    "import time\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To choose a `ZnLattice` quantizer, there are two parameters: the input dimension (d) and the radius (squared: r2). \n",
    "In the code below, we look at how many bits of code are given by various (d, r2) pairs. \n",
    "For example, if we have an input dim of d=16 and we need 42-bit codes , then set r2=60, which yields just below 42 bits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\t4: 3.58 6: 2.58 8: 4.58 10: 3.58 \n",
      "4\t4: 4.58 6: 4.58 8: 6.58 10: 4.58 12: 7.17 14: 6.58 16: 7.58 \n",
      "5\t4: 5.32 6: 6.49 8: 7.91 10: 7.64 12: 9.13 14: 8.64 16: 9.64 18: 9.51 20:10.28 22: 9.55 24:10.85 26:10.23 \n",
      "6\t4: 5.91 6: 7.98 8: 9.09 10: 9.99 12:10.61 14:11.02 16:11.67 18:12.00 20:12.10 22:12.68 24:12.99 26:13.01 28:13.32 30:13.61 32:13.79 34:14.00 36:14.09 \n",
      "7\t4: 6.39 6: 9.16 8:10.33 10:11.75 12:12.11 14:13.17 16:13.44 18:14.17 20:14.27 22:15.07 24:14.93 26:15.69 28:15.67 30:16.18 32:16.12 34:16.76 36:16.53 38:17.15 40:17.02 42:17.47 44:17.32 46:17.93 48:17.62 50:18.18 \n",
      "8\t4: 6.81 6:10.15 8:11.61 10:13.19 12:13.78 14:14.96 16:15.23 18:16.19 20:16.37 22:17.13 24:17.19 26:17.99 28:17.91 30:18.58 32:18.59 34:19.19 36:19.07 38:19.71 40:19.55 42:20.16 44:20.04 46:20.53 48:20.38 50:21.00 52:20.75 54:21.25 56:21.13 58:21.61 60:21.38 62:21.93 64:21.67 \n",
      "10\t4: 7.49 6:11.72 8:13.99 10:15.67 12:16.98 14:18.00 16:18.90 18:19.68 20:20.34 22:20.97 24:21.51 26:22.00 28:22.49 30:22.91 32:23.28 34:23.68 36:24.03 38:24.34 40:24.66 42:24.97 44:25.23 46:25.52 48:25.77 50:26.00 52:26.26 54:26.48 56:26.67 58:26.91 60:27.12 62:27.29 64:27.49 66:27.68 70:28.03 74:28.34 78:28.67 82:28.97 86:29.23 90:29.52 94:29.77 98:30.00 \n",
      "12\t4: 8.04 6:12.96 8:15.98 10:17.95 12:19.65 14:20.89 16:22.08 18:22.95 20:23.90 22:24.57 24:25.34 26:25.88 28:26.55 30:26.99 32:27.59 34:27.95 36:28.48 38:28.81 40:29.28 42:29.56 44:30.01 46:30.25 48:30.66 50:30.88 52:31.26 54:31.46 56:31.82 58:31.99 60:32.33 62:32.50 64:32.82 66:32.95 70:33.39 74:33.81 78:34.20 82:34.56 86:34.92 90:35.25 94:35.57 98:35.88 102:36.18 106:36.45 110:36.74 114:36.99 118:37.25 122:37.49 126:37.73 130:37.95 138:38.39 \n",
      "14\t4: 8.51 6:13.97 8:17.62 10:20.06 12:22.00 14:23.58 16:24.91 18:26.07 20:27.09 22:28.00 24:28.83 26:29.58 28:30.27 30:30.91 32:31.51 34:32.07 36:32.59 38:33.09 40:33.56 42:34.00 44:34.42 46:34.83 48:35.21 50:35.58 52:35.93 54:36.27 56:36.60 58:36.91 60:37.22 62:37.51 64:37.79 66:38.07 70:38.59 74:39.09 78:39.56 82:40.00 86:40.42 90:40.83 94:41.21 98:41.58 102:41.93 106:42.27 110:42.60 114:42.91 118:43.22 122:43.51 126:43.79 130:44.07 138:44.59 146:45.09 154:45.56 162:46.00 170:46.42 178:46.83 186:47.21 194:47.58 \n",
      "16\t4: 8.91 6:14.83 8:19.00 10:21.93 12:24.15 14:26.02 16:27.55 18:28.92 20:30.09 22:31.18 24:32.12 26:33.02 28:33.80 30:34.58 32:35.25 34:35.92 36:36.51 38:37.11 40:37.64 42:38.18 44:38.65 46:39.14 48:39.57 50:40.02 52:40.41 54:40.83 56:41.19 58:41.58 60:41.91 62:42.27 64:42.58 66:42.92 70:43.54 74:44.11 78:44.66 82:45.18 86:45.67 90:46.14 94:46.59 98:47.02 102:47.43 106:47.83 110:48.21 114:48.58 118:48.93 122:49.27 126:49.60 130:49.92 138:50.54 146:51.11 154:51.66 162:52.18 170:52.67 178:53.14 186:53.59 194:54.02 202:54.43 210:54.83 218:55.21 226:55.58 234:55.93 242:56.27 250:56.60 \n",
      "20\t4: 9.57 6:16.24 8:21.26 10:25.05 12:27.95 14:30.31 16:32.31 18:34.04 20:35.58 22:36.94 24:38.18 26:39.31 28:40.35 30:41.31 32:42.21 34:43.04 36:43.84 38:44.57 40:45.28 42:45.94 44:46.58 46:47.18 48:47.76 50:48.31 52:48.84 54:49.35 56:49.84 58:50.31 60:50.77 62:51.21 64:51.64 66:52.04 70:52.83 74:53.57 78:54.27 82:54.94 86:55.57 90:56.18 94:56.76 98:57.31 102:57.84 106:58.35 110:58.84 114:59.31 118:59.76 122:60.21 126:60.63 130:61.04 138:61.83 146:62.57 154:63.27 162:63.94 170:62.97 178:62.07 186:62.59 194:63.93 202:61.25 210:61.48 218:62.22 226:63.72 234:61.58 242:63.83 250:63.13 258:63.90 266:63.97 274:63.65 282:63.49 290:62.41 298:63.13 306:63.30 314:61.49 322:62.03 330:63.03 338:61.14 346:63.77 354:62.51 362:60.46 370:61.50 378:61.95 386:63.85 394:63.34 \n",
      "24\t4:10.11 6:17.38 8:23.05 10:27.54 12:31.11 14:34.00 16:36.45 18:38.57 20:40.44 22:42.11 24:43.62 26:45.00 28:46.27 30:47.45 32:48.54 34:49.57 36:50.53 38:51.44 40:52.29 42:53.11 44:53.88 46:54.62 48:55.33 50:56.00 52:56.65 54:57.27 56:57.87 58:58.45 60:59.00 62:59.54 64:60.06 66:60.57 70:61.53 74:62.44 78:63.30 82:60.33 86:63.76 90:60.32 94:58.27 98:57.97 102:63.16 106:62.41 110:62.17 114:63.45 118:62.08 122:62.31 126:63.74 130:63.64 138:63.51 146:62.29 154:63.37 162:62.25 170:63.42 178:62.61 186:63.04 194:62.51 202:63.27 210:61.25 218:61.44 226:63.89 234:58.39 242:63.84 250:60.20 258:63.41 266:62.18 274:58.80 282:61.17 290:61.40 298:61.94 306:63.95 314:63.02 322:63.38 330:63.01 338:63.04 346:58.03 354:63.16 362:60.78 370:63.67 378:63.01 386:63.77 394:63.88 402:63.54 410:62.98 418:58.38 426:60.70 434:63.64 442:62.21 450:60.80 458:62.69 466:60.96 474:62.16 482:63.91 490:62.06 498:59.97 506:63.91 514:62.96 522:62.93 530:62.73 538:63.20 546:63.50 554:61.59 562:63.38 570:59.77 \n",
      "28\t4:10.56 6:18.32 8:24.53 10:29.60 12:33.76 14:37.19 16:40.08 18:42.59 20:44.79 22:46.77 24:48.56 26:50.19 28:51.69 30:53.08 32:54.37 34:55.58 36:56.72 38:57.79 40:58.81 42:59.77 44:60.69 46:61.56 48:62.39 50:63.19 52:63.96 54:63.30 56:63.35 58:61.88 60:63.44 62:62.57 64:63.83 66:64.00 70:63.64 74:63.94 78:60.52 82:63.09 86:61.21 90:58.54 94:63.82 98:63.23 102:62.85 106:62.79 110:59.61 114:60.60 118:62.15 122:62.89 126:63.82 130:63.99 138:62.45 146:61.04 154:62.09 162:62.46 170:62.46 178:61.50 186:63.68 194:63.77 202:63.54 210:63.49 218:63.32 226:62.20 234:63.03 242:60.85 250:61.27 258:63.99 266:63.41 274:63.93 282:62.06 290:63.60 298:61.98 306:63.55 314:63.49 322:63.79 330:60.89 338:63.28 346:57.80 354:56.48 362:63.60 370:63.79 378:60.02 386:63.01 394:63.80 402:63.58 410:63.66 418:63.45 426:62.74 434:56.80 442:62.83 450:56.67 458:63.65 466:62.15 474:60.70 482:63.34 490:61.80 498:62.19 506:57.83 514:58.17 522:63.06 530:63.13 \n",
      "32\t4:10.95 6:19.13 8:25.79 10:31.34 12:36.01 14:39.94 16:43.28 18:46.17 20:48.72 22:51.00 24:53.07 26:54.95 28:56.68 30:58.28 32:59.78 34:61.17 36:62.49 38:63.72 40:63.78 42:56.97 44:62.41 46:63.57 48:63.28 50:63.58 52:63.84 54:61.12 56:62.28 58:62.90 60:62.37 62:63.90 64:63.54 66:63.07 70:63.36 74:62.25 78:63.88 82:62.09 86:63.40 90:63.81 94:63.04 98:63.13 102:63.54 106:63.46 110:62.91 114:63.11 118:59.44 122:62.04 126:63.63 130:62.92 138:62.81 146:61.66 154:60.05 162:62.83 170:63.16 178:63.14 186:61.90 194:63.93 202:63.74 210:62.68 218:62.80 226:61.84 234:60.98 242:63.58 250:61.74 258:63.30 266:62.80 274:60.15 282:63.25 290:60.60 298:59.93 306:63.91 314:63.53 322:62.56 330:61.12 338:63.67 346:63.39 354:62.04 362:59.87 370:63.36 378:63.88 386:62.95 394:60.32 402:62.87 410:63.70 418:58.54 426:63.40 434:63.97 442:63.97 450:63.13 458:63.04 466:58.82 474:58.87 \n",
      "40\t4:11.61 6:20.48 8:27.87 10:34.20 12:39.69 14:44.46 16:48.62 18:52.27 20:55.50 22:58.39 24:61.00 26:63.39 28:63.99 30:61.98 32:62.76 34:63.72 36:63.80 38:61.78 40:63.81 42:63.94 44:63.69 46:63.90 48:63.48 50:63.90 52:62.85 54:62.96 56:63.68 58:63.53 60:60.95 62:63.60 64:63.76 66:60.64 70:62.92 74:61.35 78:62.51 82:63.15 86:61.09 90:63.89 94:63.22 98:62.02 102:63.26 106:63.11 110:63.76 114:61.16 118:63.25 122:63.94 126:63.48 130:63.98 138:63.78 146:63.58 154:63.17 162:63.73 170:63.08 178:61.59 186:62.16 194:63.17 202:60.31 210:62.05 218:63.60 226:63.51 234:62.35 242:63.92 250:59.16 258:61.34 266:61.14 274:63.78 282:61.09 290:63.28 298:63.58 306:63.92 314:63.77 322:63.01 330:59.67 338:62.91 346:63.04 354:62.83 362:62.96 370:62.86 378:63.96 386:62.71 394:63.13 402:61.48 410:63.24 \n",
      "48\t4:12.14 6:21.57 8:29.55 10:36.50 12:42.62 14:48.06 16:52.90 18:57.23 20:61.10 22:63.01 24:62.85 26:63.08 28:62.66 30:63.97 32:63.29 34:63.45 36:63.10 38:63.80 40:60.67 42:63.42 44:63.26 46:62.11 48:60.34 50:63.40 52:58.54 54:62.44 56:62.06 58:62.78 60:63.94 62:60.18 64:61.13 66:61.69 70:62.97 74:62.41 78:62.20 82:62.89 86:63.79 90:59.72 94:63.37 98:62.62 102:61.98 106:62.28 110:63.80 114:63.30 118:63.19 122:63.80 126:61.69 130:63.26 138:62.41 146:63.71 154:63.24 162:62.23 170:56.06 178:62.30 186:63.89 194:56.86 202:63.59 210:62.39 218:63.53 226:63.23 234:62.75 242:63.93 250:62.76 258:62.23 266:62.61 274:63.70 282:61.90 290:62.00 298:62.59 306:62.27 314:63.97 322:62.34 330:63.82 338:63.16 346:62.06 354:63.86 362:63.32 \n",
      "56\t4:12.59 6:22.49 8:30.95 10:38.41 12:45.06 14:51.04 16:56.45 18:61.35 20:62.88 22:63.95 24:63.16 26:63.09 28:63.89 30:63.55 32:63.91 34:63.26 36:62.69 38:63.52 40:62.97 42:61.55 44:63.85 46:56.33 48:61.17 50:63.50 52:63.48 54:63.70 56:61.21 58:63.26 60:63.86 62:62.81 64:63.31 66:63.71 70:61.97 74:62.45 78:63.71 82:63.46 86:63.33 90:62.65 94:63.81 98:63.96 102:63.88 106:61.17 110:61.90 114:63.61 118:63.72 122:63.66 126:63.32 130:63.40 138:63.89 146:62.02 154:63.85 162:63.40 170:62.50 178:57.36 186:63.06 194:61.08 202:62.05 210:63.61 218:63.77 226:61.16 234:63.64 242:60.05 250:63.25 258:62.83 266:62.07 274:61.83 282:63.10 290:60.78 298:62.75 306:62.61 314:63.16 322:62.10 330:63.86 338:63.89 \n",
      "64\t4:12.98 6:23.28 8:32.16 10:40.04 12:47.15 14:53.59 16:59.47 18:63.70 20:62.95 22:63.60 24:62.18 26:61.81 28:62.56 30:63.41 32:62.34 34:60.75 36:62.21 38:63.98 40:62.37 42:62.96 44:61.32 46:63.69 48:63.90 50:62.72 52:62.98 54:63.40 56:63.34 58:60.28 60:62.32 62:62.65 64:63.37 66:63.99 70:63.38 74:62.27 78:63.99 82:61.04 86:62.93 90:61.41 94:63.77 98:62.39 102:62.66 106:59.38 110:62.53 114:61.05 118:61.19 122:63.70 126:62.93 130:63.04 138:62.97 146:63.40 154:63.79 162:62.09 170:61.60 178:63.65 186:62.59 194:63.98 202:62.69 210:63.19 218:59.44 226:60.62 234:62.89 242:63.13 250:63.35 258:63.84 266:63.22 274:63.36 282:62.37 290:58.65 298:63.80 306:63.58 314:62.85 \n"
     ]
    }
   ],
   "source": [
    "def lr(*args): \n",
    "    return list(range(*args))\n",
    "\n",
    "\n",
    "for d in lr(3, 8) + lr(8, 16, 2) + lr(16, 32, 4) + lr(32, 65, 8): \n",
    "    print(d, end=\"\\t\")\n",
    "    \n",
    "   \n",
    "    for r2 in lr(2, 32, 2) + lr(32, 64, 2) + lr(64, 128, 4) + lr(128, 256, 8) + lr(256, 1024, 8):\n",
    "        if r2 >= d ** 2: \n",
    "            continue\n",
    "        t0 = time.time()\n",
    "        nv = faiss.ZnSphereCodec(d, r2).nv\n",
    "        t1 = time.time()\n",
    "        r2 += 2\n",
    "        l = np.log2(nv)\n",
    "        print(\"%d:%5.2f \" % (r2, l), end=\"\")\n",
    "        if t1 - t0 > 4 or l > 64: \n",
    "            break\n",
    "    print()\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "bento_stylesheets": {
   "bento/extensions/flow/main.css": true,
   "bento/extensions/kernel_selector/main.css": true,
   "bento/extensions/kernel_ui/main.css": true,
   "bento/extensions/new_kernel/main.css": true,
   "bento/extensions/system_usage/main.css": true,
   "bento/extensions/theme/main.css": true
  },
  "kernelspec": {
   "display_name": "faiss",
   "language": "python",
   "name": "bento_kernel_faiss"
  },
  "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.5+"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}