Succint: Enabling Queries on Compressed Data

Rachit Agarwal, Anurag Khandelwal, Ion Stoica

UCB

在大量数据查询的时候，如果使用压缩作为优化方案，传统的压缩方法有trie树或者后缀树，但是对于内存的要求大概是10－20倍的输入数据。Burrows－Wheeler Transform(BWT)进行了优化，但也要5倍左右内存。FM-index和压缩后缀数组分别针对BWT和后缀数组使用压缩。Succint使用压缩后缀数组方法。

这里有关于后缀数组的介绍，又想起了原来搞ACM的欢乐时光 LOL

核心思路就是字典序排序生成的$$SA[i]$$，也是论文里面的$$AoS2Input$$，和名次数组$$rank[i]$$，论文里的$$Input2AoS$$。二者互逆。

后面感觉就是将压缩后缀数组应用到query，进行调整优化的问题。同时和MongoDB、Cassandra进行比较。