HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Conference Papers >

Please use this identifier to cite or link to this item:
Title: Validity information retrieval for spatio-temporal queries : theoretical performance bounds
Authors: Tao, Yufei
Mamoulis, Nikos
Papadias, Dimitris
Keywords: Spatial-temporal databases
Database queries
Validity queries
Issue Date: Jul-2003
Citation: Advances in Spatial and Temporal Databases: 8th International Symposium, 2003 (LNCS 2750) p. 159-178
Abstract: 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.
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:
Appears in Collections:CSE Conference Papers

Files in This Item:

File Description SizeFormat
papadias9.pdfpre-published version161KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.