Haven't heard of it, and I couldn't find the phrase "piecewise-linear interpolation search" online at all. Care to share? In particular, how are the pieces dete

Haven't heard of it, and I couldn't find the phrase "piecewise-linear interpolation search" online at all. Care to share? In particular, how are the pieces determined? The Google paper is "The Case for Learned Index Structures" I think? This paper discusses index structures to be stored along with the data, so it's not directly comparable to the OP, which starts with the sorted data alone. Google's use case is so dominated by lookups that as far as I can tell they don't even report on the time to construct the index. I'm not sure the same priorities hold in every domain.