Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes
Summary: Gives the first I/O‑optimal secondary index for a string x over ordered alphabet Σ: answers alphabet‑range queries reading (with internal memory (|Σ| log n)^δ blocks) within a constant factor of the information‑theoretic minimum. Uses O(n log|Σ|) bits (0th‑order entropy bound), supports update time–space tradeoffs, and an approximate variant that reduces query I/O to O(|I[a_l,a_r]| log(1/ε)) bits with false‑positive probability ε. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
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 |
|---|---|---|---|---|
| 121 | Improved Query Performance with Variant Indexes | 1997 | SIGMOD | 0.00045447517 |
| 1,035 | Bitmap Index Design and Evaluation | 1998 | SIGMOD | 0.00014532778 |
| 1,704 | An Efficient Bitmap Encoding Scheme for Selection Queries | 1999 | SIGMOD | 0.000108332 |
| 2,986 | On the Performance of Bitmap Indices for High Cardinality Attributes | 2004 | VLDB | 7.778912e-05 |
| 3,717 | Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding | 2007 | SIGMOD | 6.8210203e-05 |
| 5,596 | Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps | 2006 | VLDB | 5.4181535e-05 |
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,919 | Efficient Indexes for Diverse Top-k Range Queries | 2020 | PODS | 4.427232e-05 |
| 1,184 | On Effective Multi-Dimensional Indexing for Strings | 2000 | SIGMOD | 0.00013455208 |
| 12,294 | Worst-Case Efficient Range Search Indexing | 2009 | PODS | 4.1945683e-05 |
| 5,813 | Space-efficient Substring Occurrence Estimation | 2011 | PODS | 5.3170565e-05 |
| 7,985 | Secondary Index Optimization | 1975 | SIGMOD | 4.613363e-05 |
| 2,003 | Indexing for Data Models with Constraints and Classes (Extended Abstract) | 1993 | PODS | 9.8126082e-05 |
| 5,682 | Optimal Indexing Using Near-Minimal Space [Extended Abstract] | 2003 | PODS | 5.372736e-05 |
| 6,097 | Two-dimensional Substring Indexing | 2001 | PODS | 5.2119402e-05 |
| 8,767 | Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes | 2009 | PODS | 4.456315e-05 |
| 1,182 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS | 0.00013455963 |