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: 8609
Venue: VLDB
Year: 1997
Pagerank: 5.6435709e-05
Overall Rank: 7,326 | 49.74%
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,525	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010493702
6,157	Similarity Join over Array Data	2016	SIGMOD	5.9554363e-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
41	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00046675394
145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029548428
253	A Class of Data Structures for Associative Searching	1984	PODS	0.00023200431
354	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00020355578
371	Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases	1995	VLDB	0.00019869565
728	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014542772
994	Spatial Hash-Joins	1996	SIGMOD	0.00012764684
3,066	Size Separation Spatial Join	1997	SIGMOD	7.7941163e-05

Semantically Similar Papers

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