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: h9761bd39cb86219d
Venue: SIGMOD
Year: 2019
Pagerank: 0.00014107655
Overall Rank: 768 | 94.84%
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 70 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
422	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018488849
458	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017880664
835	Benchmarking Learned Indexes	2021	VLDB	0.00013575971
1,188	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00011598149
1,525	Updatable Learned Index with Precise Positions	2021	VLDB	0.00010355133
1,877	Effectively Learning Spatial Indices	2020	VLDB	9.4498401e-05
2,270	FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems	2022	VLDB	8.7166469e-05
2,582	Are Updatable Learned Indexes Ready?	2022	VLDB	8.2641447e-05
2,765	Instance-Optimized Data Layouts for Cloud Analytics Workloads	2021	SIGMOD	8.0401855e-05
2,839	SNARF: A Learning-Enhanced Range Filter	2022	VLDB	7.9490277e-05
2,861	APEX: A High-Performance Learned Index on Persistent Memory	2022	VLDB	7.9295281e-05
3,233	TreeLine: An Update-In-Place Key-Value Store for Modern Storage	2023	VLDB	7.5008192e-05
3,487	HUNTER: An Online Cloud Database Hybrid Tuning System for Personalized Requirements	2022	SIGMOD	7.2603973e-05
3,607	Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees	2020	VLDB	7.1645803e-05
3,621	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB	7.1510804e-05
3,708	The Case for a Learned Sorting Algorithm	2020	SIGMOD	7.0781032e-05
3,710	CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm	2022	VLDB	7.0775695e-05
4,155	LeCo: Lightweight Compression via Learning Serial Correlations	2024	SIGMOD	6.7730383e-05
4,362	NFL: Robust Learned Index via Distribution Transformation	2022	VLDB	6.6357559e-05
4,366	DILI: A Distribution-Driven Learned Index	2023	VLDB	6.6330579e-05
4,536	One Model to Rule them All: Towards Zero-Shot Learning for Databases	2022	CIDR	6.552998e-05
4,618	The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures	2022	SIGMOD	6.4981355e-05
4,635	PLIN: A Persistent Learned Index for Non-Volatile Memory with High Performance and Instant Recovery	2023	VLDB	6.4904555e-05
4,715	Hist-Tree: Those Who Ignore It Are Doomed to Learn	2021	CIDR	6.4537149e-05
4,753	GRF: A Global Range Filter for LSM-Trees with Shape Encoding	2024	SIGMOD	6.4334982e-05
4,878	Oasis: An Optimal Disjoint Segmented Learned Range Filter	2024	VLDB	6.369385e-05
5,378	Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices	2023	SIGMOD	6.1551053e-05
5,405	FILM: a Fully Learned Index for Larger-than-Memory Databases	2023	VLDB	6.1435108e-05
5,675	HMAB: Self-Driving Hierarchy of Bandits for Integrated Physical Database Design Tuning	2023	VLDB	6.0401656e-05
5,700	PilotScope: Steering Databases with Machine Learning Drivers	2024	VLDB	6.028998e-05
5,973	Towards instance-optimized data systems	2021	VLDB	5.9281867e-05
6,267	A Critical Analysis of Recursive Model Indexes	2022	VLDB	5.8283218e-05
6,597	LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves	2023	VLDB	5.7386302e-05
6,613	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD	5.7326443e-05
6,698	MOST: Model-Based Compression with Outlier Storage for Time Series Data	2023	SIGMOD	5.7040999e-05
6,787	SALI: A Scalable Adaptive Learned Index Framework based on Probability Models	2023	SIGMOD	5.6810904e-05
6,867	Accelerating String-key Learned Index Structures via Memoization-based Incremental Training	2024	VLDB	5.6581046e-05
7,157	Adaptive Hybrid Indexes	2022	SIGMOD	5.595284e-05
7,297	Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction	2024	SIGMOD	5.5609237e-05
8,207	Sieve: A Learned Data-Skipping Index for Data Analytics	2023	VLDB	5.3763264e-05
8,208	Algorithmic Complexity Attacks on Dynamic Learned Indexes	2024	VLDB	5.3761984e-05
8,382	Tuning Hierarchical Learned Indexes on Disk and Beyond	2022	SIGMOD	5.341043e-05
8,619	Limousine: Blending Learned and Classical Indexes to Self-Design Larger-than-Memory Cloud Storage Engines	2024	SIGMOD	5.3001199e-05
8,761	A New Paradigm in Tuning Learned Indexes: A Reinforcement Learning Enhanced Approach	2025	SIGMOD	5.2821881e-05
8,882	Why Are Learned Indexes So Effective but Sometimes Ineffective?	2025	VLDB	5.255795e-05
9,154	One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting	2024	SIGMOD	5.2176438e-05
9,484	PriPL-Tree: Accurate Range Query for Arbitrary Distribution under Local Differential Privacy	2024	VLDB	5.168414e-05
9,601	Can Learned Indexes be Built Efficiently? A Deep Dive into Sampling Trade-offs	2024	SIGMOD	5.153951e-05
9,746	LES3: Learning-based Exact Set Similarity Search	2021	VLDB	5.1325223e-05
9,782	Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis]	2026	SIGMOD	5.129066e-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.00049129967
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046363107
216	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00024485637
252	Database Cracking	2007	CIDR	0.00023101361
277	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00022320139
400	Monkey: Optimal Navigable Key-Value Store	2017	SIGMOD	0.00019124757
769	Bitmap Index Design and Evaluation	1998	SIGMOD	0.00014106166
812	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD	0.00013744009
954	RDF-3X: a RISC-style Engine for RDF	2008	VLDB	0.00012866296
960	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD	0.0001283613
1,506	BF-Tree: Approximate Tree Indexing	2014	VLDB	0.00010448376
1,653	Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units	2011	VLDB	9.969498e-05
1,714	Online Piece-wise Linear Approximation of Numerical Streams with Precision Guarantees	2009	VLDB	9.8119635e-05
1,896	Performance Measurements of Compressed Bitmap Indices	1999	VLDB	9.4103502e-05
2,326	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB	8.628257e-05
3,417	Revisiting Reuse for Approximate Query Processing	2017	VLDB	7.3184905e-05
3,592	Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems	2017	VLDB	7.1807308e-05
4,771	UpBit: Scalable In-Memory Updatable Bitmap Indexing	2016	SIGMOD	6.4223645e-05
4,875	Design Tradeoffs of Data Access Methods	2016	SIGMOD	6.3699172e-05

Semantically Similar Papers

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