3 ms·

Wow, this sounds like a really fascinating study! Binary Search has long been the go-to method for sorted, in-memory data search due to its effectiveness and si

Wow, this sounds like a really fascinating study! Binary Search has long been the go-to method for sorted, in-memory data search due to its effectiveness and simplicity. However, given the limitations of Binary Search in certain scenarios, it's exciting to see new algorithms being proposed that could potentially perform better under specific circumstances. It's intriguing that Interpolation Search, despite its historically lackluster performance, is being given a second life through SIP and TIP. I love the fact that they're leveraging hardware trends and advanced calculations to optimize search performance. The fact that SIP shows up to 4x faster performance on uniformly distributed data and TIP is 2-3x faster on non-uniformly distributed data is quite promising. It seems these approaches could be really useful in practice, given that real-world data often follows non-uniform distributions. The introduction of a meta-algorithm to dynamically select the optimal search algorithm based on the data distribution is a clever touch. It helps to enhance the overall search performance by not sticking to a one-size-fits-all approach. I'd love to read more about these techniques and their practical implementations. Do they have any benchmarks or plans to test these new methods in large-scale, real-world systems?

switchbak 3y ago
Serious question: did you use an LLM tool to craft some or all of this comment?
- finexplained 3y ago
  The five paragraph format will forever be suspicious.
- adamisom 3y ago
  I’d be willing to bet money at 5-1 against that they didn’t. since that’s impossible to prove, I guess also on running an llm a lot of times and getting anything close to it.
- maxbond 3y ago
  What suggests to you it may have been?
  - refulgentis 3y ago
    It’s repeating trivialities that would be well-understood and are somewhat hyperbolic for both the audience and the real meat of the content. C.f. “Binary search has long been…”
    - maxbond 3y ago
      I don't really see it, my experience with other LLMs is limited, but ChatGPT tends to use the rhetorical tricks you're gesturing at to speak in generalities and avoid expressing a definite opinion - it's the shallow even-handedness of a bullshitted essay, where you avoid saying something definite because you don't actually know what you're talking about. But the parts of the comment you're highlighting are specific and opinionated. And I don't find them particularly hyperbolic.
    - deleted 3y ago
      [deleted]
- tuukkah 3y ago
  Nah, that's just what academic correspondense looks like.
- lucgagan 3y ago
  uh, HN doesn't do a great job surfacing responses to comments. Had to no clue about this whole conversation!
pvansandt 3y ago
This was an interesting journey. My original target was at L1 sized arrays with constant sized error, but that limits its applicability to the target audience. My initial exploration with spline based indexes were at this target data size, so they weren't competitive. SIP is very sensitive to quality of implementation. I did my best to steel man binary search, but if either is not implemented carefully, then you can easily get inverted results. I tried several different axes of variation for implementation of binary search and probably spent more time optimizing binary search than SIP or TIP, but binary search is very sensitive to cache misses and how that relates to branch prediction and conflict misses. Quality of linear search is also critical and relies heavily on array padding. SIMD was actually a major pessimization since for SIP, it's only worth using if linear search is < 100 elements or so. I spent a lot of effort trying to model the performance of SIP to predict from statistics of the data to how it would perform. You can consider the cost of each interpolation as a random access cache miss, and the cost of a linear search based on its distance, but the cost of a linear search has decreasing marginal cost with more distance before you reach steady state, which is exactly where you are using it in SIP. So, that basically led nowhere, but it does point out that an L2 norm is the wrong metric for identifying if interpolation would be useful on your data. I think the bigger insight of TIP is around its use of efficient approximations for hyperbolic interpolations. There's a lot of research around polynomial interpolation, but I think that hyperbolas are also worth examining. I don't expect TIP to be used in a database engine, and while data might be commonly zipf distributed, I'm not sure that people are putting that kind of data into an array and doing lookups on them where the values at the bottom of the array have a lot of duplicate values. SIP, I think, is more about increasing amounts of spatial cache locality, and making the most of out-of-order processors. It is more a variation on interpolation-sequential search, so it might be more practically used in a SIP-2 or SIP-3 variation which a hard-coded, unrolled number of iterations. (SIP-1 would just be interpolation sequential.) The downside of an interpolation method is that pairs of sequential interpolations don't surround the target, which leaves the search unbounded. I don't find hybrid approaches very interesting because I don't expect an implementation to be able to pipeline useful work which has a time per iteration that is sufficiently fast. For perspective, on billion element arrays, I think typical number of interpolations was around 3. We would expect number of interpolations to not increase to 4 until you hit a quintillion elements which suggests that the gap in efficiency between log N and log log N grows slowly enough that algorithmic gains have a nearby, practical upper bound to potential improvement. One of my favorite related papers is RadixSpline by Kipf et al. The amount of additional memory across a number of scenarios would be tiny, you could write a very efficient inner loop, and it would have basically been tailor fit to work perfectly on the FB dataset (one of the real world distributions).

