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: 1188
Venue: PODS
Year: 1999
Pagerank: 0.00013455963
Overall Rank: 1,182 | 91.78%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
631	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00018935493
1,766	Indexing Moving Points (Extended Abstract)	2000	PODS	0.000106236
2,308	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0591406e-05
2,531	The CompleteSearch Engine: Interactive, Efficient, and Towards IR & DB Integration	2007	CIDR	8.5911728e-05
4,955	Estimating arbitrary subset sums with few probes	2005	PODS	5.8053317e-05
6,097	Two-dimensional Substring Indexing	2001	PODS	5.2119402e-05
6,917	Categorical Range Maxima Queries	2014	PODS	4.8925595e-05
7,846	Dynamic Top-K Range Reporting in External Memory	2012	PODS	4.6365341e-05
8,546	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS	4.4937074e-05
8,767	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	4.456315e-05
11,965	A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting	2014	PODS	4.1945683e-05
12,105	Space-Efficient Range Reporting for Categorical Data	2012	PODS	4.1945683e-05
12,106	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS	4.1945683e-05
12,294	Worst-Case Efficient Range Search Indexing	2009	PODS	4.1945683e-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.0032169493
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083378538
76	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057303551
1,488	On the Analysis of Indexing Schemes	1997	PODS	0.00011699446
1,502	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643406
2,013	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	9.7928688e-05
3,900	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.6518011e-05
5,013	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS	5.7598528e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,502	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643406
12,295	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS	4.1945683e-05
1,766	Indexing Moving Points (Extended Abstract)	2000	PODS	0.000106236
5,013	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS	5.7598528e-05
2,003	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS	9.8126082e-05
6,215	New Results on Two-dimensional Orthogonal Range Aggregation in External Memory	2011	PODS	5.153674e-05
8,767	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	4.456315e-05
3,900	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.6518011e-05
12,294	Worst-Case Efficient Range Search Indexing	2009	PODS	4.1945683e-05
12,106	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS	4.1945683e-05