A Qualitative Comparison Study of Data Structures for Large Line Segment Databases

Summary: Qualitative comparison of R*-tree, R+-tree, and PMR quadtree for large line-segment databases (TIGER/Line). Shows comparability and delineates when and why their disk I/O, storage, and query performance differ for point, window, nearest-segment, and enclosing-polygon tasks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2650
Venue: SIGMOD
Year: 1992
Pagerank: 9.0469646e-05
Overall Rank: 2,168 | 85.13%
DOI: 10.1145/130283.130316

Incoming Non-self Citations Over Time

Authors

1. Erik G. Hoel (United States Census Bureau)
2. Hanan Samet (University of Maryland)

BibTeX Citation

@inproceedings{hoel_sigmod92,
        title = {{A Qualitative Comparison Study of Data Structures for Large Line Segment Databases}},
        author = {Hoel, Erik G. and Samet, Hanan},
        series = {{SIGMOD} '92},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/130283.130316},
        url = {https://dl.acm.org/doi/10.1145/130283.130316},
        year = {1992}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029548428
896	On Indexing Mobile Objects	1999	PODS	0.0001334014
1,561	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00010361147
1,880	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5562066e-05
5,795	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB	6.0859946e-05
5,857	Spatial Indexing in Microsoft SQL Server 2008	2008	SIGMOD	6.0644613e-05
6,025	V-Trees - A Storage Method for Long Vector Data	1994	VLDB	6.002739e-05
6,298	Performance of Data-Parallel Spatial Operations	1994	VLDB	5.9227722e-05
8,796	The Impact of Global Clustering on Spatial Database Systems	1994	VLDB	5.3702721e-05
11,334	LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization	2024	VLDB	5.093636e-05
12,865	Analyzing Energy Behavior of Spatial Access Methods for Memory-Resident Data	2001	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.00082404462
253	A Class of Data Structures for Associative Searching	1984	PODS	0.00023200431
1,019	Redundancy in Spatial Databases	1989	SIGMOD	0.00012622386
1,814	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.6928497e-05
4,620	On Indexing Line Segments	1990	VLDB	6.6025691e-05
7,262	A Population Analysis for Hierarchical Data Structures	1987	SIGMOD	5.6612247e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
2	2,776	Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data	1991	SIGMOD
3	6,298	Performance of Data-Parallel Spatial Operations	1994	VLDB
4	2,421	Multidimensional Access Methods: Trees Have Grown Everywhere	1997	VLDB
5	96	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD
6	1,814	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD
7	9,887	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB
8	2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD
9	5,795	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB
10	3,217	Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data	2002	SIGMOD