File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/503099.503101
- Scopus: eid_2-s2.0-0347236452
- WOS: WOS:000173588000002
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Multiway Spatial Joins
Title | Multiway Spatial Joins |
---|---|
Authors | |
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? |
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 Identifier | http://hdl.handle.net/10722/89157 |
ISSN | 2023 Impact Factor: 2.2 2023 SCImago Journal Rankings: 1.730 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Mamoulis, N | en_HK |
dc.contributor.author | Papadias, D | en_HK |
dc.date.accessioned | 2010-09-06T09:53:05Z | - |
dc.date.available | 2010-09-06T09:53:05Z | - |
dc.date.issued | 2001 | en_HK |
dc.identifier.citation | Acm Transactions On Database Systems, 2001, v. 26 n. 4, p. 424-475 | en_HK |
dc.identifier.issn | 0362-5915 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/89157 | - |
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. | en_HK |
dc.language | eng | en_HK |
dc.publisher | Association for Computing Machinery, Inc. | en_HK |
dc.relation.ispartof | ACM Transactions on Database Systems | en_HK |
dc.rights | ACM Transactions on Database Systems. Copyright © Association for Computing Machinery, Inc. | en_HK |
dc.subject | Algorithms | en_HK |
dc.subject | H.2.8 [Database Management]: Database Application - spatial databases and GIS | en_HK |
dc.subject | Multiway joins | en_HK |
dc.subject | Query processing | en_HK |
dc.subject | Spatial joins | en_HK |
dc.title | Multiway Spatial Joins | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0730-0301&volume=26&issue=4&spage=424&epage=475&date=2001&atitle=Multiway+spatial+joins | en_HK |
dc.identifier.email | Mamoulis, N:nikos@cs.hku.hk | en_HK |
dc.identifier.authority | Mamoulis, N=rp00155 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1145/503099.503101 | en_HK |
dc.identifier.scopus | eid_2-s2.0-0347236452 | en_HK |
dc.identifier.hkuros | 71440 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-0347236452&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 26 | en_HK |
dc.identifier.issue | 4 | en_HK |
dc.identifier.spage | 424 | en_HK |
dc.identifier.epage | 475 | en_HK |
dc.identifier.isi | WOS:000173588000002 | - |
dc.publisher.place | United States | en_HK |
dc.identifier.scopusauthorid | Mamoulis, N=6701782749 | en_HK |
dc.identifier.scopusauthorid | Papadias, D=7005757795 | en_HK |
dc.identifier.issnl | 0362-5915 | - |