File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Article: Multiway Spatial Joins
  • Basic View
  • Metadata View
  • XML View
TitleMultiway Spatial Joins
 
AuthorsMamoulis, N1
Papadias, D2
 
KeywordsAlgorithms
H.2.8 [Database Management]: Database Application - spatial databases and GIS
Multiway joins
Query processing
Spatial joins
 
Issue Date2001
 
PublisherAssociation for Computing Machinery, Inc.
 
CitationAcm Transactions On Database Systems, 2001, v. 26 n. 4, p. 424-475 [How to Cite?]
DOI: http://dx.doi.org/10.1145/503099.503101
 
AbstractDue to the evolution of Geographical Information Systems, large collections of spatial data having various thematic contents are currently available. As a result, the interest of users is not limited to simple spatial selections and joins, but complex query types that implicate numerous spatial inputs become more common. Although several algorithms have been proposed for computing the result of pairwise spatial joins, limited work exists on processing and optimization of multiway spatial joins. In this article, we review pairwise spatial join algorithms and show how they can be combined for multiple inputs. In addition, we explore the application of synchronous traversal (ST), a methodology that processes synchronously all inputs without producing intermediate results. Then, we integrate the two approaches in an engine that includes ST and pairwise algorithms, using dynamic programming to determine the optimal execution plan. The results show that, in most cases, multiway spatial joins are best processed by combining ST with pairwise methods. Finally, we study the optimization of very large queries by employing randomized search algorithms.
 
ISSN0362-5915
2013 Impact Factor: 0.750
2013 SCImago Journal Rankings: 1.837
 
DOIhttp://dx.doi.org/10.1145/503099.503101
 
ISI Accession Number IDWOS:000173588000002
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorMamoulis, N
 
dc.contributor.authorPapadias, D
 
dc.date.accessioned2010-09-06T09:53:05Z
 
dc.date.available2010-09-06T09:53:05Z
 
dc.date.issued2001
 
dc.description.abstractDue to the evolution of Geographical Information Systems, large collections of spatial data having various thematic contents are currently available. As a result, the interest of users is not limited to simple spatial selections and joins, but complex query types that implicate numerous spatial inputs become more common. Although several algorithms have been proposed for computing the result of pairwise spatial joins, limited work exists on processing and optimization of multiway spatial joins. In this article, we review pairwise spatial join algorithms and show how they can be combined for multiple inputs. In addition, we explore the application of synchronous traversal (ST), a methodology that processes synchronously all inputs without producing intermediate results. Then, we integrate the two approaches in an engine that includes ST and pairwise algorithms, using dynamic programming to determine the optimal execution plan. The results show that, in most cases, multiway spatial joins are best processed by combining ST with pairwise methods. Finally, we study the optimization of very large queries by employing randomized search algorithms.
 
dc.description.naturelink_to_subscribed_fulltext
 
dc.identifier.citationAcm Transactions On Database Systems, 2001, v. 26 n. 4, p. 424-475 [How to Cite?]
DOI: http://dx.doi.org/10.1145/503099.503101
 
dc.identifier.doihttp://dx.doi.org/10.1145/503099.503101
 
dc.identifier.epage475
 
dc.identifier.hkuros71440
 
dc.identifier.isiWOS:000173588000002
 
dc.identifier.issn0362-5915
2013 Impact Factor: 0.750
2013 SCImago Journal Rankings: 1.837
 
dc.identifier.issue4
 
dc.identifier.openurl
 
dc.identifier.scopuseid_2-s2.0-0347236452
 
dc.identifier.spage424
 
dc.identifier.urihttp://hdl.handle.net/10722/89157
 
dc.identifier.volume26
 
dc.languageeng
 
dc.publisherAssociation for Computing Machinery, Inc.
 
dc.publisher.placeUnited States
 
dc.relation.ispartofACM Transactions on Database Systems
 
dc.relation.referencesReferences in Scopus
 
dc.rightsACM Transactions on Database Systems. Copyright © Association for Computing Machinery, Inc.
 
dc.subjectAlgorithms
 
dc.subjectH.2.8 [Database Management]: Database Application - spatial databases and GIS
 
dc.subjectMultiway joins
 
dc.subjectQuery processing
 
dc.subjectSpatial joins
 
dc.titleMultiway Spatial Joins
 
dc.typeArticle
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Mamoulis, N</contributor.author>
<contributor.author>Papadias, D</contributor.author>
<date.accessioned>2010-09-06T09:53:05Z</date.accessioned>
<date.available>2010-09-06T09:53:05Z</date.available>
<date.issued>2001</date.issued>
<identifier.citation>Acm Transactions On Database Systems, 2001, v. 26 n. 4, p. 424-475</identifier.citation>
<identifier.issn>0362-5915</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/89157</identifier.uri>
<description.abstract>Due to the evolution of Geographical Information Systems, large collections of spatial data having various thematic contents are currently available. As a result, the interest of users is not limited to simple spatial selections and joins, but complex query types that implicate numerous spatial inputs become more common. Although several algorithms have been proposed for computing the result of pairwise spatial joins, limited work exists on processing and optimization of multiway spatial joins. In this article, we review pairwise spatial join algorithms and show how they can be combined for multiple inputs. In addition, we explore the application of synchronous traversal (ST), a methodology that processes synchronously all inputs without producing intermediate results. Then, we integrate the two approaches in an engine that includes ST and pairwise algorithms, using dynamic programming to determine the optimal execution plan. The results show that, in most cases, multiway spatial joins are best processed by combining ST with pairwise methods. Finally, we study the optimization of very large queries by employing randomized search algorithms.</description.abstract>
<language>eng</language>
<publisher>Association for Computing Machinery, Inc.</publisher>
<relation.ispartof>ACM Transactions on Database Systems</relation.ispartof>
<rights>ACM Transactions on Database Systems. Copyright &#169; Association for Computing Machinery, Inc.</rights>
<subject>Algorithms</subject>
<subject>H.2.8 [Database Management]: Database Application - spatial databases and GIS</subject>
<subject>Multiway joins</subject>
<subject>Query processing</subject>
<subject>Spatial joins</subject>
<title>Multiway Spatial Joins</title>
<type>Article</type>
<identifier.openurl>http://library.hku.hk:4550/resserv?sid=HKU:IR&amp;issn=0730-0301&amp;volume=26&amp;issue=4&amp;spage=424&amp;epage=475&amp;date=2001&amp;atitle=Multiway+spatial+joins</identifier.openurl>
<description.nature>link_to_subscribed_fulltext</description.nature>
<identifier.doi>10.1145/503099.503101</identifier.doi>
<identifier.scopus>eid_2-s2.0-0347236452</identifier.scopus>
<identifier.hkuros>71440</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-0347236452&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>26</identifier.volume>
<identifier.issue>4</identifier.issue>
<identifier.spage>424</identifier.spage>
<identifier.epage>475</identifier.epage>
<identifier.isi>WOS:000173588000002</identifier.isi>
<publisher.place>United States</publisher.place>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. Hong Kong University of Science and Technology