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

可扩展的几何和高维数据结构和算法：并行和分布式方法

• 批准号: 0830618
• 负责人: Hanan Samet
• 金额: $ 22万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-04-01 至 2012-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830618&HistoricalAwards=false
• 关键词: Scalable; Geometric; Dimensional; Data; Structures

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.

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