论文地址：Quad Trees
A Data Structure for Retrieval on Composite Keys

Summary

quad tree 是适合在 composite keys 上检索的数据结构。本文讨论二维的情况，虽让这种结构可以轻松的扩展到多维。介绍了直接插入和平衡插入方法。经验分析告诉我们插入的平均时间是tree size 的对数。介绍了一种检索区域的方法，展现出了查询的高效性。定义了一种最优树，提供了一种算法在 $nlogn$ 的时间内完成优化。但是 delete 和 merging 操作似乎具有内在的困难性。

introduction

One way to attack the problem of retrieval on composite keys is to consider records arranged in a several-dimensional space, with one dimension for every attribute.
一种处理复合键（composite keys）检索的方法是将记录（records）看作是分布在多维空间中（一个字段视为一个维度），然后用一个维度作为索引进行连接。
此时 range query 可以被认为是满足制定规则的多维空间中的一片子区域。
只在一个 key 上进行检索已经有了很好的成果，binary tree、 balanced binary trees
本文将binary tree 进行扩展，并讨论在二维结构数据上的表现。最清晰的例子就是地图上的城市记录。一个简单的查询可以是：Find all the cities which are within 300 miles of Chicago or north of Seattle.

Definitions and Notation

二维 records 存储在每个节点的出度为四的树中。每个节点存储一个 record 并且最多有四个sons。树的 root 将universe 分成四份，可叫做NE、NW、SW、SE，也可以叫四个象限。如图一所示是一棵简单的树以及它表示的 records。

对于落在象限边上的点，我们通常认为一、三象限的边是闭合的，二、四象限是开放的。即一个节点的东向边上的点认为是在第一象限。这样做是有些重要的，其中之一就是可以有助于快速判断一个给定的节点位于root的哪个象限。
我们没有考虑冲突（collisions）。
给定的两个记录 A、B，我们定义 COMPARE(A,B) 为一个整数，表示B 在 A 的哪个象限，定义 COMPARE(A,A) 为 0.
共轭象限计算：CONJUGATE(DIRECTION), conjugate(N)=((N+1) mod 4)+1。
节点的实现无需指定，大多数情况下应该是language-dependent。但我们要讨论算法还是需要一些符号，这里我们认为有一种数据类型NODE，子树叫ELM，第三个子树用 ELM[3] 表示，NULL表示空节点。 通常，我们认为 zeroth subtree （ELM[0]）总是 NULL。

Insertion

使用该插入算法构建了许多不同尺寸的树来统计他们的表现。节点的值从 $2^{31}-1$ 中均匀采样，表1为结果：

其中 $X=(AVERAGETPL)/(nlogn)$，n 为节点个数，log 为自然对数。Low 和 High X 为一个标准差偏离。表中可以看出，随机的节点很少会很糟的情况。有趣的是，观察 X 列可见，它增长缓慢，暗示了在随机插入时 TPL（Total path length） 粗略的和 NlogN 成正比，其中 N 为总结点数。因此 points searching 的期望可以被认为是 log N。
需要注意的是，极端的情况非常糟，如果每一层都只有一个节点（类似二叉树最坏情况），此时 TPL 为 n(n-1)/2 ， 此时插入和查找是顺序的 $n^2$ 操作。

More Sophisticated Insertion

为了减少TPL并找到一些类似于二叉树平衡的方法，开发了一种简单的平衡算法。它不是平衡子树高度，而是注意到一些情况可以用两种方式表示，而其中一种方式具有较小的TPL。如图2和图3所示，分别为 Single balance 和 Double balance （当 COMPARE(B,C) 和 COMPARE(A,B) 共轭）。

表2是在插入过程中执行这些平衡优化的统计结果，使用的节点和表1相同。有趣的是X的值减小了约10%，standard deviations 也有轻微减小。需要注意的是，有时使用leaf-balancing的树的TPL比直接插入更大。

Searching

有两类查询可以从 quad tree 中获利：

• point search：Is the point (37, t8) in the data structure, and what is the address of the node representing it ?
• region search：What are all the points within a circle of center (15, 31) and radius 7 ? or (if the quad tree’s two dimensions represent age and annual income) "Who are all the people between the ages of 24 and 28 who earn between $ 42000 and $ 44000 per year?

对于point search，查询的平均时间与 $TPL/(numberofnodesintree)$ 成正比
对于range search，算法如下：

其中，

• Procedure IN_REGION is a boolean procedure which is passed the x and y coordinates of a node and returns TRUE if an only if the node is in the region. 判断点是否在区域内
• Procedure RECTANGLE_OVERLAPS_REGION is passed the left, right, bottom, and top extreme values of a rectilinearly oriented rectangle. RECTANGLE_OVERLAPS_REGION returns TRUE if the region being searched overlaps the described rectangle and FALSE otherwise. 判断两区域是否有重叠
• Procedure FOUND is given each node found in the region to allow processing.
• 
  可以定义相似的处理程序查找点是否在任意的连通几何形状里，并且可以使用AND、OR、NOT来指定搜索区域，因此搜索的区域是非常灵活的。
  这种灵活性也使得进行形式化的分析非常困难，所以我们进行了一些经验化的测试来研究它的性能。我们让所有的点坐标在[0,1]之间，随机化搜索区域，对于每种树尺寸我们在所使用的data上随机生成4棵树，以指定的Edge Size在4棵树中各搜索25次，共100次搜索，结果如表3所示：

其中：

• Visited 表示100次搜索访问的节点总数
• Found 表示在区域内的点的总数
• Visited/Search 表示平均每次搜索访问的节点个数
• Found/Search 表示每次搜索找到的区域内的点个数
• Visited/Found 表示平均每搜索几个点可以找到一个满足条件的点

It is likely that the lower measure will be of more concern to the user; when one is gathering a large amount of data from a certain, region one is more concerned about the cost per collected node, and when one is making a large number of small searches one is more concerned about the cost of each search.

有趣的是，我们观察到 Visited/Search 增加时，Visited/ Found 会下降。这就像不同用户关心的点不同：当做大区域的搜索时，查找涉及的节点多，用户更关心查找成功率；当作频繁的小区域搜索时，用户更希望每个小区域查找的节点个数较少。(细思不是很成立)。

Deletion

删除操作非常困难，难在如何处理子树。将他们merge 到剩余的树中不太容易处理。事实上，将其一个个的重新插入到树中似乎是比较好的选择。问题是是否存在一种 merging 算法比nlogn 更快，这里 n 是需要merge的两个树的总结点数。

An Optimization Algorithm

有时只使用上文提到的 balancing 方法还不够，节点会向一侧倾斜，或总是频繁进行point search而不更新，这时有必要进行额外的工作来对树进行优化。
我们认为优化的树有以下性质：节点K中不存在这样的子树，该子树包含一半以上K的节点。
（略）

Conclusions

• quad tree 可以高效存储二维数据，直接插入性能为nlogn， range search效率高，
• 但删除和合并难以处理
• 可以随意扩展到多维的情况

最后

以上就是眼睛大铃铛为你收集整理的阅读：Quad Trees A Data Structure for Retrieval on Composite KeysAn Optimization Algorithm的全部内容，希望文章能够帮你解决阅读：Quad Trees A Data Structure for Retrieval on Composite KeysAn Optimization Algorithm所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。