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.00013444058
Overall Rank: 1,183 | 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
628	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00018957327
1,764	Indexing Moving Points (Extended Abstract)	2000	PODS	0.0001062234
2,316	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0513688e-05
2,530	The CompleteSearch Engine: Interactive, Efficient, and Towards IR & DB Integration	2007	CIDR	8.5942205e-05
4,961	Estimating arbitrary subset sums with few probes	2005	PODS	5.7992561e-05
6,098	Two-dimensional Substring Indexing	2001	PODS	5.2078399e-05
6,919	Categorical Range Maxima Queries	2014	PODS	4.8878659e-05
7,851	Dynamic Top-K Range Reporting in External Memory	2012	PODS	4.6320876e-05
8,761	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS	4.4520434e-05
8,764	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	4.4520434e-05
11,973	A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting	2014	PODS	4.1905499e-05
12,113	Space-Efficient Range Reporting for Categorical Data	2012	PODS	4.1905499e-05
12,114	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS	4.1905499e-05
12,302	Worst-Case Efficient Range Search Indexing	2009	PODS	4.1905499e-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.0032118946
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888
75	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057450043
1,485	On the Analysis of Indexing Schemes	1997	PODS	0.00011698762
1,499	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643887
2,018	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	9.7852268e-05
3,902	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.6454492e-05
5,010	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS	5.7545425e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,499	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643887
12,303	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS	4.1905499e-05
1,764	Indexing Moving Points (Extended Abstract)	2000	PODS	0.0001062234
5,010	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS	5.7545425e-05
2,010	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS	9.8046157e-05
6,214	New Results on Two-dimensional Orthogonal Range Aggregation in External Memory	2011	PODS	5.1487236e-05
8,764	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	4.4520434e-05
3,902	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.6454492e-05
12,302	Worst-Case Efficient Range Search Indexing	2009	PODS	4.1905499e-05
12,114	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS	4.1905499e-05