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 17 of 67 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,041	DBMS Fitting: Why should we learn what we already know?	2020	CIDR	5.1709251e-05
10,097	SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index	2026	SIGMOD	5.1502319e-05
10,262	LINE: A Learned Index with Group-Enhanced Leaves and Cache-Optimized Inner Tree	2026	SIGMOD	5.093636e-05
10,267	Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions	2026	SIGMOD	5.093636e-05
10,277	On Self-Designing Learned Indexes	2026	SIGMOD	5.093636e-05
10,378	High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff	2026	SIGMOD	5.093636e-05
10,458	From Learning to Recycling: A Log-Structured Learned-Less Index	2026	SIGMOD	5.093636e-05
10,461	HIRE: A Hybrid Learned Index for Robust and Efficient Performance under Mixed Workloads	2026	SIGMOD	5.093636e-05
10,469	LM-Tree: A Hybrid Learned Index for Similarity Search in Metric Spaces	2026	SIGMOD	5.093636e-05
10,505	The Case For Language Model Approximated LIKE Predicate	2026	SIGMOD	5.093636e-05
10,569	Toward Drift-Aware Database Benchmarking	2026	VLDB	5.093636e-05
10,617	LiBox: A Learned Index as an Array to Minimize Last-Mile Search	2026	VLDB	5.093636e-05
10,682	VEGA: An Active-tuning Learned Index with Group-Wise Learning Granularity	2025	SIGMOD	5.093636e-05
10,955	DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees	2025	VLDB	5.093636e-05
11,059	Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects	2025	VLDB	5.093636e-05
11,475	Route Travel Time Estimation on A Road Network Revisited: Heterogeneity, Proximity, Periodicity and Dynamicity	2023	VLDB	5.093636e-05
11,702	LES3: Learning-based Exact Set Similarity Search	2021	VLDB	5.093636e-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