III: Small: Large-Scale High Dimensional Dense Vector Management

三：小：大规模高维密集矢量管理

• 批准号: 2212629
• 负责人: Dong Deng
• 金额: $ 59.96万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-09-01 至 2025-08-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2212629&HistoricalAwards=false
• 关键词: III; Small; Large; Scale; Dimensional

Real-world objects such as images and documents often contain rich metadata information. In addition, the rapid development of machine learning, especially deep learning, in recent years make it possible to extract meaningful relationships between real-world objects and encode them in numerical representations. In this way, the semantics of objects can be conveniently processed by computers. The numerical representations of semantics plays an important role in many data science and artificial intelligence applications, such as face recognition, image retrieval, video understanding, recommender systems, text analysis, and knowledge-base management. In these applications, the numerical representations of real-world objects and their associated metadata are usually jointly queried. While metadata management and representation management are investigated extensively independently, jointly managing metadata and representations is under-investigated making it difficult to do in practice. Unfortunately, due to the large data volume and the notorious "curse-of-dimensionality" phenomenon that makes all high-dimensional data objects appear far apart, metadata and representation joint management are challenging. To support the ability of applications to work with both traditional and numerical representations of data, this project will study how to leverage the synergy between them. If successful, this project will advance the development of science and technology by providing new knowledge about data management. Moreover, despite being widely used, metadata and representations are still largely managed by individual application developers. Without careful implementation, the performance can hardly meet the needs of a wide variety of potential users. This project will deliver an end-to-end data system to alleviate the burden on machine learning practitioners and application developers of managing the representations and metadata created by their programs by themselves. In addition, this project includes curriculum development and student training at Rutgers University to amplify the impact of the work.Large-scale high dimensional dense vectors are ubiquitous nowadays due to the rapid development of representation learning (e.g., the learned feature vectors from well-established machine-learning systems such as word2vec, doc2vec, node2vec, graph2vec, item2vec, etc.). They play an important role in many applications in areas such as data mining, natural language processing, computer vision, information retrieval, and recommendations. However, large-scale high dimensional dense vectors are notorious for being hard to query efficiently due to the well-known "curse of dimensionality" phenomenon. Existing research on high dimensional dense vector management mainly focuses on approximate nearest-neighbor search (ANNS). However, a few widely used, compute-intensive dense vector queries are under-examined by the research community and not well supported by existing systems. This project will study three of them: multi-modal ANNS, parallel vector similarity join, and rank estimation. Specifically, multi-modal ANNS are queries involving both dense vectors (e.g., vector representations of product images or documents) and their structured attributes (e.g., product price or last edit time). Given a collection of dense vectors, the vector similarity join connects every vector with its nearest neighbors. To deal with the huge computational cost of this operation, this project will study lock-free, massively parallel algorithms on CPUs and GPUs. Rank estimation approximates the inherent dimensionality of a data vector (e.g., vector representations of items in recommendation or documents in information retrieval) in a set of data vectors ordered by their distance to a relevant vector (e.g., a user purchased the item or a keyword query related to the document). Such a scheme is useful in machine-learning model evaluation. The long-term goal of this project is to build an end-to-end system to make large-scale dense vector management transparent to machine-learning practitioners and application developers.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

真实世界的对象（如图像和文档）通常包含丰富的元数据信息。此外，近年来机器学习的快速发展，特别是深度学习，使得提取现实世界对象之间有意义的关系并将其编码为数字表示成为可能。这样，对象的语义可以方便地被计算机处理。语义的数值表示在许多数据科学和人工智能应用中起着重要作用，例如人脸识别，图像检索，视频理解，推荐系统，文本分析和知识库管理。在这些应用中，真实世界对象的数字表示及其相关元数据通常被联合查询。虽然元数据管理和表示管理被广泛地独立研究，但联合管理元数据和表示的研究不足，使得在实践中很难做到。不幸的是，由于大数据量和臭名昭著的“维数灾难”现象，使所有的高维数据对象显得相距甚远，元数据和表示的联合管理是具有挑战性的。为了支持应用程序处理传统和数字数据表示的能力，本项目将研究如何利用它们之间的协同作用。如果成功，该项目将通过提供有关数据管理的新知识来推动科学和技术的发展。此外，尽管被广泛使用，元数据和表示仍然主要由个人应用程序开发人员管理。如果不认真执行，性能很难满足各种潜在用户的需求。该项目将提供一个端到端的数据系统，以减轻机器学习从业者和应用程序开发人员管理自己程序创建的表示和元数据的负担。此外，该项目还包括罗格斯大学的课程开发和学生培训，以放大工作的影响。由于表征学习的快速发展，大规模高维密集向量如今无处不在（例如，从诸如Word2vec、Doc2vec、Node2vec、Graph2vec、Item2vec等的完善的机器学习系统学习的特征向量）。它们在数据挖掘、自然语言处理、计算机视觉、信息检索和推荐等领域的许多应用中发挥着重要作用。然而，大规模的高维密集向量是臭名昭著的难以有效地查询，由于众所周知的“维数灾难”现象。现有的高维稠密向量管理研究主要集中在近似最近邻搜索（ANNS）。然而，一些广泛使用的，计算密集型的密集向量查询是由研究界研究不足，并没有得到很好的支持现有的系统。本计画将研究其中的三种：多模态人工神经网路、平行向量相似性连接、以及等级估计。具体地，多模态ANNS是涉及密集向量（例如，产品图像或文档的矢量表示）及其结构化属性（例如，产品价格或上次编辑时间）。给定一个稠密向量的集合，向量相似性连接将每个向量与其最近的邻居连接起来。为了应对这种操作的巨大计算成本，该项目将研究CPU和GPU上的无锁大规模并行算法。秩估计近似数据向量的固有维度（例如，推荐中的项目或信息检索中的文档的向量表示）在一组数据向量中，用户购买了该项目或与该文档相关的关键字查询）。这种方案在机器学习模型评估中是有用的。该项目的长期目标是建立一个端到端系统，使大规模密集矢量管理对机器学习从业者和应用程序开发人员透明。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph

• DOI: 10.14778/3603581.3603601
• 发表时间: 2023-06
• 期刊: Proc. VLDB Endow.
• 作者: Chaoji Zuo;Dong Deng