III: Small: Probabilistic Hashing for Efficient Search Learning

III：小：用于高效搜索学习的概率哈希

• 批准号: 1319830
• 负责人: Ping Li
• 金额: $ 47.51万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2013-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1319830&HistoricalAwards=false
• 关键词: III; Small; Probabilistic; Hashing; Efficient; III; Small; Probabilistic; Hashing; Efficient

Numerous applications involve massive, high-dimensional datasets. For example, the search industry routinely deals with billions of web pages, where each page is often represented as a binary vector in 2^64 dimensions. In computer vision, images are often represented as non-binary vectors in millions of dimensions. Algorithms which are capable of efficiently compressing, retrieving, and mining these datasets are of high practical importance. Mathematically rigorous and computationally efficient hashing methods will be developed to dramatically reduce ultra-high-dimensional datasets. These algorithms will be integrated with a variety of learning techniques including classification, clustering, near-neighbor search, matrix factorizations, etc. The project builds on and extends minwise hashing, and b-bit minwise hashing which are standard hashing techniques in search applications. The project aims to (i) rigorously analyze b-bit minwise hashing and develop, analyze, and apply significantly more efficient (and more accurate) to problems in search and learning; (ii) develop a unified framework of probabilistic hashing which essentially consists of one permutation followed by (at most) one random projection; (iii) develop a unified theory of summary statistics under a variety of engineering constraints (storage space, computational speed, indexing capability, adaptation to streaming, etc.). Hashing algorithms developed under this framework are expected to be substantially much more efficient and more accurate than existing popular algorithms such as random projections and minwise hashing. This general framework allows the design algorithms to accommodate many different data types (sparse or dense data, binary or real-valued data, static or streaming data), many different engineering needs (computing inner products or lp distances, kernel learning or linear learning), and different storage requirements. Anticipated results of the proposed research include rigorous and computationally efficient hashing algorithms for dealing with ultra-high-dimensional datasets, the integration of the resulting hashing algorithms into with a variety of learning techniques for classification, clustering, near-neighbor search, singular value decompositions, matrix factorization, etc; and rigorous experimental evaluation of the resulting methods on big (e.g., TeraByte or potentially PetaByte) data of the order of up to 2^64 dimensions. Broader Impacts: Effective approaches to building predictive models from extremely high dimensional data can impact many areas of science that rely on machine learning as the primary methodology for knowledge acquisition from data. The PI's education and outreach efforts aim to broaden the participation of women and underrepresented groups. The publications, software, and datasets resulting from the project will be freely disseminated to the larger scientific community.

许多应用程序涉及大量高维数据集。例如，搜索行业通常处理数十亿个网页，其中每个页面通常以2^64维度表示为二进制矢量。在计算机视觉中，图像通常表示为数百万个维度的非二进制向量。能够有效地压缩，检索和挖掘这些数据集的算法非常重要。将开发在数学上严格和计算高效的哈希方法，以大大减少超高维数据集。这些算法将与各种学习技术集成，包括分类，聚类，近邻居搜索，矩阵因素化等。该项目基于并扩展了Minwise Hashing，并且B-Bit Minwise Hashing是搜索应用中的标准哈希技术。该项目的目的是（i）严格分析B-Bit Minwise Hashing并开发，分析并应用于搜索和学习中的问题的效率更高（并且更准确）； （ii）开发一个统一的概率散列框架，该框架基本上由一个排列组成，然后是（最多）一个随机投影； （iii）在各种工程限制（存储空间，计算速度，索引能力，对流媒体的适应等）下，开发了统一统计的统一理论。预计在此框架下开发的哈希算法将比现有流行算法（例如随机预测和微小的哈希）更高效，更准确。 该一般框架允许设计算法适应许多不同的数据类型（稀疏或密集的数据，二进制或实用值数据，静态或流数据），许多不同的工程需求（计算内部产品或LP距离，内核学习或线性学习）以及不同的存储需求。拟议的研究的预期结果包括用于处理超高维数据集的严格和计算高效的哈希算法，将结果的哈希算法与各种分类，群集，近犹太人搜索，奇异的值分解，矩阵分解，矩阵分解等各种学习技术的整合；以及对最高2^64维度的大（例如Terabyte或潜在的PB）数据对所得方法进行严格的实验评估。更广泛的影响：从极高的维数据中构建预测模型的有效方法可能会影响许多依赖机器学习作为从数据获取知识的主要方法的科学领域。 PI的教育和外展工作旨在扩大妇女和代表性不足的群体的参与。该项目产生的出版物，软件和数据集将被自由传播给更大的科学界。