Article: Validity information retrieval for spatio-temporal queries: Theoretical performance bounds
| Title | Validity information retrieval for spatio-temporal queries: Theoretical performance bounds |
|---|---|
| Authors | Tao, Y2 Mamoulis, N1 Papadias, D3 |
| Issue Date | 2003 |
| Publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
| Citation | Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2003, v. 2750, p. 159-178 [How to Cite?] |
| 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. © Springer-Verlag Berlin Heidelberg 2003. |
| ISSN | 0302-9743 2011 SCImago Journal Rankings: 0.034 |
| References | References in Scopus |
| dc.contributor.author | Tao, Y |
|---|---|
| dc.contributor.author | Mamoulis, N |
| dc.contributor.author | Papadias, D |
| dc.date.accessioned | 2010-09-25T14:49:11Z |
| dc.date.available | 2010-09-25T14:49:11Z |
| dc.date.issued | 2003 |
| dc.description.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. © Springer-Verlag Berlin Heidelberg 2003. |
| dc.description.nature | Link_to_subscribed_fulltext |
| dc.identifier.citation | Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2003, v. 2750, p. 159-178 [How to Cite?] |
| dc.identifier.epage | 178 |
| dc.identifier.hkuros | 81300 |
| dc.identifier.issn | 0302-9743 2011 SCImago Journal Rankings: 0.034 |
| dc.identifier.scopus | eid_2-s2.0-35248828180 |
| dc.identifier.spage | 159 |
| dc.identifier.uri | http://hdl.handle.net/10722/93044 |
| dc.identifier.volume | 2750 |
| dc.language | eng |
| dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
| dc.publisher.place | Germany |
| dc.relation.ispartof | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| dc.relation.references | References in Scopus |
| dc.title | Validity information retrieval for spatio-temporal queries: Theoretical performance bounds |
| dc.type | Article |
Author Affiliations
- The University of Hong Kong
- Carnegie Mellon University
- Hong Kong University of Science and Technology