Query Processing for Distance Metrics

Summary: Partial precomputation of inter-object distances plus triangle-inequality pruning speeds distance-based queries on large databases. The approach introduces several heuristics, evaluates them experimentally across query types, and shows parallelism mainly helps in later query stages. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7976
Venue: VLDB
Year: 1990
Pagerank: 5.3401202e-05
Overall Rank: 5,756 | 59.96%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Tsong-Li Wang
2. Dennis Shasha

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,433	Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results	1994	SIGMOD	0.00012009649
1,631	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00011078269
5,101	Semantic Queries with Pictures: The VIMSYS Model	1991	VLDB	5.6995265e-05
8,693	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	4.466142e-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
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083378538
76	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057303551
632	The Representation and Deductive Retrieval of Complex Objects	1985	VLDB	0.00018923134
1,034	Redundancy in Spatial Databases	1989	SIGMOD	0.00014534274
1,719	Implementation Techniques of Complex Objects	1986	VLDB	0.00010787268
2,144	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.4416732e-05
6,888	Sorting, Grouping and Duplicate Elimination in the Advanced Information Management Prototype	1989	VLDB	4.8936978e-05
7,226	Efficient Search in Very Large Databases	1988	VLDB	4.7953551e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,346	Multi-objective Query Processing for Database Systems	2004	VLDB	8.9919258e-05
1,755	Efficient User-Adaptable Similarity Search in Large Multimedia Databases	1997	VLDB	0.00010669106
1,403	Efficient Processing of Top-k Spatial Preference Queries	2011	VLDB	0.00012176993
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
3,555	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD	6.9772546e-05
6,082	Query-Sensitive Embeddings	2005	SIGMOD	5.2205711e-05
1,811	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS	0.00010467197
9,143	Similarity Query Processing Using Disk Arrays	1998	SIGMOD	4.3850454e-05
575	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00019882723
5,882	Improving Adaptable Similarity Query Processing by Using Approximations	1998	VLDB	5.2892937e-05