Interpolation search

When people look up “zebra” in a dictionary, they do not open it in the middle: they open it near the very end, because “z” is the last letter. Binary search cannot do that: it halves the range without looking at what it is searching for. Interpolation search does look: it estimates the place from the values at the edges of the range and probes there. Below are five sorted rows from 45,227 cities of the world: the hashes of the names, the names themselves as in a phone book, latitudes, populations, and a made-up row with a “giant”. The scene’s window follows the range that is left, and the chord between its edges always runs along the window’s diagonal.

On the hashes the target is found in three or four probes, while binary search needs fourteen to sixteen on the same 42,311 numbers. A hash mixes the bits, the values lie evenly, and the curve in any window is almost a diagonal. On populations the search crawls: it finds a town of 22,026 people in 2139 probes. The population curve is a long shelf of tens of thousands of small towns and a cliff upwards where the cities of millions are. The chord runs high above the shelf and points almost at the left edge, and as you zoom in the picture repeats.

The idea

Interpolation search is built like binary search: a probe, a comparison, the range narrows. The difference is the choice of place. Binary search takes the middle, while interpolation search draws a straight line through the edges of the range, the points (lo, a[lo]) and (hi, a[hi]), and probes where it reaches the height of the target x.

The target stands above the lower edge by a fraction (x − a[lo]) / (a[hi] − a[lo]) of the whole rise. If the values grow evenly, it is the same fraction of the range away from its start:

fraction = (x − a[lo]) / (a[hi] − a[lo]),
pos = lo + ⌊fraction · (hi − lo)⌋.

After that everything is as in binary search. If the target is at pos, done; if what is there is smaller, search to the right of pos, if larger, to the left. The search goes on while the target lies between the values at the edges: with x < a[lo] or x > a[hi] it is not in the range. This condition is needed not only to stop in time.

Without checking the edges the fraction goes outside [0, 1], and the probe flies off beyond the array. When a[lo] = a[hi], division is impossible, but then all the values of the range are equal and any place can be probed; the listing takes lo.

Why so few probes

Take a model in which the method is good. Let the n keys be independent random numbers spread uniformly over the interval [A, B], with the ends A and B known. We search for a number x; let K be how many keys are at most x, that is, the place where x belongs. The first probe guesses it as np, where p = (x − A)/(B − A).

On a million keys the first probe misses by at most 500 places on average, while binary search after its first probe knows only which half the target is in. After that the same picture repeats on a smaller scale, and here it is an estimate rather than a proof. After a probe the new chord starts from a value close to x, and the fraction p in the new problem is small, of the order of the error divided by the range length m. The variance mp(1 − p) is then of the order of the previous error, and the new error is of the order of the square root of the previous one. The range where the target can still be shrinks as n, √n, n^1/4, …, and after k probes it is of order n^1/2k. It gets down to a few places when 2^k ≈ log₂ n, that is, at k ≈ log₂ log₂ n. For a million keys that is 4.3 probes, for a billion 4.9.

This was proved rigorously in 1978 by Yehoshua Perl, Alon Itai and Haim Avni: about log₂ log₂ n probes are enough on average, and making noticeably more is very unlikely. On the hashes from the scene log₂ log₂ 42,311 ≈ 3.94, and the listing below measured 4.0 on average.

Where it breaks

Everything rests on the curve of values being close to a straight line. If it is not, the chord lies, and one can build a row where it lies every time.

In the scene this is the “giant” row: 1 … 4999 and 10¹⁸. The window does not narrow: one place is nipped off on the left at a time, and the giant in the corner keeps pulling the chord down. Real data break the search more gently, but for the same reason.

• Populations. The median city of 45,227 has 25,247 people, 73% of the cities have fewer than 50,000, and the largest has almost 25 million. The curve is a shelf with a cliff, and the cliff plays the giant’s role: 1587 probes on average, 2211 at worst.
• The phone book. A name is a number made of its first four letters in base 27, as if the book were opened alphabetically. But the letters are unequal: 4898 names begin with S, 211 with X. Interpolation makes 17.6 probes on average, 60 at worst, and binary search 13.1.
• Latitudes. Almost two thirds of the cities lie between 20° and 60° north, and there are almost none towards the poles. A chord drawn through the extreme latitudes misses: 16.0 probes against 14.0.

Worst of all, this cannot be seen in advance: on the hashes there are almost four times fewer probes than for binary search, on the names more, and on one and the same data different targets behave differently.

Insurance

The cure is simple: alternation. An odd probe goes by the chord, an even one into the middle of the range. The halving steps guarantee that the range shrinks, and the chords keep the luck where the curve is even.

The worst case is twice as bad as binary search, but on average on our rows it comes out like this:

On latitudes the search by turns beats both. The halving steps cut off the uneven pieces, and on a short range any smooth curve is almost straight, so the chord hits again. Hence the next step: if the curve is straight piece by piece, it can be cut into pieces in advance.

A curve of straight pieces

Cut the row into pieces so that in each piece the line through its first key guesses the place of any key with an error of at most ε. A piece takes keys one at a time while such a line exists: each key allows its own range of slopes, and their intersection narrows like a cone with its apex at the first key. When the intersection is empty, a new piece begins. The index stores the starts of the pieces and the slopes. A search finds the piece by binary search over the starts, estimates the place by its line and looks for the target among the 2ε + 1 neighbouring places.

