标题：PH-tree，一个空间高效的存储结构和多维索引
ABSTRACT
- PH-tree：全称PATRICIA-hypercube-tree，是把之前一种叫做PATRICIA-trie的二叉树和超立方体合并起来设计的。
- 特色：空间高效。PH-tree是一个内存索引，带有一定的压缩性质。用这个索引存数据，有时甚至比存原数据还要小。
1. INTRODUCTION
- 搜索高效：与维数无关
- 结构与构造顺序无关
- 更新高效：最多涉及两个节点
3. THE PH-TREE
PH-tree将高维数据全部二进制表示，基于trie树的前缀和四叉树的多扇出。优点如下：
- 四叉结构，同时考虑所有维度。
- 使得访问与维度存储的顺序无关。
- 使得节点数量减少。
- 使得树高度与维度无关。
- 因为高度有限制，所以即使PH-tree不是平衡树，也不需要单独为它的平衡性考虑，因为插入，更新最多和两个节点相关。
- PH-tree节点数目虽多，但是把每个节点的size，或者说节点内空间利用率提升了，用更少的空间存储同样多的信息。当然带一些性能代价。
- 超立方体寻址很快，一次数组查询就可以完成k维分割；二叉树就要路由k个节点。
3.1 The 1D-PH-Tree
先从存放1维数据开始讲起。假设每个1维数据有4个bit来表示，1维的PH-tree就类似一个trie树，存放这些bit串。如下图。
-
这个PH-tree高度最高就是4，每一维数据的bit宽度。
image.png
3.2 The kD-PH-Tree
当存放k维数据时，第一层使用各个维度的第一个bit，依次类推。每个节点称一个超立方体，节点中的数字称地址。
image.png
3.3 Floating Point Values
浮点数都是IEEE754存储的，二进制码和十进制的大小没什么关系。因此本文转换了存储模式，使得二进制码的顺序和十进制顺序一致。
【后续是复杂度分析和实验，有空补充】
网友评论