一种内存搜索树的键值保序压缩技术-熊艳辉.pdf

243

22页

35次

2022-12-01

免费下载

ENMOTECH

Order-Preserving Key Compression for

In-Memory Search Trees

作者: 熊艳辉

部门: 核心产品研发2部

日期: 2022/12/01

SIGMOD'20 论文学习分享

数 / 据 / 驱 / 动成 / 就 / 未 / 来

Scenarios

 In-memory search Tree(内存数据结构,加速数据查询,解决内存footprint问题)

Solution

 High-speed Order-Preserving Encoder (HOPE压缩框架)

Key Techniques

 Fast dictionary-based compressor

 Identify common key patterns at a fine granularity

 Exploit the entropy to achieve high compression rates with a small dictionary

 Encodes arbitrary keys while preserving their order

Contributions

 Develop a theoretical model to reason about order-preserving dictionary designs

 Six representative compression schemes implement model in HOPE

 Evaluate HOPE on five data structures used in databases: SuRF, ART, HOT, B+tree, and Prefix B+tree

Conclusion

 Lower query latency(up to 40% lower) and better memory efficiency (up to 30% smaller) simultaneously for most

string key workloads

latency

40%

memory footprint

30%

研究结论

of 22

免费下载

关注