IVF: Inverted File Index

%23%20%2F%2F%2F%20script%0A%23%20requires-python%20%3D%20%22%3E%3D3.11%22%0A%23%20dependencies%20%3D%20%5B%0A%23%20%20%20%20%20%22marimo%22%2C%0A%23%20%20%20%20%20%22numpy%3D%3D2.4.3%22%2C%0A%23%20%20%20%20%20%22matplotlib%3D%3D3.10.3%22%2C%0A%23%20%20%20%20%20%22scipy%3D%3D1.15.3%22%2C%0A%23%20%5D%0A%23%20%2F%2F%2F%0A%0Aimport%20marimo%0A%0A__generated_with%20%3D%20%220.22.5%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22%2C%20app_title%3D%22IVF%3A%20Inverted%20File%20Index%22)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20import%20matplotlib%20as%20mpl%0A%20%20%20%20from%20scipy.spatial%20import%20Voronoi%0A%20%20%20%20mpl.rcParams.update(%7B%22text.color%22%3A%20%22white%22%2C%20%22axes.labelcolor%22%3A%20%22white%22%7D)%0A%20%20%20%20return%20Voronoi%2C%20mo%2C%20np%2C%20plt%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20How%20IVF%20Partitions%20Space%20for%20Fast%20Search%0A%0A%20%20%20%20Brute-force%20nearest%20neighbour%20search%20compares%20the%20query%20against%20every%20vector%20in%20the%20database%20--%0A%20%20%20%20%24O(N)%24%20per%20query.%20IVF%20(Inverted%20File%20Index)%20avoids%20this%20by%20partitioning%20the%20space%20with%20**k-means**.%0A%20%20%20%20Each%20cluster%20centroid%20owns%20a%20region%3B%20all%20vectors%20in%20that%20region%20go%20into%20an%20**inverted%20list**.%0A%20%20%20%20At%20query%20time%2C%20we%20find%20the%20closest%20centroids%2C%20then%20only%20scan%20vectors%20in%20those%20lists.%0A%20%20%20%20The%20number%20of%20lists%20probed%20(%60n_probe%60)%20controls%20the%20speed%2Frecall%20tradeoff.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20n_lists_slider%20%3D%20mo.ui.slider(4%2C%2050%2C%20value%3D16%2C%20step%3D1%2C%20label%3D%22n_lists%20(Voronoi%20cells)%22%2C%20show_value%3DTrue)%0A%20%20%20%20n_probe_slider%20%3D%20mo.ui.slider(1%2C%2050%2C%20value%3D3%2C%20step%3D1%2C%20label%3D%22n_probe%20(cells%20to%20search)%22%2C%20show_value%3DTrue)%0A%20%20%20%20N_slider%20%3D%20mo.ui.slider(200%2C%205000%2C%20value%3D1000%2C%20step%3D100%2C%20label%3D%22N%20(database%20size)%22%2C%20show_value%3DTrue)%0A%0A%20%20%20%20mo.hstack(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.vstack(%5Bmo.md(%22**Partitioning**%22)%2C%20n_lists_slider%2C%20N_slider%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.vstack(%5Bmo.md(%22**Search**%22)%2C%20n_probe_slider%5D)%2C%0A%20%20%20%20%20%20%20%20%5D%2C%0A%20%20%20%20%20%20%20%20gap%3D2%2C%0A%20%20%20%20)%0A%20%20%20%20return%20N_slider%2C%20n_lists_slider%2C%20n_probe_slider%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(N_slider%2C%20n_lists_slider%2C%20n_probe_slider%2C%20np)%3A%0A%20%20%20%20n_lists%20%3D%20n_lists_slider.value%0A%20%20%20%20n_probe%20%3D%20min(n_probe_slider.value%2C%20n_lists)%0A%20%20%20%20N%20%3D%20N_slider.value%0A%0A%20%20%20%20rng%20%3D%20np.random.default_rng(42)%0A%20%20%20%20points%20%3D%20rng.uniform(-10%2C%2010%2C%20size%3D(N%2C%202))%0A%0A%20%20%20%20%23%20k-means%20(manual%2C%20a%20few%20iterations%20suffice%20for%20visualization)%0A%20%20%20%20centroid_idx%20%3D%20rng.choice(N%2C%20size%3Dn_lists%2C%20replace%3DFalse)%0A%20%20%20%20centroids%20%3D%20points%5Bcentroid_idx%5D.copy()%0A%0A%20%20%20%20for%20_%20in%20range(20)%3A%0A%20%20%20%20%20%20%20%20dists%20%3D%20np.linalg.norm(points%5B%3A%2C%20None%2C%20%3A%5D%20-%20centroids%5BNone%2C%20%3A%2C%20%3A%5D%2C%20axis%3D2)%0A%20%20%20%20%20%20%20%20assignments%20%3D%20np.argmin(dists%2C%20axis%3D1)%0A%20%20%20%20%20%20%20%20for%20k%20in%20range(n_lists)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20mask%20%3D%20assignments%20%3D%3D%20k%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20mask.any()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20centroids%5Bk%5D%20%3D%20points%5Bmask%5D.mean(axis%3D0)%0A%0A%20%20%20%20%23%20final%20assignments%0A%20%20%20%20dists%20%3D%20np.linalg.norm(points%5B%3A%2C%20None%2C%20%3A%5D%20-%20centroids%5BNone%2C%20%3A%2C%20%3A%5D%2C%20axis%3D2)%0A%20%20%20%20assignments%20%3D%20np.argmin(dists%2C%20axis%3D1)%0A%20%20%20%20return%20N%2C%20assignments%2C%20centroids%2C%20n_lists%2C%20n_probe%2C%20points%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Voronoi%20Partitioning%0A%0A%20%20%20%20K-means%20divides%20the%20space%20into%20**Voronoi%20cells**%20--%20each%20point%20belongs%20to%20its%20nearest%20centroid.%0A%20%20%20%20The%20diagram%20below%20colors%20every%20database%20vector%20by%20its%20assigned%20cell.%20Large%20diamond%20markers%20are%20centroids.%0A%20%20%20%20Drag%20the%20%60n_lists%60%20slider%20to%20see%20how%20finer%20partitioning%20creates%20smaller%20cells.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(N%2C%20Voronoi%2C%20assignments%2C%20centroids%2C%20mo%2C%20n_lists%2C%20np%2C%20plt%2C%20points)%3A%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(10%2C%208))%0A%20%20%20%20_ax.set_aspect(%22equal%22)%0A%0A%20%20%20%20%23%20color%20map%20for%20clusters%0A%20%20%20%20_cmap%20%3D%20plt.cm.tab20(np.linspace(0%2C%201%2C%20max(n_lists%2C%2020)))%0A%0A%20%20%20%20%23%20draw%20Voronoi%20edges%20if%20enough%20centroids%0A%20%20%20%20if%20n_lists%20%3E%3D%203%3A%0A%20%20%20%20%20%20%20%20%23%20add%20far-away%20points%20to%20bound%20the%20Voronoi%20diagram%0A%20%20%20%20%20%20%20%20_far%20%3D%20100%0A%20%20%20%20%20%20%20%20_extended%20%3D%20np.vstack(%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20centroids%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B%5B-_far%2C%20-_far%5D%2C%20%5B_far%2C%20-_far%5D%2C%20%5B-_far%2C%20_far%5D%2C%20%5B_far%2C%20_far%5D%5D%2C%0A%20%20%20%20%20%20%20%20%5D)%0A%20%20%20%20%20%20%20%20_vor%20%3D%20Voronoi(_extended)%0A%20%20%20%20%20%20%20%20for%20_simplex%20in%20_vor.ridge_vertices%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20-1%20not%20in%20_simplex%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ax.plot(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5B_vor.vertices%5B_simplex%5B0%5D%2C%200%5D%2C%20_vor.vertices%5B_simplex%5B1%5D%2C%200%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5B_vor.vertices%5B_simplex%5B0%5D%2C%201%5D%2C%20_vor.vertices%5B_simplex%5B1%5D%2C%201%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22white%22%2C%20lw%3D0.6%2C%20alpha%3D0.4%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%23%20scatter%20points%20colored%20by%20cluster%0A%20%20%20%20for%20_k%20in%20range(n_lists)%3A%0A%20%20%20%20%20%20%20%20_mask%20%3D%20assignments%20%3D%3D%20_k%0A%20%20%20%20%20%20%20%20_color%20%3D%20_cmap%5B_k%20%25%20len(_cmap)%5D%0A%20%20%20%20%20%20%20%20_ax.scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20points%5B_mask%2C%200%5D%2C%20points%5B_mask%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20c%3D%5B_color%5D%2C%20s%3D6%2C%20alpha%3D0.6%2C%20zorder%3D2%2C%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%23%20centroids%0A%20%20%20%20_ax.scatter(%0A%20%20%20%20%20%20%20%20centroids%5B%3A%2C%200%5D%2C%20centroids%5B%3A%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20c%3D%22white%22%2C%20s%3D120%2C%20marker%3D%22D%22%2C%20edgecolors%3D%22black%22%2C%20linewidths%3D1.2%2C%20zorder%3D4%2C%0A%20%20%20%20%20%20%20%20label%3D%22Centroids%22%2C%0A%20%20%20%20)%0A%20%20%20%20for%20_i%2C%20_c%20in%20enumerate(centroids)%3A%0A%20%20%20%20%20%20%20%20_ax.annotate(%0A%20%20%20%20%20%20%20%20%20%20%20%20str(_i)%2C%20xy%3D(_c%5B0%5D%2C%20_c%5B1%5D)%2C%20fontsize%3D7%2C%20color%3D%22black%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22center%22%2C%20va%3D%22center%22%2C%20fontweight%3D%22bold%22%2C%20zorder%3D5%2C%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20_avg%20%3D%20N%20%2F%2F%20n_lists%0A%20%20%20%20_ax.annotate(%0A%20%20%20%20%20%20%20%20f%22Each%20cell%20contains%20~%7B_avg%7D%20vectors%22%2C%0A%20%20%20%20%20%20%20%20xy%3D(0.02%2C%200.97)%2C%20xycoords%3D%22axes%20fraction%22%2C%0A%20%20%20%20%20%20%20%20fontsize%3D11%2C%20color%3D%22white%22%2C%20va%3D%22top%22%2C%0A%20%20%20%20%20%20%20%20bbox%3Ddict(boxstyle%3D%22round%2Cpad%3D0.3%22%2C%20fc%3D%22%231a1a2e%22%2C%20ec%3D%22white%22%2C%20alpha%3D0.8)%2C%0A%20%20%20%20)%0A%0A%20%20%20%20_ax.set_xlim(-11%2C%2011)%0A%20%20%20%20_ax.set_ylim(-11%2C%2011)%0A%20%20%20%20_ax.set_facecolor(%22%231a1a2e%22)%0A%20%20%20%20_fig.set_facecolor(%22%231a1a2e%22)%0A%20%20%20%20_ax.tick_params(colors%3D%22gray%22)%0A%20%20%20%20for%20_sp%20in%20_ax.spines.values()%3A%0A%20%20%20%20%20%20%20%20_sp.set_color(%22gray%22)%0A%20%20%20%20_ax.set_title(f%22Voronoi%20partitioning%3A%20%7Bn_lists%7D%20cells%2C%20%7BN%7D%20vectors%22%2C%20color%3D%22white%22%2C%20fontsize%3D13%2C%20pad%3D10)%0A%20%20%20%20_ax.legend(loc%3D%22lower%20right%22%2C%20facecolor%3D%22%231a1a2e%22%2C%20edgecolor%3D%22white%22%2C%20labelcolor%3D%22white%22)%0A%20%20%20%20plt.tight_layout()%0A%20%20%20%20mo.as_html(_fig)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Search%3A%20n_probe%20in%20Action%0A%0A%20%20%20%20A%20query%20arrives%20(red%20star).%20We%20find%20the%20%60n_probe%60%20nearest%20centroids%20and%20only%20scan%20vectors%0A%20%20%20%20in%20those%20cells.%20Blue%20points%20are%20scanned%3B%20gray%20points%20are%20skipped%20entirely.%0A%20%20%20%20Red%20circles%20mark%20the%20true%20top-10%20nearest%20neighbours.%20How%20many%20fall%20inside%20the%20probed%20cells%3F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20N%2C%0A%20%20%20%20Voronoi%2C%0A%20%20%20%20assignments%2C%0A%20%20%20%20centroids%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20n_lists%2C%0A%20%20%20%20n_probe%2C%0A%20%20%20%20np%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20points%2C%0A)%3A%0A%20%20%20%20_query%20%3D%20np.array(%5B2.0%2C%203.0%5D)%0A%0A%20%20%20%20%23%20distances%20from%20query%20to%20all%20centroids%0A%20%20%20%20_cdists%20%3D%20np.linalg.norm(centroids%20-%20_query%2C%20axis%3D1)%0A%20%20%20%20_probed_ids%20%3D%20np.argsort(_cdists)%5B%3An_probe%5D%0A%0A%20%20%20%20%23%20which%20points%20are%20in%20probed%20cells%3F%0A%20%20%20%20_in_probed%20%3D%20np.isin(assignments%2C%20_probed_ids)%0A%0A%20%20%20%20%23%20true%20top-10%0A%20%20%20%20_qdists%20%3D%20np.linalg.norm(points%20-%20_query%2C%20axis%3D1)%0A%20%20%20%20_true_top10%20%3D%20np.argsort(_qdists)%5B%3A10%5D%0A%20%20%20%20_top10_in_probed%20%3D%20np.isin(_true_top10%2C%20np.where(_in_probed)%5B0%5D)%0A%20%20%20%20_recall%20%3D%20_top10_in_probed.sum()%0A%20%20%20%20_scanned%20%3D%20_in_probed.sum()%0A%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(10%2C%208))%0A%20%20%20%20_ax.set_aspect(%22equal%22)%0A%0A%20%20%20%20%23%20Voronoi%20edges%0A%20%20%20%20if%20n_lists%20%3E%3D%203%3A%0A%20%20%20%20%20%20%20%20_far%20%3D%20100%0A%20%20%20%20%20%20%20%20_extended%20%3D%20np.vstack(%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20centroids%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B%5B-_far%2C%20-_far%5D%2C%20%5B_far%2C%20-_far%5D%2C%20%5B-_far%2C%20_far%5D%2C%20%5B_far%2C%20_far%5D%5D%2C%0A%20%20%20%20%20%20%20%20%5D)%0A%20%20%20%20%20%20%20%20_vor%20%3D%20Voronoi(_extended)%0A%20%20%20%20%20%20%20%20for%20_simplex%20in%20_vor.ridge_vertices%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20-1%20not%20in%20_simplex%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ax.plot(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5B_vor.vertices%5B_simplex%5B0%5D%2C%200%5D%2C%20_vor.vertices%5B_simplex%5B1%5D%2C%200%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5B_vor.vertices%5B_simplex%5B0%5D%2C%201%5D%2C%20_vor.vertices%5B_simplex%5B1%5D%2C%201%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22white%22%2C%20lw%3D0.5%2C%20alpha%3D0.3%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%23%20unprobed%20points%3A%20gray%0A%20%20%20%20_ax.scatter(%0A%20%20%20%20%20%20%20%20points%5B~_in_probed%2C%200%5D%2C%20points%5B~_in_probed%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20c%3D%22gray%22%2C%20s%3D6%2C%20alpha%3D0.25%2C%20zorder%3D2%2C%20label%3Df%22Skipped%20(%7BN%20-%20_scanned%7D)%22%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20probed%20points%3A%20blue%0A%20%20%20%20_ax.scatter(%0A%20%20%20%20%20%20%20%20points%5B_in_probed%2C%200%5D%2C%20points%5B_in_probed%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20c%3D%22dodgerblue%22%2C%20s%3D10%2C%20alpha%3D0.7%2C%20zorder%3D3%2C%20label%3Df%22Scanned%20(%7B_scanned%7D)%22%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20probed%20centroids%3A%20large%20colored%20circles%20with%20lines%20from%20query%0A%20%20%20%20for%20_pid%20in%20_probed_ids%3A%0A%20%20%20%20%20%20%20%20_ax.plot(%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B_query%5B0%5D%2C%20centroids%5B_pid%2C%200%5D%5D%2C%20%5B_query%5B1%5D%2C%20centroids%5B_pid%2C%201%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22dodgerblue%22%2C%20lw%3D1.5%2C%20ls%3D%22--%22%2C%20alpha%3D0.7%2C%20zorder%3D3%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20_ax.scatter(%0A%20%20%20%20%20%20%20%20centroids%5B_probed_ids%2C%200%5D%2C%20centroids%5B_probed_ids%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20c%3D%22dodgerblue%22%2C%20s%3D200%2C%20marker%3D%22o%22%2C%20edgecolors%3D%22white%22%2C%20linewidths%3D2%2C%20zorder%3D5%2C%0A%20%20%20%20%20%20%20%20label%3Df%22Probed%20centroids%20(%7Bn_probe%7D)%22%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20unprobed%20centroids%3A%20small%20white%20diamonds%0A%20%20%20%20_unprobed_ids%20%3D%20np.setdiff1d(np.arange(n_lists)%2C%20_probed_ids)%0A%20%20%20%20_ax.scatter(%0A%20%20%20%20%20%20%20%20centroids%5B_unprobed_ids%2C%200%5D%2C%20centroids%5B_unprobed_ids%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20c%3D%22white%22%2C%20s%3D50%2C%20marker%3D%22D%22%2C%20alpha%3D0.4%2C%20zorder%3D4%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20true%20top-10%3A%20red%20open%20circles%0A%20%20%20%20_ax.scatter(%0A%20%20%20%20%20%20%20%20points%5B_true_top10%2C%200%5D%2C%20points%5B_true_top10%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20facecolors%3D%22none%22%2C%20edgecolors%3D%22red%22%2C%20s%3D120%2C%20linewidths%3D2%2C%20zorder%3D6%2C%0A%20%20%20%20%20%20%20%20label%3Df%22True%20top-10%20(recall%20%3D%20%7B_recall%7D%2F10)%22%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20query%20point%0A%20%20%20%20_ax.scatter(%0A%20%20%20%20%20%20%20%20%5B_query%5B0%5D%5D%2C%20%5B_query%5B1%5D%5D%2C%0A%20%20%20%20%20%20%20%20c%3D%22red%22%2C%20s%3D250%2C%20marker%3D%22*%22%2C%20edgecolors%3D%22white%22%2C%20linewidths%3D1%2C%20zorder%3D7%2C%0A%20%20%20%20%20%20%20%20label%3D%22Query%22%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20stats%20box%0A%20%20%20%20_pct%20%3D%20100%20*%20_scanned%20%2F%20N%0A%20%20%20%20_ax.annotate(%0A%20%20%20%20%20%20%20%20f%22Scanning%20%7B_scanned%7D%2F%7BN%7D%20vectors%20(%7B_pct%3A.1f%7D%25)%5CnRecall%20%3D%20%7B_recall%7D%2F10%22%2C%0A%20%20%20%20%20%20%20%20xy%3D(0.02%2C%200.97)%2C%20xycoords%3D%22axes%20fraction%22%2C%0A%20%20%20%20%20%20%20%20fontsize%3D12%2C%20color%3D%22white%22%2C%20va%3D%22top%22%2C%0A%20%20%20%20%20%20%20%20bbox%3Ddict(boxstyle%3D%22round%2Cpad%3D0.4%22%2C%20fc%3D%22%231a1a2e%22%2C%20ec%3D%22dodgerblue%22%2C%20alpha%3D0.9)%2C%0A%20%20%20%20)%0A%0A%20%20%20%20_ax.set_xlim(-11%2C%2011)%0A%20%20%20%20_ax.set_ylim(-11%2C%2011)%0A%20%20%20%20_ax.set_facecolor(%22%231a1a2e%22)%0A%20%20%20%20_fig.set_facecolor(%22%231a1a2e%22)%0A%20%20%20%20_ax.tick_params(colors%3D%22gray%22)%0A%20%20%20%20for%20_sp%20in%20_ax.spines.values()%3A%0A%20%20%20%20%20%20%20%20_sp.set_color(%22gray%22)%0A%20%20%20%20_ax.set_title(f%22IVF%20search%3A%20n_probe%3D%7Bn_probe%7D%2C%20n_lists%3D%7Bn_lists%7D%22%2C%20color%3D%22white%22%2C%20fontsize%3D13%2C%20pad%3D10)%0A%20%20%20%20_ax.legend(loc%3D%22lower%20right%22%2C%20facecolor%3D%22%231a1a2e%22%2C%20edgecolor%3D%22white%22%2C%20labelcolor%3D%22white%22%2C%20fontsize%3D9)%0A%20%20%20%20plt.tight_layout()%0A%20%20%20%20mo.as_html(_fig)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20n_probe%20vs%20Recall%20Tradeoff%0A%0A%20%20%20%20For%20each%20value%20of%20%60n_probe%60%20(1%20through%20n_lists)%2C%20we%20measure%20recall%4010%20and%20the%20fraction%20of%20the%20database%0A%20%20%20%20scanned.%20The%20sweet%20spot%20is%20often%20around%20%24%5Csqrt%7B%5Ctext%7Bn%5C_lists%7D%7D%24%20--%20marked%20with%20a%20dashed%20vertical%20line%20--%0A%20%20%20%20where%20recall%20is%20already%20high%20but%20we%20scan%20only%20a%20small%20fraction%20of%20vectors.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(assignments%2C%20centroids%2C%20mo%2C%20n_lists%2C%20np%2C%20plt%2C%20points)%3A%0A%20%20%20%20_query%20%3D%20np.array(%5B2.0%2C%203.0%5D)%0A%20%20%20%20_qdists%20%3D%20np.linalg.norm(points%20-%20_query%2C%20axis%3D1)%0A%20%20%20%20_true_top10%20%3D%20set(np.argsort(_qdists)%5B%3A10%5D.tolist())%0A%0A%20%20%20%20_cdists%20%3D%20np.linalg.norm(centroids%20-%20_query%2C%20axis%3D1)%0A%20%20%20%20_centroid_order%20%3D%20np.argsort(_cdists)%0A%0A%20%20%20%20_recalls%20%3D%20%5B%5D%0A%20%20%20%20_scan_fracs%20%3D%20%5B%5D%0A%20%20%20%20_probes%20%3D%20list(range(1%2C%20n_lists%20%2B%201))%0A%0A%20%20%20%20for%20_np%20in%20_probes%3A%0A%20%20%20%20%20%20%20%20_probed_ids%20%3D%20_centroid_order%5B%3A_np%5D%0A%20%20%20%20%20%20%20%20_in_probed%20%3D%20np.isin(assignments%2C%20_probed_ids)%0A%20%20%20%20%20%20%20%20_scanned_idx%20%3D%20set(np.where(_in_probed)%5B0%5D.tolist())%0A%20%20%20%20%20%20%20%20_found%20%3D%20len(_true_top10%20%26%20_scanned_idx)%0A%20%20%20%20%20%20%20%20_recalls.append(_found%20%2F%2010)%0A%20%20%20%20%20%20%20%20_scan_fracs.append(_in_probed.sum()%20%2F%20len(points))%0A%0A%20%20%20%20_sweet%20%3D%20int(np.round(np.sqrt(n_lists)))%0A%0A%20%20%20%20_fig%2C%20_ax1%20%3D%20plt.subplots(figsize%3D(10%2C%205))%0A%0A%20%20%20%20%23%20recall%20curve%0A%20%20%20%20_color_r%20%3D%20%22dodgerblue%22%0A%20%20%20%20_ax1.plot(_probes%2C%20_recalls%2C%20color%3D_color_r%2C%20lw%3D2.5%2C%20marker%3D%22o%22%2C%20markersize%3D4%2C%20label%3D%22Recall%4010%22)%0A%20%20%20%20_ax1.set_xlabel(%22n_probe%22%2C%20color%3D%22white%22%2C%20fontsize%3D12)%0A%20%20%20%20_ax1.set_ylabel(%22Recall%4010%22%2C%20color%3D_color_r%2C%20fontsize%3D12)%0A%20%20%20%20_ax1.tick_params(axis%3D%22y%22%2C%20labelcolor%3D_color_r)%0A%20%20%20%20_ax1.set_ylim(-0.05%2C%201.1)%0A%0A%20%20%20%20%23%20scan%20fraction%20on%20right%20axis%0A%20%20%20%20_ax2%20%3D%20_ax1.twinx()%0A%20%20%20%20_color_s%20%3D%20%22tomato%22%0A%20%20%20%20_ax2.plot(_probes%2C%20_scan_fracs%2C%20color%3D_color_s%2C%20lw%3D2%2C%20ls%3D%22--%22%2C%20marker%3D%22s%22%2C%20markersize%3D3%2C%20label%3D%22Fraction%20scanned%22)%0A%20%20%20%20_ax2.set_ylabel(%22Fraction%20of%20DB%20scanned%22%2C%20color%3D_color_s%2C%20fontsize%3D12)%0A%20%20%20%20_ax2.tick_params(axis%3D%22y%22%2C%20labelcolor%3D_color_s)%0A%20%20%20%20_ax2.set_ylim(-0.05%2C%201.1)%0A%0A%20%20%20%20%23%20sweet%20spot%20line%0A%20%20%20%20_ax1.axvline(_sweet%2C%20color%3D%22white%22%2C%20ls%3D%22%3A%22%2C%20lw%3D1.5%2C%20alpha%3D0.7)%0A%20%20%20%20_sweet_idx%20%3D%20_sweet%20-%201%0A%20%20%20%20if%20_sweet_idx%20%3C%20len(_recalls)%3A%0A%20%20%20%20%20%20%20%20_ax1.annotate(%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22sqrt(n_lists)%20%3D%20%7B_sweet%7D%5Cnrecall%20%3D%20%7B_recalls%5B_sweet_idx%5D%3A.0%25%7D%2C%20scan%20%3D%20%7B_scan_fracs%5B_sweet_idx%5D%3A.0%25%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20xy%3D(_sweet%2C%20_recalls%5B_sweet_idx%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20xytext%3D(_sweet%20%2B%20n_lists%20*%200.15%2C%200.5)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D10%2C%20color%3D%22white%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20arrowprops%3Ddict(arrowstyle%3D%22-%3E%22%2C%20color%3D%22white%22%2C%20lw%3D1.2)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20bbox%3Ddict(boxstyle%3D%22round%2Cpad%3D0.3%22%2C%20fc%3D%22%231a1a2e%22%2C%20ec%3D%22white%22%2C%20alpha%3D0.9)%2C%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%23%20styling%0A%20%20%20%20_ax1.set_facecolor(%22%231a1a2e%22)%0A%20%20%20%20_fig.set_facecolor(%22%231a1a2e%22)%0A%20%20%20%20_ax1.tick_params(colors%3D%22gray%22)%0A%20%20%20%20_ax2.tick_params(colors%3D%22gray%22)%0A%20%20%20%20for%20_sp%20in%20_ax1.spines.values()%3A%0A%20%20%20%20%20%20%20%20_sp.set_color(%22gray%22)%0A%20%20%20%20for%20_sp%20in%20_ax2.spines.values()%3A%0A%20%20%20%20%20%20%20%20_sp.set_color(%22gray%22)%0A%20%20%20%20_ax1.set_title(f%22Tradeoff%3A%20n_probe%20vs%20recall%20and%20scan%20fraction%20(n_lists%3D%7Bn_lists%7D)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22white%22%2C%20fontsize%3D13%2C%20pad%3D10)%0A%0A%20%20%20%20%23%20combined%20legend%0A%20%20%20%20_lines1%2C%20_labels1%20%3D%20_ax1.get_legend_handles_labels()%0A%20%20%20%20_lines2%2C%20_labels2%20%3D%20_ax2.get_legend_handles_labels()%0A%20%20%20%20_ax1.legend(_lines1%20%2B%20_lines2%2C%20_labels1%20%2B%20_labels2%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20loc%3D%22center%20right%22%2C%20facecolor%3D%22%231a1a2e%22%2C%20edgecolor%3D%22white%22%2C%20labelcolor%3D%22white%22)%0A%0A%20%20%20%20plt.tight_layout()%0A%20%20%20%20mo.as_html(_fig)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20The%20Boundary%20Problem%0A%0A%20%20%20%20IVF%20misses%20neighbours%20when%20the%20query%20sits%20near%20a%20Voronoi%20boundary.%0A%20%20%20%20The%20diagram%20below%20zooms%20into%20exactly%20this%20situation%3A%20the%20query's%20nearest%20centroid%0A%20%20%20%20is%20in%20**Cell%20A**%2C%20but%20the%20true%20nearest%20neighbour%20lives%20in%20**Cell%20B**%20just%20across%20the%20boundary.%0A%20%20%20%20With%20%60n_probe%3D1%60%20we%20miss%20it.%20With%20%60n_probe%3D2%60%20we%20find%20it.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20_rng%20%3D%20np.random.default_rng(7)%0A%0A%20%20%20%20%23%20two%20centroids%20close%20together%0A%20%20%20%20_cA%20%3D%20np.array(%5B-1.5%2C%200.0%5D)%0A%20%20%20%20_cB%20%3D%20np.array(%5B1.5%2C%200.0%5D)%0A%0A%20%20%20%20%23%20generate%20points%20around%20each%20centroid%0A%20%20%20%20_ptsA%20%3D%20_rng.normal(loc%3D_cA%2C%20scale%3D1.2%2C%20size%3D(40%2C%202))%0A%20%20%20%20_ptsB%20%3D%20_rng.normal(loc%3D_cB%2C%20scale%3D1.2%2C%20size%3D(40%2C%202))%0A%0A%20%20%20%20%23%20query%20near%20the%20boundary%2C%20slightly%20on%20side%20A%0A%20%20%20%20_query%20%3D%20np.array(%5B-0.15%2C%200.3%5D)%0A%0A%20%20%20%20%23%20plant%20a%20true%20nearest%20neighbour%20just%20across%20the%20boundary%20in%20cell%20B%0A%20%20%20%20_true_nn%20%3D%20np.array(%5B0.25%2C%200.45%5D)%0A%20%20%20%20_ptsB%20%3D%20np.vstack(%5B_ptsB%2C%20_true_nn%5D)%0A%0A%20%20%20%20_dist_q_nn%20%3D%20np.linalg.norm(_query%20-%20_true_nn)%0A%20%20%20%20_dist_q_cA%20%3D%20np.linalg.norm(_query%20-%20_cA)%0A%20%20%20%20_dist_q_cB%20%3D%20np.linalg.norm(_query%20-%20_cB)%0A%0A%20%20%20%20_fig%2C%20(_ax1%2C%20_ax2)%20%3D%20plt.subplots(1%2C%202%2C%20figsize%3D(14%2C%206))%0A%0A%20%20%20%20for%20_ax%2C%20_title%2C%20_probe_b%20in%20%5B%0A%20%20%20%20%20%20%20%20(_ax1%2C%20%22n_probe%20%3D%201%3A%20MISS%22%2C%20False)%2C%0A%20%20%20%20%20%20%20%20(_ax2%2C%20%22n_probe%20%3D%202%3A%20FOUND%22%2C%20True)%2C%0A%20%20%20%20%5D%3A%0A%20%20%20%20%20%20%20%20_ax.set_aspect(%22equal%22)%0A%0A%20%20%20%20%20%20%20%20%23%20Voronoi%20boundary%3A%20perpendicular%20bisector%20of%20the%20two%20centroids%20(vertical%20line%20at%20x%3D0)%0A%20%20%20%20%20%20%20%20_ax.axvline(0%2C%20color%3D%22white%22%2C%20lw%3D2%2C%20ls%3D%22-%22%2C%20alpha%3D0.6%2C%20zorder%3D1)%0A%20%20%20%20%20%20%20%20_ax.text(-2.5%2C%204.0%2C%20%22Cell%20A%22%2C%20fontsize%3D14%2C%20color%3D%22orange%22%2C%20fontweight%3D%22bold%22%2C%20ha%3D%22center%22)%0A%20%20%20%20%20%20%20%20_ax.text(2.5%2C%204.0%2C%20%22Cell%20B%22%2C%20fontsize%3D14%2C%20color%3D%22limegreen%22%2C%20fontweight%3D%22bold%22%2C%20ha%3D%22center%22)%0A%0A%20%20%20%20%20%20%20%20%23%20cell%20A%20points%3A%20always%20scanned%0A%20%20%20%20%20%20%20%20_ax.scatter(_ptsA%5B%3A%2C%200%5D%2C%20_ptsA%5B%3A%2C%201%5D%2C%20c%3D%22dodgerblue%22%2C%20s%3D20%2C%20alpha%3D0.7%2C%20zorder%3D2%2C%20label%3D%22Scanned%20(Cell%20A)%22)%0A%0A%20%20%20%20%20%20%20%20%23%20cell%20B%20points%3A%20scanned%20only%20if%20probed%0A%20%20%20%20%20%20%20%20if%20_probe_b%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.scatter(_ptsB%5B%3A%2C%200%5D%2C%20_ptsB%5B%3A%2C%201%5D%2C%20c%3D%22dodgerblue%22%2C%20s%3D20%2C%20alpha%3D0.7%2C%20zorder%3D2%2C%20label%3D%22Scanned%20(Cell%20B)%22)%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.scatter(_ptsB%5B%3A%2C%200%5D%2C%20_ptsB%5B%3A%2C%201%5D%2C%20c%3D%22gray%22%2C%20s%3D20%2C%20alpha%3D0.3%2C%20zorder%3D2%2C%20label%3D%22Skipped%20(Cell%20B)%22)%0A%0A%20%20%20%20%20%20%20%20%23%20centroids%0A%20%20%20%20%20%20%20%20_ax.scatter(%5B_cA%5B0%5D%5D%2C%20%5B_cA%5B1%5D%5D%2C%20c%3D%22orange%22%2C%20s%3D180%2C%20marker%3D%22D%22%2C%20edgecolors%3D%22white%22%2C%20linewidths%3D1.5%2C%20zorder%3D5)%0A%20%20%20%20%20%20%20%20_ax.annotate(%22Centroid%20A%22%2C%20xy%3D(_cA%5B0%5D%2C%20_cA%5B1%5D)%2C%20xytext%3D(_cA%5B0%5D%20-%200.3%2C%20_cA%5B1%5D%20-%200.8)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D10%2C%20color%3D%22orange%22%2C%20fontweight%3D%22bold%22%2C%20ha%3D%22center%22)%0A%0A%20%20%20%20%20%20%20%20_cb_color%20%3D%20%22dodgerblue%22%20if%20_probe_b%20else%20%22gray%22%0A%20%20%20%20%20%20%20%20_ax.scatter(%5B_cB%5B0%5D%5D%2C%20%5B_cB%5B1%5D%5D%2C%20c%3D_cb_color%2C%20s%3D180%2C%20marker%3D%22D%22%2C%20edgecolors%3D%22white%22%2C%20linewidths%3D1.5%2C%20zorder%3D5)%0A%20%20%20%20%20%20%20%20_ax.annotate(%22Centroid%20B%22%2C%20xy%3D(_cB%5B0%5D%2C%20_cB%5B1%5D)%2C%20xytext%3D(_cB%5B0%5D%20%2B%200.3%2C%20_cB%5B1%5D%20-%200.8)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D10%2C%20color%3D_cb_color%2C%20fontweight%3D%22bold%22%2C%20ha%3D%22center%22)%0A%0A%20%20%20%20%20%20%20%20%23%20lines%20from%20query%20to%20centroids%0A%20%20%20%20%20%20%20%20_ax.plot(%5B_query%5B0%5D%2C%20_cA%5B0%5D%5D%2C%20%5B_query%5B1%5D%2C%20_cA%5B1%5D%5D%2C%20color%3D%22orange%22%2C%20lw%3D2%2C%20ls%3D%22--%22%2C%20zorder%3D3)%0A%20%20%20%20%20%20%20%20_ax.annotate(f%22d%3D%7B_dist_q_cA%3A.2f%7D%22%2C%20xy%3D((_query%5B0%5D%2B_cA%5B0%5D)%2F2%2C%20(_query%5B1%5D%2B_cA%5B1%5D)%2F2%20-%200.3)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D9%2C%20color%3D%22orange%22%2C%20ha%3D%22center%22)%0A%20%20%20%20%20%20%20%20if%20_probe_b%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.plot(%5B_query%5B0%5D%2C%20_cB%5B0%5D%5D%2C%20%5B_query%5B1%5D%2C%20_cB%5B1%5D%5D%2C%20color%3D%22dodgerblue%22%2C%20lw%3D2%2C%20ls%3D%22--%22%2C%20zorder%3D3)%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.annotate(f%22d%3D%7B_dist_q_cB%3A.2f%7D%22%2C%20xy%3D((_query%5B0%5D%2B_cB%5B0%5D)%2F2%2C%20(_query%5B1%5D%2B_cB%5B1%5D)%2F2%20%2B%200.3)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D9%2C%20color%3D%22dodgerblue%22%2C%20ha%3D%22center%22)%0A%0A%20%20%20%20%20%20%20%20%23%20query%0A%20%20%20%20%20%20%20%20_ax.scatter(%5B_query%5B0%5D%5D%2C%20%5B_query%5B1%5D%5D%2C%20c%3D%22red%22%2C%20s%3D300%2C%20marker%3D%22*%22%2C%20edgecolors%3D%22white%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20linewidths%3D1%2C%20zorder%3D7%2C%20label%3D%22Query%22)%0A%0A%20%20%20%20%20%20%20%20%23%20true%20nearest%20neighbour%0A%20%20%20%20%20%20%20%20_nn_color%20%3D%20%22red%22%0A%20%20%20%20%20%20%20%20_ax.scatter(%5B_true_nn%5B0%5D%5D%2C%20%5B_true_nn%5B1%5D%5D%2C%20facecolors%3D%22none%22%2C%20edgecolors%3D_nn_color%2C%20s%3D200%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20linewidths%3D2.5%2C%20zorder%3D6%2C%20label%3Df%22True%20NN%20(d%3D%7B_dist_q_nn%3A.2f%7D)%22)%0A%20%20%20%20%20%20%20%20_ax.plot(%5B_query%5B0%5D%2C%20_true_nn%5B0%5D%5D%2C%20%5B_query%5B1%5D%2C%20_true_nn%5B1%5D%5D%2C%20color%3D_nn_color%2C%20lw%3D1.5%2C%20ls%3D%22%3A%22%2C%20zorder%3D4)%0A%0A%20%20%20%20%20%20%20%20%23%20result%20annotation%0A%20%20%20%20%20%20%20%20if%20_probe_b%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.annotate(%22FOUND%22%2C%20xy%3D(_true_nn%5B0%5D%20%2B%200.3%2C%20_true_nn%5B1%5D%20%2B%200.5)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D14%2C%20color%3D%22limegreen%22%2C%20fontweight%3D%22bold%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20bbox%3Ddict(boxstyle%3D%22round%2Cpad%3D0.2%22%2C%20fc%3D%22%231a1a2e%22%2C%20ec%3D%22limegreen%22))%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.annotate(%22MISSED%22%2C%20xy%3D(_true_nn%5B0%5D%20%2B%200.3%2C%20_true_nn%5B1%5D%20%2B%200.5)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D14%2C%20color%3D%22red%22%2C%20fontweight%3D%22bold%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20bbox%3Ddict(boxstyle%3D%22round%2Cpad%3D0.2%22%2C%20fc%3D%22%231a1a2e%22%2C%20ec%3D%22red%22))%0A%0A%20%20%20%20%20%20%20%20_ax.set_xlim(-5%2C%205)%0A%20%20%20%20%20%20%20%20_ax.set_ylim(-4%2C%205)%0A%20%20%20%20%20%20%20%20_ax.set_facecolor(%22%231a1a2e%22)%0A%20%20%20%20%20%20%20%20_ax.tick_params(colors%3D%22gray%22)%0A%20%20%20%20%20%20%20%20for%20_sp%20in%20_ax.spines.values()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_sp.set_color(%22gray%22)%0A%20%20%20%20%20%20%20%20_ax.set_title(_title%2C%20color%3D%22white%22%2C%20fontsize%3D13%2C%20pad%3D10)%0A%20%20%20%20%20%20%20%20_ax.legend(loc%3D%22lower%20left%22%2C%20facecolor%3D%22%231a1a2e%22%2C%20edgecolor%3D%22white%22%2C%20labelcolor%3D%22white%22%2C%20fontsize%3D8)%0A%0A%20%20%20%20_fig.set_facecolor(%22%231a1a2e%22)%0A%20%20%20%20plt.tight_layout()%0A%20%20%20%20mo.as_html(_fig)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20This%20is%20why%20**n_probe%20%3E%201%20is%20almost%20always%20necessary**.%20A%20single%20probe%20only%20guarantees%20finding%0A%20%20%20%20the%20nearest%20neighbour%20if%20the%20query%20is%20well%20inside%20its%20Voronoi%20cell.%20Near%20boundaries%20--%20which%20is%0A%20%20%20%20where%20most%20interesting%20queries%20land%20in%20high%20dimensions%20--%20neighbours%20leak%20into%20adjacent%20cells.%0A%20%20%20%20Increasing%20n_probe%20plugs%20those%20leaks%20at%20the%20cost%20of%20scanning%20more%20vectors.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A