Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

PGM Indexes: Learned indexes that match B-tree performance with 83x less space

pgm.di.unipi.it

Post reply on HN
Print view View original

21–30 of 124 posts

Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space

#21

Post by brokencode »

harperlee wrote: post #4

They should have chosen another name, the acronym PGM already stands for Probabilistic Graphical Model and they overlap in possible usages.

This type of comment is pretty common, but never adds to the discussion. Some things are going to have similar names, and usually it just doesn’t matter.

Take Rust the game and Rust the programming language. How often do people confuse them? I’ve never seen it happen. Never mind the fact that rust is also a compound that forms when iron combines with oxygen.

In my book, it’s better to come up with a name that makes sense or is memorable as long as it’s not very confusing.

Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space

#22

Post by sa46 »

joe_the_user wrote: post #19

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…

If there's even a rough order to the underlying data, I'll buy their claim. On ordered data, a Postgres block-range index (BRIN) is often several orders of magnitude smaller than a B-tree index.

If the data is random, I suspect you're right and the PGM index is no-better than a B-tree index. Most data does have an order and would probably see similar gains.

Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space

#23

Post by hansvm »

sa46 wrote: post #22
joe_the_user wrote: post #19

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…

If there's even a rough order to the underlying data, I'll buy their claim. On ordered data, a Postgres block-range index (BRIN) is often several orders of magnitude smaller than a B-tree index. If the data is random, I suspect you're right and the PGM index is no-better than a B-tree index. Most data does have an order and would probably see similar gains.

Not only is there a rough order, they explicitly require the ability to meaningfully embed data into the reals, and the performance gains come from assuming those embeddings have simple delta distributions. I wouldn't be surprised if the technique is worse than useless when that assumption is violated.

Edit: I don't have time right now, but a toy example I like to throw at these kinds of problems is mapping primes to their indices (e.g. 2->0, 3->1, 5->2, ...). General-purpose learning algorithms can usually make a little headway with it, but not much, and only with substantial resources thrown at the problem. I'd be shocked if that toy example were any faster with their solution than a b-tree.

Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space

#25

Post by petergeoghegan »

joe_the_user wrote: post #19

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 paper says 83x, and even makes stronger claims that are fairly unqualified:

In short, the experimental achievements of the PGM-index are: (i) better space occupancy than the FITing-tree by up to 75% and than the CSS-tree by a factor 83×, with the same or better query time; (ii) uniform improvement of the performance of RMI in terms of query time and space occupancy, and 15× faster construction, while requiring no hyperparameter tuning; (iii) better query and update time than a B+-tree by up to 71% in various dynamic workloads while reducing its space occupancy by four orders of magnitude (from gigabytes to few megabytes).

I wonder why it was just four orders of magnitude, though. Why not six or twelve?

Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space

#26

Post by jltsiren »

Some context: A few years ago, there was a paper from Google (https://dl.acm.org/doi/10.1145/3183713.3196909) that made learned data structures popular for a while. They started from the idea that indexes such as B-trees approximate an increasing function with one-sided error. By using that perspective and allowing two-sided error, they were able to make the index very small (and consequently quite fast).

Many data structure researchers got interested in the idea and developed a number of improvements. The PGM-index is one of those. Its main idea is to use piecewise linear approximations (that can be built in a single quick pass over the data) instead of the machine learning black box the Google paper was using.

Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space

#28

Post by xucheng »

joe_the_user wrote: post #19

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 size comparison here only concerns the size of index. That is the size of the data is excluded.

Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space

#29

Post by siscia »

joe_the_user wrote: post #19

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.

Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space

#30

Post by xucheng »

hansvm wrote: post #23
sa46 wrote: post #22

Earlier quoted context omitted.

If there's even a rough order to the underlying data, I'll buy their claim. On ordered data, a Postgres block-range index (BRIN) is often several orders of magnitude smaller than a B-tree index. If the data is random, I suspect you're right and the PGM index is no-better than a B-tree index. Most data does have an order and would probably see similar gains.

Not only is there a rough order, they explicitly require the ability to meaningfully embed data into the reals, and the performance gains come from assuming those embeddings have simple delta distributions. I wouldn't be surprised if the technique is worse than useless when that assumption is violated. Edit: I don't have time right now, but a toy example I like to throw at these kinds of problems is mapping primes to…

Due to the prime number theorem, your toy example actually has a very good approximated mapping.
Post reply on HN