空间数据库中基于Voronoi图的反k最近邻查询研究

摘要

随着空间数据库在实际应用领域的广泛发展，空间查询中的最近邻查询及其变体查询研究成为热点问题。已有的最近邻查询已经不能满足广泛的应用需求，为此最近邻查询研究的数据环境从理想的欧氏空间转变到复杂的障碍空间，数据对象也从点对象转变为线段对象。作为一类重要的空间数据查询，反k最近邻查询有着重要的研究价值。由于现有研究并没有涉及障碍空间中的组反k最近邻查询问题以及针对线段对象的反k最近邻查询问题，故本文研究的重点是利用Voronoi图的邻接特性对障碍组反k最近邻查询及线段反k最近邻查询进行系统的研究。
　　本研究主要内容包括：⑴为了解决已有研究成果不能有效处理障碍空间中的组反k最近邻查询问题，根据障碍物集合是否发生变化提出了两种情况下的查询方法，一种是静态障碍物环境下的查询（简称STA_OGRkNN查询），另一种是动态障碍物环境下的查询（简称DYN_OGRkNN查询）。其中STA_OGRkNN查询方法利用剪枝策略可以在剪枝阶段快速地缩小查询范围，提高整个算法的查询效率，在精炼阶段又有效地提高了算法的准确性，进一步给出了3种情况下的DYN_OGRkNN查询算法。⑵针对现有的基于点对象的反k最近邻查询研究存在的局限性，提，出了基于线段的反k最近邻查询方法。该方法获得的结果集是将查询线段作为k最近邻的线段集合。查询过程分别为剪枝过程和精炼过程，首先利用5个剪枝策略筛选出候选者，再根据定义得到精确的结果集，该方法通过剪枝可以大大提高查询速度，通过对候选者进行精炼又提高了算法的准确度。⑶将线段反k最近邻查询应用到数据集动态更新的情况，提出相应的判定规则及查询方法。由于数据集动态更新的不确定性，因此提出数据集插入线段以及删除线段情况下的线段反k最近邻查询算法。这两种算法均分为两个阶段:处理数据集阶段、判定阶段。根据插入线段和删除线段这两种情况分别提出不同的判定规则，通过判定规则可以避免冗余查询，进而提高查询效率。

目录

声明

摘要

第1章 绪论

1．1 课题研究的目的及意义

1．2 国内外研究现状

1．2．1 基于点对象的最近邻查询及其变体查询

1．2．2 基于线段对象的最近邻查询及其变体查询

1．3 课题的来源及研究内容

1．3．1 课题来源

1．3．2 课题的主要研究内容

第2章 基础知识

2．1 Voronoi图

2．1．1 Voronoi图的定义及性质

2．1．2 基于Voronoi图的索引结构V-树

2．2 线段Voronoi图

2．2．1 线段Voronoi图的定义及性质

2．2．2 线段Voronoi图相关定理

2．3 本章小结

第3章 障碍空间中基于Voronoi图的组反k最近邻查询

3．1 相关概念与定义

3．2 静态障碍物环境下的OGRkNN查询方法

3．2．1 剪枝策略

3．2．2 剪枝算法

3．2．3 精炼策略

3．2．4 精炼算法

3．3 动态障碍物环境下的OGRkNN查询方法

3．3．1 障碍物动态增加情况下的OGRkNN查询

3．3．2 障碍物动态减少情况下的OGRkNN查询

3．3．3 障碍物动态移动情况下的OGRkNN查询

3．4 实验比较与分析

3．5 本章小结

第4章 空间数据库中的线段反k最近邻查询

4．1 相关概念与定义

4．2 剪枝过程

4．2．1 剪枝策略

4．2．2 剪枝算法

4．3 精炼过程

4．4 实验结果与分析

4．5 本章小结

第5章 数据集动态更新情况下的线段反k最近邻查询

5．1 数据集动态增加情况下的LRkNN查询

5．1．1 判定规则

5．1．1 判定算法

5．2 数据集动态减少情况下的LRkNN查询

5．2．1 判定规则

5．2．2 判定算法

5．3 数据集动态更新情况下的LRkNN查询算法

5．4 实验结果与分析

5．5 本章小结

结论

参考文献

攻读硕士学位期间所发表的学术论文

致谢