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

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, the extra steps to find the right spline can overweight the advantage of reduced error, so I think both search optimizations and building indices can coexist, shifting around where search should be the base case for an indexed search. Building and maintaining indices is also not free, so it's interesting to try to do your best with much less index maintenance.