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: h714a3e2cc600ad20
Venue: VLDB
Year: 1990
Pagerank: 6.5492954e-05
Overall Rank: 4,522 | 69.69%
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 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,554	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010236406
1,647	Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results	1994	SIGMOD	9.9747449e-05
5,420	Semantic Queries with Pictures: The VIMSYS Model	1991	VLDB	6.1245865e-05
8,813	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	5.2570736e-05
10,969	Lower-Bound Distance Queries under Partial Information	2026	VLDB	4.9605343e-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
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045231517
102	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00033850505
866	The Representation and Deductive Retrieval of Complex Objects	1985	VLDB	0.00013342501
1,038	Redundancy in Spatial Databases	1989	SIGMOD	0.00012349149
1,915	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.368237e-05
1,933	Implementation Techniques of Complex Objects	1986	VLDB	9.3441192e-05
6,986	Sorting, Grouping and Duplicate Elimination in the Advanced Information Management Prototype	1989	VLDB	5.6115347e-05
7,381	Efficient Search in Very Large Databases	1988	VLDB	5.5226733e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,014	Multi-objective Query Processing for Database Systems	2004	VLDB
2	1,825	Efficient User-Adaptable Similarity Search in Large Multimedia Databases	1997	VLDB
3	1,480	Efficient Processing of Top-k Spatial Preference Queries	2011	VLDB
4	20	Similarity Search in High Dimensions via Hashing	1999	VLDB
5	3,893	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD
6	5,991	Query-Sensitive Embeddings	2005	SIGMOD
7	2,080	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS
8	9,631	Similarity Query Processing Using Disk Arrays	1998	SIGMOD
9	598	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD
10	5,970	Improving Adaptable Similarity Query Processing by Using Approximations	1998	VLDB