• ISSN 0258-2724
  • CN 51-1277/U
  • EI Compendex
  • Scopus
  • Indexed by Core Journals of China, Chinese S&T Journal Citation Reports
  • Chinese S&T Journal Citation Reports
  • Chinese Science Citation Database
Volume 25 Issue 3
May  2012
Turn off MathJax
Article Contents
YANG Zexue, HAO Zhongxiao. Continuous Visible Reverse Nearest Neighbor Queries in Spatial Databases[J]. Journal of Southwest Jiaotong University, 2012, 25(3): 451-457. doi: 10.3969/j.issn.0258-2724.2012.03.016
Citation: YANG Zexue, HAO Zhongxiao. Continuous Visible Reverse Nearest Neighbor Queries in Spatial Databases[J]. Journal of Southwest Jiaotong University, 2012, 25(3): 451-457. doi: 10.3969/j.issn.0258-2724.2012.03.016

Continuous Visible Reverse Nearest Neighbor Queries in Spatial Databases

doi: 10.3969/j.issn.0258-2724.2012.03.016
  • Received Date: 20 Jan 2011
  • Publish Date: 25 Jun 2012
  • 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.

     

  • loading
  • 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.
    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.
    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.
    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.
    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.
    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.
    郝忠孝. 时空数据库-查询与推理[M]. 北京:科学出版社,2010: 52-98.
    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.
    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.
    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.
    TAO Y, PAPADIAS D, LIAN X, et al. Multi-dimensional reverse kNN search[J]. The VLDB Journal, 2007, 16(3): 293-316.
    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.
    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.
    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.
    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.
    王艳秋,徐传飞,于戈,等. 一种面向不确定对象的可见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.
    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.
    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.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索
    Article views(1330) PDF downloads(232) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return