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: 7977
Venue: VLDB
Year: 1990
Pagerank: 5.3396192e-05
Overall Rank: 5,751 | 60.04%
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,432	Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results	1994	SIGMOD	0.00012000371
1,605	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00011180126
5,100	Semantic Queries with Pictures: The VIMSYS Model	1991	VLDB	5.6940372e-05
8,687	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	4.4621895e-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.00083300888
75	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057450043
637	The Representation and Deductive Retrieval of Complex Objects	1985	VLDB	0.00018812264
1,035	Redundancy in Spatial Databases	1989	SIGMOD	0.00014524981
1,714	Implementation Techniques of Complex Objects	1986	VLDB	0.00010777308
2,144	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.4375327e-05
6,890	Sorting, Grouping and Duplicate Elimination in the Advanced Information Management Prototype	1989	VLDB	4.8892941e-05
7,225	Efficient Search in Very Large Databases	1988	VLDB	4.7910249e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,351	Multi-objective Query Processing for Database Systems	2004	VLDB	8.9836468e-05
1,755	Efficient User-Adaptable Similarity Search in Large Multimedia Databases	1997	VLDB	0.00010661725
1,317	Efficient Processing of Top-k Spatial Preference Queries	2011	VLDB	0.00012615781
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076824554
3,549	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD	6.9792126e-05
6,077	Query-Sensitive Embeddings	2005	SIGMOD	5.2203422e-05
1,808	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS	0.00010476269
9,173	Similarity Query Processing Using Disk Arrays	1998	SIGMOD	4.3807204e-05
574	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.0001987713
5,889	Improving Adaptable Similarity Query Processing by Using Approximations	1998	VLDB	5.2842168e-05