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: hf5a28b2212b1a345
Venue: PODS
Year: 1999
Pagerank: 0.00010252232
Overall Rank: 1,559 | 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
574	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016173068
1,646	Indexing Moving Points (Extended Abstract)	2000	PODS	9.9929961e-05
2,104	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0366183e-05
3,115	The CompleteSearch Engine: Interactive, Efficient, and Towards IR & DB Integration	2007	CIDR	7.6338594e-05
4,870	Estimating arbitrary subset sums with few probes	2005	PODS	6.3737999e-05
6,616	Two-dimensional Substring Indexing	2001	PODS	5.7330951e-05
7,667	Categorical Range Maxima Queries	2014	PODS	5.4772833e-05
8,250	Dynamic Top-K Range Reporting in External Memory	2012	PODS	5.3689663e-05
8,913	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS	5.2559789e-05
9,100	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	5.2283159e-05
12,454	A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting	2014	PODS	4.9793485e-05
12,593	Space-Efficient Range Reporting for Categorical Data	2012	PODS	4.9793485e-05
12,594	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS	4.9793485e-05
12,779	Worst-Case Efficient Range Search Indexing	2009	PODS	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
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045337853
101	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00033937215
1,527	On the Analysis of Indexing Schemes	1997	PODS	0.00010350889
1,589	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00010139591
2,179	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	8.9120272e-05
4,060	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.8250997e-05
4,834	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS	6.3883011e-05

Semantically Similar Papers

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