III: Small: Managing Spatial Data in a Distributed Environment

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