西南交通大学学报 2012, 47(3) 451-457 DOI:   10.3969/j.issn.0258-2724.2012.03.016  ISSN: 0258-2724 CN: 51-1277/U

本期目录 | 下期目录 | 过刊浏览 | 高级检索                                                            [打印本页]   [关闭]
论文
扩展功能
本文信息
Supporting info
PDF(0KB)
[HTML全文]
参考文献
服务与反馈
把本文推荐给朋友
加入我的书架
加入引用管理器
引用本文
Email Alert
文章反馈
浏览反馈信息
本文关键词相关文章
障碍
空间查询
空间数据库
可视性
本文作者相关文章
杨泽雪
郝忠孝
PubMed
Article by Yang,Z.X
Article by Hao,Z.X

空间数据库中连续可视反向最近邻查询

杨泽雪1,2, 郝忠孝1,3

1. 哈尔滨理工大学计算机科学与技术学院, 黑龙江 哈尔滨 150080;
2. 黑龙江工程学院计算机科学与技术系, 黑龙江 哈尔滨 150050;
3. 哈尔滨工业大学计算机科学与技术学院, 黑龙江 哈尔滨 150001

摘要

为了解决障碍物环境中连续反向最近邻的查询问题,考虑到障碍物的存在,将可视性加到连续反向最近邻查询中,提出了一种新的连续反向最近邻查询的变体——连续可视反向最近邻查询.给出了线段可视性判断方法和相应的剪枝策略,提出了连续可视反向最近邻查询算法.该算法通过过滤步骤得到一个候选集,通过精炼步骤去掉错误的候选,通过分裂步骤找到查询结果.实验结果表明,该算法的执行时间与查询线段的长度呈线性关系增长,查询效率较高.

关键词 障碍   空间查询   空间数据库   可视性  

Continuous Visible Reverse Nearest Neighbor Queries in Spatial Databases

YANG Zexue1,2, HAO Zhongxiao1,3

1. College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China;
2. Department of Computer Science and Technology, Heilongjiang Institute of Technology, Harbin 150050, China;
3. College of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China

Abstract:

In order to solve the problem of CRNN (continuous reverse nearest neighbor) query in an obstacle environment, the visibility was added to the CRNN query by taking obstacles into consideration, and a novel variant of CRNN queries, namely continuous visible reverse nearest neighbor (CVRNN) search, was introduced. The segment visibility judgment method and the corresponding pruning strategy were given. A CVRNN query processing algorithm was proposed. With this algorithm, a candidate set is gotten through a filter step, the wrong candidates were removed by a refinement step, and query results are founded through a splitting step. Experimental results show that the algorithm execution time increases linearly with the length of query line segment, and the proposed algorithm has a high query efficiency.

Keywords: obstruct   spatial query   spatial database   visibility  
收稿日期 2011-01-20 修回日期  网络版发布日期 2012-05-29 
DOI: 10.3969/j.issn.0258-2724.2012.03.016
基金项目:

国家自然科学基金资助项目(60673136);黑龙江省自然科学基金资助项目(F200601)

通讯作者:
作者简介: 杨泽雪(1978-),女,讲师,博士研究生,研究方向为空间数据库查询,电话:13091434533,E-mail:yzx1978@126.com; 郝忠孝(1940-),男,教授,博士生导师,研究方向为空值环境下数据库理论、无环数据库、主动数据库、时态数据库和 空间数据库理论及应用等.

参考文献:

