Earticle

초록

영어

Finding k nearest neighbours to one query point on road network is the typical kNN problem, and attracts lots of research interests in recent years with the development of mobile technologies. In this paper, we study a variant of the kNN problem, namely mkNN, which returns k objects for m query points. We firstly propose a baseline algorithm, which solves the mkNN problem in naive way. We then propose an optimized algorithm, which avoids the redundant computation of the baseline algorithm by organizing objects using index to firstly get candidate objects, such that to reduce the number of visited nodes of the given road network. Our third algorithm further improves the performance by using a tighter threshold to greatly reduce the number of visited nodes. We make detailed comparison between the three algorithms and show their benefits w.r.t. the mkNN problem.

목차

Abstract
 1. Introduction
 2. Preliminaries and Related Work
  2.1. Preliminaries
  2.2. Related Work
 3. The Baseline Algorithm
 4. The Optimized Algorithms
  4.1. The mkNN-O Algorithm
  4.2. The mkNN-O+ Algorithm
 5. Experiment
  5.1. Experimental Setup
  5.2. Performance Comparison
 6. Conclusions
 References

키워드

저자

• Xian Tang [ School of Economics and Management, Yanshan University, Qinhuangdao, China ]

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  International Journal of Grid and Distributed Computing

• 간기

  격월간

• pISSN

  2005-4262

• 수록기간

  2008~2016

• 십진분류

  KDC 505 DDC 605