Scalable evaluation of trajectory queries over imprecise location data

Xike Xie, Man Lung Yiu, Reynold Cheng, Hua Lu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

11 Citations (Scopus)

Abstract

Trajectory queries, which retrieve nearby objects for every point of a given route, can be used to identify alerts of potential threats along a vessel route, or monitor the adjacent rescuers to a travel path. However, the locations of these objects (e.g., threats, succours) may not be precisely obtained due to hardware limitations of measuring devices, as well as complex natures of the surroundings. For such data, we consider a common model, where the possible locations of an object are bounded by a closed region, called 'imprecise region'. Ignoring or coarsely wrapping imprecision can render low query qualities, and cause undesirable consequences such as missing alerts of threats and poor response rescue time. Also, the query is quite time-consuming, since all points on the trajectory are considered. In this paper, we study how to efficiently evaluate trajectory queries over imprecise objects, by proposing a novel concept, u -bisector, which is an extension of bisector specified for imprecise data. Based on the u -bisector, we provide an efficient and versatile solution which supports different shapes of commonly-used imprecise regions (e.g., rectangles, circles, and line segments). Extensive experiments on real datasets show that our proposal achieves better efficiency, quality, and scalability than its competitors.
Original languageEnglish
Article number6514876
Pages (from-to)2029-2044
Number of pages16
JournalIEEE Transactions on Knowledge and Data Engineering
Volume26
Issue number8
DOIs
Publication statusPublished - 1 Jan 2014

Keywords

  • imprecise object
  • possible nearest neighbor
  • Trajectory query
  • u-bisector

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Cite this