Twin Grid Files: Space Optimizing Access Schemes

Summary: Twin Grid Files split a point set across two grids to maximize storage utilization (≈90% vs 69% for standard grid), built with essentially no extra cost. Dynamic version redistributes on insert/delete; range queries remain at least as fast as on the standard grid. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2452
Venue: SIGMOD
Year: 1988
Pagerank: 6.3286498e-05
Overall Rank: 5,183 | 64.45%
DOI: 10.1145/50202.50222

Incoming Non-self Citations Over Time

Authors

1. Andreas Hutflesz (University of Karlsruhe)
2. Hans-Werner Six (Fern University in Hagen)
3. Peter Widmayer (University of Karlsruhe)

BibTeX Citation

@inproceedings{hutflesz_sigmod88,
        title = {{Twin Grid Files: Space Optimizing Access Schemes}},
        author = {Hutflesz, Andreas and Six, Hans-Werner and Widmayer, Peter},
        series = {{SIGMOD} '88},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/50202.50222},
        url = {https://dl.acm.org/doi/10.1145/50202.50222},
        year = {1988}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
873	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013481915
936	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00013092484
1,877	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.5658249e-05
3,771	Query Processing Method for Multi-Attribute Clustered Relations	1990	VLDB	7.1391812e-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.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
1,032	The BANG file: a new kind of grid file	1987	SIGMOD	0.00012530965
1,814	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.6928497e-05
4,357	Balanced Multidimensional Extendible Hash Tree	1986	PODS	6.7463723e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,303	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS
2	5,202	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB
3	6,777	Techniques for Design and Implementation of Efficient Spatial Access Methods	1988	VLDB
4	6,089	Window Query-Optimal Clustering of Spatial Objects	1995	PODS
5	3,972	Tight bounds for 2-dimensional indexing schemes	1998	PODS
6	6,619	(Almost) Optimal Parallel Block Access for Range Queries	2000	PODS
7	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
8	936	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB
9	13,054	Algorithms for Loading Parallel Grid Files	1993	SIGMOD
10	4,978	Efficient Spatial Access To A Data Base	1982	SIGMOD