Redundancy in Spatial Databases

Summary: Redundancy in spatial indexes: storing objects redundantly in z-order to boost accuracy and reduce disk I/O. There is an optimal redundancy level; accuracy rises with redundancy but shows diminishing returns; analyzes z-order search and experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2512
Venue: SIGMOD
Year: 1989
Pagerank: 0.00012622386
Overall Rank: 1,019 | 93.02%
DOI: 10.1145/67544.66954

Incoming Non-self Citations Over Time

Authors

1. Jack A. Orenstein (Object Design, Inc.)

BibTeX Citation

@inproceedings{orenstein_sigmod89,
        title = {{Redundancy in Spatial Databases}},
        author = {Orenstein, Jack A.},
        series = {{SIGMOD} '89},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/67544.66954},
        url = {https://dl.acm.org/doi/10.1145/67544.66954},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029548428
354	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00020355578
728	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014542772
994	Spatial Hash-Joins	1996	SIGMOD	0.00012764684
1,880	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5562066e-05
2,168	A Qualitative Comparison Study of Data Structures for Large Line Segment Databases	1992	SIGMOD	9.0469646e-05
2,249	A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces	1990	SIGMOD	8.8700017e-05
2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.7650894e-05
4,070	Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension	1996	VLDB	6.9272604e-05
4,620	On Indexing Line Segments	1990	VLDB	6.6025691e-05
5,798	Query Processing for Distance Metrics	1990	VLDB	6.0856815e-05
5,888	Clustering Techniques for Minimizing External Path Length	1996	VLDB	6.0498293e-05
5,912	Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data	1995	PODS	6.0442093e-05
8,003	Towards Designing and Learning Piecewise Space-Filling Curves	2023	VLDB	5.5084586e-05
8,061	Raster Intervals: An Approximation Technique for Polygon Intersection Joins	2023	SIGMOD	5.4953977e-05
8,796	The Impact of Global Clustering on Spatial Database Systems	1994	VLDB	5.3702721e-05
12,690	Efficient Query Processing on Unstructured Tetrahedral Meshes	2006	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 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
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.00082404462
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
96	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00034590762
253	A Class of Data Structures for Associative Searching	1984	PODS	0.00023200431

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,104	Spatial Priority Search: An Access Technique for Scaleless Maps	1991	SIGMOD
2	522	Multi-Step Processing of Spatial Joins	1994	SIGMOD
3	3,703	Approximation Techniques for Spatial Data	2004	SIGMOD
4	6,777	Techniques for Design and Implementation of Efficient Spatial Access Methods	1988	VLDB
5	96	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD
6	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
7	8,796	The Impact of Global Clustering on Spatial Database Systems	1994	VLDB
8	3,972	Tight bounds for 2-dimensional indexing schemes	1998	PODS
9	1,512	On the Analysis of Indexing Schemes	1997	PODS
10	2,249	A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces	1990	SIGMOD