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
- 1. Rasmus Pagh (IT University of Copenhagen)
- 2. Srinivasa Rao Satti (Seoul National University)
BibTeX Citation
@inproceedings{pagh_pods09,
address = {New York, NY, USA},
series = {{PODS} '09},
title = {{Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes}},
url = {https://dl.acm.org/doi/10.1145/1559795.1559824},
doi = {10.1145/1559795.1559824},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Pagh, Rasmus and Satti, Srinivasa Rao},
year = {2009}
}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 |
|---|---|---|---|---|
| 104 | Improved Query Performance with Variant Indexes | 1997 | SIGMOD | 0.00033932213 |
| 794 | Bitmap Index Design and Evaluation | 1998 | SIGMOD | 0.00013969303 |
| 1,464 | An Efficient Bitmap Encoding Scheme for Selection Queries | 1999 | SIGMOD | 0.00010689981 |
| 2,773 | On the Performance of Bitmap Indices for High Cardinality Attributes | 2004 | VLDB | 8.1382209e-05 |
| 3,524 | Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding | 2007 | SIGMOD | 7.3448437e-05 |
| 5,472 | Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps | 2006 | VLDB | 6.2058219e-05 |
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 9,073 | Efficient Indexes for Diverse Top-k Range Queries | 2020 | PODS |
| 2 | 2,648 | On Effective Multi-Dimensional Indexing for Strings | 2000 | SIGMOD |
| 3 | 12,489 | Worst-Case Efficient Range Search Indexing | 2009 | PODS |
| 4 | 6,818 | Space-efficient Substring Occurrence Estimation | 2011 | PODS |
| 5 | 8,302 | Secondary Index Optimization | 1975 | SIGMOD |
| 6 | 2,003 | Indexing for Data Models with Constraints and Classes (Extended Abstract) | 1993 | PODS |
| 7 | 6,753 | Optimal Indexing Using Near-Minimal Space [Extended Abstract] | 2003 | PODS |
| 8 | 6,491 | Two-dimensional Substring Indexing | 2001 | PODS |
| 9 | 8,937 | Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes | 2009 | PODS |
| 10 | 1,529 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS |