BIGDATA: F: DKA: Collaborative Research: Structured Nearest Neighbor Search in High Dimensions

大型数据集分析中的一个基本问题是找到一个或多个与输入查询尽可能相似的数据项。例如，当用户想要识别照片中捕获的产品时，就会出现这种情况。相应的计算问题，称为最近邻（NN）搜索，已经吸引了大量的研究，有几个算法具有重要的影响。然而，神经网络的技术水平受到重要的理论和实践限制。特别是，它没有提供一种自然的方法来利用许多应用程序中存在的数据结构。例如，虽然所描绘的物体的身份不会随着物体的照明或位置的变化而改变，但目前的神经网络算法会将生成的图像视为完全不同的图像，从而会错误地识别物体。为了克服这个困难，在这个项目中，pi将开发新的高效算法，将问题结构纳入NN搜索。pi期望这些方法将为许多大规模数据分析任务产生更好的结果。为了确保这项工作基于一个重要的应用，pi将专注于计算机视觉，这是一个互联网规模的数据集具有重大影响的领域。神经网络搜索对计算机视觉至关重要，事实上，许多高级计算机视觉研究人员将改进的神经网络技术视为他们的首要算法。图像和视频具有重要的结构，通常在本质上是空间的，像图切这样的算法技术已经能够相当成功地利用这些结构。提出的工作将制定利用额外结构的神经网络搜索的新变体，并将设计有效的算法来解决大型数据集上的这些问题。特别是，pi将研究三种结构化的神经网络问题公式。同时最近邻查询涉及多个查询，其中答案应该彼此兼容。变换下的最近邻考虑对各种图像变换不变的距离。子空间的最近邻涉及在一组线性或仿射子空间中搜索最接近查询点的子空间。该项目更广泛的影响包括算法和图像处理方面的研究生培训。欲了解更多信息，请参阅该项目的网站：http://cs.brown.edu/~pff/SNN/

A fundamental problem in the analysis of large datasets consists of finding one or more data items that are as similar as possible to an input query. This situation occurs, for example, when a user wants to identify a product captured in a photo. The corresponding computational problem, called Nearest Neighbor (NN) Search, has attracted a large body of research, with several algorithms having significant impact. Yet the state of the art in NN suffers from important theoretical and practical limitations. In particular, it does not provide a natural way to exploit data *structure* that is present in many applications. For example, although the identity of a depicted object does not change when one varies the lighting or the position of the object, the current NN algorithms will treat the resulting images as completely different from each other and thus will mis-identify the object. To overcome this difficulty, in this project the PIs will develop new efficient algorithms that incorporate problem structure into NN search. The PIs expect that such methods will produce substantially better results for many massive data analysis tasks.To ensure that the work is grounded in an important application, the PIs will focus on computer vision, an area where Internet-scale datasets are having a substantial impact. NN search is vital for computer vision, and in fact many senior computer vision researchers view improved NN techniques as their top algorithmic priority. Image and video have significant structure, often spatial in nature, which algorithmic techniques such as graph cuts have been able to exploit with considerable success. The proposed work will formulate new variants of NN search that make use of additional structure, and will design efficient algorithms to solve these problems over large datasets. In particular, the PIs will investigate three structured NN problem formulations. Simultaneous nearest-neighbor queries involves multiple queries where the answers should be compatible with each other. Nearest-neighbor under transformations considers distances that are invariant to a variety of image transformations. Nearest-neighbors for subspaces involves searching a set of linear or affine subspaces for the one that comes closest to a query point. Broader impacts of the project include graduate training in both algorithms and image processing.For further information see the project web site at: http://cs.brown.edu/~pff/SNN/