MP-RW-LSH: An Efficient Multi-Probe LSH Solution to ANNS-L1

Summary: MP-RW-LSH is the first multi-probe LSH for ANNS under L1, delivering improved scalability and query efficiency over prior LSH methods. CP-LSH is shown unsuitable for multi-probe extension, and the framework enables ANNS-E (edit distance) that surpasses the state of the art. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12726
Venue: VLDB
Year: 2021
Pagerank: 5.093636e-05
Overall Rank: 11,732 | 19.51%
DOI: 10.14778/3484224.3484226

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Huayi Wang (Georgia Institute of Technology)
2. Jingfan Meng (Georgia Institute of Technology)
3. Long Gong (Meta)
4. Jun Xu (Georgia Institute of Technology)
5. Mitsunori Ogihara (University of Miami)

BibTeX Citation

@article{wang_vldb21,
        title = {{MP-RW-LSH: An Efficient Multi-Probe LSH Solution to ANNS-L1}},
        author = {Wang, Huayi and Meng, Jingfan and Gong, Long and Xu, Jun and Ogihara, Mitsunori},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {13},
        pages = {3267--3280},
        doi = {10.14778/3484224.3484226},
        url = {https://doi.org/10.14778/3484224.3484226},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
93	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034701237
287	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.00022323585
369	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00019945234
581	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016153395
991	Bayesian Locality Sensitive Hashing for Fast Similarity Search	2012	VLDB	0.00012793339
1,546	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	0.00010407159
1,572	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	0.00010329197
2,010	iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search	2020	VLDB	9.3085202e-05
3,279	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	7.5711218e-05
4,112	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.8944534e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,666	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS
2	1,572	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD
3	5,800	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB
4	990	SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB
5	1,546	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB
6	3,389	Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond	2017	VLDB
7	1,934	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB
8	3,279	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD
9	332	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB
10	287	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB