PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search

Summary: PM-LSH uses a PM-tree index with a tunable confidence interval to enable fast, accurate c-ANN in high dimensions. An efficient algorithm atop the PM-tree prunes candidates and improves speed and accuracy over prior LSH. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hb505d0c4ae3c4bdb
Venue: VLDB
Year: 2020
Pagerank: 0.00010558941
Overall Rank: 1,460 | 90.22%
DOI: 10.14778/3377369.3377374
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Bolong Zheng (Huazhong University of Science and Technology)
2. Xi Zhao (Huazhong University of Science and Technology)
3. Lianggui Weng (Huazhong University of Science and Technology)
4. Nguyen Quoc Viet Hung (Griffith University)
5. Hang Liu (Stevens Institute of Technology)
6. Christian S. Jensen (Aalborg University)

BibTeX Citation

@article{zheng_vldb20,
        title = {{PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search}},
        author = {Zheng, Bolong and Zhao, Xi and Weng, Lianggui and Hung, Nguyen Quoc Viet and Liu, Hang and Jensen, Christian S.},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {5},
        pages = {643--655},
        doi = {10.14778/3377369.3377374},
        url = {https://doi.org/10.14778/3377369.3377374},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 29 of 29 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
181	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.00026425782
802	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.00013822222
1,229	ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data	2024	SIGMOD	0.00011420277
1,280	Manu: A Cloud Native Vector Database Management System	2022	VLDB	0.00011199537
1,318	VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning	2020	VLDB	0.00011035606
1,601	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	0.00010092977
1,618	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	0.00010045437
1,797	SingleStore-V: An Integrated Vector Database System in SingleStore	2024	VLDB	9.6056634e-05
3,244	Similarity Query Processing for High-Dimensional Data	2020	VLDB	7.479122e-05
4,157	Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes	2024	VLDB	6.7596305e-05
4,368	UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search	2025	VLDB	6.6237291e-05
5,227	Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere	2021	SIGMOD	6.2080477e-05
5,294	FARGO: Fast Maximum Inner Product Search via Global Multi-Probing	2023	VLDB	6.1780995e-05
5,526	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	6.0804398e-05
6,256	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB	5.8162066e-05
7,121	A New Sparse Data Clustering Method Based On Frequent Items	2023	SIGMOD	5.580601e-05
7,286	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	5.5493084e-05
7,358	Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-based ANN Index Updates	2025	VLDB	5.5288758e-05
7,719	VSAG: An Optimized Search Framework for Graph-based Approximate Nearest Neighbor Search	2025	VLDB	5.4543461e-05
8,392	MicroNN: An On-device Disk-resident Updatable Vector Database	2025	SIGMOD	5.3246348e-05
10,128	Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-based ANN Search	2025	VLDB	5.0615166e-05
10,356	Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search	2026	SIGMOD	5.0156513e-05
10,538	GEM: A Native Graph-based Index for Multi-Vector Retrieval	2026	SIGMOD	4.9605343e-05
10,586	TaCo: Data-adaptive and Query-aware Subspace Collision for High-dimensional Approximate Nearest Neighbor Search	2026	SIGMOD	4.9605343e-05
10,768	SVFusion: A CPU-GPU Co-Processing Architecture for Large-Scale Real-Time Vector Search	2026	VLDB	4.9605343e-05
10,780	Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search	2026	VLDB	4.9605343e-05
11,118	Elastic Index Selection for Label-Hybrid AKNN Search	2026	VLDB	4.9605343e-05
11,968	ONe Index for All Kernels (ONIAK): A Zero Re-Indexing LSH Solution to ANNS-ALT (After Linear Transformation)	2022	VLDB	4.9605343e-05
12,085	MP-RW-LSH: An Efficient Multi-Probe LSH Solution to ANNS-L1	2021	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011386412
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00057610161
281	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.00022262975
286	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00022090962
339	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00020558018
562	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016344855
578	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016079505
987	Bayesian Locality Sensitive Hashing for Fast Similarity Search	2012	VLDB	0.00012643645
1,524	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	0.0001033427
2,080	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS	9.058838e-05
2,369	Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing	2013	VLDB	8.5487072e-05
2,570	Locality-Sensitive Hashing for Earthquake Detection: A Case Study of Scaling Data-Driven Science	2018	VLDB	8.2599759e-05
3,187	Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond	2017	VLDB	7.538584e-05
3,552	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD	7.1888282e-05
6,971	Searching Web Data using MinHash LSH	2016	SIGMOD	5.615257e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,524	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD
2	2,501	DSH: Data Sensitive Hashing for High-Dimensional k-NN Search	2014	SIGMOD
3	562	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB
4	2,968	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD
5	925	SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB
6	286	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB
7	5,526	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB
8	339	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD
9	578	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD
10	1,618	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB