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: haa6aff37adfed6e2
Venue: SIGMOD
Year: 2019
Pagerank: 8.7776298e-05
Overall Rank: 2,236 | 84.97%
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
430	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018409112
848	Benchmarking Learned Indexes	2021	VLDB	0.00013506188
2,788	Lethe: A Tunable Delete-Aware LSM Engine	2020	SIGMOD	8.0133966e-05
2,837	SNARF: A Learning-Enhanced Range Filter	2022	VLDB	7.9527715e-05
3,714	The Case for a Learned Sorting Algorithm	2020	SIGMOD	7.0769061e-05
3,803	CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm	2022	VLDB	7.0127652e-05
4,508	NFL: Robust Learned Index via Distribution Transformation	2022	VLDB	6.5704964e-05
4,616	The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures	2022	SIGMOD	6.5000712e-05
4,721	Hist-Tree: Those Who Ignore It Are Doomed to Learn	2021	CIDR	6.4541703e-05
6,077	When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories	2023	SIGMOD	5.893943e-05
7,535	Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction	2024	SIGMOD	5.5003117e-05
8,873	Why Are Learned Indexes So Effective but Sometimes Ineffective?	2025	VLDB	5.2582842e-05
9,346	External Merge Sort for Top-K Queries: Eager input filtering guided by histograms	2020	SIGMOD	5.1901145e-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
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047731453
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046284649
361	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.00020006406
1,085	On B-tree Indices for Skewed Distributions	1992	VLDB	0.00012112632

Semantically Similar Papers

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