论文部分内容阅读
空间数据查询是空间数据管理的重要内容，在时空数据库、空间数据库、地理信息系统和智能交通系统等中有着广泛的应用，因此，开发高效的空间数据查询处理算法显得尤为重要。但是，由于空间数据的多维性以及空间操作没有统一的基础构件集合等，空间数据查询处理不同于传统的关系数据查询处理，需要平衡考虑CPU和I/O代价，需要针对具体特定的查询类型设计和优化处理算法。 基于距离的空间查询是空间数据查询中的重要类型，它回答空间对象之间有关距离关系的检索请求。尽管基于距离的空间查询在已经在多个领域中得到研究和应用，但是，随着应用的不断深入，新的基于距离的空间查询形式不断出现。约束K最接近查询、成组K最近邻居查询以及全局K最近邻居查询就是新的基于距离的空间查询类型。 尽管存在多种空间数据索引结构和度量空间，R树类型索引结构以及欧氏空间仍是基于距离的空间查询处理中主要的流行的索引结构和度量空间，对于新的基于距离的空间查询处理算法的设计使用R树类型索引和欧氏度量空间。 分支界定技术作为一种算法设计技术广泛地应用于设计树型数据结构上查询处理算法，而分支界定算法对R树的遍历主要存在深度优先和最好优先两种方式，为了开发高效基于距离的空间查询分支界定算法，定义R树类型索引结构上的距离度量函数并给出和证明相关的性质。 给定两个数据集和一个空间约束区域，约束K最接近对查询检索给定区域中K最接近对。和传统的K最近对查询不同，约束K最接近对中的元素必须出现在给定区域中。作为设计的算法的基础，形式化地定义和描述约束K最接近对查询并给出相应性质。由于约束K最接近对查询直觉上可以看作距离连接和范围查询的组合，通过变换距离连接和范围查询的执行顺序，给出了两个两阶段处理算法。为了设计分支界定处理算法，扩充定义距离度量函数，并推导出这些函数的性质，在这些定义和性质上，给出了用于搜索空间裁减的裁减规则、加快搜索距离减小的更新规则和尽快地获得结果的访问顺序规则。利用这些规则设计了单阶段的分支界定算法。通过大量实验比较和分析了算法的性能，从实验结果可以看出单阶段的分支界定算法具有较好的性能。 成组K最接近对查询检索多个数据集相对于一个中心数据集的聚集情况，它是最接近对查询的一般情形。多次最近邻居方法针对中心数据集中每个对象，依次计算它在其他数据集中的K最近邻居，然后构造最终的结果。基于阀值思想的算法依次对数据集和中心数据集求最接近对，然后求其他数据集的最近邻居，最后构造聚集元组和更新阀值。阀值算法按照渐进的方式输出结果，它对查询的计算呈现某种收敛特性。通过大量的实验对多次最近邻居方法和阀值方法进行比较和分析可以看出，阀值方法具有较好的伸缩性、较快的查询响应时间和较少的磁盘节点访问次数。 给定一个运动的查询对象，一个静止或者运动的数据集，全局K最近邻居查询检索在一个指定的时间范围内和查询对象最近的K个邻居。由于全局K最近邻居是查询对象的连续K最近邻居的子集，通过执行连续K最近邻居查询可以获得查询对象的全局最近邻居。当数据集静止时，全局K最近邻居查询可以转化为求查询对象移动轨迹的K最近邻居。在定义的最小可能距离度量以及其他度量函数的基础上设计深度优先和最好优先的分支界定算法。当数据集运动时，对全局距离进行详细定义，并设计相应的TPR树上分支界定查询处理算法。大量的实验的结果显示分支界定算法明显优于基于连续最近邻居的算法，而最好优先遍历算法的性能好于深度优先算法。 通过分析基于距离的空间查询的特点，借鉴和改进现有的研究工作，对新的基于距离的空间查询的查询处理算法进行了研究，讨论了这些新距离查询的应用，丰富基于距离的空间查询的内容。