File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Constraint-based processing of multiway spatial joins

TitleConstraint-based processing of multiway spatial joins
Authors
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
Citation
Algorithmica (New York), 2001, v. 30 n. 2, p. 188-215 How to Cite?
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.
Persistent Identifierhttp://hdl.handle.net/10722/152195
ISSN
2013 Impact Factor: 0.567
References

 

Author Affiliations
  1. Computer Technology Institute
  2. Hong Kong University of Science and Technology
DC FieldValueLanguage
dc.contributor.authorPapadias, Den_US
dc.contributor.authorMamoulis, Nen_US
dc.contributor.authorTheodoridis, Yen_US
dc.date.accessioned2012-06-26T06:36:26Z-
dc.date.available2012-06-26T06:36:26Z-
dc.date.issued2001en_US
dc.identifier.citationAlgorithmica (New York), 2001, v. 30 n. 2, p. 188-215en_US
dc.identifier.issn0178-4617en_US
dc.identifier.urihttp://hdl.handle.net/10722/152195-
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.en_US
dc.languageengen_US
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htmen_US
dc.relation.ispartofAlgorithmica (New York)en_US
dc.subjectConstraint Satisfactionen_US
dc.subjectR-Treesen_US
dc.subjectSpatial Databasesen_US
dc.subjectSpatial Joinsen_US
dc.titleConstraint-based processing of multiway spatial joinsen_US
dc.typeArticleen_US
dc.identifier.emailMamoulis, N:nikos@cs.hku.hken_US
dc.identifier.authorityMamoulis, N=rp00155en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.scopuseid_2-s2.0-0010601326en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0010601326&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume30en_US
dc.identifier.issue2en_US
dc.identifier.spage188en_US
dc.identifier.epage215en_US
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridPapadias, D=7005757795en_US
dc.identifier.scopusauthoridMamoulis, N=6701782749en_US
dc.identifier.scopusauthoridTheodoridis, Y=6701808265en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats