3 ms·
Note by compression they mean keeping internal blocks closer to full. It looks like a good thesis and advisors are reputable. But this comes with a trade-off.
by alecco 7y ago
Note by compression they mean keeping internal blocks closer to full. It looks like a good thesis and advisors are reputable.
But this comes with a trade-off. As blocks are full, inserts trigger more often a cascade effect. Batching inserts helps but once you need to apply the batch that could take a long time to rebalance potentially the whole tree. This adds a fat tail to insert times. But in many read-heavy scenarios it is a good trade-off.
- dgacmu 7y agoThere was an aspect of that in the first part of the thesis, but the rest has techniques that are independent. You can roughly break the thesis down by paper: * Hybrid Indexes (a read-only, full-block kinda thing where you have to handle inserts by using a second read-write tree) * SuRF, a succinct range filter data structure * Order-Preserving Key Compression for In-Memory Search Trees Each of them can be used independent of the others, or combined. You can find two of those papers on Huanchen's web page: http://www.cs.cmu.edu/~huanche1/ http://www.cs.cmu.edu/~huanche1/ the third is to-appear, but you can find a preprint on arxiv: https://arxiv.org/abs/2003.02391 https://arxiv.org/abs/2003.02391
- alecco 7y agoExcellent. Great job!