Integration of Spatial Join Algorithms for Processing Multiple Inputs

Summary: Proposes slot index spatial join (SISJ) for a two-input join where only one input is indexed by an R-tree. Extends SISJ and spatial joins to multiway in-DB operators; studies relational vs. spatial multiway joins; offers a DP-based plan optimizer. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hcc2f2641cfc561bd
Venue: SIGMOD
Year: 1999
Pagerank: 6.3503189e-05
Overall Rank: 4,927 | 66.88%
DOI: 10.1145/304182.304183

Incoming Non-self Citations Over Time

Authors

1. Nikos Mamoulis (Hong Kong University of Science and Technology)
2. Dimitris Papadias (Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{mamoulis_sigmod99,
        title = {{Integration of Spatial Join Algorithms for Processing Multiple Inputs}},
        author = {Mamoulis, Nikos and Papadias, Dimitris},
        series = {{SIGMOD} '99},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/304182.304183},
        url = {https://dl.acm.org/doi/10.1145/304182.304183},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,719	Closest Pair Queries in Spatial Databases	2000	SIGMOD	9.7976056e-05
2,421	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB	8.4897323e-05
6,052	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	5.9028248e-05
7,904	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	5.4295914e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
28	Nearest Neighbor Queries	1995	SIGMOD	0.00051312804
101	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00033937215
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00031645463
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029061754
487	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017462723
752	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014246504
994	Spatial Hash-Joins	1996	SIGMOD	0.00012636707
1,546	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00010294163
1,922	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.3751198e-05
1,956	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.3169059e-05
2,358	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.5817166e-05
2,588	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB	8.2518251e-05
3,120	Size Separation Spatial Join	1997	SIGMOD	7.6300049e-05
3,347	Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees	1995	SIGMOD	7.3933163e-05
7,904	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	5.4295914e-05
9,597	Similarity Query Processing Using Disk Arrays	1998	SIGMOD	5.1557462e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,540	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD
2	1,922	Scalable Sweeping-Based Spatial Join	1998	VLDB
3	527	Multi-Step Processing of Spatial Joins	1994	SIGMOD
4	994	Spatial Hash-Joins	1996	SIGMOD
5	1,552	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD
6	11,489	Optimal (Multiway) Spatial Joins	2024	PODS
7	146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
8	2,358	Spatial Joins Using Seeded Trees	1994	SIGMOD
9	3,120	Size Separation Spatial Join	1997	SIGMOD
10	7,904	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS