gvinciguerra

5 ms·

1. 1.▲
   by gvinciguerra 6y ago

   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 ;)
2. 2.▲
   by gvinciguerra 6y ago

   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. Thanks again!
3. 3.▲
   by gvinciguerra 6y ago

   Not at all @virattara ;) I don't have an answer right now, I just need to think about it more deeply
4. 4.▲
   by gvinciguerra 6y ago

   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 https://news.ycombinator.com&
5. 5.▲
   by gvinciguerra 6y ago

   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 months of wor
6. 6.▲
   by gvinciguerra 6y ago

   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 (
7. 7.▲
   by gvinciguerra 6y ago

   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 main memory in less t
8. 8.▲
   by gvinciguerra 6y ago

   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 setting of the RDBMS).
9. 9.▲
   by gvinciguerra 6y ago

   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 alre
10. 10.▲
    by gvinciguerra 6y ago

    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/
11. 11.▲
    by gvinciguerra 6y ago

    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.
12. 12.▲
    by gvinciguerra 6y ago

    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 prefi
13. 13.▲
    by gvinciguerra 6y ago

    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 disk page. It's
14. 14.▲
    by gvinciguerra 6y ago

    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, and then use the PGM-in
15. 15.▲
    by gvinciguerra 6y ago

    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 ma
16. 16.▲
    by gvinciguerra 6y ago

    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 keys
17. 17.▲
    by gvinciguerra 6y ago

    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 is open-so
18. 18.▲
    by gvinciguerra 6y ago

    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 ans