DBScholar

Back to papers

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
1490
Venue
PODS
Year
2009
Pagerank
5.3483178e-05
Overall Rank
8,937 | 38.69%
DOI
10.1145/1559795.1559825

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{yi_pods09,
        address = {New York, NY, USA},
        series = {{PODS} '09},
        title = {{Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes}},
        url = {https://dl.acm.org/doi/10.1145/1559795.1559825},
        doi = {10.1145/1559795.1559825},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Yi, Ke},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank Citing Paper Year Venue Pagerank
11,751 On the I/O Complexity of the k-Nearest Neighbors Problem 2020 PODS 5.093636e-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
981 Incremental Organization for Data Recording and Warehousing 1997 VLDB 0.0001284025
1,512 On the Analysis of Indexing Schemes 1997 PODS 0.00010536001
1,529 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00010482997
2,396 A Novel Index Supporting High Volume Data Warehouse Insertions 1999 VLDB 8.6345567e-05
3,972 Tight bounds for 2-dimensional indexing schemes 1998 PODS 6.9814651e-05
4,730 A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries 1998 PODS 6.5348792e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 6,753 Optimal Indexing Using Near-Minimal Space [Extended Abstract] 2003 PODS
2 12,163 A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting 2014 PODS
3 2,020 Query and Update Efficient B+-Tree Based Indexing of Moving Objects 2004 VLDB
4 12,489 Worst-Case Efficient Range Search Indexing 2009 PODS
5 8,689 Adaptive Index Structures 2002 VLDB
6 12,490 Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes 2009 PODS
7 2,003 Indexing for Data Models with Constraints and Classes (Extended Abstract) 1993 PODS
8 4,914 A General Solution of the n-dimensional B-tree Problem 1995 SIGMOD
9 4,730 A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries 1998 PODS
10 1,529 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS