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: 8167
Venue: VLDB
Year: 1990
Pagerank: 6.0856815e-05
Overall Rank: 5,798 | 60.23%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Tsong-Li Wang (New York University)
2. Dennis Shasha (New York University)

BibTeX Citation

@article{wang_vldb90,
        title = {{Query Processing for Distance Metrics}},
        author = {Wang, Tsong-Li and Shasha, Dennis},
        journal = {PVLDB},
        series = {{VLDB} '90},
        pages = {602--613},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,525	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010493702
1,603	Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results	1994	SIGMOD	0.00010236342
5,273	Semantic Queries with Pictures: The VIMSYS Model	1991	VLDB	6.2888624e-05
8,848	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	5.3577837e-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
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
96	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00034590762
848	The Representation and Deductive Retrieval of Complex Objects	1985	VLDB	0.00013651467
1,019	Redundancy in Spatial Databases	1989	SIGMOD	0.00012622386
1,877	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.5658249e-05
1,882	Implementation Techniques of Complex Objects	1986	VLDB	9.5505879e-05
6,996	Sorting, Grouping and Duplicate Elimination in the Advanced Information Management Prototype	1989	VLDB	5.7301343e-05
7,342	Efficient Search in Very Large Databases	1988	VLDB	5.6386997e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,932	Multi-objective Query Processing for Database Systems	2004	VLDB
2	1,776	Efficient User-Adaptable Similarity Search in Large Multimedia Databases	1997	VLDB
3	1,441	Efficient Processing of Top-k Spatial Preference Queries	2011	VLDB
4	21	Similarity Search in High Dimensions via Hashing	1999	VLDB
5	3,866	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD
6	5,909	Query-Sensitive Embeddings	2005	SIGMOD
7	2,101	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS
8	9,417	Similarity Query Processing Using Disk Arrays	1998	SIGMOD
9	592	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD
10	5,838	Improving Adaptable Similarity Query Processing by Using Approximations	1998	VLDB