权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

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

基本信息

批准号：
1447476
负责人：
Piotr Indyk
金额：
$ 50万
依托单位：
Massachusetts Institute of Technology
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2015
资助国家：
美国
起止时间：
2015-09-15 至 2019-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1447476&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)搜索，已经吸引了大量的研究，有几种算法具有重要的影响。然而，神经网络的最新技术水平受到重要的理论和实践限制。特别是，它没有提供一种自然的方式来利用许多应用程序中存在的数据*结构*。例如，尽管当改变对象的光照或位置时，所描绘的对象的身份不会改变，但是当前的神经网络算法会将所得到的图像视为彼此完全不同，从而会误识别该对象。为了克服这一困难，在这个项目中，PI将开发新的高效算法，将问题结构合并到NN搜索中。PIS预计，这种方法将为许多海量数据分析任务带来显著更好的结果。为了确保工作立足于重要的应用，PIS将专注于计算机视觉，这是一个互联网规模的数据集正在产生重大影响的领域。神经网络搜索对计算机视觉至关重要，事实上，许多资深计算机视觉研究人员将改进的神经网络技术视为他们的首要算法。图像和视频具有重要的结构，在本质上通常是空间的，而诸如图形切割之类的算法技术已经能够相当成功地利用这种结构。这项工作将形成利用附加结构的神经网络搜索的新变体，并将设计有效的算法来解决大数据集上的这些问题。特别是，PI将调查三个结构化的NN问题公式。同时最近邻查询涉及多个查询，其中答案应该彼此兼容。变换下的最近邻考虑对各种图像变换不变的距离。子空间的最近邻居涉及到在一组线性或仿射子空间中搜索最接近查询点的子空间。该项目的更广泛影响包括算法和图像处理方面的研究生培训。有关更多信息，请参阅该项目的网站：http://cs.brown.edu/~pff/SNN/

项目成果

期刊论文数量（4）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Practical Data-Dependent Metric Compression with Provable Guarantees

具有可证明保证的实用数据相关度量压缩

DOI：
发表时间：
2017
期刊：
Annual Conference on Neural Information Processing Systems
影响因子：
0
作者：
Indyk, Piotr;Razenshteyn, Ilya P.;Wagner, Tal
通讯作者：
Wagner, Tal

On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks

DOI：
发表时间：
2017-04
期刊：
ArXiv
影响因子：
0
作者：
A. Backurs;P. Indyk;Ludwig Schmidt
通讯作者：
A. Backurs;P. Indyk;Ludwig Schmidt

Set Cover in Sub-linear Time

以亚线性时间设定封面

DOI：
发表时间：
2018
期刊：
Annual ACM-SIAM Symposium on Discrete Algorithms
影响因子：
0
作者：
Indyk, Piotr;Mahabadi, Sepideh;Rubinfeld, Ronitt;Vakilian, Ali;Yodpinyanee, Anak
通讯作者：
Yodpinyanee, Anak