HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Journal/Magazine Articles >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/187
Title: Multiway spatial joins
Authors: Mamoulis, Nikos
Papadias, Dimitris
Keywords: Spatial joins
Multiway joins
Query processing
Algorithms
Issue Date: 2001
Citation: ACM transactions on database systems, v. 26, no. 4, 2001, p. 424-475
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 paper 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.
Rights: © ACM, 2001. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM transactions on database systems, v. 26, no. 4, 2001, p. 424-475
URI: http://hdl.handle.net/1783.1/187
Appears in Collections:CSE Journal/Magazine Articles

Files in This Item:

File Description SizeFormat
TODS.pdfpre-published version433KbAdobe PDFView/Open

Find published version via OpenURL Link Resolver

All items in this Repository are protected by copyright, with all rights reserved.