[1] FLIP K, MUTHUKRISHNAN S. Influence sets based on reverse nearest neighbor queries//Proc. of the 2000 ACM SIGMOD International Conference on Management of Data. Dallas: Association for Computing Machinery, 2000: 201-212.
[2] YANG C, LINK I. An index structure for efficient reverse nearest neighbor queries//Proc. of the IEEE International Conference on Data Engineering. Heidelberg:Institute of Electrical and Electronics Engineers Computer Society, 2001: 485-492.
[3] STANOI I, AGRAWAL D, ABBADI A. Reverse nearest neighbor queries for dynamic databases//ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery. Dallas: Association for Computing Machinery, 2000: 44-53.
[4] TAO Y, PAPADIAS D, LIAN X. Reverse kNN search in arbitrary dimensionality//Proc. of the 30th Very Large Data Bases Conference.Toronto:VLDB Endowment, 2004: 744-755.
[5] SINGH A, FERHATOSMANOGLU H, TOSUN A. High dimensional reverse nearest neighbor queries//Proc. of ACM CIKM International Conference on Information and Knowledge Management. New Orleans: Association for Computing Machinery, 2003: 91-98.
[6] TAO Y, YIU M L, MAMOULIS N. Reverse nearest neighbor search in metric spaces[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(9): 1239-1252.
[7] 郝忠孝. 时空数据库-查询与推理[M]. 北京:科学出版社,2010: 52-98.
[8] BENETIS R, JENSEN C S, KARCIAUSKAS G, et al. Nearest and reverse nearest neighbor queries for moving objects[J]. The VLDB Journal, 2006, 15(3): 229-249.
[9] KANG J M, MOKBEL M F, SHEKHAR S, et al. Continuous evaluation of monochromatic and bichromatic reverse nearest neighbors//Proc. of International Conference on Data Engineering. Istanbul: IEEE, 2007: 806-815.
[10] XIA T, ZHANG D. Continuous reverse nearest neighbor monitoring//Proc. of International Conference on Data Engineering.Atlanta:Institute of Electrical and Electronics Engineers Computer Society, 2006: 77-86.
[11] TAO Y, PAPADIAS D, LIAN X, et al. Multi-dimensional reverse kNN search[J]. The VLDB Journal, 2007, 16(3): 293-316.
[12] WU Wei, YANG Fei, CHAN Cheeyong, et al. Continuous reverse k-nearest-neighbor monitoring//Proc. of the 9th International Conf. on Mobile Data Management (MDM'08). Beijing: IEEE, 2008: 132-139.
[13] ZHANG J, PAPADIAS D, MOURATISIS K, et al. Spatial queries in the presence of obstacles//Proc. of the 9th International Conference on Extending Database Technology. Berlin: Springer-Verlag, 2004: 366-384.
[14] NUTANONG S, TANIN E, ZHANG R. Visible nearest neighbor queries//Proc. of the 12th International Conference on Database Systems for Advanced Applications. Bangkok: Springer Verlag, 2007: 876-883.
[15] GAO Y, ZHENG B, LEE W C, et al. Continuous visible nearestneighbor queries//Proc. of the 12th International Conference on Extending Database Technology. Saint Petersburg:Association for Computing Machinery, 2009: 144-155.
[16] 王艳秋,徐传飞,于戈,等. 一种面向不确定对象的可见k近邻查询算法[J]. 计算机学报,2010,33(10): 1943-1952. WANG Yanqiu, XU Chuanfei, YU Ge, et al.Visible k nearest neighbor queries over uncertain data[J]. Chinese Journal of Computers, 2010, 33(10): 1943-1952.
[17] GAO Y, ZHENG B, Continuous obstructed nearest neighbor queries in spatial databases//Proc. of ACM Special Interest Group on Management of Data Conference 2009. Providence: Association for Computing Machinery, 2009: 577-589.
[18] GAO Y, ZHENG B, LEE W C, et al. On efficient visible reverse k-nearest neighbor query processing in spatial databases[J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(9): 1314-1327.

本刊中的类似文章
1.关振宏;朱 峰 .用于平面单轴对称结构电磁波散射的减元技术 [J]. 西南交通大学学报, 2002,37(2): 215-217
2.陈震远;许荣中;陈震武.内孤立子遇海脊障碍物的能量消散和速度分布 [J]. 西南交通大学学报, 2006,41(4): 433-437

文章评论 (请注意:本站实行文责自负, 请不要发表与学术无关的内容!评论内容不代表本站观点.)

Copyright 2008 by 西南交通大学学报