Article: Multiway Spatial Joins

File Download

No File Attached
The HKU Scholars Hub has contact details for these author(s).
- Professor Mamoulis, Nikolaos

Links for fulltext
(May Require Subscription)

Publisher Website: 10.1145/503099.503101
Scopus: eid_2-s2.0-0347236452
Find via

Supplementary

Citations:
- Scopus:
- Web of Science:
- PubMed Central:
Item Statistics (The Hub)
Appears in Collections:
- Computer Science: Journal/Magazine Articles

Title	Multiway Spatial Joins
Authors	Mamoulis, N1 Papadias, D2
Keywords	Algorithms H.2.8 [Database Management]: Database Application - spatial databases and GIS Multiway joins Query processing Spatial joins
Issue Date	2001
Publisher	Association for Computing Machinery, Inc.
Citation	Acm Transactions On Database Systems, 2001, v. 26 n. 4, p. 424-475 [How to Cite?] DOI: http://dx.doi.org/10.1145/503099.503101
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.
ISSN	0362-5915 2011 Impact Factor: 1.0 2011 SCImago Journal Rankings: 0.059
DOI	http://dx.doi.org/10.1145/503099.503101
ISI Accession Number ID	WOS:000173588000002
References	References in Scopus

DC Field	Value
dc.contributor.author	Mamoulis, N
dc.contributor.author	Papadias, D
dc.date.accessioned	2010-09-06T09:53:05Z
dc.date.available	2010-09-06T09:53:05Z
dc.date.issued	2001
dc.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.
dc.description.nature	Link_to_subscribed_fulltext
dc.identifier.citation	Acm 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.doi	http://dx.doi.org/10.1145/503099.503101
dc.identifier.epage	475
dc.identifier.hkuros	71440
dc.identifier.isi	WOS:000173588000002
dc.identifier.issn	0362-5915 2011 Impact Factor: 1.0 2011 SCImago Journal Rankings: 0.059
dc.identifier.issue	4
dc.identifier.openurl
dc.identifier.scopus	eid_2-s2.0-0347236452
dc.identifier.spage	424
dc.identifier.uri	http://hdl.handle.net/10722/89157
dc.identifier.volume	26
dc.language	eng
dc.publisher	Association for Computing Machinery, Inc.
dc.publisher.place	United States
dc.relation.ispartof	ACM Transactions on Database Systems
dc.relation.references	References in Scopus
dc.rights	ACM Transactions on Database Systems. Copyright © Association for Computing Machinery, Inc.
dc.subject	Algorithms
dc.subject	H.2.8 [Database Management]: Database Application - spatial databases and GIS
dc.subject	Multiway joins
dc.subject	Query processing
dc.subject	Spatial joins
dc.title	Multiway Spatial Joins
dc.type	Article

<?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

The University of Hong Kong
Hong Kong University of Science and Technology

Article: Multiway Spatial Joins

The HKU Scholars Hub has contact details for these author(s).