论文部分内容阅读
高维数据空间中的最近邻查询问题被广泛应用于数据库,图像检索和许多其它相关领域。受“维数灾难”的影响,这一问题变得越来越重要。本文研究且实现了DCR(Data Co-Reduction)算法。使用近年研究所得的联合聚类方法,DCR通过压缩原始数据集合的规模和维数,将高维数据集合压缩至更加紧密的子空间中。索引结构同K最近邻查询过程本文使用了过滤和精炼策略。本文通过使用联合聚类算法建立了更加紧确的距离下界。因此DCR算法能够有效提升k最近邻查询算法的效率。特别的,DCR算法通过同时考虑到数据集合规模和维数的二元性,实现了相似性查询的最优化。实验结果表明在大规模数据集合上DCR算法在过滤能力和查询响应时间两方面都有着优秀的性能表现。近年来,DCR算法被认为是K最近邻查询领域非常优秀的解决方法。然而,由于该算法在访问候选点时需要进行大量的随机I/O,效率上受到影响。为了保证返回结果的质量,需要访问足够多的查询对象,由此会带来大量的I/O开销。为了解决这一问题,本文提出了一个新的索引方法,ZOrder索引,该索引结构通过最大化单次I/O中访问候选点的数目,使得查询中磁盘页面I/O次数最小。本文的主要贡献可以总结为:首先,本文根据数据点的访问顺序定义了能够评估数据集合中两个数据点ZOrder编码之间距离的方式。由此能够得到数据集合对应的ZOrder编码集合的编码线序关系,并且根据该线序关系实现对数据点的排序。其次,本文证明了ZOrder索引算法能够将具有相似ZOrder编码的数据点存储在连续的磁盘页面。在最近邻搜索过程中,ZOrder索引算法在较少次数的硬盘内存间的I/O就能完成。在几次硬盘内存间I/O之后,便能得到足够多的候选点,从而不仅大幅度减少查询响应时间,也提高了返回结果的准确度。通过对真实数据集合上的实验,并同经典的最近邻查询算法的实验结果的比对分析,能够证明ZOrder索引算法良好的空间和时间效率。