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: 11040
Venue: VLDB
Year: 2015
Pagerank: 5.5529869e-05
Overall Rank: 5,352 | 62.77%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
770	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00016917602
4,731	Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art	2025	SIGMOD	5.966659e-05
10,166	FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1945683e-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
79	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056242144
137	H-Store: A High-Performance, Distributed Main Memory Transaction Processing System	2008	VLDB	0.00042342967
709	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00017768547
1,229	SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00013157271

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,542	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011456321
867	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00015792021
8,763	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS	4.456315e-05
4,724	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	5.9697823e-05
2,181	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	9.3451821e-05
709	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00017768547
2,023	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	9.7544991e-05
4,090	Finding Near Neighbors Through Cluster Pruning	2007	PODS	6.4577834e-05
10,165	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1945683e-05
4,070	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.4784181e-05