Merci打包方案
- 1 超图划分
将所有的数据划分为等大小的子图，降低打包数量。面临的问题：现有算法生成的子图都是固定大小，浪费空间；
- 2 设计关系感知的可变聚类方案
开始的时候给每个元素一个cluster，然后进行合并。合并的理由是这合并聚类后的Benefit大于Cost。
具体来说：
- Cost：由于Cluster中所有的特征都要打包，所以其打包的空间开销为：
image.png
所以可以计算出Cluster-A与Cluster-B打包后内存增加量为：
image.png
- Benefit：如下图，q1~q4是每一个推理sample的访问，其中f为每个访问中的vector。
image.png
其中I1代表：f1出现在q2，q3中，所以I1 = {q2,q3}；即f1出现在了哪个访问中；
第三步，将I1与I3合并（现在I1就是C1，C1目前只包括f1一个元素）的Benefit为2（有两次查询都会用到q2，q3，即原来要对q2，q3做两次操作，现在就做1次就行）
第四步，合并f1与f2，即I1,3。
image.png
这里可以理解为：把f1与f2同时打包，对q1，q2，q3都有好处（单个出现的情况也算）。
最后这里使用benefit-cost ratio：
image.png
预处理操作
1 来一个query，需要定位这些Vector属于哪个cluster，所以需要建立map；
2 建立Table索引
image.png
操作一：
将相同size的cluster打包成一个cluster
重新给每个Vector标记ID；
操作二：
- remap结束后，需要给每个cluster建立table索引，一个Cluster需要这么多内容：
image.png
- memoization table是一个2维数组，存储了R个向量；
image.png
具体步骤
1 对每个Cluster生成所有的打包组合；
2 使用one-hot格式对vector进行编码；
3 二进制对应的十进制的值-1（去掉空集）；
此外再维护一个table表来标识每个group的索引；
对于查询操作：
image.png
- 1 找到vector对应的cluster组：这里是以7为例子。
首先比较Group的First id后，发现7属于Group 1 。之后通过(feature ID - group first ID) / csize计算出7属于第1组的那个cluster：
image.png
此时我们想得到7+9的结果，怎么做呢？
image.png
image.png
这里可以理解为用Cluster的offset + 这个数据在这个Cluster的具体位置。
