Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How fast does interpolation search converge?

lemire.me

Post reply on HN
Print view View original

21–27 of 27 posts

Re: How fast does interpolation search converge?

#21

Post by unnouinceput »

tpolzer wrote: post #19
unnouinceput wrote: post #8

As a side note, if you have the possibility to sort data before searching values in it then implement trie: https://en.wikipedia.org/wiki/Trie This is the best for data with very few updates/modifications and a lot of queries. One example would be points of interest on a map, like restaurants on google maps. Not like those restaurants gets updated/modified every single day but you do have clients that while using you…

If you're already using Postgres, isn't that precisely what GiST indexes are meant for?

Yes, they are. But those are general approach. While a good approach my implementation was custom made for the client's need, allowing to achieve a better performance.

Re: How fast does interpolation search converge?

#23

Post by kzrdude »

jqpabc123 wrote: post #22

The problem I see is the assumption of a uniform distribution. The problem spaces I normally deal with involve clumps of data, not really uniform except within each clump.

is there something that's better than interpolation search and binary search, for that kind of data?

Re: How fast does interpolation search converge?

#24

Post by jonstewart »

Const-me wrote: post #18

One good thing about binary search is memory access pattern. The element in the middle of the array is tested every single time. Similarly, the elements at 25% and 75% of the array are tested very often, in 50% searches/each. Modern computers have very slow memory compared to computation speed, and multi-level caches to compensate. Binary search RAM access pattern, when done many times, is friendly towards these mult…

It’s true that those places will get cached, but binary search tends to dance around the address space a bit too much with large arrays. That’s one of the advantages of interpolation search—provided the items are uniformly distributed.

Re: How fast does interpolation search converge?

#26

Post by jqpabc123 »

kzrdude wrote: post #23
jqpabc123 wrote: post #22

The problem I see is the assumption of a uniform distribution. The problem spaces I normally deal with involve clumps of data, not really uniform except within each clump.

is there something that's better than interpolation search and binary search, for that kind of data?

It's often possible to do "better" by tuning something toward the data set. Finding something that is always better is hard.

One thing I have done is a double binary search.

Store prefixes and suffixes seperately. A binary search of the prefixes identifies the suffix clump to search with a binary search. This involves a slight increase in storage --- each prefix needs a suffix pointer.

But maybe I will now try an interpolation search on the suffixes.

Re: How fast does interpolation search converge?

#27

Post by ntonozzi »

nn3 wrote: post #11

I think Microsoft uses with btrees: https://github.com/microsoft/ALEX Of course they call it "ML", but it's just a linear interpolation for faster tree search.

Very cool, seems much higher quality than the RMI library. I’m hoping more of these learned data structures make their way into libraries.
Post reply on HN