File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Article: Validity information retrieval for spatio-temporal queries: Theoretical performance bounds
  • Basic View
  • Metadata View
  • XML View
TitleValidity information retrieval for spatio-temporal queries: Theoretical performance bounds
 
AuthorsTao, Y2
Mamoulis, N1
Papadias, D3
 
Issue Date2003
 
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
CitationLecture 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?]
 
AbstractThe 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.
 
ISSN0302-9743
2012 SCImago Journal Rankings: 0.332
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorTao, Y
 
dc.contributor.authorMamoulis, N
 
dc.contributor.authorPapadias, D
 
dc.date.accessioned2010-09-25T14:49:11Z
 
dc.date.available2010-09-25T14:49:11Z
 
dc.date.issued2003
 
dc.description.abstractThe 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.natureLink_to_subscribed_fulltext
 
dc.identifier.citationLecture 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.epage178
 
dc.identifier.hkuros81300
 
dc.identifier.issn0302-9743
2012 SCImago Journal Rankings: 0.332
 
dc.identifier.scopuseid_2-s2.0-35248828180
 
dc.identifier.spage159
 
dc.identifier.urihttp://hdl.handle.net/10722/93044
 
dc.identifier.volume2750
 
dc.languageeng
 
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
dc.publisher.placeGermany
 
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
 
dc.relation.referencesReferences in Scopus
 
dc.titleValidity information retrieval for spatio-temporal queries: Theoretical performance bounds
 
dc.typeArticle
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Tao, Y</contributor.author>
<contributor.author>Mamoulis, N</contributor.author>
<contributor.author>Papadias, D</contributor.author>
<date.accessioned>2010-09-25T14:49:11Z</date.accessioned>
<date.available>2010-09-25T14:49:11Z</date.available>
<date.issued>2003</date.issued>
<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</identifier.citation>
<identifier.issn>0302-9743</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/93044</identifier.uri>
<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. &#169; Springer-Verlag Berlin Heidelberg 2003.</description.abstract>
<language>eng</language>
<publisher>Springer Verlag. The Journal&apos;s web site is located at http://springerlink.com/content/105633/</publisher>
<relation.ispartof>Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</relation.ispartof>
<title>Validity information retrieval for spatio-temporal queries: Theoretical performance bounds</title>
<type>Article</type>
<description.nature>Link_to_subscribed_fulltext</description.nature>
<identifier.scopus>eid_2-s2.0-35248828180</identifier.scopus>
<identifier.hkuros>81300</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-35248828180&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>2750</identifier.volume>
<identifier.spage>159</identifier.spage>
<identifier.epage>178</identifier.epage>
<publisher.place>Germany</publisher.place>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. Carnegie Mellon University
  3. Hong Kong University of Science and Technology