File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Article: Constraint-based processing of multiway spatial joins
  • Basic View
  • Metadata View
  • XML View
TitleConstraint-based processing of multiway spatial joins
 
AuthorsPapadias, D2
Mamoulis, N2
Theodoridis, Y1
 
KeywordsConstraint Satisfaction
R-Trees
Spatial Databases
Spatial Joins
 
Issue Date2001
 
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
 
CitationAlgorithmica (New York), 2001, v. 30 n. 2, p. 188-215 [How to Cite?]
 
AbstractA multiway spatial join combines information found in three or more spatial relations with respect to some spatial predicates. Motivated by their close correspondence with constraint satisfaction problems (CSPs), we show how multiway spatial joins can be processed by systematic search algorithms traditionally used for CSPs. This paper describes two different strategies, window reduction and synchronous traversal, that take advantage of underlying spatial indexes to prune the search space effectively. In addition, we provide cost models and optimization methods that combine the two strategies to compute more efficient execution plans. Finally, we evaluate the efficiency of the proposed techniques and the accuracy of the cost models through extensive experimentation with several query and data combinations.
 
ISSN0178-4617
2013 Impact Factor: 0.567
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorPapadias, D
 
dc.contributor.authorMamoulis, N
 
dc.contributor.authorTheodoridis, Y
 
dc.date.accessioned2012-06-26T06:36:26Z
 
dc.date.available2012-06-26T06:36:26Z
 
dc.date.issued2001
 
dc.description.abstractA multiway spatial join combines information found in three or more spatial relations with respect to some spatial predicates. Motivated by their close correspondence with constraint satisfaction problems (CSPs), we show how multiway spatial joins can be processed by systematic search algorithms traditionally used for CSPs. This paper describes two different strategies, window reduction and synchronous traversal, that take advantage of underlying spatial indexes to prune the search space effectively. In addition, we provide cost models and optimization methods that combine the two strategies to compute more efficient execution plans. Finally, we evaluate the efficiency of the proposed techniques and the accuracy of the cost models through extensive experimentation with several query and data combinations.
 
dc.description.naturelink_to_subscribed_fulltext
 
dc.identifier.citationAlgorithmica (New York), 2001, v. 30 n. 2, p. 188-215 [How to Cite?]
 
dc.identifier.epage215
 
dc.identifier.issn0178-4617
2013 Impact Factor: 0.567
 
dc.identifier.issue2
 
dc.identifier.scopuseid_2-s2.0-0010601326
 
dc.identifier.spage188
 
dc.identifier.urihttp://hdl.handle.net/10722/152195
 
dc.identifier.volume30
 
dc.languageeng
 
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
 
dc.publisher.placeUnited States
 
dc.relation.ispartofAlgorithmica (New York)
 
dc.relation.referencesReferences in Scopus
 
dc.subjectConstraint Satisfaction
 
dc.subjectR-Trees
 
dc.subjectSpatial Databases
 
dc.subjectSpatial Joins
 
dc.titleConstraint-based processing of multiway spatial joins
 
dc.typeArticle
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Papadias, D</contributor.author>
<contributor.author>Mamoulis, N</contributor.author>
<contributor.author>Theodoridis, Y</contributor.author>
<date.accessioned>2012-06-26T06:36:26Z</date.accessioned>
<date.available>2012-06-26T06:36:26Z</date.available>
<date.issued>2001</date.issued>
<identifier.citation>Algorithmica (New York), 2001, v. 30 n. 2, p. 188-215</identifier.citation>
<identifier.issn>0178-4617</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/152195</identifier.uri>
<description.abstract>A multiway spatial join combines information found in three or more spatial relations with respect to some spatial predicates. Motivated by their close correspondence with constraint satisfaction problems (CSPs), we show how multiway spatial joins can be processed by systematic search algorithms traditionally used for CSPs. This paper describes two different strategies, window reduction and synchronous traversal, that take advantage of underlying spatial indexes to prune the search space effectively. In addition, we provide cost models and optimization methods that combine the two strategies to compute more efficient execution plans. Finally, we evaluate the efficiency of the proposed techniques and the accuracy of the cost models through extensive experimentation with several query and data combinations.</description.abstract>
<language>eng</language>
<publisher>Springer New York LLC. The Journal&apos;s web site is located at http://link.springer.de/link/service/journals/00453/index.htm</publisher>
<relation.ispartof>Algorithmica (New York)</relation.ispartof>
<subject>Constraint Satisfaction</subject>
<subject>R-Trees</subject>
<subject>Spatial Databases</subject>
<subject>Spatial Joins</subject>
<title>Constraint-based processing of multiway spatial joins</title>
<type>Article</type>
<description.nature>link_to_subscribed_fulltext</description.nature>
<identifier.scopus>eid_2-s2.0-0010601326</identifier.scopus>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-0010601326&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>30</identifier.volume>
<identifier.issue>2</identifier.issue>
<identifier.spage>188</identifier.spage>
<identifier.epage>215</identifier.epage>
<publisher.place>United States</publisher.place>
</item>
Author Affiliations
  1. Computer Technology Institute
  2. Hong Kong University of Science and Technology