Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees

Summary: Studies how topological relations emerge from projections of Minimum Bounding Rectangles, quantifying MBR-revealed info about enclosed objects. Applies to R-trees, R+-trees, and R*-trees to minimize disk I/Os for complex spatial queries (conjunctions/disjunctions) and outlines extensions. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h7e1a383108795a56
Venue: SIGMOD
Year: 1995
Pagerank: 7.3899839e-05
Overall Rank: 3,346 | 77.52%
DOI: 10.1145/223784.223798

Incoming Non-self Citations Over Time

Authors

1. Dimitris Papadias (University of California San Diego)
2. Yannis Theodoridis (National Technical University of Athens)
3. Timos Sellis (National Technical University of Athens)
4. Max J. Egenhofer (University of Maine)

BibTeX Citation

@inproceedings{papadias_sigmod95,
        title = {{Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees}},
        author = {Papadias, Dimitris and Theodoridis, Yannis and Sellis, Timos and Egenhofer, Max J.},
        series = {{SIGMOD} '95},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/223784.223798},
        url = {https://dl.acm.org/doi/10.1145/223784.223798},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
207	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00024976482
1,405	A Model for the Prediction of R-tree Performance	1996	PODS	0.00010759378
2,422	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB	8.4857212e-05
3,254	Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data	2002	SIGMOD	7.487573e-05
3,429	SVQ: Streaming Video Queries	2019	SIGMOD	7.3032345e-05
3,761	Approximation Techniques for Spatial Data	2004	SIGMOD	7.0403969e-05
4,928	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.3473148e-05
5,965	Spatial Indexing in Microsoft SQL Server 2008	2008	SIGMOD	5.9302348e-05
13,240	Algorithms for Querying by Spatial Structure	1998	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 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.0019923528
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011402175
28	Nearest Neighbor Queries	1995	SIGMOD	0.00051292389
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045319457
527	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00016874202
7,509	Reasoning about Spatial Relationships in Picture Retrieval Systems	1994	VLDB	5.5048473e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,659	Time-Parameterized Queries in Spatio-Temporal Databases	2002	SIGMOD
2	1,862	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD
3	11,495	Optimal (Multiway) Spatial Joins	2024	PODS
4	1,721	Closest Pair Queries in Spatial Databases	2000	SIGMOD
5	7,500	Boosting Spatial Pruning: On Optimal Pruning of MBRs	2010	SIGMOD
6	459	Query Processing in Spatial Network Databases	2003	VLDB
7	4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD
8	2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD
9	7,908	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS
10	146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD