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: h5eaea4944ee67bcf
Venue: SIGMOD
Year: 1992
Pagerank: 8.8556449e-05
Overall Rank: 2,205 | 85.18%
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
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029061754
926	On Indexing Mobile Objects	1999	PODS	0.00013047723
1,589	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00010139591
1,922	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.3751198e-05
5,905	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB	5.9509027e-05
5,963	Spatial Indexing in Microsoft SQL Server 2008	2008	SIGMOD	5.9330399e-05
6,145	V-Trees - A Storage Method for Long Vector Data	1994	VLDB	5.8717297e-05
6,418	Performance of Data-Parallel Spatial Operations	1994	VLDB	5.7907247e-05
8,960	The Impact of Global Clustering on Spatial Database Systems	1994	VLDB	5.249844e-05
11,652	LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization	2024	VLDB	4.9793485e-05
13,155	Analyzing Energy Behavior of Spatial Access Methods for Memory-Resident Data	2001	VLDB	4.9793485e-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.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0008122792
264	A Class of Data Structures for Associative Searching	1984	PODS	0.00022757762
1,035	Redundancy in Spatial Databases	1989	SIGMOD	0.00012393393
1,861	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.4871409e-05
4,716	On Indexing Line Segments	1990	VLDB	6.4554004e-05
7,412	A Population Analysis for Hierarchical Data Structures	1987	SIGMOD	5.5342698e-05

Semantically Similar Papers

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