Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search?

Summary: Proposes SIP and TIP, in-memory search for sorted arrays with slope-based and three-point interpolation to beat Binary Search. Adds a meta-algorithm to auto-switch among SIP, TIP, and Binary Search, yielding up to 4x/2-3x speedups on varied data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5668
Venue: SIGMOD
Year: 2019
Pagerank: 8.9255716e-05
Overall Rank: 2,222 | 84.76%
DOI: 10.1145/3299869.3300075

Incoming Non-self Citations Over Time

Authors

1. Peter Van Sandt (University of Wisconsin)
2. Yannis Chronis (University of Wisconsin)
3. Jignesh M. Patel (University of Wisconsin)

BibTeX Citation

@inproceedings{sandt_sigmod19,
        title = {{Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search?}},
        author = {Van Sandt, Peter and Chronis, Yannis and Patel, Jignesh M.},
        series = {{SIGMOD} '19},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3299869.3300075},
        url = {https://dl.acm.org/doi/10.1145/3299869.3300075},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
447	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018322593
847	Benchmarking Learned Indexes	2021	VLDB	0.0001365768
2,755	Lethe: A Tunable Delete-Aware LSM Engine	2020	SIGMOD	8.163097e-05
2,919	SNARF: A Learning-Enhanced Range Filter	2022	VLDB	7.9628657e-05
3,729	CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm	2022	VLDB	7.1683974e-05
3,865	The Case for a Learned Sorting Algorithm	2020	SIGMOD	7.0621718e-05
4,414	NFL: Robust Learned Index via Distribution Transformation	2022	VLDB	6.7159984e-05
4,516	The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures	2022	SIGMOD	6.6489359e-05
4,660	Hist-Tree: Those Who Ignore It Are Doomed to Learn	2021	CIDR	6.5797541e-05
5,954	When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories	2023	SIGMOD	6.0292226e-05
7,392	Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction	2024	SIGMOD	5.6265456e-05
8,709	Why Are Learned Indexes So Effective but Sometimes Ineffective?	2025	VLDB	5.3789739e-05
9,172	External Merge Sort for Top-K Queries: Eager input filtering guided by histograms	2020	SIGMOD	5.3092396e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
43	The Case for Learned Index Structures	2018	SIGMOD	0.00046060254
360	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.00020182846
1,059	On B-tree Indices for Skewed Distributions	1992	VLDB	0.00012377809

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	507	Interpolation-Based Index Maintenance	1983	PODS
2	3,212	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB
3	10,638	A Theoretical Framework for Distribution-Aware Dataset Search	2025	PODS
4	7,342	Efficient Search in Very Large Databases	1988	VLDB
5	6,851	Maximum Inner Product is Query-Scaled Nearest Neighbor	2025	VLDB
6	2,245	Fast Set Intersection in Memory	2011	VLDB
7	1,561	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS
8	204	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB
9	1,717	Improving the Performance of List Intersection	2009	VLDB
10	6,329	An Eight-Dimensional Systematic Evaluation of Optimized Search Algorithms on Modern Processors	2018	VLDB