|
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 |
Size | Format |
|---|
| TODS.pdf | pre-published version | 433Kb | Adobe PDF | View/Open |
|
Find published version via |
All items in this Repository are protected by copyright, with all rights reserved.
|
