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: 2450
Venue: SIGMOD
Year: 1989
Pagerank: 0.00014534274
Overall Rank: 1,034 | 92.81%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Jack A. Orenstein

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
148	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041182766
290	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00028919734
925	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015264328
1,174	Spatial Hash-Joins	1996	SIGMOD	0.00013486418
1,997	A Qualitative Comparison Study of Data Structures for Large Line Segment Databases	1992	SIGMOD	9.8322994e-05
2,094	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5547223e-05
2,472	A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces	1990	SIGMOD	8.7237893e-05
2,672	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.3363695e-05
3,527	Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension	1996	VLDB	7.0073154e-05
4,547	On Indexing Line Segments	1990	VLDB	6.0986695e-05
5,196	Clustering Techniques for Minimizing External Path Length	1996	VLDB	5.6365164e-05
5,461	Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data	1995	PODS	5.4947899e-05
5,756	Query Processing for Distance Metrics	1990	VLDB	5.3401202e-05
8,263	Raster Intervals: An Approximation Technique for Polygon Intersection Joins	2023	SIGMOD	4.5464722e-05
8,405	Towards Designing and Learning Piecewise Space-Filling Curves	2023	VLDB	4.5224126e-05
8,601	The Impact of Global Clustering on Spatial Database Systems	1994	VLDB	4.4875358e-05
12,497	Efficient Query Processing on Unstructured Tetrahedral Meshes	2006	SIGMOD	4.1945683e-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.0032169493
5	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0018397217
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083378538
76	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057303551
216	A Class of Data Structures for Associative Searching	1984	PODS	0.00033542705

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,810	Spatial Priority Search: An Access Technique for Scaleless Maps	1991	SIGMOD	4.4442316e-05
478	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.0002222104
3,543	Approximation Techniques for Spatial Data	2004	SIGMOD	6.9917053e-05
6,571	Techniques for Design and Implementation of Efficient Spatial Access Methods	1988	VLDB	5.0061936e-05
76	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057303551
1,182	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013455963
8,601	The Impact of Global Clustering on Spatial Database Systems	1994	VLDB	4.4875358e-05
3,900	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.6518011e-05
1,488	On the Analysis of Indexing Schemes	1997	PODS	0.00011699446
2,472	A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces	1990	SIGMOD	8.7237893e-05