III: Small: Managing Spatial Data in a Distributed Environment

分布式计算的进步使位于Internet上的资源池能够为许多计算需求提供可伸缩的、健壮的解决方案。像b谷歌的BigTable和Amazon的Dynamo这样的分布式键值存储系统允许并行索引和检索大量数据，而像MapReduce和Pregel这样的分布式计算框架提供了一种容错的方式来使用分布式计算资源处理大量数据。这些分布式计算技术被应用于空间数据库领域。具体来说，在分布式环境中存储和检索空间数据所涉及的问题，以及使用分布式计算框架并行处理空间查询。所有这些方法都依赖于散列的变体，以便在分布数据时获得接近恒定的时间行为，并且它们尽可能接近距离保持是可取的。具体来说，邻近的空间对象应该具有相似的散列值。特别是，希望能够仅通过考虑它们的散列值来估计两个对象之间的距离（在给定的错误范围内）。这样的哈希函数允许使用简单的哈希表查找操作执行近似范围查询。其他问题涉及空间查询的并行处理。一些简单的例子是距离连接查询，它查找（来自两个不同集合的）对象对（p,q），其中p和q之间的距离小于给定的阈值，或者计算道路网络中每个节点到每个其他节点的最短路径。更困难的是那些不易分解为多个并行运行任务的空间问题，如距离半连接查询、网络Voronoi图构建等。这需要开发一种通用方法来并行遍历图或树以解决这些查询问题。理想情况下，该方法应该很少或不需要并行任务之间的通信，这将通过允许并行任务产生冗余的结果来完成，然后可以修剪这些结果。所开发的工具将有助于提高空间数据管理的健壮性和可伸缩性。并行查询处理结果对于需要遍历树或图（通常是空间嵌入的）的查询问题非常有用。拥有一种并行遍历图或树的方法，只需很少或不需要通信，就可以使用分布式计算资源处理许多类型的空间查询，而当前的通信成本可能非常高。具体来说，可以预期这些工具将使空间应用，如在线地图、计算机辅助设计、在线游戏和科学模拟，能够处理兆兆字节的空间数据，而目前的技术不可能或效率低下。这对所有处理空间数据的组织都很有用，并将尝试在一些政府机构中使用它。此外，该项目还为研究生和本科生提供教育和研究机会。项目网站（http://www.cs.umd.edu/~hjs/distributed-spatial.html）将用于传播结果。

Advances in distributed computing enable the pooling of resources located across the Internet to provide a scalable, and robust solution for many computational needs. Distributed key-value store systems like Google's BigTable and Amazon's Dynamo allow the indexing and retrieval of a large amount of data in parallel, while distributed computing frameworks like MapReduce and Pregel provide a fault-tolerant way to process a large amount of data using distributed computing resources. These distributed computing techniques are applied to the spatial database domain. Specifically, issues involved in storing and retrieving spatial data in a distributed environment, as well as, processing spatial queries in parallel using a distributed computing framework are investigated. All of these methods rely on variants of hashing in order to obtain near constant time behavior in distributing the data and it is preferable that they are as close as possible to being distance-preserving. Specifically, spatial objects in proximity should have similar hash values. In particular, it is desirable to be able to estimate how far apart two objects are (within a given error bound) by just considering their hash values. Such hash functions enable performing an approximate range query using simple hash table lookup operations. Other issues involve the parallel processing of spatial queries. Some easy examples are the distance join query which finds pairs (p,q) of objects (from two different sets) where the distance between p and q is less than a given threshold, or computing the shortest paths from each node to every other node in a road network. More difficult are the spatial problems which can not be easily decomposed into multiple tasks running in parallel, e.g., the distance semi-join query, and network Voronoi diagram construction. This requires developing a generic method to traverse a graph or a tree in parallel to solve these query problems. Ideally, the method should require little or no communication between parallel tasks which will be accomplished by allowing the parallel tasks to produce redundant results which can then be pruned.The developed tools will help improve the robustness and scalability for spatial data management. The parallel query processing results can be useful for query problems which requires traversing a tree or a graph which are often spatially embedded. Having a method to traverse a graph or a tree in parallel that requires little or no communication enables processing of many types of spatial queries using distributed computing resources where currently communication can be very costly. Specifically, it can be expected that the tools will enable spatial applications such as online mapping, computer aided design, online gaming and scientific simulations to handle terabytes of spatial data while it is impossible or inefficient to do with the current technologies. This is of utility to all organizations that process spatial data and attempts will be made to use it in some government agencies. In addition, the project provides educational and research opportunities for graduate and undergraduates. The project web site (http://www.cs.umd.edu/~hjs/distributed-spatial.html) will be used to disseminate results.