61–70 of 124 posts
In the example they sort the data array. Does that mean this works just on sorted arrays? Insert and delete performance would be horrible I guess.
Isn’t sorting required for range based indexes?
I've only heard of B-trees in passing. In what kinds of situations are these data structures used?
I don't get it. I've implemented B-trees. The majority of space the used by a B-tree is the data itself. Each N-ary leaf of the tree is a basically a vector of data with maybe some bookkeeping at the ends. The leaves are more than half of the tree. Sure, you can compress the data. But that depends on the data, completely random data can't be compress. Other data can be. But a point blank 83x space claim seems bizarre…
The index does not store the data at all, it store slopes. You start by sorting the data, make a piecewise linear interpolation, and you store each slope as triplet (key, slope, intercept) with key being the smallest value in the piecewise interpolation. I find it quite clever to be honest. I am not sure how it works on inserts and delete, didn't read the whole paper. More digestible info on the slides.
And what do you mean by "intercept". Are you referring to the "b" in that same equation?
If that's true, in what way is that an optimization to storing "x" and "y" at each node?
Earlier quoted context omitted.
The index does not store the data at all, it store slopes. You start by sorting the data, make a piecewise linear interpolation, and you store each slope as triplet (key, slope, intercept) with key being the smallest value in the piecewise interpolation. I find it quite clever to be honest. I am not sure how it works on inserts and delete, didn't read the whole paper. More digestible info on the slides.
I'm almost good at math. Could you enlighten me, when you say "slope", are you talking about the slope of a line as defined by "The Equation of a Straight line" [0], i.e. the "m" in "y=mx+b"? And what do you mean by "intercept". Are you referring to the "b" in that same equation? If that's true, in what way is that an optimization to storing "x" and "y" at each node? [0] https://www.mathsisfun.com/equation_of_line.ht…
Hello everyone. I'm Giorgio, the co-author of the PGM-index paper together with Paolo Ferragina. First of all, I'd like to thank @hbrundage for sharing our work here and also all those interested in it. I'll do my best to answer any doubt in this thread. Also, I'd like to mention two other related papers: - "Why are learned indexes so effective?" presented at ICML 20, and co-authored with Paolo Ferragina and Fabrizio…
Can PGM index and linear approximation models in general be applied to clustered indexes, where actual data of variable size are stored in the index along with the keys?
They should have chosen another name, the acronym PGM already stands for Probabilistic Graphical Model and they overlap in possible usages.
Earlier quoted context omitted.
I'm almost good at math. Could you enlighten me, when you say "slope", are you talking about the slope of a line as defined by "The Equation of a Straight line" [0], i.e. the "m" in "y=mx+b"? And what do you mean by "intercept". Are you referring to the "b" in that same equation? If that's true, in what way is that an optimization to storing "x" and "y" at each node? [0] https://www.mathsisfun.com/equation_of_line.ht…
As parent said, it is a piecewise linear interpolation, which means it is divided into line segments. Hence you don't need the parameters for the whole index, only for each segment, as the parameters are the same for each point in the same segment.
After having linearly interpolated the points on the curve piecewise, instead of a smooth curve, you now have line segments that connect to other line segments, each point now connected to the next, not smoothly, but linearly, and each of those lines/segments can be optimized by storing only slope and intercept. Yes?
That seems both ingenious and very, very straight-forward. What is the reason behind us not having deployed massive amounts of search indices into the world that were built using this method? Has the drawback of this method been too great?
The drawback to me seems to be the amount of computation needed to produce such an index.
Earlier quoted context omitted.
The index does not store the data at all, it store slopes. You start by sorting the data, make a piecewise linear interpolation, and you store each slope as triplet (key, slope, intercept) with key being the smallest value in the piecewise interpolation. I find it quite clever to be honest. I am not sure how it works on inserts and delete, didn't read the whole paper. More digestible info on the slides.
I'm almost good at math. Could you enlighten me, when you say "slope", are you talking about the slope of a line as defined by "The Equation of a Straight line" [0], i.e. the "m" in "y=mx+b"? And what do you mean by "intercept". Are you referring to the "b" in that same equation? If that's true, in what way is that an optimization to storing "x" and "y" at each node? [0] https://www.mathsisfun.com/equation_of_line.ht…
Hello everyone. I'm Giorgio, the co-author of the PGM-index paper together with Paolo Ferragina. First of all, I'd like to thank @hbrundage for sharing our work here and also all those interested in it. I'll do my best to answer any doubt in this thread. Also, I'd like to mention two other related papers: - "Why are learned indexes so effective?" presented at ICML 20, and co-authored with Paolo Ferragina and Fabrizio…
I enjoyed glossing over the paper (will read it properly after work), but it was not immediately obvious to me how to implement this for strings. I'm no expert in this area, so this might have an obvious answer. I mean I guess you could treat characters as base 2^32 or something like that and convert a string to a real that way, but often strings have a non-trivial sort orders.