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 将开发新的高效算法，将问题结构纳入神经网络搜索中。 PI 期望此类方法将为许多海量数据分析任务带来更好的结果。为了确保工作以重要应用为基础，PI 将重点关注计算机视觉，这是互联网规模数据集产生重大影响的领域。神经网络搜索对于计算机视觉至关重要，事实上，许多高级计算机视觉研究人员将改进的神经网络技术视为他们算法的首要任务。图像和视频具有重要的结构，通常本质上是空间结构，诸如图割之类的算法技术已经能够利用这种结构并取得相当大的成功。所提出的工作将制定利用附加结构的神经网络搜索的新变体，并将设计有效的算法来解决大型数据集上的这些问题。特别是，PI 将研究三种结构化的神经网络问题表述。同时的最近邻查询涉及多个查询，其中答案应该彼此兼容。变换下的最近邻考虑对各种图像变换不变的距离。子空间的最近邻涉及在一组线性或仿射子空间中搜索最接近查询点的子空间。该项目更广泛的影响包括算法和图像处理方面的研究生培训。有关更多信息，请参阅该项目网站：http://cs.brown.edu/~pff/SNN/

项目成果

期刊论文数量（4）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Practical Data-Dependent Metric Compression with Provable Guarantees

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

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

Set Cover in Sub-linear Time

以亚线性时间设定封面

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

Approximate Nearest Neighbors in Limited Space

有限空间中的近似最近邻

DOI：
10.5220/0008124204220428
发表时间：
2018-06-30
期刊：
Journal of Computational and Applied Mathematics
影响因子：
2.4
作者：
P. Indyk;Tal Wagner
通讯作者：
Tal Wagner

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

关于经验风险最小化的细粒度复杂性：核方法和神经网络

DOI：
10.1128/spectrum.01557-22
发表时间：
2022-12-21
期刊：
ArXiv
影响因子：
3.7
作者：
Xu, Siyi;Huang, Jinlan;Xun, Zhen;Li, Shiqi;Fu, Ya;Lin, Ni;Wu, Wennan;Chen, Tianbin;Liu, Can;Ou, Qishui
通讯作者：
Ou, Qishui