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

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

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.