Interpolation Search Can Be Fast, in Some Situations, Sometimes, If You Try!
summary
Claims that interpolation search beats binary for large, mostly-uniform sorted arrays by grouping values into bucketed by value range segments, storing bucket starts, and doing a binary search inside the bucket; worst case equals binary search but typical cost drops toward log log N. Implementation replaces slow divides with a precomputed reciprocal multiply-and-shift using 64-bit unsigned multiply producing a 128-bit product using mulq; microbenchmarks show fewer comparisons and real speedup on realistic data.
AI-written summary · about
chapters (15)
- 0:00Intro
- 0:40Background
- 1:30Old Solution
- 2:14What Do We Know
- 2:37Main Idea
- 3:05What NOT to do
- 3:43Buckets
- 4:27Visuals
- 5:32Second Idea
- 7:01Recap
- 7:11Why is it cool
- 7:45Can we improve it
- 8:16X divided by Y
- 8:39K divided by Y
- 9:26C Code
related talks
32mUnder the Hood: Key Algorithms Powering Vector Search
43mOpenSearch and the Path to a Trillion-scale Vector Database
26mFast Erasure Coding for Data Storage: A Comprehensive Study of the Acceleration...
34mThe Challenges of Making Vector Search Billion-scale
18mSpeed Up Your Search: Concurrency and Merge Policies to the Rescue
48mTricks from in-memory databases
45mBeyond Lists: High Performance Data Structures
40mUsing Native CPU Vectorized Instructions for 60% Speedup on Lucene's KNN Vector Search