Could this be used for/generalized for Nd spatial proximity lookup tables?
Yep, I'm working on a multidimensional version that I hope to upload to the main repo (https://github.com/gvinciguerra/PGM-index) in a few weeks.
PGM Indexes: Learned indexes that match B-tree performance with 83x less space
71–80 of 124 posts
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#72Their slides https://pgm.di.unipi.it/slides-pgm-index-vldb.pdf about PGM index, page 21.
They stop at page size of 1024 bytes - that indicates they are tested in-memory situation. And, which is worse, their compression ratio advantage almost halves when block size is doubled. Thus, what about B-tree with blocks of 16K or even 256K?
Also, what about log-structured merge trees where bigger levels can use bigger pages and, which is quite important, these bigger levels can be constructed using (partial) data scan. These bigger levels can (and should) be immutable, which enables simple byte slicing of keys and RLE compression.
So, where's a comparison with more or less contemporary data structures and algorithms? Why beat half a century old data structure using settings of said data structure that favors your approach?
My former colleague once said "give your baseline some love and it will surprise you". I see no love for B-trees in the PGM work.
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#73I 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…
So, from a quick read, I think there are a few things at play here that allow for "compression of random data".
One, and probably the biggest one, _this isn't lossless compression_. As other commenters mentioned, this aggregates groups of points into line segments and stores their slopes (allowing for a pre-specified error of up to epsilon).
Two, while the sample input data is randomly generated, it then needs to be sorted before it can be used here. This completely changes the distributional qualities (see: order statistics sampled from a uniform distribution [0]). Just as a toy example, suppose this was a million randomly-generated binary digits. Sure, you could store the million digits in sorted order, or you could just use run-length encoding and say "I have 499,968 zeroes and 500,032 ones" [1].
[0] https://en.wikipedia.org/wiki/Order_statistic#Order_statisti...
[1] I know, this is a dense sampling on the input space. But that's the sort of intuition that allows you to compress sorted data better than you'd be able to compress the unsorted data. The provided C++ code provides a sparse sampling.
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#74Some 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…
Hi Jouni!
You may find interesting these other papers of ours:
- The ALENEX21 paper "A 'learned' approach to quicken and compress rank/select dictionaries" (http://pages.di.unipi.it/vinciguerra/publication/learned-ran..., https://github.com/gvinciguerra/la_vector), where we introduce a compressed bitvector supporting efficient rank and select queries, which is competitive with several well-established implementations of succinct data structures.
- The ICML20 paper "Why are learned indexes so effective?" (http://pages.di.unipi.it/vinciguerra/publication/learned-ind...) where we prove that, under some general assumptions on the input data, the space of the PGM-index is actually O(n/B^2) whp (versus Θ(n/B) of classic B-trees).
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#75This is interesting. Could this be adapted to store 2D data, like how a quadtree is a 2D range tree? (If you link me to a paper / pseudocode for that, I could implement it.) I imagine it would be useful in GIS, gaming, etc.
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#76They 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 s…
People confuse the game and the language all the time in Reddit. We even had a talk at RustConf a few years back about teaching an ML model how to distinguish them.
(That said I agree with your post generally...)
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#77This is interesting. Could this be adapted to store 2D data, like how a quadtree is a 2D range tree? (If you link me to a paper / pseudocode for that, I could implement it.) I imagine it would be useful in GIS, gaming, etc.
Maybe space filling curve 2D to !D map gets you most of the way there?
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#78Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#79Their slides https://pgm.di.unipi.it/slides-pgm-index-vldb.pdf about PGM index, page 21. They stop at page size of 1024 bytes - that indicates they are tested in-memory situation. And, which is worse, their compression ratio advantage almost halves when block size is doubled. Thus, what about B-tree with blocks of 16K or even 256K? Also, what about log-structured merge trees where bigger levels can use bigger pages a…
Hi @thesz!
The experiment you are referring to is done in main memory with an optimised in-memory B+tree implementation. We didn't plot the performance for larger page sizes because in our machine they performed poorly, as you can already see from the configuration with 1024-byte pages. So we're not favouring our approach at all.
Note also that next-gen memories have smaller and smaller access granularities. For example, the Intel's Optane DC Persistent Memory accesses blocks of 256 bytes, while the Intel's Optane DC SSD accesses blocks of 4 KB. I guess that data structures with blocks of 16K-256K are disproportionate in these cases.
About LSM-trees, nothing prevents you to use a PGM-index (which you can construct during the compaction of levels, thus without scanning data twice) to speed up the search on a long immutable level. Or also, to use a PGM-index on data which is organised into RLE-compressed disk pages ;)
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#80Earlier quoted context omitted.
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.
You are right, variable-length strings are difficult. You could try to pack as many characters as possible in a computer word (or in a big int data type), say P characters, and then use the PGM-index to find the strings that share a prefix of P chars with the given query string. I discussed this solution in a GitHub issue ( https://github.com/gvinciguerra/PGM-index/issues/8#issuecomm... ). It may work in practice, bu…
Hi Giorgio, thanks for sharing!
You mentioned that tries have had recent advancements, could you please point me to a paper about these advancements so I can learn more? I did a quick Google search but wasn't able to find anything that seemed relevant.