Viewing profile — gvinciguerra

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…

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 (…

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 o…

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…

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-val…

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 y…

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 becaus…

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.…

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 the…

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 indirectio…

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 …

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 pag…

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 …

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 …

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 t…