FITing-Tree: A Data-aware Index Structure

Summary: FITing-Tree presents a data-aware index that uses piecewise-linear approximations bounded by a tunable error. A cost model selects the error to balance lookup latency and storage, delivering near full-index performance with orders of magnitude less memory on real datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5734
Venue: SIGMOD
Year: 2019
Pagerank: 0.0001401445
Overall Rank: 790 | 94.59%
DOI: 10.1145/3299869.3319860

Incoming Non-self Citations Over Time

Authors

1. Alex Galakatos (Brown University)
2. Michael Markovitch (Brown University)
3. Carsten Binnig (Technical University of Darmstadt)
4. Rodrigo Fonseca (Brown University)
5. Tim Kraska (Massachusetts Institute of Technology)

BibTeX Citation

@inproceedings{galakatos_sigmod19,
        title = {{FITing-Tree: A Data-aware Index Structure}},
        author = {Galakatos, Alex and Markovitch, Michael and Binnig, Carsten and Fonseca, Rodrigo and Kraska, Tim},
        series = {{SIGMOD} '19},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3299869.3319860},
        url = {https://dl.acm.org/doi/10.1145/3299869.3319860},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 67 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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
847	Benchmarking Learned Indexes	2021	VLDB	0.0001365768
1,174	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00011817414
1,551	Updatable Learned Index with Precise Positions	2021	VLDB	0.00010381398
1,840	Effectively Learning Spatial Indices	2020	VLDB	9.6404567e-05
2,233	FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems	2022	VLDB	8.8968964e-05
2,806	Are Updatable Learned Indexes Ready?	2022	VLDB	8.1013097e-05
2,910	APEX: A High-Performance Learned Index on Persistent Memory	2022	VLDB	7.9700885e-05
2,919	SNARF: A Learning-Enhanced Range Filter	2022	VLDB	7.9628657e-05
3,035	Instance-Optimized Data Layouts for Cloud Analytics Workloads	2021	SIGMOD	7.8297746e-05
3,535	TreeLine: An Update-In-Place Key-Value Store for Modern Storage	2023	VLDB	7.3333933e-05
3,587	HUNTER: An Online Cloud Database Hybrid Tuning System for Personalized Requirements	2022	SIGMOD	7.2829345e-05
3,595	Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees	2020	VLDB	7.2736195e-05
3,729	CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm	2022	VLDB	7.1683974e-05
3,792	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB	7.1220982e-05
3,865	The Case for a Learned Sorting Algorithm	2020	SIGMOD	7.0621718e-05
4,065	LeCo: Lightweight Compression via Learning Serial Correlations	2024	SIGMOD	6.930275e-05
4,300	DILI: A Distribution-Driven Learned Index	2023	VLDB	6.773869e-05
4,414	NFL: Robust Learned Index via Distribution Transformation	2022	VLDB	6.7159984e-05
4,468	One Model to Rule them All: Towards Zero-Shot Learning for Databases	2022	CIDR	6.6819041e-05
4,516	The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures	2022	SIGMOD	6.6489359e-05
4,578	PLIN: A Persistent Learned Index for Non-Volatile Memory with High Performance and Instant Recovery	2023	VLDB	6.6210545e-05
4,660	Hist-Tree: Those Who Ignore It Are Doomed to Learn	2021	CIDR	6.5797541e-05
4,664	GRF: A Global Range Filter for LSM-Trees with Shape Encoding	2024	SIGMOD	6.5787544e-05
5,261	Oasis: An Optimal Disjoint Segmented Learned Range Filter	2024	VLDB	6.2955539e-05
5,423	Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices	2023	SIGMOD	6.2242567e-05
5,447	FILM: a Fully Learned Index for Larger-than-Memory Databases	2023	VLDB	6.2149491e-05
5,558	HMAB: Self-Driving Hierarchy of Bandits for Integrated Physical Database Design Tuning	2023	VLDB	6.1749098e-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
6,459	LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves	2023	VLDB	5.8727182e-05
6,462	PilotScope: Steering Databases with Machine Learning Drivers	2024	VLDB	5.8717744e-05
6,590	MOST: Model-Based Compression with Outlier Storage for Time Series Data	2023	SIGMOD	5.8316635e-05
6,687	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD	5.8022308e-05
6,874	SALI: A Scalable Adaptive Learned Index Framework based on Probability Models	2023	SIGMOD	5.7489487e-05
7,012	Adaptive Hybrid Indexes	2022	SIGMOD	5.7262686e-05
7,368	Accelerating String-key Learned Index Structures via Memoization-based Incremental Training	2024	VLDB	5.6315363e-05
7,392	Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction	2024	SIGMOD	5.6265456e-05
8,039	Algorithmic Complexity Attacks on Dynamic Learned Indexes	2024	VLDB	5.5021992e-05
8,056	Sieve: A Learned Data-Skipping Index for Data Analytics	2023	VLDB	5.4983582e-05
8,214	Tuning Hierarchical Learned Indexes on Disk and Beyond	2022	SIGMOD	5.4658344e-05
8,463	Limousine: Blending Learned and Classical Indexes to Self-Design Larger-than-Memory Cloud Storage Engines	2024	SIGMOD	5.4205593e-05
8,591	A New Paradigm in Tuning Learned Indexes: A Reinforcement Learning Enhanced Approach	2025	SIGMOD	5.4059856e-05
8,709	Why Are Learned Indexes So Effective but Sometimes Ineffective?	2025	VLDB	5.3789739e-05
8,986	One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting	2024	SIGMOD	5.3387783e-05
9,300	PriPL-Tree: Accurate Range Query for Arbitrary Distribution under Local Differential Privacy	2024	VLDB	5.289545e-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
9,998	SWIX: A Memory-efficient Sliding Window Learned Index	2024	SIGMOD	5.1814573e-05

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 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.00049302774
43	The Case for Learned Index Structures	2018	SIGMOD	0.00046060254
227	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00023958508
259	Database Cracking	2007	CIDR	0.00023119313
278	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00022476841
446	Monkey: Optimal Navigable Key-Value Store	2017	SIGMOD	0.00018332392
794	Bitmap Index Design and Evaluation	1998	SIGMOD	0.00013969303
797	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD	0.00013927251
944	RDF-3X: a RISC-style Engine for RDF	2008	VLDB	0.00013067088
964	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD	0.00012934147
1,492	BF-Tree: Approximate Tree Indexing	2014	VLDB	0.00010588267
1,655	Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units	2011	VLDB	0.00010103504
1,688	Online Piece-wise Linear Approximation of Numerical Streams with Precision Guarantees	2009	VLDB	0.00010003536
1,867	Performance Measurements of Compressed Bitmap Indices	1999	VLDB	9.5903618e-05
2,302	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB	8.7808696e-05
3,370	Revisiting Reuse for Approximate Query Processing	2017	VLDB	7.4700891e-05
3,576	Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems	2017	VLDB	7.2936598e-05
4,826	Design Tradeoffs of Data Access Methods	2016	SIGMOD	6.4904836e-05
4,988	UpBit: Scalable In-Memory Updatable Bitmap Indexing	2016	SIGMOD	6.4107392e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,378	High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff	2026	SIGMOD
2	8,214	Tuning Hierarchical Learned Indexes on Disk and Beyond	2022	SIGMOD
3	9,635	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
4	7,678	The hcC-tree: An Efficient Index Structure For Object Oriented Databases	1994	VLDB
5	6,429	Just-In-Time Data Structures	2015	CIDR
6	1,551	Updatable Learned Index with Precise Positions	2021	VLDB
7	1,813	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD
8	8,689	Adaptive Index Structures	2002	VLDB
9	7,012	Adaptive Hybrid Indexes	2022	SIGMOD
10	219	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB