Convex Polygon Planar Range Queries on the Cloud: Grid vs. Angle-Based Partitioning
Convex Polygon Planar Range Queries on the Cloud: Grid vs. Angle-Based Partitioning
复制标题
云上的凸多边形平面范围查询：网格与基于角度的分区
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Giannis Tzimas
中科院分区：
文献类型：
--
作者：
Nikolaos Nodarakis;S. Sioutas;P. Gerolymatos;A. Tsakalidis;Giannis Tzimas
多边形检索问题本质上是对n个二维点的集合进行预处理的问题，因此在给定一个特殊的ContainedIn空间查询的情况下，可以有效地报告落在多边形内部的点的子集。这种查询在计算机图形学、空间数据库和GIS应用等领域有很大的适用性。然而，随着空间数据规模的快速增长，现有的集中式解决方案无法在合理的响应时间内检索结果。在本文中，我们提出了一种新的MapReduce算法，有效地处理凸多边形平面范围查询的分布式方式。我们应用基于网格和基于角度的分区方案的数据空间，并进行比较分析。通过我们的实验评估，我们证明了我们的系统是有效的，鲁棒性和可扩展性。
The polygon retrieval problem is, in essence, the problem of preprocessing a set of n 2-dimensional points, so than given a special ContainedIn spatial query, the subset of points falling inside the polygon can be reported efficiently. Such queries find great applicability in areas such as computer graphics, spatial databases and GIS applications. However, as the size of spatial data grows rapidly existing centralized solutions fail to retrieve the results in reasonable response time. In this paper, we propose a novel MapReduce algorithm for efficiently processing convex polygon planar range queries in a distributed manner. We apply a grid-based and an angle-based partitioning scheme on the data space and perform a comparative analysis. Through our experimental evaluation we prove that our system is efficient, robust and scalable.