Hist-Tree: Those Who Ignore It Are Doomed to Learn

Summary: Argues learned indexes' gains largely reflect implicit assumptions (sortedness/range) rather than ML modeling, and that a traditional structure can exploit them. Proposes Hist-Tree — a histogram-based tree with a compact read-only layout — that outperforms RMI, PGM, and RadixSpline by up to 1.8–2.7× lookup latency. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 418
Venue: CIDR
Year: 2021
Pagerank: 6.5797541e-05
Overall Rank: 4,660 | 68.03%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Andrew Crotty (Brown University)

BibTeX Citation

@inproceedings{crotty_cidr21,
        address = {Amsterdam, Netherlands},
        series = {{CIDR} '21},
        title = {{Hist-Tree: Those Who Ignore It Are Doomed to Learn}},
        booktitle = {Proceedings of the {Conference} on {Innovative} {Data} {Systems} {Research}},
        author = {Crotty, Andrew},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,806	Are Updatable Learned Indexes Ready?	2022	VLDB	8.1013097e-05
2,919	SNARF: A Learning-Enhanced Range Filter	2022	VLDB	7.9628657e-05
3,792	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB	7.1220982e-05
5,974	Towards instance-optimized data systems	2021	VLDB	6.0230488e-05
6,163	A Critical Analysis of Recursive Model Indexes	2022	VLDB	5.9532723e-05
7,368	Accelerating String-key Learned Index Structures via Memoization-based Incremental Training	2024	VLDB	5.6315363e-05
7,768	The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures	2022	VLDB	5.5475685e-05
9,411	Can Learned Indexes be Built Efficiently? A Deep Dive into Sampling Trade-offs	2024	SIGMOD	5.274743e-05
9,599	Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis]	2026	SIGMOD	5.2492748e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
43	The Case for Learned Index Structures	2018	SIGMOD	0.00046060254
67	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00038461275
204	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00025342994
278	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00022476841
447	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018322593
477	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017851226
568	SageDB: A Learned Database System	2019	CIDR	0.0001641553
790	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.0001401445
847	Benchmarking Learned Indexes	2021	VLDB	0.0001365768
873	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013481915
1,174	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00011817414
2,222	Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search?	2019	SIGMOD	8.9255716e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,461	HIRE: A Hybrid Learned Index for Robust and Efficient Performance under Mixed Workloads	2026	SIGMOD
2	8,709	Why Are Learned Indexes So Effective but Sometimes Ineffective?	2025	VLDB
3	1,551	Updatable Learned Index with Precise Positions	2021	VLDB
4	477	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB
5	8,214	Tuning Hierarchical Learned Indexes on Disk and Beyond	2022	SIGMOD
6	7,392	Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction	2024	SIGMOD
7	3,792	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB
8	6,687	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD
9	43	The Case for Learned Index Structures	2018	SIGMOD
10	847	Benchmarking Learned Indexes	2021	VLDB