Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems

Summary: Hippo indexes page ranges, not tuple pointers, using lightweight histograms and distribution-based grouping to prune irrelevant pages. It delivers B+-Tree-like selective-query performance with up to 100× lower space and 1,000× lower maintenance overhead. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hded90e62c868e9a3
Venue: VLDB
Year: 2017
Pagerank: 7.1582591e-05
Overall Rank: 3,601 | 75.87%
DOI: 10.14778/3025111.3025120
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Jia Yu (Arizona State University)
2. Mohamed Sarwat (Arizona State University)

BibTeX Citation

@article{yu_vldb17,
        title = {{Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems}},
        author = {Yu, Jia and Sarwat, Mohamed},
        journal = {PVLDB},
        series = {{VLDB} '17},
        volume = {10},
        number = {4},
        doi = {10.14778/3025111.3025120},
        url = {https://doi.org/10.14778/3025111.3025120},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046249672
774	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00014063511
2,249	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.7479608e-05
3,081	Pushing Data-Induced Predicates Through Joins in Big-Data Clusters	2020	VLDB	7.6515625e-05
8,222	Sieve: A Learned Data-Skipping Index for Data Analytics	2023	VLDB	5.3585489e-05
8,505	Provenance-based Data Skipping	2022	VLDB	5.3126038e-05
8,516	Tree-Encoded Bitmaps	2020	SIGMOD	5.3110731e-05
11,195	Dynamic Pruning for Recursive Joins	2025	SIGMOD	4.9605343e-05
12,227	HERMIT in Action: Succinct Secondary Indexing Mechanism via Correlation Exploration	2019	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
34	The Design Of Postgres	1986	SIGMOD	0.00049063803
216	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00024446892
1,435	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010659454
1,507	BF-Tree: Approximate Tree Indexing	2014	VLDB	0.0001041737
1,532	Column Imprints: A Secondary Index Structure	2013	SIGMOD	0.00010312002
1,805	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	9.5936926e-05
1,924	The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing	2014	SIGMOD	9.3535088e-05
2,810	On the Performance of Bitmap Indices for High Cardinality Attributes	2004	VLDB	7.9609074e-05
3,744	NET-FLi: On-the-fly Compression, Archiving and Indexing of Streaming Network Traffic	2010	VLDB	7.0372503e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,076	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB
2	5,149	Holistic Indexing in Main-memory Column-stores	2015	SIGMOD
3	1,846	Merging What's Cracked, Cracking What's Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB
4	3,383	A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms	2016	SIGMOD
5	8,558	AirIndex: Versatile Index Tuning Through Data and Storage	2023	SIGMOD
6	5,397	Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices	2023	SIGMOD
7	1,529	Updatable Learned Index with Precise Positions	2021	VLDB
8	8,401	Tuning Hierarchical Learned Indexes on Disk and Beyond	2022	SIGMOD
9	7,180	Adaptive Hybrid Indexes	2022	SIGMOD
10	964	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD