A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems

Summary: Generalized framework to reduce expensive distance calls in proximity problems by modeling distance comparisons as linear inequalities. Graph-based solutions plus a practitioner guide; experiments on large real-world datasets demonstrate reduced distance calls. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6193
Venue: SIGMOD
Year: 2021
Pagerank: 4.466142e-05
Overall Rank: 8,693 | 39.53%
DOI: 10.1145/3448016.3457303

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,351	On Efficient Approximate Queries over Machine Learning Models	2023	VLDB	4.3524472e-05

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.0032169493
5	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0018397217
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.0005181666
284	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00028994728
708	Near Neighbor Search in Large Metric Spaces	1995	VLDB	0.00017772684
5,756	Query Processing for Distance Metrics	1990	VLDB	5.3401202e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,467	Fast and Exact Outlier Detection in Metric Spaces: A Proximity Graph-based Approach	2021	SIGMOD	4.1945683e-05
1,542	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011456321
11,554	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	4.1945683e-05
1,768	Closest Pair Queries in Spatial Databases	2000	SIGMOD	0.00010622873
1,183	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS	0.00013455596
4,070	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.4784181e-05
1,811	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS	0.00010467197
10,923	k-Clustering with Comparison and Distance Oracles	2024	PODS	4.1945683e-05
10,165	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1945683e-05
10,007	Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation	2026	PODS	4.1945683e-05