On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)

Summary: Settles two-dimensional indexability: 3-sided queries with constant redundancy and access overhead; 4-sided schemes achieving optimal redundancy vs access-overhead tradeoff. Provides dynamic external-memory structures: 3-sided optimal bounds (O(N/B) space, O(log_B N) updates, O(log_B N+T/B) queries); 4-sided achieves optimal query I/Os with near-optimal space/update costs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1187
Venue: PODS
Year: 1999
Pagerank: 0.00010482997
Overall Rank: 1,529 | 89.52%
DOI: 10.1145/303976.304010

Incoming Non-self Citations Over Time

Authors

1. Lars Arge (Duke University)
2. Vasilis Samoladas (University of Texas)
3. Jeffrey Scott Vitter (Aarhus University; Duke University; INRIA)

BibTeX Citation

@inproceedings{arge_pods99,
        address = {New York, NY, USA},
        series = {{PODS} '99},
        title = {{On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/303976.304010},
        doi = {10.1145/303976.304010},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Arge, Lars and Samoladas, Vasilis and Vitter, Jeffrey Scott},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
560	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016525569
1,611	Indexing Moving Points (Extended Abstract)	2000	PODS	0.00010218339
2,062	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.24085e-05
3,064	The CompleteSearch Engine: Interactive, Efficient, and Towards IR & DB Integration	2007	CIDR	7.8008109e-05
4,761	Estimating arbitrary subset sums with few probes	2005	PODS	6.5196044e-05
6,491	Two-dimensional Substring Indexing	2001	PODS	5.8641664e-05
7,521	Categorical Range Maxima Queries	2014	PODS	5.6029996e-05
8,173	Dynamic Top-K Range Reporting in External Memory	2012	PODS	5.4740049e-05
8,750	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS	5.3766157e-05
8,937	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	5.3483178e-05
12,163	A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting	2014	PODS	5.093636e-05
12,302	Space-Efficient Range Reporting for Categorical Data	2012	PODS	5.093636e-05
12,303	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS	5.093636e-05
12,489	Worst-Case Efficient Range Search Indexing	2009	PODS	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
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
96	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00034590762
1,512	On the Analysis of Indexing Schemes	1997	PODS	0.00010536001
1,561	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00010361147
2,135	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	9.1133971e-05
3,972	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.9814651e-05
4,730	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS	6.5348792e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,561	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS
2	12,490	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS
3	1,611	Indexing Moving Points (Extended Abstract)	2000	PODS
4	4,730	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS
5	2,003	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS
6	6,160	New Results on Two-dimensional Orthogonal Range Aggregation in External Memory	2011	PODS
7	8,937	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
8	3,972	Tight bounds for 2-dimensional indexing schemes	1998	PODS
9	12,489	Worst-Case Efficient Range Search Indexing	2009	PODS
10	12,303	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS