Scalable Geometric and High Dimensional Data Structures and Algorithms: A Parallel and Distributed Approach

建议：0830618注册：大学。MarylandPI：Samet，HananTITLE：可伸缩几何和高维数据结构和算法：一种并行和分布式方法ABSTRACT商品计算成本的稳步下降以及对计算能力日益增长的渴望的民主化，主要是由强大的搜索引擎产生的海量数据推动的，这导致了对传统方法如何解决涉及搜索的问题的重新审视。随着越来越多的应用程序成为网络服务(即技术术语中的“云应用程序”)，人们越来越期望能够以能够同时为数百万用户提供服务的规模实时获得和提供答案。对于许多复杂的问题，这种期望迫使人们重新思考解决方案的范式。特别是，人们越来越认识到，速度和规模要求意味着提供服务的唯一方法是将解决方案过程分离为两个步骤：一个步骤预先计算所有可能问题的解决方案空间，并可能提供它的编码，以及一个导航解决方案空间的步骤。该研究探索了空间网络中回答最短路径和最近邻查询的解耦范式，其效果是将沿网络计算最短路径的过程与寻找最近邻的过程解耦，旨在通过加速相似性搜索任务来提高对包括地图、文档、视频、图像和音乐在内的海量用户生成数据的可访问性。这总是涉及到利用各种方法对数据进行排序，其中还包括开发构建适当的多维和空间索引的方法。通过专注于使用GPU和分布式处理，以及通过预计算来分离，它将计算能力的增加带来的好处带给了更广泛的用户，这些用户通常可以使用这种能力。此外，通过展示在空间网络中使用解耦来计算最近邻居所获得的能力，它刺激了针对其他搜索问题的可扩展解决方案的发展。

PROPOSAL: 0830618INSTITUTION: Univ. of MarylandPI: Samet, HananTITLE: Scalable Geometric and High Dimensional Data Structures and Algorithms: A Parallel and Distributed ApproachABSTRACTThe steadily decreasing cost of commodity computing as well as the democratization of the increasing thirst for computing power, fueled largely by the massive volumes of data generated by powerful search engines, has led to a reexamination of how the traditional methods of solving problems that involve search. As more and more applications become web services (i.e., ``cloud applications'' in technology parlance), there is an increasing expectation that answers be obtained and provided in real time and at a scale that is capable of servicing millions of users at the same time. For many complex problems, this expectation forces a rethink of the solution paradigm. In particular, there is an increasing realization that the speed and scale requirements mean that the only way to provide the service is to decouple the solution process into two steps: one that precomputes a solution space to all possible problems, and possibly provides an encoding of it, and one that navigates the solution space. This research explores the decoupling paradigm in the context of answering shortest path and nearest neighbor queries in a spatial network, where the effect is to decouple the process of computing shortest paths along the network from the process of finding the nearest neighbors.This research aims at increasing the accessibility to massive amounts of user generated data including maps, documents, videos, images, and music by speeding up the similarity searching task. This invariably involves taking advantage of ways to sort the data which also includes developing methods to build appropriate multidimensional and spatial indexes. By focusing on making use of GPUs and distributed processing, as well as decoupling via pre-computation, it brings the benefits of this increase in computing power to a wider range of users who often have this power at their disposal. In addition, by demonstrating the power obtained by the use of decoupling in computing nearest neighbors in a spatial network it stimulates the development of scalable solutions to other search problems.