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.7591557e-05
Overall Rank: 2,247 | 84.94%
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
427	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018429918
834	Benchmarking Learned Indexes	2021	VLDB	0.00013539098
2,796	Lethe: A Tunable Delete-Aware LSM Engine	2020	SIGMOD	7.9849253e-05
2,844	SNARF: A Learning-Enhanced Range Filter	2022	VLDB	7.9291659e-05
3,715	The Case for a Learned Sorting Algorithm	2020	SIGMOD	7.0549546e-05
3,716	CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm	2022	VLDB	7.0541948e-05
4,385	NFL: Robust Learned Index via Distribution Transformation	2022	VLDB	6.613814e-05
4,621	The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures	2022	SIGMOD	6.4828493e-05
4,727	Hist-Tree: Those Who Ignore It Are Doomed to Learn	2021	CIDR	6.4327925e-05
6,075	When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories	2023	SIGMOD	5.8776022e-05
7,314	Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction	2024	SIGMOD	5.5425359e-05
8,903	Why Are Learned Indexes So Effective but Sometimes Ineffective?	2025	VLDB	5.238416e-05
9,381	External Merge Sort for Top-K Queries: Eager input filtering guided by histograms	2020	SIGMOD	5.170504e-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.00047654188
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046249672
360	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.00019959166
1,086	On B-tree Indices for Skewed Distributions	1992	VLDB	0.00012069306

Semantically Similar Papers

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