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)
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,558 | On the I/O Complexity of the k-Nearest Neighbors Problem | 2020 | PODS | 4.1905499e-05 |
Previous
Page 1 / 1
Next
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,071 | Incremental Organization for Data Recording and Warehousing | 1997 | VLDB | 0.00014265647 |
| 1,183 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS | 0.00013444058 |
| 1,485 | On the Analysis of Indexing Schemes | 1997 | PODS | 0.00011698762 |
| 2,391 | A Novel Index Supporting High Volume Data Warehouse Insertions | 1999 | VLDB | 8.8946187e-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 |
Previous
Page 1 / 1
Next