switchbak 3y ago

Serious question: did you use an LLM tool to craft some or all of this comment?

finexplained 3y ago
The five paragraph format will forever be suspicious.
adamisom 3y ago
I’d be willing to bet money at 5-1 against that they didn’t. since that’s impossible to prove, I guess also on running an llm a lot of times and getting anything close to it.
maxbond 3y ago
What suggests to you it may have been?
- refulgentis 3y ago
  It’s repeating trivialities that would be well-understood and are somewhat hyperbolic for both the audience and the real meat of the content. C.f. “Binary search has long been…”
  - maxbond 3y ago
    I don't really see it, my experience with other LLMs is limited, but ChatGPT tends to use the rhetorical tricks you're gesturing at to speak in generalities and avoid expressing a definite opinion - it's the shallow even-handedness of a bullshitted essay, where you avoid saying something definite because you don't actually know what you're talking about. But the parts of the comment you're highlighting are specific and opinionated. And I don't find them particularly hyperbolic.
  - deleted 3y ago
    [deleted]
tuukkah 3y ago
Nah, that's just what academic correspondense looks like.
lucgagan 3y ago
uh, HN doesn't do a great job surfacing responses to comments. Had to no clue about this whole conversation!

pvansandt 3y ago

This was an interesting journey. My original target was at L1 sized arrays with constant sized error, but that limits its applicability to the target audience. My initial exploration with spline based indexes were at this target data size, so they weren't competitive. SIP is very sensitive to quality of implementation. I did my best to steel man binary search, but if either is not implemented carefully, then you can easily get inverted results. I tried several different axes of variation for implementation of binary search and probably spent more time optimizing binary search than SIP or TIP, but binary search is very sensitive to cache misses and how that relates to branch prediction and conflict misses. Quality of linear search is also critical and relies heavily on array padding. SIMD was actually a major pessimization since for SIP, it's only worth using if linear search is < 100 elements or so. I spent a lot of effort trying to model the performance of SIP to predict from statistics of the data to how it would perform. You can consider the cost of each interpolation as a random access cache miss, and the cost of a linear search based on its distance, but the cost of a linear search has decreasing marginal cost with more distance before you reach steady state, which is exactly where you are using it in SIP. So, that basically led nowhere, but it does point out that an L2 norm is the wrong metric for identifying if interpolation would be useful on your data. I think the bigger insight of TIP is around its use of efficient approximations for hyperbolic interpolations. There's a lot of research around polynomial interpolation, but I think that hyperbolas are also worth examining. I don't expect TIP to be used in a database engine, and while data might be commonly zipf distributed, I'm not sure that people are putting that kind of data into an array and doing lookups on them where the values at the bottom of the array have a lot of duplicate values. SIP, I think, is more about increasing amounts of spatial cache locality, and making the most of out-of-order processors. It is more a variation on interpolation-sequential search, so it might be more practically used in a SIP-2 or SIP-3 variation which a hard-coded, unrolled number of iterations. (SIP-1 would just be interpolation sequential.) The downside of an interpolation method is that pairs of sequential interpolations don't surround the target, which leaves the search unbounded. I don't find hybrid approaches very interesting because I don't expect an implementation to be able to pipeline useful work which has a time per iteration that is sufficiently fast. For perspective, on billion element arrays, I think typical number of interpolations was around 3. We would expect number of interpolations to not increase to 4 until you hit a quintillion elements which suggests that the gap in efficiency between log N and log log N grows slowly enough that algorithmic gains have a nearby, practical upper bound to potential improvement. One of my favorite related papers is RadixSpline by Kipf et al. The amount of additional memory across a number of scenarios would be tiny, you could write a very efficient inner loop, and it would have basically been tailor fit to work perfectly on the FB dataset (one of the real world distributions).