The direction-constrained k nearest neighbor query

详细信息    查看全文

• 作者：Min-Joong Lee ; Dong-Wan Choi ; SangYeon Kim ; Ha-Myung Park ; Sunghee Choi…
• 刊名：GeoInformatica
• 出版年：2016
• 出版时间：July 2016
• 年：2016
• 卷：20
• 期：3
• 页码：471-502
• 全文大小：4,325 KB
• 刊物类别：Earth and Environmental Science
• 刊物主题：Geography
  Geographical Information Systems and Cartography
  Data Structures, Cryptology and Information Theory
  Computer Science, general
  Information Storage and Retrieval
  Multimedia Information Systems
  
• 出版者：Springer Netherlands
• ISSN：1573-7624
• 卷排序：20

文摘

Finding k nearest neighbor objects in spatial databases is a fundamental problem in many geospatial systems and the direction is one of the key features of a spatial object. Moreover, the recent tremendous growth of sensor technologies in mobile devices produces an enormous amount of spatio-directional (i.e., spatially and directionally encoded) objects such as photos. Therefore, an efficient and proper utilization of the direction feature is a new challenge. Inspired by this issue and the traditional k nearest neighbor search problem, we devise a new type of query, called the direction-constrained k nearest neighbor (DCkNN) query. The DCkNN query finds k nearest neighbors from the location of the query such that the direction of each neighbor is in a certain range from the direction of the query. We develop a new index structure called MULTI, to efficiently answer the DCkNN query with two novel index access algorithms based on the cost analysis. Furthermore, our problem and solution can be generalized to deal with spatio-circulant dimensional (such as a direction and circulant periods of time such as an hour, a day, and a week) objects. Experimental results show that our proposed index structure and access algorithms outperform two adapted algorithms from existing kNN algorithms.Keywordsk nearest neighbor searchR-treeSpatial and directional object