File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Multiway Spatial Joins

TitleMultiway Spatial Joins
Authors
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.
Citation
Acm Transactions On Database Systems, 2001, v. 26 n. 4, p. 424-475 How to Cite?
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.
Persistent Identifierhttp://hdl.handle.net/10722/89157
ISSN
2013 Impact Factor: 0.750
2013 SCImago Journal Rankings: 1.837
ISI Accession Number ID
References

 

Author Affiliations
  1. The University of Hong Kong
  2. Hong Kong University of Science and Technology
DC FieldValueLanguage
dc.contributor.authorMamoulis, Nen_HK
dc.contributor.authorPapadias, Den_HK
dc.date.accessioned2010-09-06T09:53:05Z-
dc.date.available2010-09-06T09:53:05Z-
dc.date.issued2001en_HK
dc.identifier.citationAcm Transactions On Database Systems, 2001, v. 26 n. 4, p. 424-475en_HK
dc.identifier.issn0362-5915en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89157-
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.en_HK
dc.languageengen_HK
dc.publisherAssociation for Computing Machinery, Inc.en_HK
dc.relation.ispartofACM Transactions on Database Systemsen_HK
dc.rightsACM Transactions on Database Systems. Copyright © Association for Computing Machinery, Inc.en_HK
dc.subjectAlgorithmsen_HK
dc.subjectH.2.8 [Database Management]: Database Application - spatial databases and GISen_HK
dc.subjectMultiway joinsen_HK
dc.subjectQuery processingen_HK
dc.subjectSpatial joinsen_HK
dc.titleMultiway Spatial Joinsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0730-0301&volume=26&issue=4&spage=424&epage=475&date=2001&atitle=Multiway+spatial+joinsen_HK
dc.identifier.emailMamoulis, N:nikos@cs.hku.hken_HK
dc.identifier.authorityMamoulis, N=rp00155en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1145/503099.503101en_HK
dc.identifier.scopuseid_2-s2.0-0347236452en_HK
dc.identifier.hkuros71440en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0347236452&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume26en_HK
dc.identifier.issue4en_HK
dc.identifier.spage424en_HK
dc.identifier.epage475en_HK
dc.identifier.isiWOS:000173588000002-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridMamoulis, N=6701782749en_HK
dc.identifier.scopusauthoridPapadias, D=7005757795en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats