Guo, Q and Palanisamy, B and Karimi, HA
(2015)
A MapReduce Algorithm for Polygon Retrieval in Geospatial Analysis.
In: UNSPECIFIED.
Abstract
The proliferation of data acquisition devices like 3D laser scanners had led to the burst of large-scale spatial terrain data which imposes many challenges to spatial data analysis and computation. With the advent of several emerging cloud technologies, a natural and cost-effective approach to managing such large-scale data is to store and process such datasets in a publicly hosted cloud service using modern distributed computing paradigms such as MapReduce. For several key spatial data analysis and computation problems, polygon retrieval is a fundamental operation which is often computed under real-time constraints. However, existing sequential algorithms fail to meet this demand effectively given that terrain data in recent years have witnessed an unprecedented growth in both volume and rate. In this work, we present a MapReduce-based parallel polygon retrieval algorithm which aims at minimizing the IO and CPU loads of the map and reduce tasks during spatial data processing. Our proposed algorithm first hierarchically indexes the spatial terrain data using a quad-tree index, with the help of which, a significant amount of data is filtered out in the pre-processing stage based on the query object. In addition, a prefix tree based on the quad-tree index is built to query the relationship between the terrain data and query area in real time which leads to significant savings in both I/O load and CPU time. The performance of the proposed techniques is evaluated in a Hadoop cluster and the results demonstrate that the proposed techniques are scalable and lead to more than 35% reduction in execution time of the polygon retrieval operation over existing distributed algorithms.
Share
| Citation/Export: |
|
| Social Networking: |
|
Details
| Item Type: |
Conference or Workshop Item
(UNSPECIFIED)
|
| Status: |
Published |
| Creators/Authors: |
|
| Date: |
19 August 2015 |
| Date Type: |
Publication |
| Access Restriction: |
No restriction; Release the ETD for access worldwide immediately. |
| Journal or Publication Title: |
Proceedings - 2015 IEEE 8th International Conference on Cloud Computing, CLOUD 2015 |
| Page Range: |
901 - 908 |
| Event Type: |
Conference |
| DOI or Unique Handle: |
10.1109/cloud.2015.123 |
| Institution: |
University of Pittsburgh |
| Schools and Programs: |
School of Information Sciences > Information Science |
| Refereed: |
Yes |
| ISBN: |
9781467372879 |
| Date Deposited: |
17 Jun 2015 20:40 |
| Last Modified: |
30 Mar 2021 13:55 |
| URI: |
http://d-scholarship.pitt.edu/id/eprint/25414 |
Metrics
Monthly Views for the past 3 years
Plum Analytics
Altmetric.com
Actions (login required)
 |
View Item |
![[img]](http://d-scholarship.pitt.edu/style/images/fileicons/application_pdf.png)
![[img]](http://d-scholarship.pitt.edu/style/images/fileicons/text_plain.png)
![[feed]](/images/feed-icon-32x32.png){kind=icon}