City populations with ε = 64 fit into 18 pieces. Bookmarks every 129 keys, which would give the same window, would need 238. Six pieces are enough for the hashes instead of 328, and 25 for latitudes instead of 252. There are about as many probes as for binary search; the gain is in memory: for populations the index is 13 times smaller, for hashes 55 times, and the last probes go within 129 neighbouring keys, which for 64-bit keys is one kilobyte of memory.

This is how the learned indexes of databases are built. FITing-tree in 2019 cut the key curve with a greedy “shrinking cone”, PGM-index in 2020 so that there were as few pieces as possible, and built the same kind of pieces over the starts of the pieces. This is interpolation search that has, instead of one chord for the whole curve, a chord for each almost straight piece.

Code

The listing builds from 45,227 cities the same five rows as the scene and searches each for every 50th value in three ways: by the chord, by turns and by binary search. For each way it prints the mean and the largest number of probes.

sorted row                 size  interpolation       by turns         binary
                                    mean   max     mean   max     mean   max
hashes of the names       42311      4.0     9      6.7    15     14.4    16
names, a phone book       17205     17.6    60     12.9    23     13.1    15
latitudes                 32407     16.0    43     10.2    17     14.0    15
populations               30576   1587.2  2211     12.3    23     13.9    15
1 .. 4999 and one giant    5000   2476.0  4951      4.9    15     11.3    13

The largest number of probes for the giant, 4951, is the worst-case claim in action: the target at place 4950 is searched for by probes at places 0, 1, …, 4950. Search by turns on the same targets makes at most 15 probes, and its bound is 2⌊log₂ 5000⌋ + 2 = 26.

Probes and time

A probe is not a unit of time. A probe of binary search has comparisons and a shift, while a probe by the chord also has subtractions, a multiplication and a division, in Go 128-bit ones at that. The benchmark below looks up random keys among n random 63-bit ones; on them the curve is even, as on hashes.

On a million keys search by the chord makes 4.4 probes on average, binary search 19.0: 4.3 times fewer. But in time the difference is almost twofold in Go and 1.4 times in Python. On a thousand keys in Python search by the chord does not win: the interpreter spends as much on multiplying and dividing big numbers as was saved on probes. The gain grows with n: when the array does not fit in the cache, what becomes expensive is each probe, not the arithmetic in it.

Others have seen something similar. Perl, Itai and Avni wrote in 1978 that in a machine’s memory interpolation search runs level with binary search and is slightly faster only on files of more than 5000 records; the gain in probes matters when each probe is a disk read. In git interpolation over hashes was tried from 2007: SHA-1 hashes are uniform, there is no better case. In 2017 it was removed: on git rev-list --objects --all in the Linux kernel repository it gave 37.4 seconds against 35.4 without it. And in 2019 Peter Van Sandt, Yannis Chronis and Jignesh Patel showed that a careful implementation that reuses the slope of the previous chord can be up to four times faster than binary search on uniform data.

What it costs

The last row is two binary searches: over the m starts of the pieces and over a window of 2ε + 1 places. Cutting into pieces with a greedy cone is one pass, O(n). The average case by the chord is log₂ log₂ n only for uniform keys. On other distributions it can be anything, up to linear, and without insurance this search is sensibly used only where the shape of the data is known in advance.

Where it works

• git. The pack index of objects has a table of 256 numbers: how many hashes begin with a byte no greater than the given one. By the first byte of a hash the table at once gives a range of length about n/256, and the binary search runs over it. This is interpolation done in advance and with a table. And the oid_pos function in git’s code makes only the first probe by the chord, by a pair of hash bytes, and halves after that.
• Learned indexes. FITing-tree, PGM-index and their descendants store, instead of the pages of a B-tree, straight pieces with a guaranteed error. The article’s problem is about this.
• Dictionaries. Letter tabs cut into the page edges are the same table as in git: the share of pages for each letter is known in advance, and interpolation is left to do inside the letter.
• Roots of equations. The secant method (regula falsi) looks for the root of a monotonic function the same way: it draws a line through the ends of the interval and takes the point where it crosses zero. And the illness is the same: on a convex function one end gets stuck, and convergence becomes slow. So is the cure: Brent’s method, for example in scipy.optimize.brentq, interleaves chords and parabolas with bisection.

History

Search by estimating the place was described by Wesley Peterson in 1957, in a paper on finding records in random-access storage. Four years later Peterson would devise the cyclic redundancy check, CRC. Peterson believed that on average the search needed no fewer than half of log₂ n accesses. The estimate turned out too pessimistic. In 1976 Andrew Yao and Frances Yao proved by an intricate combinatorial argument that on random uniform tables log₂ log₂ n is enough, and that no search can do noticeably better on average. In 1977 Perl and Edward Reingold gave an intuitive explanation, and in 1978 Perl, Itai and Avni their own proof and an experiment: on 400,000 uniform keys 4.28 accesses on average with log₂ log₂ n = 4.21.

After that the method was considered a pretty theory for decades: in memory it lost to binary search because of the cost of a probe, and on non-uniform data because of the number of probes. It came back with learned indexes: if the curve is not straight as a whole, it can be made straight piece by piece.

Problems

In the problem the moments of earthquakes, the populations and the latitudes of cities have to be cut into straight pieces with that very shrinking cone, and the pieces counted. The keys go up to 2·10¹⁸, and the slopes have to be compared exactly.