How Locality Sensitive Hashing Works

%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%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(%0A%20%20%20%20width%3D%22medium%22%2C%0A%20%20%20%20app_title%3D%22How%20Locality%20Sensitive%20Hashing%20Works%22%2C%0A)%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%20Locality%20Sensitive%20Hashing%20Works%0A%0A%20%20%20%20Finding%20the%20nearest%20neighbours%20in%20a%20set%20of%20%24N%24%20vectors%20each%20of%20dimension%20%24d%24%0A%20%20%20%20costs%20%24O(Nd)%24%20with%20a%20brute-force%20scan.%20Locality%20Sensitive%20Hashing%20(LSH)%20trades%0A%20%20%20%20exact%20results%20for%20approximate%20ones%2C%20hashing%20vectors%20so%20that%20**nearby%20points%20are%0A%20%20%20%20likely%20to%20collide**%20and%20distant%20points%20are%20not.%20The%20result%20is%20**sub-linear%20query%0A%20%20%20%20time**%20--%20you%20only%20compare%20against%20a%20small%20candidate%20set%20instead%20of%20the%20whole%20database.%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%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Parameters%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%20k_slider%20%3D%20mo.ui.slider(1%2C%2020%2C%20value%3D8%2C%20step%3D1%2C%20label%3D%22k%20(hash%20functions%20per%20table)%22%2C%20show_value%3DTrue)%0A%20%20%20%20L_slider%20%3D%20mo.ui.slider(1%2C%2030%2C%20value%3D10%2C%20step%3D1%2C%20label%3D%22L%20(number%20of%20tables)%22%2C%20show_value%3DTrue)%0A%20%20%20%20N_slider%20%3D%20mo.ui.slider(100%2C%205000%2C%20value%3D1000%2C%20step%3D100%2C%20label%3D%22N%20(database%20vectors)%22%2C%20show_value%3DTrue)%0A%20%20%20%20d_slider%20%3D%20mo.ui.slider(2%2C%20128%2C%20value%3D2%2C%20step%3D1%2C%20label%3D%22d%20(dimensions)%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(%5Bk_slider%2C%20L_slider%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.vstack(%5BN_slider%2C%20d_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%20L_slider%2C%20N_slider%2C%20k_slider%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%20Random%20Hyperplane%20Hashing%0A%0A%20%20%20%20In%202D%20a%20%22hyperplane%22%20is%20just%20a%20line%20through%20the%20origin.%20Each%20random%20line%20splits%20the%20plane%0A%20%20%20%20into%20two%20half-planes.%20Every%20point%20gets%20a%20hash%20**bit**%3A%200%20or%201%20depending%20on%20which%20side%20it%0A%20%20%20%20falls%20on.%20With%20%24k%24%20random%20lines%20the%20space%20is%20carved%20into%20up%20to%20%242%5Ek%24%20**buckets**%20--%20points%0A%20%20%20%20in%20the%20same%20bucket%20share%20all%20%24k%24%20bits.%0A%0A%20%20%20%20Use%20the%20slider%20below%20to%20add%20more%20hyperplanes%20and%20watch%20the%20partition%20refine.%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%20k_vis_slider%20%3D%20mo.ui.slider(1%2C%206%2C%20value%3D3%2C%20step%3D1%2C%20label%3D%22k%20(hyperplanes)%22%2C%20show_value%3DTrue)%0A%20%20%20%20k_vis_slider%0A%20%20%20%20return%20(k_vis_slider%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(k_vis_slider%2C%20mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20_rng%20%3D%20np.random.default_rng(42)%0A%20%20%20%20_n_pts%20%3D%2020%0A%20%20%20%20_pts%20%3D%20_rng.standard_normal((_n_pts%2C%202))%0A%0A%20%20%20%20_k%20%3D%20k_vis_slider.value%0A%20%20%20%20_normals%20%3D%20_rng.standard_normal((_k%2C%202))%0A%20%20%20%20_normals%20%3D%20_normals%20%2F%20np.linalg.norm(_normals%2C%20axis%3D1%2C%20keepdims%3DTrue)%0A%0A%20%20%20%20%23%20compute%20hash%20bucket%20for%20each%20point%3A%20tuple%20of%20bits%0A%20%20%20%20_signs%20%3D%20(_pts%20%40%20_normals.T%20%3E%3D%200).astype(int)%20%20%23%20(n_pts%2C%20k)%0A%20%20%20%20_bucket_ids%20%3D%20np.array(%5Bint(%22%22.join(str(b)%20for%20b%20in%20row)%2C%202)%20for%20row%20in%20_signs%5D)%0A%0A%20%20%20%20%23%20assign%20a%20colour%20to%20each%20unique%20bucket%0A%20%20%20%20_unique%20%3D%20np.unique(_bucket_ids)%0A%20%20%20%20_cmap%20%3D%20plt.cm.tab20(np.linspace(0%2C%201%2C%20max(len(_unique)%2C%201)))%0A%20%20%20%20_bucket_color%20%3D%20%7Bb%3A%20_cmap%5Bi%5D%20for%20i%2C%20b%20in%20enumerate(_unique)%7D%0A%20%20%20%20_colors%20%3D%20%5B_bucket_color%5Bb%5D%20for%20b%20in%20_bucket_ids%5D%0A%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(8%2C%208))%0A%20%20%20%20_ax.set_aspect(%22equal%22)%0A%0A%20%20%20%20%23%20draw%20hyperplane%20lines%20(extend%20across%20the%20visible%20region)%0A%20%20%20%20_lim%20%3D%20np.abs(_pts).max()%20%2B%201.0%0A%20%20%20%20for%20_i%20in%20range(_k)%3A%0A%20%20%20%20%20%20%20%20_n%20%3D%20_normals%5B_i%5D%0A%20%20%20%20%20%20%20%20%23%20line%20perpendicular%20to%20normal%3A%20direction%20is%20(-ny%2C%20nx)%0A%20%20%20%20%20%20%20%20_d%20%3D%20np.array(%5B-_n%5B1%5D%2C%20_n%5B0%5D%5D)%0A%20%20%20%20%20%20%20%20_p1%20%3D%20_d%20*%20_lim%0A%20%20%20%20%20%20%20%20_p2%20%3D%20-_d%20*%20_lim%0A%20%20%20%20%20%20%20%20_ax.plot(%5B_p1%5B0%5D%2C%20_p2%5B0%5D%5D%2C%20%5B_p1%5B1%5D%2C%20_p2%5B1%5D%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22white%22%2C%20lw%3D1.5%2C%20alpha%3D0.6%2C%20ls%3D%22--%22)%0A%20%20%20%20%20%20%20%20%23%20label%20the%20hyperplane%20with%20its%20normal%20direction%0A%20%20%20%20%20%20%20%20_label_pos%20%3D%20_n%20*%20(_lim%20*%200.85)%0A%20%20%20%20%20%20%20%20_ax.annotate(f%22h%7B_i%2B1%7D%22%2C%20xy%3D_label_pos%2C%20fontsize%3D10%2C%20color%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%20ha%3D%22center%22%2C%20va%3D%22center%22%2C%0A%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.15%22%2C%20fc%3D%22%231a1a2e%22%2C%20ec%3D%22white%22%2C%20alpha%3D0.8))%0A%0A%20%20%20%20%23%20draw%20points%20coloured%20by%20bucket%0A%20%20%20%20_ax.scatter(_pts%5B%3A%2C%200%5D%2C%20_pts%5B%3A%2C%201%5D%2C%20c%3D_colors%2C%20s%3D120%2C%20edgecolors%3D%22white%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20linewidths%3D0.8%2C%20zorder%3D5)%0A%0A%20%20%20%20%23%20label%20each%20point%20with%20its%20bucket%20id%0A%20%20%20%20for%20_i%20in%20range(_n_pts)%3A%0A%20%20%20%20%20%20%20%20_ax.annotate(f%22%7B_bucket_ids%5B_i%5D%3A0%7B_k%7Db%7D%22%2C%20xy%3D(_pts%5B_i%2C%200%5D%2C%20_pts%5B_i%2C%201%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xytext%3D(5%2C%205)%2C%20textcoords%3D%22offset%20points%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D7%2C%20color%3D%22white%22%2C%20alpha%3D0.8)%0A%0A%20%20%20%20_ax.set_xlim(-_lim%2C%20_lim)%0A%20%20%20%20_ax.set_ylim(-_lim%2C%20_lim)%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_xlabel(%22x%22%2C%20color%3D%22gray%22)%0A%20%20%20%20_ax.set_ylabel(%22y%22%2C%20color%3D%22gray%22)%0A%20%20%20%20_ax.set_title(%0A%20%20%20%20%20%20%20%20f%22%7B_k%7D%20hyperplane(s)%20create%20up%20to%20%7B2**_k%7D%20buckets%20--%20%7Blen(_unique)%7D%20occupied%20here%22%2C%0A%20%20%20%20%20%20%20%20color%3D%22white%22%2C%20fontsize%3D12%2C%20pad%3D12%2C%0A%20%20%20%20)%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%20Collision%20Probability%0A%0A%20%20%20%20For%20a%20random%20hyperplane%20through%20the%20origin%2C%20two%20vectors%20collide%20(land%20on%20the%20same%20side)%0A%20%20%20%20with%20probability%0A%0A%20%20%20%20%24%24P(%5Ctext%7Bsame%20bit%7D)%20%3D%201%20-%20%5Cfrac%7B%5Ctheta%7D%7B%5Cpi%7D%24%24%0A%0A%20%20%20%20where%20%24%5Ctheta%24%20is%20the%20angle%20between%20them.%20The%20plot%20below%20overlays%20this%20theoretical%20curve%0A%20%20%20%20with%20an%20empirical%20simulation%3A%20for%20each%20angle%20we%20generate%201000%20random%20hyperplanes%20and%0A%20%20%20%20measure%20the%20actual%20collision%20rate.%20The%20two%20curves%20should%20match%20closely.%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%20%20%20%20_n_trials%20%3D%201000%0A%20%20%20%20_angles_deg%20%3D%20np.linspace(0%2C%20180%2C%2037)%0A%20%20%20%20_angles_rad%20%3D%20np.deg2rad(_angles_deg)%0A%0A%20%20%20%20%23%20theoretical%0A%20%20%20%20_p_theory%20%3D%201.0%20-%20_angles_rad%20%2F%20np.pi%0A%0A%20%20%20%20%23%20empirical%3A%20for%20each%20angle%2C%20create%20a%20pair%20of%20unit%20vectors%20at%20that%20angle%2C%0A%20%20%20%20%23%20then%20test%20against%20random%20hyperplanes%0A%20%20%20%20_p_empirical%20%3D%20np.zeros_like(_angles_deg)%0A%20%20%20%20_hyperplanes%20%3D%20_rng.standard_normal((_n_trials%2C%202))%0A%20%20%20%20_hyperplanes%20%3D%20_hyperplanes%20%2F%20np.linalg.norm(_hyperplanes%2C%20axis%3D1%2C%20keepdims%3DTrue)%0A%0A%20%20%20%20_v1%20%3D%20np.array(%5B1.0%2C%200.0%5D)%0A%20%20%20%20for%20_i%2C%20_ang%20in%20enumerate(_angles_rad)%3A%0A%20%20%20%20%20%20%20%20_v2%20%3D%20np.array(%5Bnp.cos(_ang)%2C%20np.sin(_ang)%5D)%0A%20%20%20%20%20%20%20%20_hash1%20%3D%20(_hyperplanes%20%40%20_v1)%20%3E%3D%200%0A%20%20%20%20%20%20%20%20_hash2%20%3D%20(_hyperplanes%20%40%20_v2)%20%3E%3D%200%0A%20%20%20%20%20%20%20%20_p_empirical%5B_i%5D%20%3D%20np.mean(_hash1%20%3D%3D%20_hash2)%0A%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(9%2C%205))%0A%0A%20%20%20%20_ax.plot(_angles_deg%2C%20_p_theory%2C%20color%3D%22cyan%22%2C%20lw%3D2.5%2C%20label%3Dr%22Theory%3A%20%241%20-%20%5Ctheta%2F%5Cpi%24%22)%0A%20%20%20%20_ax.scatter(_angles_deg%2C%20_p_empirical%2C%20color%3D%22tomato%22%2C%20s%3D30%2C%20zorder%3D5%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20label%3Df%22Empirical%20(%7B_n_trials%7D%20hyperplanes)%22)%0A%0A%20%20%20%20_ax.set_xlabel(%22Angle%20between%20vectors%20(degrees)%22%2C%20color%3D%22gray%22)%0A%20%20%20%20_ax.set_ylabel(%22P(same%20hash%20bit)%22%2C%20color%3D%22gray%22)%0A%20%20%20%20_ax.set_title(%22Collision%20probability%20vs.%20angle%22%2C%20color%3D%22white%22%2C%20fontsize%3D12%2C%20pad%3D12)%0A%20%20%20%20_ax.legend(fontsize%3D10%2C%20facecolor%3D%22%231a1a2e%22%2C%20edgecolor%3D%22gray%22%2C%20labelcolor%3D%22white%22)%0A%20%20%20%20_ax.set_xlim(0%2C%20180)%0A%20%20%20%20_ax.set_ylim(-0.05%2C%201.05)%0A%0A%20%20%20%20%23%20reference%20lines%0A%20%20%20%20_ax.axhline(0.5%2C%20color%3D%22gray%22%2C%20ls%3D%22%3A%22%2C%20lw%3D0.8%2C%20alpha%3D0.5)%0A%20%20%20%20_ax.axvline(90%2C%20color%3D%22gray%22%2C%20ls%3D%22%3A%22%2C%20lw%3D0.8%2C%20alpha%3D0.5)%0A%20%20%20%20_ax.annotate(%2290%5Cu00b0%20%5Cu2192%20P%20%3D%200.5%22%2C%20xy%3D(92%2C%200.52)%2C%20fontsize%3D9%2C%20color%3D%22gray%22)%0A%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%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%20Amplification%3A%20k%20and%20L%0A%0A%20%20%20%20A%20single%20hash%20bit%20barely%20separates%20neighbours%20from%20non-neighbours.%20LSH%20amplifies%0A%20%20%20%20the%20gap%20with%20two%20knobs%3A%0A%0A%20%20%20%20-%20**k**%20hash%20functions%20per%20table%20--%20a%20candidate%20must%20match%20on%20**all%20k**%20bits%2C%20so%20the%0A%20%20%20%20%20%20per-table%20collision%20probability%20drops%20to%20%24p%5Ek%24.%20This%20makes%20the%20S-curve%20**steeper**%0A%20%20%20%20%20%20(better%20at%20discriminating%20close%20vs.%20far).%0A%20%20%20%20-%20**L**%20independent%20tables%20--%20a%20candidate%20is%20returned%20if%20it%20matches%20in%20**any**%20table%2C%0A%20%20%20%20%20%20giving%20overall%20probability%20%241%20-%20(1%20-%20p%5Ek)%5EL%24.%20This%20shifts%20the%20curve%20**right**%0A%20%20%20%20%20%20(better%20recall%20for%20true%20neighbours).%0A%0A%20%20%20%20The%20dashed%20lines%20mark%20a%20%22true%20neighbour%22%20at%20%24p_1%20%3D%200.85%24%20and%20a%20%22false%20neighbour%22%20at%0A%20%20%20%20%24p_2%20%3D%200.3%24.%20Watch%20how%20tuning%20k%20and%20L%20opens%20the%20gap%20between%20their%20detection%20rates.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(L_slider%2C%20k_slider%2C%20mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20_k%20%3D%20k_slider.value%0A%20%20%20%20_L%20%3D%20L_slider.value%0A%20%20%20%20_p%20%3D%20np.linspace(0%2C%201%2C%20500)%0A%20%20%20%20_overall%20%3D%201.0%20-%20(1.0%20-%20_p**_k)**_L%0A%0A%20%20%20%20_p1%20%3D%200.85%20%20%23%20true%20neighbour%20collision%20prob%0A%20%20%20%20_p2%20%3D%200.30%20%20%23%20false%20neighbour%20collision%20prob%0A%20%20%20%20_y1%20%3D%201.0%20-%20(1.0%20-%20_p1**_k)**_L%0A%20%20%20%20_y2%20%3D%201.0%20-%20(1.0%20-%20_p2**_k)**_L%0A%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(9%2C%206))%0A%0A%20%20%20%20_ax.plot(_p%2C%20_overall%2C%20color%3D%22cyan%22%2C%20lw%3D2.5%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20label%3Drf%22%241%20-%20(1%20-%20p%5E%7B%7B%7B_k%7D%7D%7D)%5E%7B%7B%7B_L%7D%7D%7D%24%22)%0A%0A%20%20%20%20%23%20reference%20lines%20for%20true%20neighbour%0A%20%20%20%20_ax.axvline(_p1%2C%20color%3D%22tomato%22%2C%20ls%3D%22--%22%2C%20lw%3D1.2%2C%20alpha%3D0.7)%0A%20%20%20%20_ax.axhline(_y1%2C%20color%3D%22tomato%22%2C%20ls%3D%22--%22%2C%20lw%3D1.2%2C%20alpha%3D0.7)%0A%20%20%20%20_ax.plot(_p1%2C%20_y1%2C%20%22o%22%2C%20color%3D%22tomato%22%2C%20ms%3D8%2C%20zorder%3D5)%0A%20%20%20%20_ax.annotate(f%22true%20neighbour%5Cnp%3D%7B_p1%7D%2C%20detected%3D%7B_y1%3A.3f%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xy%3D(_p1%2C%20_y1)%2C%20xytext%3D(_p1%20-%200.25%2C%20_y1%20-%200.15)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D10%2C%20color%3D%22tomato%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arrowprops%3Ddict(arrowstyle%3D%22-%3E%22%2C%20color%3D%22tomato%22%2C%20lw%3D1.2)%2C%0A%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%22tomato%22%2C%20alpha%3D0.9))%0A%0A%20%20%20%20%23%20reference%20lines%20for%20false%20neighbour%0A%20%20%20%20_ax.axvline(_p2%2C%20color%3D%22goldenrod%22%2C%20ls%3D%22--%22%2C%20lw%3D1.2%2C%20alpha%3D0.7)%0A%20%20%20%20_ax.axhline(_y2%2C%20color%3D%22goldenrod%22%2C%20ls%3D%22--%22%2C%20lw%3D1.2%2C%20alpha%3D0.7)%0A%20%20%20%20_ax.plot(_p2%2C%20_y2%2C%20%22o%22%2C%20color%3D%22goldenrod%22%2C%20ms%3D8%2C%20zorder%3D5)%0A%20%20%20%20_ax.annotate(f%22false%20neighbour%5Cnp%3D%7B_p2%7D%2C%20detected%3D%7B_y2%3A.4f%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xy%3D(_p2%2C%20_y2)%2C%20xytext%3D(_p2%20%2B%200.08%2C%20_y2%20%2B%200.15)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D10%2C%20color%3D%22goldenrod%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arrowprops%3Ddict(arrowstyle%3D%22-%3E%22%2C%20color%3D%22goldenrod%22%2C%20lw%3D1.2)%2C%0A%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%22goldenrod%22%2C%20alpha%3D0.9))%0A%0A%20%20%20%20_ax.set_xlabel(r%22Single-bit%20collision%20probability%20%24p%24%22%2C%20color%3D%22gray%22)%0A%20%20%20%20_ax.set_ylabel(%22Overall%20candidate%20probability%22%2C%20color%3D%22gray%22)%0A%20%20%20%20_ax.set_title(%0A%20%20%20%20%20%20%20%20f%22Amplification%20curve%3A%20k%3D%7B_k%7D%2C%20L%3D%7B_L%7D%20%20%7C%20%20%22%0A%20%20%20%20%20%20%20%20f%22true%3D%7B_y1%3A.3f%7D%2C%20false%3D%7B_y2%3A.4f%7D%22%2C%0A%20%20%20%20%20%20%20%20color%3D%22white%22%2C%20fontsize%3D12%2C%20pad%3D12%2C%0A%20%20%20%20)%0A%20%20%20%20_ax.legend(fontsize%3D11%2C%20facecolor%3D%22%231a1a2e%22%2C%20edgecolor%3D%22gray%22%2C%20labelcolor%3D%22white%22%2C%20loc%3D%22upper%20left%22)%0A%20%20%20%20_ax.set_xlim(0%2C%201)%0A%20%20%20%20_ax.set_ylim(-0.05%2C%201.05)%0A%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%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%20Full%20LSH%20Demo%0A%0A%20%20%20%20Below%20we%20generate%20%24N%24%20random%202D%20points%20and%20pick%20a%20query%20point.%20LSH%20builds%20%24L%24%20hash%20tables%2C%0A%20%20%20%20each%20with%20%24k%24%20random%20hyperplanes.%20The%20**candidate%20set**%20(blue)%20contains%20every%20point%20that%0A%20%20%20%20shares%20a%20bucket%20with%20the%20query%20in%20at%20least%20one%20table.%20The%20**true%20top-10**%20nearest%20neighbours%0A%20%20%20%20are%20shown%20in%20red.%20Notice%20how%20LSH%20finds%20most%20true%20neighbours%20while%20scanning%20only%20a%20fraction%0A%20%20%20%20of%20the%20database.%0A%0A%20%20%20%20Move%20the%20query%20point%20with%20the%20sliders%20below.%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%20qx_slider%20%3D%20mo.ui.slider(-3.0%2C%203.0%2C%20value%3D0.0%2C%20step%3D0.1%2C%20label%3D%22Query%20x%22%2C%20show_value%3DTrue)%0A%20%20%20%20qy_slider%20%3D%20mo.ui.slider(-3.0%2C%203.0%2C%20value%3D0.0%2C%20step%3D0.1%2C%20label%3D%22Query%20y%22%2C%20show_value%3DTrue)%0A%20%20%20%20mo.hstack(%5Bqx_slider%2C%20qy_slider%5D%2C%20gap%3D2)%0A%20%20%20%20return%20qx_slider%2C%20qy_slider%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(L_slider%2C%20N_slider%2C%20k_slider%2C%20mo%2C%20np%2C%20plt%2C%20qx_slider%2C%20qy_slider)%3A%0A%20%20%20%20_rng%20%3D%20np.random.default_rng(123)%0A%20%20%20%20_N%20%3D%20N_slider.value%0A%20%20%20%20_k%20%3D%20k_slider.value%0A%20%20%20%20_L%20%3D%20L_slider.value%0A%20%20%20%20_top_k%20%3D%2010%0A%0A%20%20%20%20_db%20%3D%20_rng.standard_normal((_N%2C%202))%0A%20%20%20%20_query%20%3D%20np.array(%5Bqx_slider.value%2C%20qy_slider.value%5D)%0A%0A%20%20%20%20%23%20build%20L%20hash%20tables%2C%20each%20with%20k%20random%20hyperplanes%0A%20%20%20%20_candidates%20%3D%20set()%0A%20%20%20%20for%20_t%20in%20range(_L)%3A%0A%20%20%20%20%20%20%20%20_normals%20%3D%20_rng.standard_normal((_k%2C%202))%0A%20%20%20%20%20%20%20%20_normals%20%3D%20_normals%20%2F%20np.linalg.norm(_normals%2C%20axis%3D1%2C%20keepdims%3DTrue)%0A%0A%20%20%20%20%20%20%20%20%23%20hash%20all%20database%20points%0A%20%20%20%20%20%20%20%20_db_hashes%20%3D%20(_db%20%40%20_normals.T%20%3E%3D%200).astype(int)%20%20%23%20(N%2C%20k)%0A%20%20%20%20%20%20%20%20_query_hash%20%3D%20(_query%20%40%20_normals.T%20%3E%3D%200).astype(int)%20%20%23%20(k%2C)%0A%0A%20%20%20%20%20%20%20%20%23%20find%20points%20in%20the%20same%20bucket%20as%20the%20query%20(all%20k%20bits%20match)%0A%20%20%20%20%20%20%20%20_match%20%3D%20np.all(_db_hashes%20%3D%3D%20_query_hash%2C%20axis%3D1)%0A%20%20%20%20%20%20%20%20_candidates.update(np.where(_match)%5B0%5D)%0A%0A%20%20%20%20_candidates%20%3D%20np.array(sorted(_candidates))%20if%20_candidates%20else%20np.array(%5B%5D%2C%20dtype%3Dint)%0A%0A%20%20%20%20%23%20true%20nearest%20neighbours%20(brute%20force)%0A%20%20%20%20_dists%20%3D%20np.linalg.norm(_db%20-%20_query%2C%20axis%3D1)%0A%20%20%20%20_true_top%20%3D%20np.argsort(_dists)%5B%3A_top_k%5D%0A%0A%20%20%20%20%23%20recall%3A%20what%20fraction%20of%20true%20top-10%20are%20in%20the%20candidate%20set%3F%0A%20%20%20%20_recall%20%3D%20np.isin(_true_top%2C%20_candidates).sum()%20%2F%20_top_k%20if%20len(_candidates)%20%3E%200%20else%200.0%0A%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(9%2C%208))%0A%20%20%20%20_ax.set_aspect(%22equal%22)%0A%0A%20%20%20%20%23%20all%20points%20in%20gray%0A%20%20%20%20_ax.scatter(_db%5B%3A%2C%200%5D%2C%20_db%5B%3A%2C%201%5D%2C%20c%3D%22gray%22%2C%20s%3D10%2C%20alpha%3D0.3%2C%20label%3D%22Database%22)%0A%0A%20%20%20%20%23%20candidates%20in%20blue%0A%20%20%20%20if%20len(_candidates)%20%3E%200%3A%0A%20%20%20%20%20%20%20%20_ax.scatter(_db%5B_candidates%2C%200%5D%2C%20_db%5B_candidates%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20c%3D%22dodgerblue%22%2C%20s%3D25%2C%20alpha%3D0.6%2C%20edgecolors%3D%22none%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20label%3Df%22Candidates%20(%7Blen(_candidates)%7D)%22)%0A%0A%20%20%20%20%23%20true%20top-k%20in%20red%20(drawn%20on%20top)%0A%20%20%20%20_ax.scatter(_db%5B_true_top%2C%200%5D%2C%20_db%5B_true_top%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20c%3D%22tomato%22%2C%20s%3D60%2C%20edgecolors%3D%22white%22%2C%20linewidths%3D0.8%2C%20zorder%3D6%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20label%3Df%22True%20top-%7B_top_k%7D%22)%0A%0A%20%20%20%20%23%20query%20point%20as%20a%20star%0A%20%20%20%20_ax.scatter(_query%5B0%5D%2C%20_query%5B1%5D%2C%20marker%3D%22*%22%2C%20c%3D%22lime%22%2C%20s%3D250%2C%20edgecolors%3D%22white%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20linewidths%3D1.0%2C%20zorder%3D7%2C%20label%3D%22Query%22)%0A%0A%20%20%20%20%23%20draw%20circles%20around%20true%20top-k%20that%20were%20found%20by%20LSH%0A%20%20%20%20_found_mask%20%3D%20np.isin(_true_top%2C%20_candidates)%0A%20%20%20%20for%20_i%2C%20_idx%20in%20enumerate(_true_top)%3A%0A%20%20%20%20%20%20%20%20if%20_found_mask%5B_i%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.scatter(_db%5B_idx%2C%200%5D%2C%20_db%5B_idx%2C%201%5D%2C%20facecolors%3D%22none%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%20edgecolors%3D%22lime%22%2C%20s%3D150%2C%20lw%3D1.5%2C%20zorder%3D5)%0A%0A%20%20%20%20_pct%20%3D%20100.0%20*%20len(_candidates)%20%2F%20_N%20if%20_N%20%3E%200%20else%200.0%0A%20%20%20%20_ax.set_title(%0A%20%20%20%20%20%20%20%20f%22Scanned%20%7Blen(_candidates)%7D%2F%7B_N%7D%20candidates%20(%7B_pct%3A.1f%7D%25%20of%20database)%2C%20%22%0A%20%20%20%20%20%20%20%20f%22recall%20%7B_recall%3A.0%25%7D%22%2C%0A%20%20%20%20%20%20%20%20color%3D%22white%22%2C%20fontsize%3D12%2C%20pad%3D12%2C%0A%20%20%20%20)%0A%20%20%20%20_ax.legend(fontsize%3D10%2C%20facecolor%3D%22%231a1a2e%22%2C%20edgecolor%3D%22gray%22%2C%20labelcolor%3D%22white%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20loc%3D%22upper%20right%22)%0A%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_xlabel(%22x%22%2C%20color%3D%22gray%22)%0A%20%20%20%20_ax.set_ylabel(%22y%22%2C%20color%3D%22gray%22)%0A%0A%20%20%20%20_lim%20%3D%20max(np.abs(_db).max()%2C%20np.abs(_query).max())%20%2B%200.5%0A%20%20%20%20_ax.set_xlim(-_lim%2C%20_lim)%0A%20%20%20%20_ax.set_ylim(-_lim%2C%20_lim)%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_(L_slider%2C%20N_slider%2C%20k_slider%2C%20mo%2C%20np%2C%20qx_slider%2C%20qy_slider)%3A%0A%20%20%20%20%23%20recompute%20stats%20for%20the%20callout%20box%20(mirrors%20the%20cell%20above%2C%20lightweight)%0A%20%20%20%20_rng%20%3D%20np.random.default_rng(123)%0A%20%20%20%20_N%20%3D%20N_slider.value%0A%20%20%20%20_k%20%3D%20k_slider.value%0A%20%20%20%20_L%20%3D%20L_slider.value%0A%20%20%20%20_top_k%20%3D%2010%0A%0A%20%20%20%20_db%20%3D%20_rng.standard_normal((_N%2C%202))%0A%20%20%20%20_query%20%3D%20np.array(%5Bqx_slider.value%2C%20qy_slider.value%5D)%0A%0A%20%20%20%20_candidates%20%3D%20set()%0A%20%20%20%20for%20_t%20in%20range(_L)%3A%0A%20%20%20%20%20%20%20%20_normals%20%3D%20_rng.standard_normal((_k%2C%202))%0A%20%20%20%20%20%20%20%20_normals%20%3D%20_normals%20%2F%20np.linalg.norm(_normals%2C%20axis%3D1%2C%20keepdims%3DTrue)%0A%20%20%20%20%20%20%20%20_db_hashes%20%3D%20(_db%20%40%20_normals.T%20%3E%3D%200).astype(int)%0A%20%20%20%20%20%20%20%20_query_hash%20%3D%20(_query%20%40%20_normals.T%20%3E%3D%200).astype(int)%0A%20%20%20%20%20%20%20%20_match%20%3D%20np.all(_db_hashes%20%3D%3D%20_query_hash%2C%20axis%3D1)%0A%20%20%20%20%20%20%20%20_candidates.update(np.where(_match)%5B0%5D)%0A%0A%20%20%20%20_candidates%20%3D%20np.array(sorted(_candidates))%20if%20_candidates%20else%20np.array(%5B%5D%2C%20dtype%3Dint)%0A%20%20%20%20_dists%20%3D%20np.linalg.norm(_db%20-%20_query%2C%20axis%3D1)%0A%20%20%20%20_true_top%20%3D%20np.argsort(_dists)%5B%3A_top_k%5D%0A%20%20%20%20_recall%20%3D%20np.isin(_true_top%2C%20_candidates).sum()%20%2F%20_top_k%20if%20len(_candidates)%20%3E%200%20else%200.0%0A%20%20%20%20_pct%20%3D%20100.0%20*%20len(_candidates)%20%2F%20_N%20if%20_N%20%3E%200%20else%200.0%0A%0A%20%20%20%20mo.md(rf%22%22%22%0A%20%20%20%20%3E%20**Stats%3A**%20Scanned%20**%7Blen(_candidates)%7D**%20%2F%20%7B_N%7D%20candidates%20(**%7B_pct%3A.1f%7D%25**%20of%20database)%2C%20recall%20**%7B_recall%3A.0%25%7D**%0A%20%20%20%20%3E%0A%20%20%20%20%3E%20k%20%3D%20%7B_k%7D%20hash%20functions%20per%20table%2C%20L%20%3D%20%7B_L%7D%20tables.%0A%20%20%20%20%3E%20Green%20circles%20mark%20true%20top-%7B_top_k%7D%20neighbours%20that%20LSH%20successfully%20found.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%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%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%20mo%2C%20np%2C%20plt%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A