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.5741203e-05
Overall Rank: 4,501 | 69.74%
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,552	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010275036
1,640	Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results	1994	SIGMOD	0.00010011692
5,399	Semantic Queries with Pictures: The VIMSYS Model	1991	VLDB	6.1478087e-05
8,786	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	5.2768554e-05
10,899	Lower-Bound Distance Queries under Partial Information	2026	VLDB	4.9793485e-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.00045337853
101	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00033937215
863	The Representation and Deductive Retrieval of Complex Objects	1985	VLDB	0.00013392127
1,035	Redundancy in Spatial Databases	1989	SIGMOD	0.00012393393
1,903	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.4032472e-05
1,920	Implementation Techniques of Complex Objects	1986	VLDB	9.3768105e-05
6,964	Sorting, Grouping and Duplicate Elimination in the Advanced Information Management Prototype	1989	VLDB	5.6328172e-05
7,355	Efficient Search in Very Large Databases	1988	VLDB	5.5436083e-05

Semantically Similar Papers

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