Hi @magicalhippo and @midjji. Please, have a look at the main repo, I just uploaded an implementation of the multidimensional PGM-index supporting orthogonal range searches ;)
Hi @crazypython and thank you! Yep, I just added an implementation of the multidimensional PGM-index in the main repo. If you want to improve it, you are more than welcome. Drop me an email if you have some ideas.…
Not at all @virattara ;) I don't have an answer right now, I just need to think about it more deeply
From a Big-Oh point of view, the answer is a big yes. No matter the memory technology or the disk page size, be it 256B or 16KB, the PGM-index can scale as B-trees or even better (see my comment here…
Thank you so much for your interest, BenoitP! Right now I'm focusing more on the design of compressed data structures. RDBMS are complex systems, and gaining sufficient knowledge of their internals would require several…
Hi @Gh0stRAT, you are very welcome! For prefix search on strings, I recommend the classic String B-tree paper (https://dl.acm.org/doi/10.1145/301970.301973). Among recent results, there's the c-trie++ paper…
Hi @kreeben, the construction is very fast, it can be done in linear time with a single scan of the data. Just to give you some figures, we constructed a PGM-index on 10^12 key-value pairs (8 bytes + 8 bytes) loaded in…
Thank you @mr_gibbins. I think an implementation in RDBMS is worth exploring. After all, the page size of the PGM-index can be tuned to match the one of the media you are storing your data to (or to match the default…
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,…
Hi Jouni! You may find interesting these other papers of ours: - The ALENEX21 paper "A 'learned' approach to quicken and compress rank/select dictionaries"…
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.
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…
Yep, in that case you could use an indirection vector containing, for each key k, the offset to the first byte of k. This is what is typically done in B-trees, where the indirection vector is stored in the header of a…
Hi @zupa-hu! In the paper we focused on indexing keys, as the compression of keys and values is an orthogonal problem. For example, you can compress disk pages containing keys and values with a method of your choice,…
Hi @jabberwcky! The plot refers to a B+tree implementation optimised for main-memory (https://panthema.net/2007/stx-btree/). We didn't show the performance for larger/smaller page sizes because in our machine they…
Hi @etaioinshrdlu! The worst-case bounds are discussed in *Section 2.2* and *Theorem 1*. Essentially, we have the following bounds: Query: O(log_c(m) log_2(ε/B)) I/Os Space of the index: O(m) where: n = number of input…
Hi @legulere! Yep, the example of Figure 2 shows only a static PGM-index on a sorted array. Insertion and deletions are discussed in Section 3 "Dynamic PGM-index" and experimented in Section 7.3. The Dynamic PGM-index…
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…
Hi @magicalhippo and @midjji. Please, have a look at the main repo, I just uploaded an implementation of the multidimensional PGM-index supporting orthogonal range searches ;)
Hi @crazypython and thank you! Yep, I just added an implementation of the multidimensional PGM-index in the main repo. If you want to improve it, you are more than welcome. Drop me an email if you have some ideas.…
Not at all @virattara ;) I don't have an answer right now, I just need to think about it more deeply
From a Big-Oh point of view, the answer is a big yes. No matter the memory technology or the disk page size, be it 256B or 16KB, the PGM-index can scale as B-trees or even better (see my comment here…
Thank you so much for your interest, BenoitP! Right now I'm focusing more on the design of compressed data structures. RDBMS are complex systems, and gaining sufficient knowledge of their internals would require several…
Hi @Gh0stRAT, you are very welcome! For prefix search on strings, I recommend the classic String B-tree paper (https://dl.acm.org/doi/10.1145/301970.301973). Among recent results, there's the c-trie++ paper…
Hi @kreeben, the construction is very fast, it can be done in linear time with a single scan of the data. Just to give you some figures, we constructed a PGM-index on 10^12 key-value pairs (8 bytes + 8 bytes) loaded in…
Thank you @mr_gibbins. I think an implementation in RDBMS is worth exploring. After all, the page size of the PGM-index can be tuned to match the one of the media you are storing your data to (or to match the default…
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,…
Hi Jouni! You may find interesting these other papers of ours: - The ALENEX21 paper "A 'learned' approach to quicken and compress rank/select dictionaries"…
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.
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…
Yep, in that case you could use an indirection vector containing, for each key k, the offset to the first byte of k. This is what is typically done in B-trees, where the indirection vector is stored in the header of a…
Hi @zupa-hu! In the paper we focused on indexing keys, as the compression of keys and values is an orthogonal problem. For example, you can compress disk pages containing keys and values with a method of your choice,…
Hi @jabberwcky! The plot refers to a B+tree implementation optimised for main-memory (https://panthema.net/2007/stx-btree/). We didn't show the performance for larger/smaller page sizes because in our machine they…
Hi @etaioinshrdlu! The worst-case bounds are discussed in *Section 2.2* and *Theorem 1*. Essentially, we have the following bounds: Query: O(log_c(m) log_2(ε/B)) I/Os Space of the index: O(m) where: n = number of input…
Hi @legulere! Yep, the example of Figure 2 shows only a static PGM-index on a sorted array. Insertion and deletions are discussed in Section 3 "Dynamic PGM-index" and experimented in Section 7.3. The Dynamic PGM-index…
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…