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.5189807e-05
Overall Rank: 7,468 | 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,552	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010275036
6,149	Similarity Join over Array Data	2016	SIGMOD	5.8706665e-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.00045773967
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029061754
264	A Class of Data Structures for Associative Searching	1984	PODS	0.00022757762
364	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00019976696
385	Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases	1995	VLDB	0.0001946565
752	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014246504
994	Spatial Hash-Joins	1996	SIGMOD	0.00012636707
3,120	Size Separation Spatial Join	1997	SIGMOD	7.6300049e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,266	Parallel evaluation of multi-join queries	1995	SIGMOD
2	360	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,059	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD
5	2,136	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
6	6,223	A Forward Scan based Plane Sweep Algorithm for Parallel Interval Joins	2017	VLDB
7	7,348	A Scalable and Generic Approach to Range Joins	2022	VLDB
8	7,293	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS
9	1,292	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD
10	2,464	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS