Evaluating continuous K-nearest neighbor query on moving objects with uncertainty

Yuan Ko Huang, Shi Jei Liao, Chiang Lee

Research output: Contribution to journalArticle

18 Citations (Scopus)

Abstract

Continuous K-nearest neighbor (C K NN) query is one of the most fundamental queries in the field of spatio-temporal databases. Given a time interval [ts, te], a C K NN query is to retrieve the K-nearest neighbors (K NNs) of a moving user at each time instant within [ts, te]. Existing methods for processing a C K NN query, however, assume that each object moves with a fixed direction and/or a fixed speed. In this paper, we relieve this assumption by allowing both the moving speed and the moving direction of each object to vary. This uncertainty on speed and direction of a moving object would increase the complexity of processing a C K NN query. We thoroughly analyze the involved issues incurred by this uncertainty and propose a continuous possible KNN (CPKNN) algorithm to effectively find the objects that could be the K NNs. These objects are termed the possible KNNs (PKNNs) in this paper. A probability-based model is designed accordingly to quantify the possibility of each P K NN being the K NN. In addition, we design a PKNN updating mechanism to rapidly evaluate the new query result when object updates occur. Comprehensive experiments are conducted to demonstrate the effectiveness and the efficiency of the proposed approach.

Original languageEnglish
Pages (from-to)415-437
Number of pages23
JournalInformation Systems
Volume34
Issue number4-5
DOIs
Publication statusPublished - 2009 Jun 1

Fingerprint

Processing
Uncertainty
Experiments

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture

Cite this

Huang, Yuan Ko ; Liao, Shi Jei ; Lee, Chiang. / Evaluating continuous K-nearest neighbor query on moving objects with uncertainty. In: Information Systems. 2009 ; Vol. 34, No. 4-5. pp. 415-437.
@article{adbccfa7c8ed4aa3b4d576d2daf259bb,
title = "Evaluating continuous K-nearest neighbor query on moving objects with uncertainty",
abstract = "Continuous K-nearest neighbor (C K NN) query is one of the most fundamental queries in the field of spatio-temporal databases. Given a time interval [ts, te], a C K NN query is to retrieve the K-nearest neighbors (K NNs) of a moving user at each time instant within [ts, te]. Existing methods for processing a C K NN query, however, assume that each object moves with a fixed direction and/or a fixed speed. In this paper, we relieve this assumption by allowing both the moving speed and the moving direction of each object to vary. This uncertainty on speed and direction of a moving object would increase the complexity of processing a C K NN query. We thoroughly analyze the involved issues incurred by this uncertainty and propose a continuous possible KNN (CPKNN) algorithm to effectively find the objects that could be the K NNs. These objects are termed the possible KNNs (PKNNs) in this paper. A probability-based model is designed accordingly to quantify the possibility of each P K NN being the K NN. In addition, we design a PKNN updating mechanism to rapidly evaluate the new query result when object updates occur. Comprehensive experiments are conducted to demonstrate the effectiveness and the efficiency of the proposed approach.",
author = "Huang, {Yuan Ko} and Liao, {Shi Jei} and Chiang Lee",
year = "2009",
month = "6",
day = "1",
doi = "10.1016/j.is.2009.01.001",
language = "English",
volume = "34",
pages = "415--437",
journal = "Information Systems",
issn = "0306-4379",
publisher = "Elsevier Limited",
number = "4-5",

}

Evaluating continuous K-nearest neighbor query on moving objects with uncertainty. / Huang, Yuan Ko; Liao, Shi Jei; Lee, Chiang.

In: Information Systems, Vol. 34, No. 4-5, 01.06.2009, p. 415-437.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Evaluating continuous K-nearest neighbor query on moving objects with uncertainty

AU - Huang, Yuan Ko

AU - Liao, Shi Jei

AU - Lee, Chiang

PY - 2009/6/1

Y1 - 2009/6/1

N2 - Continuous K-nearest neighbor (C K NN) query is one of the most fundamental queries in the field of spatio-temporal databases. Given a time interval [ts, te], a C K NN query is to retrieve the K-nearest neighbors (K NNs) of a moving user at each time instant within [ts, te]. Existing methods for processing a C K NN query, however, assume that each object moves with a fixed direction and/or a fixed speed. In this paper, we relieve this assumption by allowing both the moving speed and the moving direction of each object to vary. This uncertainty on speed and direction of a moving object would increase the complexity of processing a C K NN query. We thoroughly analyze the involved issues incurred by this uncertainty and propose a continuous possible KNN (CPKNN) algorithm to effectively find the objects that could be the K NNs. These objects are termed the possible KNNs (PKNNs) in this paper. A probability-based model is designed accordingly to quantify the possibility of each P K NN being the K NN. In addition, we design a PKNN updating mechanism to rapidly evaluate the new query result when object updates occur. Comprehensive experiments are conducted to demonstrate the effectiveness and the efficiency of the proposed approach.

AB - Continuous K-nearest neighbor (C K NN) query is one of the most fundamental queries in the field of spatio-temporal databases. Given a time interval [ts, te], a C K NN query is to retrieve the K-nearest neighbors (K NNs) of a moving user at each time instant within [ts, te]. Existing methods for processing a C K NN query, however, assume that each object moves with a fixed direction and/or a fixed speed. In this paper, we relieve this assumption by allowing both the moving speed and the moving direction of each object to vary. This uncertainty on speed and direction of a moving object would increase the complexity of processing a C K NN query. We thoroughly analyze the involved issues incurred by this uncertainty and propose a continuous possible KNN (CPKNN) algorithm to effectively find the objects that could be the K NNs. These objects are termed the possible KNNs (PKNNs) in this paper. A probability-based model is designed accordingly to quantify the possibility of each P K NN being the K NN. In addition, we design a PKNN updating mechanism to rapidly evaluate the new query result when object updates occur. Comprehensive experiments are conducted to demonstrate the effectiveness and the efficiency of the proposed approach.

UR - http://www.scopus.com/inward/record.url?scp=65049091726&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=65049091726&partnerID=8YFLogxK

U2 - 10.1016/j.is.2009.01.001

DO - 10.1016/j.is.2009.01.001

M3 - Article

VL - 34

SP - 415

EP - 437

JO - Information Systems

JF - Information Systems

SN - 0306-4379

IS - 4-5

ER -