Research map / Learning theory and algorithms / Prediction and decision losses
Sublinear Time Nearest Neighbor Search over Generalized Weighted Space
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use S2-ALSH (spherical asymmetric transform + SRP) instead of SL-ALSH (spherical transform + E2LSH) | NNS over generalized weighted space · Mnist, Sift, MovieLens ranking experiments | precision-recall for top-10 NNs | Helped |
| Increase U from π/4 to π in the spherical transform (ablation) | SL-ALSH and S2-ALSH · Sift, binary and normal w | precision-recall | Helped |
| Increase number of hash functions K from 128 to 512 (ablation) | SL-ALSH and S2-ALSH · Sift, binary and normal w | precision-recall | Helped |
| Use the spherical SRP-based scheme vs E2LSH on identical weights | S2-ALSH vs E2LSH · Mnist and Sift bucketing, identical w | fraction to scan at recall | No clear effect |
| Use asymmetric transform (SL/S2-ALSH) instead of plain E2LSH on identical weights | SL-ALSH, S2-ALSH vs E2LSH · MovieLens ranking and bucketing | precision-recall and fraction to scan | Hurt |
| Sublinear bucketing with S2-ALSH/SL-ALSH vs linear scan | SL-ALSH and S2-ALSH · Mnist and Sift, identical/binary/uniform w | fraction of dataset scanned: one to two orders of magnitude | Helped |
Closest papers by meaning
- Falconn++: A Locality-sensitive Filtering Approach for Approximate Nearest Neighbor Search (NeurIPS 2022 · similarity 0.89)
- Learning to Hash Robustly, Guaranteed (ICML 2022 · similarity 0.87)
- SAH: Shifting-Aware Asymmetric Hashing for Reverse k Maximum Inner Product Search (AAAI 2023 · similarity 0.87)
- An algorithm for L1 nearest neighbor search via monotonic embedding (NeurIPS 2016 · similarity 0.86)
- Fast k-Nearest Neighbour Search via Prioritized DCI (ICML 2017 · similarity 0.86)
- Re-randomized Densification for One Permutation Hashing and Bin-wise Consistent Weighted Sampling (NeurIPS 2019 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.