Construction of rectangle trapezoid circle tree and indeterminate near neighbor relations query

doi:10.11772/j.issn.1001-9081.2015.01.0115

Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (1): 115-120.DOI: 10.11772/j.issn.1001-9081.2015.01.0115

Previous Articles Next Articles

Construction of rectangle trapezoid circle tree and indeterminate near neighbor relations query

LI Song¹, LI Lin², WANG Miao^1,3, CUI Huanyu¹, ZHANG Liping¹

1. School of Computer Science and Technology, Harbin University of Science and Technology, Harbin Heilongjiang 150080, China;
2. TDLTE Testing Department, Nokia Solutions and Networks System Technology, Hangzhou Zhejiang 310000, China;
3. Department of Computer Science and Engineering, Henan Institute of Engineering, Zhengzhou Henan 451191, China

Received:2014-08-22 Revised:2014-10-09 Online:2015-01-01 Published:2015-01-26

RTC树的构建与不确定近邻关系查询方法

李松¹, 李林², 王淼^1,3, 崔环宇¹, 张丽平¹

1. 哈尔滨理工大学计算机科学与技术学院, 哈尔滨150080;
2. 诺基亚通信系统技术有限公司 TDLTE测试部, 杭州310000;
3. 河南工程学院计算机科学与工程系, 郑州451191

通讯作者: 李松
作者简介:李松(1977-),男,江苏沛县人,副教授,博士,主要研究方向:数据库、数据挖掘、数据查询;李林(1979-),男,江苏沛县人,工程师,硕士,主要研究方向:信息定位、查询技术;王淼(1981-),男,河南信阳人,副教授,博士,主要研究方向:数据查询、空间关系推理;崔环宇(1990-),男,黑龙江大庆人,硕士研究生,主要研究方向:数据查询与分析;张丽平(1976-),女,辽宁铁岭人,副教授,硕士,主要研究方向:数据结构、算法设计、数据库.
基金资助:
黑龙江省教育厅科学技术研究项目(12541128).

Abstract

Abstract:

The spatial index structure and the query technology plays an important role in the spatial database. According to the disadvantages in the approximation and organization of the complex spatial objects of the existing methods, a new index structure based on Minimum Bounding Rectangle (MBR), trapezoid and circle (RTC (Rectangle Trapezoid Circle) tree) was proposed. To deal with the Nearest Neighbor (NN) query of the complex spatial data objects effectively, the NN query based on RTC (NNRTC) algorithm was given. The NNRTC algorithm could reduce the nodes traversal and the distance calculation by using the pruning rules. According to the influence of the barriers on the spatial data set, the barrier-NN query based on RTC tree (BNNRTC) algorithm was proposed. The BNNRTC algorithm first queried in an idea space and then judged the query result. To deal with the dynamic simple continuous NN chain query, the Simple Continues NN chain query based on RTC tree (SCNNCRTC) algorithm was given. The experimental results show that the proposed methods can improve the efficiency of 60%-80% in dealing with large complex spatial object data set with respect to the query method based on R tree.

Key words: spatial database, R tree, RTC (Rectangle Trapezoid Circle) tree, Nearest Neighbor (NN), simple continues near neighbor chain

摘要：

空间索引结构和查询技术在空间数据库中具有重要的作用,针对已有的方法在复杂空间数据对象的近似和组织方面的局限性,提出了一种基于最小外接矩形(MBR)、梯形和圆的新的索引结构(RTC树).为了有效处理复杂空间数据对象的最近邻(NN)关系查询问题,提出了基于RTC树的最近邻查询(NNRTC)算法,NNRTC算法利用剪枝规则可减少节点遍历和距离计算.针对障碍物对数据集中最近邻的影响问题,提出了障碍物环境下的基于RTC树的最近邻查询(BNNRTC)算法,BNNRTC算法先在理想空间进行查询,再对查询结果进行判断.为了有效处理动态单纯型连续近邻链查询问题,进一步给出了基于RTC树的动态单纯型连续近邻链查询(SCNNCRTC)算法.实验结果表明,相对基于R树的查询方法,所提的方法在处理数据量较大的复杂空间对象的数据集时可提高60%~80%的效率.

