pvansandt

4 ms·

1.
by pvansandt 3y ago
If your data is uniformly distributed, you wouldn't expect higher order approximations to reduce error. You would have to weigh the cost of that approximation against using an interpolation to get more local data. So, a linear equation
2.
by pvansandt 3y ago
This wouldn't go into a standard library since it's distribution dependent, but you might be interested to note a non-trivial (nor game changing) improvement to leveldb query time even with all the other work that it's doing
3.
by pvansandt 3y ago
Piecewise linear was one of the first things that I experimented with, but it is getting near to index based approaches, which is a different topic. It also is inefficient for non polynomial distributions. On things that approach linear, th
4.
by pvansandt 3y ago
Big fan on your presentation on binary search that amortised multiple concurrent searches. I did several variations on binary search and always compared against the best one. [0] From what I remember, some variations were compiled to a bran
5.
by pvansandt 3y ago
I (author) agree that certainly at the higher end of element counts, it would be a very strange decision to not use an index. One of my favorite related papers is RadixSpline by Kipf, which shows an index based approach. However, the inner
6.
by 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,