Parallel Algorithms for High-dimensional Proximity Joins

Summary: Proposes a parallel multidimensional proximity-join using the epsilon-kdB tree, with empirical comparison to space-partitioning approaches. Demonstrates scalable performance on a shared-nothing IBM SP2, handles data skew, and applies to time-series similarity mining. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: ha1f83a55fc0fdd4a
Venue: VLDB
Year: 1997
Pagerank: 5.4981344e-05
Overall Rank: 7,491 | 49.79%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. John C. Shafer (International Business Machines (IBM))
2. Rakesh Agrawal (International Business Machines (IBM))

BibTeX Citation

@article{shafer_vldb97,
        title = {{Parallel Algorithms for High-dimensional Proximity Joins}},
        author = {Shafer, John C. and Agrawal, Rakesh},
        journal = {PVLDB},
        series = {{VLDB} '97},
        pages = {176--185},
        year = {1997}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,554	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010236406
6,168	Similarity Join over Array Data	2016	SIGMOD	5.8484846e-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	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00045609336
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.000289618
267	A Class of Data Structures for Associative Searching	1984	PODS	0.00022688423
363	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00019931086
386	Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases	1995	VLDB	0.00019396455
760	Partition Based Spatial-Merge Join	1996	SIGMOD	0.0001419395
999	Spatial Hash-Joins	1996	SIGMOD	0.00012590189
3,131	Size Separation Spatial Join	1997	SIGMOD	7.6016052e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,280	Parallel evaluation of multi-join queries	1995	SIGMOD
2	359	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD
3	2,886	Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment	2021	VLDB
4	3,072	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD
5	2,151	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
6	6,238	A Forward Scan based Plane Sweep Algorithm for Parallel Interval Joins	2017	VLDB
7	7,373	A Scalable and Generic Approach to Range Joins	2022	VLDB
8	7,313	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS
9	1,296	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD
10	2,475	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS