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: 3145
Venue: SIGMOD
Year: 1999
Pagerank: 6.4949956e-05
Overall Rank: 4,815 | 66.97%
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,685	Closest Pair Queries in Spatial Databases	2000	SIGMOD	0.00010017073
2,375	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB	8.6753909e-05
5,932	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	6.0369275e-05
7,744	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	5.5541724e-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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
28	Nearest Neighbor Queries	1995	SIGMOD	0.00052102434
96	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00034590762
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.0003221055
145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029548428
479	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017789732
728	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014542772
994	Spatial Hash-Joins	1996	SIGMOD	0.00012764684
1,517	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00010520118
1,880	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5562066e-05
1,901	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.5068846e-05
2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.7650894e-05
2,548	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB	8.432498e-05
3,066	Size Separation Spatial Join	1997	SIGMOD	7.7941163e-05
3,290	Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees	1995	SIGMOD	7.5531472e-05
7,744	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	5.5541724e-05
9,417	Similarity Query Processing Using Disk Arrays	1998	SIGMOD	5.2740525e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,426	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD
2	1,880	Scalable Sweeping-Based Spatial Join	1998	VLDB
3	522	Multi-Step Processing of Spatial Joins	1994	SIGMOD
4	994	Spatial Hash-Joins	1996	SIGMOD
5	11,141	Optimal (Multiway) Spatial Joins	2024	PODS
6	1,525	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD
7	145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
8	2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD
9	3,066	Size Separation Spatial Join	1997	SIGMOD
10	7,744	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS