[1]万静,唐贝贝,何云斌,等. 一种障碍空间中移动对象的连续k最近邻查询方法[J].哈尔滨理工大学学报,2018,(03):44-50.[doi:10.15938/j.jhust.2018.03.008]
 WAN Jing,TANG Bei-bei,HE Yun-bin,et al. A Continuous k-Nearest Neighbor Query Methodfor Moving Data in Obstructed Spaces[J].哈尔滨理工大学学报,2018,(03):44-50.[doi:10.15938/j.jhust.2018.03.008]
点击复制

 一种障碍空间中移动对象的连续k最近邻查询方法()
分享到:

《哈尔滨理工大学学报》[ISSN:1007-2683/CN:23-1404/N]

卷:
期数:
2018年03期
页码:
44-50
栏目:
材料科学与工程
出版日期:
2018-06-25

文章信息/Info

Title:
 A Continuous k-Nearest Neighbor Query Method
for Moving Data in Obstructed Spaces
作者:
 万静唐贝贝何云斌李松
 哈尔滨理工大学 计算机科学与技术学院,黑龙江 哈尔滨 150080
Author(s):
 WAN JingTANG Bei-beiHE Yun-binLi Song
 WT6BZ〗(School of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China
关键词:
 关键词:R树k最近邻查询不确定性可视性障碍距离
Keywords:
 Keywords:Rtree knearest neighbor query uncertainty visibility obstructed distance
分类号:
TP311.13
DOI:
10.15938/j.jhust.2018.03.008
文献标志码:
A
摘要:
 摘要:针对时空数据库中的连续移动对象的最近邻查询问题,提出COpKNN(continuous obstructed possible knearest neighbor)查询:在二维空间中,给定一个移动查询点q、一组移动查询对象集合P和一组多边形障碍物集合O,根据障碍距离的概念,查询q所有可能的k最近邻集合。由于移动对象本身的不确定性以及现实生活中障碍物的存在,已有的查询方式不再适用COpKNN查询。COpKNN查询包括三个子过程:根据可视图、R树和堆排序的概念,给出计算两点之间障碍距离(大于等于欧几里得距离)的方法;基于R树的查询方式查找在用户给定时间段内q所有可能的k最近邻结果集(初步结果,也叫候选集);采用Mindist(E,q)和候选集更新算法UpdataC(pn)对k最近邻结果集进行剪枝,得到较为精确的k最近邻结果集。实验数据集和障碍物集均采用真实的数据集,理论研究和实验结果表明,该方法具有良好的效率。
Abstract:
 Abstract:To solve the nearest neighbor query of continuously moving objects in Spatiotemporal database, we study novel form of continuous knearest neighbor query in the presence of obstacles, namely continuous obstructed possible k nearest neighbor (COpKNN) search. Given a data set P, an obstacle set O, and a query point q in a twodimensional space, a COpKNN query retrieves all possible knearest neighbors of each point on q according to the obstructed distance. Duo to the inherent of moving data objects and the existence of obstacles in our real life, previous techniques to answer nearest neighbor (NN) query cannot be directly applied to the COpKNN problem. The P COpKNN query method mainly includes three subalgorithms: according to the concept of Visibility graph, Rtree and Heap Sort,given the method of calculation of the obstacle distance(greater than or equal Euclidean distance) between two points; find all possible knearest neighbors of q between user given time period based on Rtree; Using Mindist (E,q) and the candidate set update algorithm UpdataC (pn) to prune kNNs to get the correct knearest neighbors. Experimental data sets and obstacle sets are all based on real data sets,theoretical and experimental results show that the method with good efficiency mentioned herein.

参考文献/References:

 
[1]李传文,谷峪,李芳芳,等. 一种障碍空间中不确定对象的连续最近邻查询方法[J].计算机学报,2010,33(8):1359-1368.
[2]KOLAHDOUZAN MR,SHAHABI C. Continuous K Nearest Neighbor Queries in Spatial Network Databases[C].STDBM,2004,9(4):33-40.
[3]HUANG YK,LIAO SJ,LEE C. Efficient Continuous Knearest Neighbor Query Processing Over Moving Objects with Uncertain Speed and Direction[J]. Springer Berlin Heidelberg,2008,5069 (5):549-557.
[4]SISTLA A. Prasad, WOLFSON Ouri, XU Bo. Continuous Nearestneighbor Queries with Location Uncertainty[J]. The VLDB Journal,2015,24(1):25-50.
[5]孙冬璞,郝忠孝. 移动对象历史轨迹的连续最近邻查询算法[J].计算机工程,2009,35(1):52-54.
[6]黄敬良,郝忠孝. 移动对象的K个连续最近邻查询算法[J].哈尔滨理工大学学报,2007,12(6):24-27.
[7]刘彬,万静. 基于R-树的连续最近邻查询算法优化研究[J].信息技术,2008,32(1):78-79.
[8]袁培森,沙朝峰,王晓玲,等. 一种基于学习的高维数据c-近似最近邻查询算法[J].软件学报,2012,23(8):2018-2031.
[9]李松,张丽平,刘艳,等. 障碍物环境下的动态单纯型连续近邻链查询[J].计算机工程,2014,40(8):52-57.
[10]张丽平,李松,郝忠孝,等. 障碍物增减情况下的单纯型连续近邻链查询[J].计算机工程与应用,2015,51(11):99-113.
[11]GAO Yunjun, ZHENG Baihua. Continuous Obstructed Nearest Neighbor Queries in Spatial Databases[C]. Proceedings of the 28th ACM SIGMOD International Conference of Management of Data,2009,9(4): 577-590.
[12]MOKBEL MF, CHOW CY, AREF WG.The Newcasper: Query Processing for Location Services Without Compromisingprivacy[C]// International Conference on Very Large Data Bases, 2009, 34(4):763-774.
[13]HUANG YuanKo, CHEN ChaoChun, LEE Chiang. Continuous Knearest Neighbor Query for Moving Objects with Uncertain Velocity[J]. Geoinformatica,2009,13(1): 1-25.
[14]孙冬璞,郝晓红,高爽,等. 概率可视最近邻查询算法[J].哈尔滨理工大学学报,2013,18(6):58-63.
[15]郝忠孝. 时空数据库查询与推理[M].北京:科学出版社,2010.
[16]JUJR SACK.Handbook of Computational Geometry[M]. Ottawa: Elsevier Science,2000:829-876. 
[17]ZHANG J, PAPADIAS D, MOURATIDIS K, et al.Spatial Queries in the Presence of Obstacles[R]. Lecture Notes in Computer Science, 2004, 2992:366-384.
[18]BERG M De, KREVELD M Van, OVERMARS M, et al. Computational Geometry: Algorithms and Applications[C]. Library Philosophy & Practice,2011(1):333-334.
[19]XIA C, HSU D, TUNG AKH. A Fast Filter for Obstructed Nearest Neighbor Queries[J]. Key Technologies for Data Management,2004,3112:203-215.
[20]SHARIR M, SCHORR A.On Shortest Paths Inpolyhedral Spaces[J]. SIAM Journal on Computing, 1987,15(1):193-215.
[21]GHOSH SK, MOUNT DM.An Output Sensitive Algorithm for Computing Visibility Graphs[J]. Foundations of Computer Science Annual Symposium on,2012,20(5):11-19.
[22]LI Chuanwen, GU Yu, LI Fangfang, et al. Moving Knearest Neighbour Query Over Obstructed Regions[C]// Advances inWeb Technologies Application, 2010:29-35.

相似文献/References:

[1]孙永全,郭建英,陈洪科,等.AMSAA模型可靠性增长预测方法的改进[J].哈尔滨理工大学学报,2010,(05):49.
 SUN Yong-quan,GUO Jian-ying,CHEN Hong-ke,et al.An Improved Reliability Growth Prediction Algorithm Based on AMSAA Model[J].哈尔滨理工大学学报,2010,(03):49.
[2]滕志军,李晓霞,郑权龙,等.矿井巷道的MIMO信道几何模型及其信道容量分析[J].哈尔滨理工大学学报,2012,(02):14.
 TENG Zhi-jun,LI Xiao-xia,ZHENG Quan-long.Geometric Model for Mine MIMO Channels and Its Capacity Analysis[J].哈尔滨理工大学学报,2012,(03):14.
[3]李艳苹,张礼勇.新训练序列下的改进OFDM符号定时算法[J].哈尔滨理工大学学报,2012,(02):19.
 LI Yan-ping,ZHANG Li-yong.An Improved Algorithm of OFDM Symbol Timing Based on A New Training Sequence[J].哈尔滨理工大学学报,2012,(03):19.
[4]赵彦玲,车春雨,铉佳平,等.钢球全表面螺旋线展开机构运动特性分析[J].哈尔滨理工大学学报,2013,(01):37.
 ZHAO Yan-ling,CHE Chun-yu,XUAN Jia-ping,et al.[J].哈尔滨理工大学学报,2013,(03):37.
[5]李冬梅,卢旸,刘伟华,等.一类具有连续接种的自治SEIR传染病模型[J].哈尔滨理工大学学报,2013,(01):73.
 LI Dong-mei,LU Yang,LIU Wei-hua.[J].哈尔滨理工大学学报,2013,(03):73.
[6]华秀英,刘文德.奇Hamiltonian李超代数偶部的非负Z-齐次导子空间[J].哈尔滨理工大学学报,2013,(01):76.
 HUA Xiu-ying,LIU Wen-de.[J].哈尔滨理工大学学报,2013,(03):76.
[7]桂存兵,刘洋,何业军,等.基于LCC谐振电路阻抗匹配的光伏发电最大功率点跟踪[J].哈尔滨理工大学学报,2013,(01):90.
 GUI Cun-bing,LIU Yong,HE Ye-jun.[J].哈尔滨理工大学学报,2013,(03):90.
[8]翁凌,闫利文,夏乾善,等.PI/TiC@Al2O3复合薄膜的制备及其电性能研究[J].哈尔滨理工大学学报,2013,(02):25.
 WENG Ling,YAN Li-wen,XIA Qian-shan.[J].哈尔滨理工大学学报,2013,(03):25.
[9]姜彬,林爱琴,王松涛,等.高速铣刀安全性设计理论与方法[J].哈尔滨理工大学学报,2013,(02):63.
 JIANG Bin,LIN Ai-qin,WANG Song-tao,et al.[J].哈尔滨理工大学学报,2013,(03):63.
[10]李星纬,李晓东,张颖彧,等.EVOH 磺酸锂电池隔膜的制备及微观形貌[J].哈尔滨理工大学学报,2013,(05):18.
 LI Xing- wei,LI Xiao- dong,ZHANG Ying- yu,et al.The Preparation and Microcosmic Morphology oEVOH- SO Li Lithium Ion Battery Septum[J].哈尔滨理工大学学报,2013,(03):18.

备注/Memo

备注/Memo:
 基金项目: 黑龙江省教育厅科学技术研究项目(12531z004).
更新日期/Last Update: 2018-10-18