Permutation Search Methods are Efficient, Yet Faster Search is Possible

Summary: Permutation-based kNN uses pivot-ranked permutations as distance proxies for metric and non-metric spaces. Evaluated against multi-probe LSH, VP-tree, and proximity-graph baselines on large in-memory image/text data, permutation methods show reasonable accuracy and efficiency; code and data released. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11228
Venue: VLDB
Year: 2015
Pagerank: 6.4197336e-05
Overall Rank: 4,970 | 65.91%
DOI: 10.14778/2824032.2824059

Incoming Non-self Citations Over Time

Authors

1. Bilegsaikhan Naidan (Norwegian Institute of Technology)
2. Leonid Boytsov (Carnegie Mellon University)
3. Eric Nyberg (Carnegie Mellon University)

BibTeX Citation

@article{naidan_vldb15,
        title = {{Permutation Search Methods are Efficient, Yet Faster Search is Possible}},
        author = {Naidan, Bilegsaikhan and Boytsov, Leonid and Nyberg, Eric},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {12},
        pages = {1618--1629},
        doi = {10.14778/2824032.2824059},
        url = {https://doi.org/10.14778/2824032.2824059},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
398	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00019194947
3,240	Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art	2025	SIGMOD	7.6071649e-05
10,455	FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044853085
83	H-Store: A High-Performance, Distributed Main Memory Transaction Processing System	2008	VLDB	0.00036185259
690	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.0001492934
990	SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00012796562

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
2	580	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB
3	5,666	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS
4	4,850	Nearest-Neighbor Searching Under Uncertainty	2012	PODS
5	1,546	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB
6	690	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD
7	1,244	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD
8	4,657	Finding Near Neighbors Through Cluster Pruning	2007	PODS
9	10,454	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
10	3,710	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD