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.00010535847
Overall Rank: 1,481 | 90.05%
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
189	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.0002585319
803	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.00013838349
1,225	ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data	2024	SIGMOD	0.00011447937
1,325	VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning	2020	VLDB	0.00011016872
1,456	Manu: A Cloud Native Vector Database Management System	2022	VLDB	0.00010588868
1,600	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	0.00010111099
1,618	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	0.00010053127
1,979	SingleStore-V: An Integrated Vector Database System in SingleStore	2024	VLDB	9.271804e-05
3,232	Similarity Query Processing for High-Dimensional Data	2020	VLDB	7.5029541e-05
4,347	UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search	2025	VLDB	6.6457039e-05
4,600	Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes	2024	VLDB	6.5055567e-05
5,222	Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere	2021	SIGMOD	6.2205593e-05
5,274	FARGO: Fast Maximum Inner Product Search via Global Multi-Probing	2023	VLDB	6.1985959e-05
5,530	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	6.0907372e-05
6,244	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB	5.8355024e-05
7,098	A New Sparse Data Clustering Method Based On Frequent Items	2023	SIGMOD	5.5991152e-05
7,267	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	5.5677188e-05
7,337	Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-based ANN Index Updates	2025	VLDB	5.5472184e-05
7,706	VSAG: An Optimized Search Framework for Graph-based Approximate Nearest Neighbor Search	2025	VLDB	5.4724414e-05
8,376	MicroNN: An On-device Disk-resident Updatable Vector Database	2025	SIGMOD	5.3422998e-05
10,094	Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-based ANN Search	2025	VLDB	5.0783086e-05
10,330	Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search	2026	SIGMOD	5.0322912e-05
10,472	GEM: A Native Graph-based Index for Multi-Vector Retrieval	2026	SIGMOD	4.9769913e-05
10,520	TaCo: Data-adaptive and Query-aware Subspace Collision for High-dimensional Approximate Nearest Neighbor Search	2026	SIGMOD	4.9769913e-05
10,707	SVFusion: A CPU-GPU Co-Processing Architecture for Large-Scale Real-Time Vector Search	2026	VLDB	4.9769913e-05
10,719	Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search	2026	VLDB	4.9769913e-05
11,057	Elastic Index Selection for Label-Hybrid AKNN Search	2026	VLDB	4.9769913e-05
11,924	ONe Index for All Kernels (ONIAK): A Zero Re-Indexing LSH Solution to ANNS-ALT (After Linear Transformation)	2022	VLDB	4.9769913e-05
12,041	MP-RW-LSH: An Efficient Multi-Probe LSH Solution to ANNS-L1	2021	VLDB	4.9769913e-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.0011402175
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.0005758001
278	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.00022310642
297	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00021849337
338	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00020600264
562	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016350316
576	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016118297
990	Bayesian Locality Sensitive Hashing for Fast Similarity Search	2012	VLDB	0.00012643446
1,527	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	0.00010350688
2,077	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS	9.0758123e-05
2,363	Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing	2013	VLDB	8.572554e-05
2,568	Locality-Sensitive Hashing for Earthquake Detection: A Case Study of Scaling Data-Driven Science	2018	VLDB	8.2839378e-05
3,221	Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond	2017	VLDB	7.5144104e-05
3,546	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD	7.209991e-05
6,957	Searching Web Data using MinHash LSH	2016	SIGMOD	5.6320332e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,527	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,955	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD
5	927	SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB
6	297	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB
7	5,530	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB
8	338	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD
9	576	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