Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes

Summary: Introduce dynamic indexability and prove tradeoff lower bounds for dynamic 1D range indexes with query cost O(q+K/B) and amortized insertion O(u/B). Show q·log(u/q)=Ω(log B) for q=O(log B) and u·log q=Ω(log B) for larger q, implying buffered B-tree variants optimal when M=B^{O(1)}. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1491
Venue: PODS
Year: 2009
Pagerank: 4.456315e-05
Overall Rank: 8,767 | 39.01%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Ke Yi

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,554	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,077	Incremental Organization for Data Recording and Warehousing	1997	VLDB	0.00014247204
1,182	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013455963
1,488	On the Analysis of Indexing Schemes	1997	PODS	0.00011699446
2,396	A Novel Index Supporting High Volume Data Warehouse Insertions	1999	VLDB	8.8997169e-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
5,682	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS	5.372736e-05
11,965	A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting	2014	PODS	4.1945683e-05
1,774	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	0.00010604097
12,294	Worst-Case Efficient Range Search Indexing	2009	PODS	4.1945683e-05
8,474	Adaptive Index Structures	2002	VLDB	4.5029015e-05
12,295	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS	4.1945683e-05
2,003	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS	9.8126082e-05
4,672	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD	6.0085156e-05
5,013	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS	5.7598528e-05
1,182	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013455963