Article: Constraint-based processing of multiway spatial joins

File Download Links for fulltext
(May Require Subscription)
Supplementary
  • 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
2011 Impact Factor: 0.604
2011 SCImago Journal Rankings: 0.042
ReferencesReferences in Scopus
DC Field
Value
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
2011 Impact Factor: 0.604
2011 SCImago Journal Rankings: 0.042
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
Author Affiliations
  1. Computer Technology Institute
  2. Hong Kong University of Science and Technology