Continuous aggregate nearest neighbor queries

Hicham G. Elmongui, Mohamed F. Mokbel, Walid G. Aref

Research output: Contribution to journalArticlepeer-review

28 Scopus citations

Abstract

This paper addresses the problem of continuous aggregate nearest-neighbor (CANN) queries for moving objects in spatio-temporal data stream management systems. A CANN query specifies a set of landmarks, an integer k, and an aggregate distance function f (e. g., min, max, or sum), where f computes the aggregate distance between a moving object and each of the landmarks. The answer to this continuous query is the set of k moving objects that have the smallest aggregate distance f. A CANN query may also be viewed as a combined set of nearest neighbor queries. We introduce several algorithms to continuously and incrementally answer CANN queries. Extensive experimentation shows that the proposed operators outperform the state-of-the-art algorithms by up to a factor of 3 and incur low memory overhead.

Original languageEnglish (US)
Pages (from-to)63-95
Number of pages33
JournalGeoInformatica
Volume17
Issue number1
DOIs
StatePublished - Jan 2013

Bibliographical note

Funding Information:
This work is supported in part by the National Science Foundation under Grant Numbers IIS-0811954, III-1117766, IIS-0964639, IIS-0811935, CNS-0708604, IIS-0952977 (NSF CAREER) and by a Microsoft Research Gift.

Keywords

  • Aggregate nearest neighbor
  • Continuous query
  • Spatio-temporal query

Fingerprint

Dive into the research topics of 'Continuous aggregate nearest neighbor queries'. Together they form a unique fingerprint.

Cite this