Construction of rectangle trapezoid circle tree and indeterminate near neighbor relations query
LI Song1, LI Lin2, WANG Miao1,3, CUI Huanyu1, ZHANG Liping1
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
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.
李松, 李林, 王淼, 崔环宇, 张丽平. RTC树的构建与不确定近邻关系查询方法[J]. 计算机应用, 2015, 35(1): 115-120.
LI Song, LI Lin, WANG Miao, CUI Huanyu, ZHANG Liping. Construction of rectangle trapezoid circle tree and indeterminate near neighbor relations query. Journal of Computer Applications, 2015, 35(1): 115-120.
[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.)
2015, Vol. 35 