关键词: 空间数据库, R树, RTC树, 最近邻, 单纯型连续近邻链

CLC Number:

TP311.13

LI Song, LI Lin, WANG Miao, CUI Huanyu, ZHANG Liping. Construction of rectangle trapezoid circle tree and indeterminate near neighbor relations query[J]. Journal of Computer Applications, 2015, 35(1): 115-120.

李松, 李林, 王淼, 崔环宇, 张丽平. RTC树的构建与不确定近邻关系查询方法[J]. 计算机应用, 2015, 35(1): 115-120.

References

[1] HAO Z. Querying and reasoning in spatial database [M]. Beijing: Science Press, 2010: 11-13.(郝忠孝.时空数据库查询与推理[M].北京:科学出版社,2010:11-13.)
[2] LI S, ZHANG L, SUN D. Spatial relation query and analysis [M]. Harbin: Harbin Institute of Technology Press, 2011: 24.(李松,张丽平,孙冬璞.空间关系查询与分析[M].哈尔滨:哈尔滨工业大学出版社,2011:24.)
[3] ZHANG M, LU F, SHEN P, et al. The evolvement and progress of R tree family [J]. Chinese Journal of Computers, 2005, 28(3): 289-300.(张明波,陆峰,申排伟,等.R树家族的演变与发展[J].计算机学报,2005,28(3):289-300.)
[4] SUN D, SONG Y, LIU H, et al. Nodes splitting of R^*-tree based on multi-objective genetic algorithm [J]. Journal of Computer-Aided Design & Computer Graphics, 2013, 25(10): 1454-1459.(孙殿柱,宋洋,刘华东,等.R^*-树结点多目标遗传分裂算法[J].计算机辅助设计与图形学学报,2013,25(10):1454-1459.)
[5] MOURATIDIS K, YIU M L, PAPADIAS D, et al. Continuous nearest neighbor monitoring in road networks [C]// Proceeding of the 32nd International Conference on Very Large Data Bases. [S.l.]: VLDB Endowment, 2006: 234-247.
[6] QI F, JIN S, LIU G, et al. Approximation reverse k nearest neighbor queries in road network [J]. Journal of Chinese Computer Systems, 2010, 31(8): 1599-1603.(齐峰,金顺福,刘国华,等.道路网络环境下的近似反k最近邻查询算法[J].小型微型计算机系统,2010,31(8):1599-1603.)
[7] NUTANONG S, TANIN E, ZHANG R. Incremental evaluation of visible nearest neighbor queries [J]. IEEE Transactions on Knowledge Engineering, 2010, 22(7): 665-681.
[8] GAO Y, ZHENG B, CHEN G, et al. Visible reverse k-nearest neighbor query processing in spatial databases [J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(11): 1314-1327.
[9] HU L, JING Y, KU W, et al. Enforcing k nearest neighbor query integrity on road networks [C]// Proceedings of the 20th International Conference on Advances in Geographic Information Systems. New York: ACM, 2012: 346-349.
[10] ELMONGUI H G, MOKBEL M F, AREF W G. Continuous aggregate nearest neighbor queries [J]. GeoInformatica, 2013, 17(1): 63-95.
[11] MIAO D, SHI S, LI J. An algorithm on probabilistic frequent nearest neighbor query over snapshots of uncertain database with locally correlation [J]. Journal of Computer Research and Development, 2011, 48(10): 1812-1822.(苗东菁,石胜飞,李建中.一种局部相关不确定数据库快照集合上的概率频繁最近邻算法[J].计算机研究与发展,2011,48(10):1812-1822.)
[12] YUAN P, SHA C, WANG X, et al. c-approximate nearest neighbor query algorithm based on learning for high dimensional data [J]. Journal of Software, 2012, 23(8): 2018-2031.(袁培森,沙朝锋,王晓玲,等.一种基于学习的高维数据c-近似最近邻查询算法[J].软件学报,2012,23(8):2018-2031.)
[13] LI S, ZHANG L, ZHU D, et al. Simple continues near neighbor chain query in dynamic constrained regions [J]. Computer Science, 2014, 41(6): 136-141.(李松,张丽平,朱德龙,等.动态受限区域内的单纯型连续近邻链查询方法[J].计算机科学,2014,41(6):136-141.)
[14] ZHANG L, LI S, LI L, et al. Simple continues near neighbor chain query of the datasets based on the R tree [J]. Journal of Computational Information Systems, 2012, 8(22): 9159-9166.
[15] ZHANG L, LI S, ZHAO J, et al. Simple continuous near neighbor chain query in constrained regions [J]. Journal of Computer Applications, 2014,34(2):406-410.(张丽平,李松,赵纪桥,等.受限区域内的单纯型连续近邻链查询方法[J].计算机应用,2014,34(2):406-410.)

Construction of rectangle trapezoid circle tree and indeterminate near neighbor relations query

RTC树的构建与不确定近邻关系查询方法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	LI Mingwei, JIANG Qingyuan, XIE Yinpeng, HE Jindong, WU Dan. Hash learning based malicious SQL detection [J]. Journal of Computer Applications, 2021, 41(1): 121-126.
[2]	HOU Haiyao, QIAN Yurong, YING Changtian, ZHANG Han, LU Xueyuan, ZHAO Yi. Spatio-temporal query algorithm based on Hilbert-R tree hierarchical index [J]. Journal of Computer Applications, 2018, 38(10): 2869-2874.
[3]	BI Chongchun, MENG Xiangfu, ZHANG Xiaoyan, TANG Yanhuan, TANG Xiaoliang, LIANG Haibo. Coupling similarity-based approach for categorizing spatial database query results [J]. Journal of Computer Applications, 2018, 38(1): 152-158.
[4]	QIAN Xiaojie, DU Shenghao. Component retrieval method based on identification of faceted classification and cluster tree [J]. Journal of Computer Applications, 2017, 37(10): 2973-2977.
[5]	WANG Miao HUANG Zhiguo LI Song. Inverse reasoning of 3D cardinal direction relations based on block algebra [J]. Journal of Computer Applications, 2014, 34(4): 1144-1148.
[6]	ZHANG Liping Lisong ZHAO Jiqiao HAO Xiaohong. Simple continuous near neighbor chain query in constrained regions [J]. Journal of Computer Applications, 2014, 34(2): 406-410.
[7]	WEN Hui CHEN Yufei WANG Zhicheng ZHAO Xiaodong YUE Xiaodong. Liver segmentation method based on hierarchical vascular tree [J]. Journal of Computer Applications, 2013, 33(09): 2658-2661.
[8]	WANG Miao LI Songyang. Research survey on formal description for direction relations [J]. Journal of Computer Applications, 2013, 33(05): 1324-1329.
[9]	LU Bing-liang LIU Na. Snapshot K neighbor query processing on moving objects in road networks [J]. Journal of Computer Applications, 2011, 31(11): 3078-3083.
[10]	HE Huai-qing YANG Peng. Improved algorithm on contour line position relation [J]. Journal of Computer Applications, 2011, 31(05): 1193-1197.
[11]	Wei-qun LIU Yuan-chen LI. Delay-constrained multicast routing algorithm based on optimized path selection [J]. Journal of Computer Applications, 2011, 31(04): 925-927.
[12]	CHEN Xiang WU Yue. Mining association rules of geographic information system based on concept lattice [J]. Journal of Computer Applications, 2011, 31(03): 686-689.
[13]	. New MPH-based delay-constrained Steiner tree algorithm [J]. Journal of Computer Applications, 2010, 30(11): 3056-3058.
[14]	. NNlists-based k-path nearest neighbor query in road networks [J]. Journal of Computer Applications, 2010, 30(07): 1947-1949.
[15]	. Delay-constrained multicast routing algorithm based on optimized Floyd shortest path algorithm [J]. Journal of Computer Applications, 2010, 30(05): 1176-1178.