Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures

Summary: RkNN under arbitrary non-metric dissimilarities, where query-time aggregation over attribute distances defines the distance. Uses AL-Tree for group-level reasoning to prune RkNN, beating naive scans and block-based methods on real and synthetic data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10250
Venue: VLDB
Year: 2010
Pagerank: 5.093636e-05
Overall Rank: 12,463 | 14.50%
DOI: 10.14778/1920841.1920999

Incoming Non-self Citations Over Time

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

Authors

1. Deepak P (IBM)
2. Prasad M Deshpande (IBM)

BibTeX Citation

@article{p_vldb10,
        title = {{Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures}},
        author = {P, Deepak and Deshpande, Prasad M},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        pages = {1243--1254},
        doi = {10.14778/1920841.1920999},
        url = {https://doi.org/10.14778/1920841.1920999},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0020210012
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010828372
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040719947
546	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00016734556
1,612	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010218134
1,847	Efficient Computation of Reverse Skyline Queries	2007	VLDB	9.6252055e-05
1,967	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB	9.3804693e-05
3,710	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	7.1780127e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,259	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD
2	9,163	Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study	2026	SIGMOD
3	28	Nearest Neighbor Queries	1995	SIGMOD
4	9,165	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB
5	690	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD
6	10,454	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
7	3,363	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD
8	6,561	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB
9	1,612	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB
10	3,710	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD