Pith. sign in

REVIEW 4 cited by

Learning Space Partitions for Nearest Neighbor Search

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1901.08544 v4 pith:SMQ2H2S3 submitted 2019-01-24 cs.LG cs.CGcs.DSstat.ML

Yihe Dong , Piotr Indyk , Ilya Razenshteyn , Tal Wagner This is my paper · ORCID
classification cs.LGcs.CGcs.DSstat.ML
keywords partitionsneuralspacegeneralgraphnearestneighborpartitioning
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
abstract

Space partitions of $\mathbb{R}^d$ underlie a vast and important class of fast nearest neighbor search (NNS) algorithms. Inspired by recent theoretical work on NNS for general metric spaces [Andoni, Naor, Nikolov, Razenshteyn, Waingarten STOC 2018, FOCS 2018], we develop a new framework for building space partitions reducing the problem to balanced graph partitioning followed by supervised classification. We instantiate this general approach with the KaHIP graph partitioner [Sanders, Schulz SEA 2013] and neural networks, respectively, to obtain a new partitioning procedure called Neural Locality-Sensitive Hashing (Neural LSH). On several standard benchmarks for NNS, our experiments show that the partitions obtained by Neural LSH consistently outperform partitions found by quantization-based and tree-based methods as well as classic, data-oblivious LSH.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. (Learned) Frequency Estimation Algorithms under Zipfian Distribution

    cs.DS 2019-08 conditional novelty 7.0 of 10

    Under Zipfian frequencies, Count-Min's expected error is Θ(k log(kn/B)/B), Count-Sketch gets its first nearly tight bounds, and learned Count-Sketch achieves Θ(1/B).

  2. Cluster with Auctions for Vector Search

    cs.IR 2026-07 conditional novelty 6.0 of 10

    CwA jointly learns a balanced database partition and a query-adapted neural probing function, achieving up to 4.7x higher ANNS throughput at equal recall.

  3. Inference-time sparse attention with asymmetric indexing

    cs.CL 2025-02 conditional novelty 6.0 of 10

    Saap approximates attention by clustering keys with k-means and learning a query classifier, reducing KV-cache lookups about 20x at 4-5% selectivity with small accuracy loss on several long-context benchmarks.

  4. On Storage Neural Network Augmented Approximate Nearest Neighbor Search

    cs.LG 2025-01 conditional novelty 6.0 of 10

    A neural network that predicts the correct cluster for a query, combined with duplicated cluster assignment, reduces storage reads in approximate nearest neighbor search.

Pith tools