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: 5607
Venue: SIGMOD
Year: 2019
Pagerank: 8.2082721e-05
Overall Rank: 2,734 | 81.01%
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
819	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00016237497
1,438	Benchmarking Learned Indexes	2021	VLDB	0.00011965956
3,363	Lethe: A Tunable Delete-Aware LSM Engine	2020	SIGMOD	7.1680649e-05
3,614	SNARF: A Learning-Enhanced Range Filter	2022	VLDB	6.9124805e-05
4,086	The Case for a Learned Sorting Algorithm	2020	SIGMOD	6.4579358e-05
4,830	CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm	2022	VLDB	5.8884997e-05
5,154	Hist-Tree: Those Who Ignore It Are Doomed to Learn	2021	CIDR	5.6548237e-05
5,310	The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures	2022	SIGMOD	5.5713508e-05
5,655	NFL: Robust Learned Index via Distribution Transformation	2022	VLDB	5.3877506e-05
6,226	When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories	2023	SIGMOD	5.1413982e-05
8,100	Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction	2024	SIGMOD	4.5821762e-05
9,121	External Merge Sort for Top-K Queries: Eager input filtering guided by histograms	2020	SIGMOD	4.3878169e-05
9,745	Why Are Learned Indexes So Effective but Sometimes Ineffective?	2025	VLDB	4.2856385e-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
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
101	The Case for Learned Index Structures	2018	SIGMOD	0.00049778866
538	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.00020632609
639	On B-tree Indices for Skewed Distributions	1992	VLDB	0.00018782897

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,449	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.0803234e-05
254	Interpolation-Based Index Maintenance	1983	PODS	0.00030506096
10,353	A Theoretical Framework for Distribution-Aware Dataset Search	2025	PODS	4.1905499e-05
7,225	Efficient Search in Very Large Databases	1988	VLDB	4.7910249e-05
8,484	Maximum Inner Product is Query-Scaled Nearest Neighbor	2025	VLDB	4.4956257e-05
2,465	Fast Set Intersection in Memory	2011	VLDB	8.7344475e-05
1,499	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643887
240	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00031526134
1,121	Improving the Performance of List Intersection	2009	VLDB	0.00013838956
6,441	An Eight-Dimensional Systematic Evaluation of Optimized Search Algorithms on Modern Processors	2018	VLDB	5.0546366e-05