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

BIGDATA：F：DKA：协作研究：高维结构化最近邻搜索

• 批准号: 1447413
• 负责人: Pedro Felzenszwalb
• 金额: $ 25万
• 依托单位: Brown University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-15 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1447413&HistoricalAwards=false
• 关键词: BIGDATA; DKA; Collaborative; Research; Structured

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/

大型数据集分析中的一个基本问题是找到与输入查询一样相似的一个或多个数据项。例如，当用户想识别照片中捕获的产品时，发生这种情况。相应的计算问题称为最近的邻居（NN）搜索，吸引了大量研究，几种算法具有重大影响。然而，新南非的最新技术受到了重要的理论和实际局限性。特别是，它没有提供自然的方法来利用许多应用程序中存在的数据 *结构 *。例如，尽管所描绘的对象的身份在变化的照明或对象位置变化时不会改变，但当前的NN算法将将结果映像视为完全不同的彼此不同，因此会误导对象。为了克服这一困难，在这个项目中，PI将开发新的有效算法，将问题结构纳入NN搜索。 PI预计，此类方法将为许多大规模的数据分析任务产生更好的结果。为了确保在重要的应用程序中基础工作，PI将专注于计算机视觉，该领域是Internet规模数据集对此产生重大影响的领域。 NN搜索对于计算机视觉至关重要，实际上，许多高级计算机视觉研究人员将改进的NN技术视为其最佳算法优先级。图像和视频具有重要的结构，通常本质上是空间的，算法技术（例如剪图）能够以相当的成功来利用。拟议的工作将制定NN搜索的新变体，以利用其他结构，并将设计有效的算法以在大型数据集上解决这些问题。特别是，PI将研究三个结构化的NN问题制定。同时最近的邻居查询涉及多个查询，其中答案应彼此兼容。转换下最近的邻居考虑了各种图像变换不变的距离。子空间最近的近脑涉及搜索最接近查询点的线性或仿射子空间。 该项目的更广泛影响包括算法和图像处理的研究生培训。有关更多信息，请参见项目网站：http：//cs.brown.edu/~pff/snn/