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: 6255
Venue: SIGMOD
Year: 2021
Pagerank: 5.3577837e-05
Overall Rank: 8,848 | 39.30%
DOI: 10.1145/3448016.3457303

Incoming Non-self Citations Over Time

Authors

1. Jees Augustine (University of Texas Arlington)
2. Suraj Shetiya (University of Texas Arlington)
3. Mohammadreza Esfandiari (New Jersey Institute of Technology)
4. Senjuti Basu Roy (New Jersey Institute of Technology)
5. Gautam Das (University of Texas Arlington)

BibTeX Citation

@inproceedings{augustine_sigmod21,
        title = {{A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems}},
        author = {Augustine, Jees and Shetiya, Suraj and Esfandiari, Mohammadreza and Roy, Senjuti Basu and Das, Gautam},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3457303},
        url = {https://dl.acm.org/doi/10.1145/3448016.3457303},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,353	On Efficient Approximate Queries over Machine Learning Models	2023	VLDB	5.2829539e-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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.00082404462
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040719947
277	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00022537944
784	Near Neighbor Search in Large Metric Spaces	1995	VLDB	0.00014069958
5,798	Query Processing for Distance Metrics	1990	VLDB	6.0856815e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,634	Fast and Exact Outlier Detection in Metric Spaces: A Proximity Graph-based Approach	2021	SIGMOD
2	1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
3	11,751	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS
4	1,685	Closest Pair Queries in Spatial Databases	2000	SIGMOD
5	1,137	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS
6	3,710	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
7	2,101	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS
8	11,143	k-Clustering with Comparison and Distance Oracles	2024	PODS
9	10,454	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
10	10,179	Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation	2026	PODS