基于QR树索引的面包含关系求解算法

doi:10.3969/j.issn.1000-3428.2010.21.013

计算机工程 ›› 2010, Vol. 36 ›› Issue (21): 37-39. doi: 10.3969/j.issn.1000-3428.2010.21.013

基于QR树索引的面包含关系求解算法

孙晓明1,2，吉根林1,2

(1. 南京师范大学计算机科学与技术学院，南京 210097；2. 江苏省信息安全保密技术工程研究中心，南京 210097)

出版日期:2010-11-05 发布日期:2010-11-03
作者简介:孙晓明(1986－)，女，硕士研究生，主研方向：数据挖掘；吉根林，教授、博士、博士生导师
基金资助:
国家自然科学基金资助项目(40871176)

Algorithm for Computing Region Inclusion Relations Based on QR-tree Index

SUN Xiao-ming1,2, JI Gen-lin1,2

(1. School of Computer Science and Technology, Nanjing Normal University, Nanjing 210097, China; 2. Jiangsu Research Center of Information Security & Privacy Technology, Nanjing 210097, China)

Online:2010-11-05 Published:2010-11-03

摘要/Abstract

摘要： 为提高空间拓扑计算中求解面包含关系的效率，提出一种基于QR树索引的面包含关系求解算法。根据空间对象的几何信息建立QR树索引，利用QR树查找面包含的空间对象，并将该算法应用于基于线面包含关系的GML空间聚类。实验结果表明该算法能有效提高计算面包含关系的时间效率。

关键词: 面包含关系, 空间索引, R树, QR树

Abstract: In order to improve the efficiency of computing region inclusion relations, this paper proposes an algorithm for computing region inclusion relations based on QR-tree index. The algorithm builds a QR-tree index according to the information of spatial objects and queries all spatial objects including the region on the QR-tree. The algorithm is applied to spatial clustering in GML data based on line-region inclusion relations. Experimental results show that the algorithm is effective and efficient.

Key words: region inclusion relations, spatial index, R-tree, QR-tree

中图分类号:

TP301.6

孙晓明, 吉根林. 基于QR树索引的面包含关系求解算法[J]. 计算机工程, 2010, 36(21): 37-39.

SUN Xiao-Meng, JI Gen-Lin. Algorithm for Computing Region Inclusion Relations Based on QR-tree Index[J]. Computer Engineering, 2010, 36(21): 37-39.

http://www.ecice06.com/CN/Y2010/V36/I21/37

参考文献

[1] Robinson J T. The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Index[C]//Proc. of ACM SIGMOD International Conference on Management of Data. New York, USA: ACM Press, 1981: 10-18. [2] Henrich A, Six H, Widmayer P. The LSD Tree: Spatial Access to Multidimensional Point and Nonpoint Objects[C]//Proc. of the 15th International Conference on Very Large Data Bases. San Francisco, USA: Morgan Kaufmann Publishers Inc., 1989: 45-53. [3] Guttman A. R-trees: A Dynamic Index Structures for Spatial Searching[C]//Proc. of ACM SIGMOD International Conference on Management of Data. New York, USA: ACM Press, 1984: 47-57. [4] Bechman N, Kriegel H P, Schneider R, et al. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles[C]// Proc. of ACM SIGMOD International Conference on Management of Data. New York, USA: ACM Press, 1990: 322-331. [5] Fu Yuchen, Hu Zhiyong, Guo Wei, et al. QR-Tree: A Hybrid Spatial Index Structure[C]//Proc. of International Conference on Machine Learning and Cybernetics. Xi’an, China: [s. n.], 2003: 459-463. [6] Nievergelt J, Hinterberger H, Sevcik K C. The Grid File: An Adaptable Symmetric Multikey File Structure[J]. ACM Trans. on Database Systems, 1984, 9(1): 38-71. [7] Zhang Mingbo, Lu Feng, Chen Changxiu, et al. A Forced Transplant Algorithm for Dynamic R-tree Implementation[C]//Lecture Notes in Computer Science. [S. l.]: Springer, 2006: 459-466. [8] Zhang Donghui, Xia Tian. A Novel Improvement to the R*-tree Spatial Index Using Gain/Loss Metrics[C]//Proc. of the 12th Annual ACM International Workshop on Geographic Information Systems. New York, USA: ACM Press, 2004: 204-213. [9] 张明波, 陆锋, 申排伟, 等. R树家族的演变和发展[J]. 计算机学报, 2005, 28(3): 289-300. [10] 张丽, 吉根林. 一种基于线面包含关系的GML空间聚类算法[J]. 山东大学学报: 工学版, 2009, 39(2): 21-25.

[1]	汤文琳, 谢凯, 文畅, 贺建飚. 深度聚类索引下的海量地震数据快速三维可视化[J]. 计算机工程, 2022, 48(11): 275-283.
[2]	唐鸿成, 文畅, 冯文祥, 谢凯, 方文青. 基于智能聚类模型的海量数据快速显示方法[J]. 计算机工程, 2019, 45(8): 53-59.
[3]	曾梦琪, 马蔚吟, 李力. 基于混合相似度的高效图像检索方案[J]. 计算机工程, 2019, 45(11): 262-268.
[4]	王晓璇,王珺,贾莹莹,张鑫. 无线传感器网络拓扑修复算法综述[J]. 计算机工程, 2018, 44(8): 93-99.
[5]	易显天,徐展,郭承军,刘丹,张可. 基于Patricia树的空间索引结构[J]. 计算机工程, 2015, 41(12): 69-74.
[6]	李松,张丽平,刘艳,郝晓红,杨和禹. 障碍物环境下的动态单纯型连续近邻链查询[J]. 计算机工程, 2014, 40(8): 52-57.
[7]	吴勇，罗腾元，王美珍. 可定位图像采集与检索方法研究[J]. 计算机工程, 2014, 40(7): 207-211,220.
[8]	高峻，郝忠孝. 受限网络模糊对象最近邻查询[J]. 计算机工程, 2014, 40(3): 39-45.
[9]	赵龙，闵世平，代强玲. 基于八叉树的三维地质剖面生成算法[J]. 计算机工程, 2014, 40(2): 250-255.
[10]	赵景昌,白润才,刘光伟,刘威. 基于空间索引与碰撞检测的TIN求交算法[J]. 计算机工程, 2014, 40(12): 296-301.
[11]	高峻, 郝忠孝. 空间数据库平面曲线的点最近邻查询[J]. 计算机工程, 2012, 38(15): 46-49.
[12]	张丽平, 李林, 李松, 郝晓红. 预定数据链规模的单纯型连续近邻链查询[J]. 计算机工程, 2012, 38(10): 51-53.
[13]	杨春德, 秦宗伟. 一种改进的时延受限多播路由算法[J]. 计算机工程, 2012, 38(10): 83-85.
[14]	李光师, 孟祥茹. Oracle中矢量数据安全保护方法[J]. 计算机工程, 2012, 38(10): 102-104.
[15]	李松, 张丽平, 蔡志涛, 郝晓, 王淼. 数据集中单纯型连续近邻链查询方法[J]. 计算机工程, 2012, 38(04): 82-83.

选择文件类型/文献管理软件名称

选择包含的内容

基于QR树索引的面包含关系求解算法

Algorithm for Computing Region Inclusion Relations Based on QR-tree Index

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于QR树索引的面包含关系求解算法

Algorithm for Computing Region Inclusion Relations Based on QR-tree Index

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价