|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE Conference Papers >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/2513
|
| 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 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 |
| URI: | http://hdl.handle.net/1783.1/2513 |
| Appears in Collections: | CSE Conference Papers
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| papadias9.pdf | pre-published version | 161Kb | Adobe PDF | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
