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: 5606
Venue: SIGMOD
Year: 2019
Pagerank: 8.2087602e-05
Overall Rank: 2,732 | 81.00%
DOI: 10.1145/3299869.3300075

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
826	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00016224841
1,460	Benchmarking Learned Indexes	2021	VLDB	0.00011887068
3,386	Lethe: A Tunable Delete-Aware LSM Engine	2020	SIGMOD	7.1577103e-05
3,611	SNARF: A Learning-Enhanced Range Filter	2022	VLDB	6.9191399e-05
4,097	The Case for a Learned Sorting Algorithm	2020	SIGMOD	6.4551616e-05
4,646	CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm	2022	VLDB	6.0250374e-05
5,157	Hist-Tree: Those Who Ignore It Are Doomed to Learn	2021	CIDR	5.6589595e-05
5,428	The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures	2022	SIGMOD	5.5091613e-05
5,642	NFL: Robust Learned Index via Distribution Transformation	2022	VLDB	5.3929294e-05
6,229	When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories	2023	SIGMOD	5.1463389e-05
8,101	Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction	2024	SIGMOD	4.5854141e-05
9,123	External Merge Sort for Top-K Queries: Eager input filtering guided by histograms	2020	SIGMOD	4.3920263e-05
9,746	Why Are Learned Indexes So Effective but Sometimes Ineffective?	2025	VLDB	4.2897489e-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
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
102	The Case for Learned Index Structures	2018	SIGMOD	0.00049545203
540	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.0002063443
638	On B-tree Indices for Skewed Distributions	1992	VLDB	0.00018798677

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,448	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.0844401e-05
255	Interpolation-Based Index Maintenance	1983	PODS	0.00030498284
10,341	A Theoretical Framework for Distribution-Aware Dataset Search	2025	PODS	4.1945683e-05
7,226	Efficient Search in Very Large Databases	1988	VLDB	4.7953551e-05
8,485	Maximum Inner Product is Query-Scaled Nearest Neighbor	2025	VLDB	4.4999394e-05
2,464	Fast Set Intersection in Memory	2011	VLDB	8.7524354e-05
1,502	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643406
238	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00031642425
1,124	Improving the Performance of List Intersection	2009	VLDB	0.00013847565
6,461	An Eight-Dimensional Systematic Evaluation of Optimized Search Algorithms on Modern Processors	2018	VLDB	5.0538774e-05