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: 2451
Venue: SIGMOD
Year: 1989
Pagerank: 0.00014524981
Overall Rank: 1,035 | 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
147	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041201518
290	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00028845557
923	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015254021
1,174	Spatial Hash-Joins	1996	SIGMOD	0.00013490827
2,001	A Qualitative Comparison Study of Data Structures for Large Line Segment Databases	1992	SIGMOD	9.8275076e-05
2,119	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5036401e-05
2,471	A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces	1990	SIGMOD	8.7158825e-05
2,673	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.3323551e-05
3,528	Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension	1996	VLDB	7.0033241e-05
4,544	On Indexing Line Segments	1990	VLDB	6.0939082e-05
5,194	Clustering Techniques for Minimizing External Path Length	1996	VLDB	5.6318244e-05
5,469	Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data	1995	PODS	5.4895279e-05
5,751	Query Processing for Distance Metrics	1990	VLDB	5.3396192e-05
8,089	Towards Designing and Learning Piecewise Space-Filling Curves	2023	VLDB	4.5855593e-05
8,260	Raster Intervals: An Approximation Technique for Polygon Intersection Joins	2023	SIGMOD	4.5421134e-05
8,599	The Impact of Global Clustering on Spatial Database Systems	1994	VLDB	4.4832771e-05
12,506	Efficient Query Processing on Unstructured Tetrahedral Meshes	2006	SIGMOD	4.1905499e-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.0032118946
5	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0018380955
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888
75	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057450043
217	A Class of Data Structures for Associative Searching	1984	PODS	0.00033533621

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,810	Spatial Priority Search: An Access Technique for Scaleless Maps	1991	SIGMOD	4.4399995e-05
479	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00022182486
3,540	Approximation Techniques for Spatial Data	2004	SIGMOD	6.9922652e-05
6,569	Techniques for Design and Implementation of Efficient Spatial Access Methods	1988	VLDB	5.0017701e-05
75	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057450043
1,183	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013444058
8,599	The Impact of Global Clustering on Spatial Database Systems	1994	VLDB	4.4832771e-05
3,902	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.6454492e-05
1,485	On the Analysis of Indexing Schemes	1997	PODS	0.00011698762
2,471	A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces	1990	SIGMOD	8.7158825e-05