Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/2513

Validity information retrieval for spatio-temporal queries: Theoretical performance bounds

Authors Tao, YF
Mamoulis, N
Papadias, D
Issue Date 2003
Source Lecture notes in computer science, v. 2750, 2003, p. 159-178
Summary The results of traditional spatial queries (i.e., range search, nearest neighbor, etc.) are usually meaningless in spatio-temporal applications, because they will be invalidated by the movements of query and/or data objects. In practice, a query result R should be accompanied with validity information specifying (i) the (future) time T that R will expire, and (ii) the change C of R at time T (so that R can be updated incrementally). Although several algorithms have been proposed for this problem, their worst-case performance is the same as that of sequential scan. This paper presents the first theoretical study on validity queries, and develops indexes and algorithms with attractive I/O complexities. Our discussion covers numerous important variations of the problem and different query/object mobility combinations. The solutions involve a set of non-trivial reductions that reveal the problem characteristics and permit the deployment of existing structures.
Subjects
ISSN 0302-9743
Rights The original publication is available at http://www.springerlink.com/. Please use the appropriate URL and/or DOI for the article.The access script to link to it is: http://library.ust.hk/cgi/db/doi.pl?10.1007/b11839
Language English
Format Article
Access View full-text via Web of Science
View full-text via Scopus
Find@HKUST
Files in this item:
File Description Size Format
papadias9.pdf 161.68 kB Adobe PDF