14
$\begingroup$

I just read Can this algorithm still be considered a Binary Search algorithm? and recalled that a few years back I wrote an indexer/search for log files to find log entries in large plain text files by date/time window.

Whilst doing this, I decided to try interpolation search (I didn't know that was what it was called, I kind of stumbled across the idea by myself). Then for some reason I continued to the idea of alternating interpolation steps with binary split steps: On step 0 I would interpolate to decide test point, then step 1 I would take the exact midpoint etc.

I then benchmarked the system using pure interpolation search, pure binary search and my combination attempt. The alternating approach was a clear winner, both in time and number of tests required before finding a set of randomly chosen times.

Inspired by the linked question, I just made a quick search for "alternating interpolation search and binary search" and found nothing. I also tried "hedged interpolation search" as suggested on my comment on one of the answers.

Have I stumbled across a known thing? Is there any theoretical justification for it being faster for certain types of data? The log files were typically large for the time (e.g. 1-2 GB of text with maybe 10 million rows to search), and the spread of dates/times in them was complex with heavy bursts of activity, general peak times and quiet times. My benchmark tests sampled from an even distribution of target times to find.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
5
$\begingroup$

Have I stumbled across a known thing?

There are various methods, based on a mix of interpolation-search and binary search, with a $O(log\ log\ n)$ average case access time (uniform distribution) and $O(log\ n)$ worst case time (values unevenly distributed):

  • Introspective search is your method (iterating between an interpolation search and a binary search). I haven't further details.

  • Interpolation-binary search (IBS) by N. Santoro, J. B. Sidney (1985).

    The general idea is that interpolation search is useful only when the array searched is larger than a given threshold. When the considered search segment is smaller than a user-defined threshold, binary search is applied unconditionally. Vice-versa, over that threshold, an interpolation search step is applied, followed eventually by a binary search step.

    This has many common points with your approach.

  • Adaptive search (AS) by Biagio Bonasera, Emilio Ferrara, Giacomo Fiumara, Francesco Pagano, Alessandro Provetti

    Using the authors' words:

    [Interpolation-binary search] devised a similar solution that combines (but does not blend) together interpolation and binary search. Although the asymptotic complexity is the same, there are some marked differences.

    [CUT]

    Hence, it is possible to show that for any input AS will not take more elementary operations than IBS.

    The algorithm may spend up to double number of operations than "simple" interpolation search in carefully finding out the best halving of the search segment, which in turn will mean that less iterations shall be needed to complete (but you have an even greater overhead).

Improve this answer
$\endgroup$
6
$\begingroup$

Interleaving two algorithms to get the best of both worlds is a known technique, though it is usually stated as running them in "parallel" and returning an answer as soon as either terminates.

Though theoretically faster, interpolation search has two disadvantages compared to binary search:

  • It has terrible (linear) worst case performance

  • The overhead of computing the midpoint is rather large; a binary search iteration is hundreds of times faster than an interpolation search one

I would expect that an approach where you do interpolation search while the range is large and switch to binary search when the range becomes small is the most efficient. It would be nice if you could try this experiment.

As your dataset becomes small, the difference between $\log n$ and $\log \log n$ becomes insignificant; $\log n$ is already really small, and $\log \log n$ couldn't possibly be much smaller. At this point, the overhead of doing interpolation search is not worth it compared to the iterations you might save.

I think that your results can be explained by two phenomena:

  • Combining with binary search allows you to avoid the worst-case behavior

  • The positive effect of switching to binary search on a small dataset

Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ You wrote: "a binary search iteration is hundreds of times faster than an interpolation search one". Please note that in OP's case, the difference between computing the midpoint in those two methods is dwarfed by the I/O time necessary to retrieve the midpoint's value. $\endgroup$
    – liori
    Commented Jun 17, 2016 at 0:26
  • $\begingroup$ @liori: The early few iterations of repeated binary searches on the same data might be more cache-friendly, because the same few elements are used. So the quarters and maybe eighths can be expected to stay hot in cache. Starting with binary and switching to interpolated after three iterations might make sense, if the ranges are big enough. (Or if you can do async I/O and use whichever result arrives first). $\endgroup$
    – Peter Cordes
    Commented Jun 17, 2016 at 0:47
  • $\begingroup$ Also, even for an in-memory search, a cache miss (over 200 cycles latency) has a couple times the latency of even a 64bit integer division (32-96cycles), on Intel Haswell for example. 32bit integer division is significantly faster (22-29cycles). Main memory bandwidth is a shared resource for all cores, but integer division only uses resources duplicated on each core. $\endgroup$
    – Peter Cordes
    Commented Jun 17, 2016 at 0:54
  • 2
    $\begingroup$ However, memory latency is much worse than memory bandwidth, since even multiple scattered accesses go faster if they're in flight at once. It's a win to prefetch (with prefetcht0 instructions) both possibilities for the NEXT iteration before loading the current midpoint, for an in-memory bsearch on modern x86 hardware. You can't do that if you can't predict the next fetch addresses ahead of time. So practical implementation details can be significant, aside from theoretical considerations. $\endgroup$
    – Peter Cordes
    Commented Jun 17, 2016 at 0:56
  • $\begingroup$ @liori: Definitely I/O per midpoint was the main factor when indexing a log file, as it was being read on demand in order to find records. There was probably more than two orders of magnitude between calculating offset in file and reading a block - therefore number of midpoints calculated would be the deciding factor. I think if I replicate now without a log file to index - something I will try and post here - that there might not be a measurable speed difference, but there might be a measurable "number of midpoints needed" difference. $\endgroup$
    – Neil Slater
    Commented Jun 17, 2016 at 5:40
2
$\begingroup$

Last study published here and compared with Adaptive search experimentally. Interpolated binary search: An efficient hybrid search algorithm on ordered datasets

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.