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.00045429472 |
| 1,033 | Bitmap Index Design and Evaluation | 1998 | SIGMOD | 0.0001453376 |
| 1,701 | An Efficient Bitmap Encoding Scheme for Selection Queries | 1999 | SIGMOD | 0.00010828605 |
| 2,984 | On the Performance of Bitmap Indices for High Cardinality Attributes | 2004 | VLDB | 7.7768363e-05 |
| 3,699 | Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding | 2007 | SIGMOD | 6.827026e-05 |
| 5,605 | Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps | 2006 | VLDB | 5.413565e-05 |
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,921 | Efficient Indexes for Diverse Top-k Range Queries | 2020 | PODS | 4.4229886e-05 |
| 1,184 | On Effective Multi-Dimensional Indexing for Strings | 2000 | SIGMOD | 0.00013442644 |
| 12,302 | Worst-Case Efficient Range Search Indexing | 2009 | PODS | 4.1905499e-05 |
| 5,825 | Space-efficient Substring Occurrence Estimation | 2011 | PODS | 5.3119504e-05 |
| 7,988 | Secondary Index Optimization | 1975 | SIGMOD | 4.6089395e-05 |
| 2,010 | Indexing for Data Models with Constraints and Classes (Extended Abstract) | 1993 | PODS | 9.8046157e-05 |
| 5,695 | Optimal Indexing Using Near-Minimal Space [Extended Abstract] | 2003 | PODS | 5.3675705e-05 |
| 6,098 | Two-dimensional Substring Indexing | 2001 | PODS | 5.2078399e-05 |
| 8,764 | Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes | 2009 | PODS | 4.4520434e-05 |
| 1,183 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS | 0.00013444058 |