Please use this identifier to cite or link to this item:

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

Authors Tao, YF
Mamoulis, N.
Papadias, D. View this author's profile
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.
ISSN 0302-9743
Rights The original publication is available at Please use the appropriate URL and/or DOI for the article.The access script to link to it is:
Language English
Format Article
Access View full-text via Web of Science
View full-text via Scopus
Files in this item:
File Description Size Format
papadias9.pdf 165560 B Adobe PDF