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

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

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.