Efficient evaluation of continuous spatio-temporal queries on moving objects with uncertain velocity

Yuan Ko Huang, Chiang Lee

Research output: Contribution to journalArticle

13 Citations (Scopus)

Abstract

Continuous Range (CR) query and Continuous K-Nearest Neighbor (CKNN) query are two important types of spatio-temporal queries. Given a time interval [t s, t e] and a moving query object q, a CR query is to find the moving objects whose Euclidean distances to q are within a user-given distance at each time instant within [t s, t e]. A CKNN query is to retrieve the K-Nearest Neighbors (KNNs) of this query object q at each time instant within [t s, t e]. In this paper, we investigate how to process these spatio-temporal queries efficiently under the situation that the velocity of each object is not fixed. This uncertainty on the velocity of object inevitably results in high complexity in processing spatio-temporal queries. We will discuss the complications incurred by this uncertainty and propose two algorithms, namely the Possibility-based possible within objects searching algorithm and the Possibility-based possible KNN searching algorithm, for the CR query and the CKNN query, respectively. A Possibility-based model is designed accordingly to quantify the possibility of each object being the result of a CR query or a CKNN query. Comprehensive experiments are performed to demonstrate the effectiveness and the efficiency of the proposed approaches.

Original languageEnglish
Pages (from-to)163-200
Number of pages38
JournalGeoInformatica
Volume14
Issue number2
DOIs
Publication statusPublished - 2010 Apr 1

Fingerprint

evaluation
uncertainty
Processing
experiment
Experiments
Uncertainty
efficiency

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Geography, Planning and Development

Cite this

@article{88727d9478e1440fb8385b014357d5e8,
title = "Efficient evaluation of continuous spatio-temporal queries on moving objects with uncertain velocity",
abstract = "Continuous Range (CR) query and Continuous K-Nearest Neighbor (CKNN) query are two important types of spatio-temporal queries. Given a time interval [t s, t e] and a moving query object q, a CR query is to find the moving objects whose Euclidean distances to q are within a user-given distance at each time instant within [t s, t e]. A CKNN query is to retrieve the K-Nearest Neighbors (KNNs) of this query object q at each time instant within [t s, t e]. In this paper, we investigate how to process these spatio-temporal queries efficiently under the situation that the velocity of each object is not fixed. This uncertainty on the velocity of object inevitably results in high complexity in processing spatio-temporal queries. We will discuss the complications incurred by this uncertainty and propose two algorithms, namely the Possibility-based possible within objects searching algorithm and the Possibility-based possible KNN searching algorithm, for the CR query and the CKNN query, respectively. A Possibility-based model is designed accordingly to quantify the possibility of each object being the result of a CR query or a CKNN query. Comprehensive experiments are performed to demonstrate the effectiveness and the efficiency of the proposed approaches.",
author = "Huang, {Yuan Ko} and Chiang Lee",
year = "2010",
month = "4",
day = "1",
doi = "10.1007/s10707-009-0081-8",
language = "English",
volume = "14",
pages = "163--200",
journal = "GeoInformatica",
issn = "1384-6175",
publisher = "Kluwer Academic Publishers",
number = "2",

}

Efficient evaluation of continuous spatio-temporal queries on moving objects with uncertain velocity. / Huang, Yuan Ko; Lee, Chiang.

In: GeoInformatica, Vol. 14, No. 2, 01.04.2010, p. 163-200.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Efficient evaluation of continuous spatio-temporal queries on moving objects with uncertain velocity

AU - Huang, Yuan Ko

AU - Lee, Chiang

PY - 2010/4/1

Y1 - 2010/4/1

N2 - Continuous Range (CR) query and Continuous K-Nearest Neighbor (CKNN) query are two important types of spatio-temporal queries. Given a time interval [t s, t e] and a moving query object q, a CR query is to find the moving objects whose Euclidean distances to q are within a user-given distance at each time instant within [t s, t e]. A CKNN query is to retrieve the K-Nearest Neighbors (KNNs) of this query object q at each time instant within [t s, t e]. In this paper, we investigate how to process these spatio-temporal queries efficiently under the situation that the velocity of each object is not fixed. This uncertainty on the velocity of object inevitably results in high complexity in processing spatio-temporal queries. We will discuss the complications incurred by this uncertainty and propose two algorithms, namely the Possibility-based possible within objects searching algorithm and the Possibility-based possible KNN searching algorithm, for the CR query and the CKNN query, respectively. A Possibility-based model is designed accordingly to quantify the possibility of each object being the result of a CR query or a CKNN query. Comprehensive experiments are performed to demonstrate the effectiveness and the efficiency of the proposed approaches.

AB - Continuous Range (CR) query and Continuous K-Nearest Neighbor (CKNN) query are two important types of spatio-temporal queries. Given a time interval [t s, t e] and a moving query object q, a CR query is to find the moving objects whose Euclidean distances to q are within a user-given distance at each time instant within [t s, t e]. A CKNN query is to retrieve the K-Nearest Neighbors (KNNs) of this query object q at each time instant within [t s, t e]. In this paper, we investigate how to process these spatio-temporal queries efficiently under the situation that the velocity of each object is not fixed. This uncertainty on the velocity of object inevitably results in high complexity in processing spatio-temporal queries. We will discuss the complications incurred by this uncertainty and propose two algorithms, namely the Possibility-based possible within objects searching algorithm and the Possibility-based possible KNN searching algorithm, for the CR query and the CKNN query, respectively. A Possibility-based model is designed accordingly to quantify the possibility of each object being the result of a CR query or a CKNN query. Comprehensive experiments are performed to demonstrate the effectiveness and the efficiency of the proposed approaches.

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

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

U2 - 10.1007/s10707-009-0081-8

DO - 10.1007/s10707-009-0081-8

M3 - Article

VL - 14

SP - 163

EP - 200

JO - GeoInformatica

JF - GeoInformatica

SN - 1384-6175

IS - 2

ER -