III: Small: Managing Spatial Data in a Distributed Environment

分布式计算的进步使得跨Internet的资源共享能够为许多计算需求提供可扩展的、健壮的解决方案。像Google的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.