Nearest Neighbor Search Under Uncertainty

• URL: http://arxiv.org/abs/2103.05057v1
• Date: Mon, 8 Mar 2021 20:20:01 GMT
• Title: Nearest Neighbor Search Under Uncertainty
• Authors: Blake Mason, Ardhendu Tripathy, Robert Nowak
• Abstract summary: Nearest Neighbor Search (NNS) is a central task in knowledge representation, learning, and reasoning. This paper studies NNS under Uncertainty (NNSU)
• Score: 19.225091554227948
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Nearest Neighbor Search (NNS) is a central task in knowledge representation, learning, and reasoning. There is vast literature on efficient algorithms for constructing data structures and performing exact and approximate NNS. This paper studies NNS under Uncertainty (NNSU). Specifically, consider the setting in which an NNS algorithm has access only to a stochastic distance oracle that provides a noisy, unbiased estimate of the distance between any pair of points, rather than the exact distance. This models many situations of practical importance, including NNS based on human similarity judgements, physical measurements, or fast, randomized approximations to exact distances. A naive approach to NNSU could employ any standard NNS algorithm and repeatedly query and average results from the stochastic oracle (to reduce noise) whenever it needs a pairwise distance. The problem is that a sufficient number of repeated queries is unknown in advance; e.g., a point maybe distant from all but one other point (crude distance estimates suffice) or it may be close to a large number of other points (accurate estimates are necessary). This paper shows how ideas from cover trees and multi-armed bandits can be leveraged to develop an NNSU algorithm that has optimal dependence on the dataset size and the (unknown)geometry of the dataset.

Related papers

• Inferring Neural Signed Distance Functions by Overfitting on Single Noisy Point Clouds through Finetuning Data-Driven based Priors [53.6277160912059]
  We propose a method to promote pros of data-driven based and overfitting-based methods for better generalization, faster inference, and higher accuracy in learning neural SDFs. We introduce a novel statistical reasoning algorithm in local regions which is able to finetune data-driven based priors without signed distance supervision, clean point cloud, or point normals.
  arXiv  Detail & Related papers  (2024-10-25T16:48:44Z)
• Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
  We introduce a new adaptive $k$-nearest neighbours ($kK$-NN) algorithm that explores the local curvature at a sample to adaptively defining the neighborhood size. Results on many real-world datasets indicate that the new $kK$-NN algorithm yields superior balanced accuracy compared to the established $k$-NN method.
  arXiv  Detail & Related papers  (2024-09-08T13:08:45Z)
• k-NNN: Nearest Neighbors of Neighbors for Anomaly Detection [20.204147875108976]
  Anomaly detection aims at identifying images that deviate significantly from the norm. We propose a new operator that takes into account the varying structure & importance of the features in the embedding space. We show that by simply replacing the nearest neighbor component in existing algorithms by our k-NNN operator, while leaving the rest of the algorithms untouched, each algorithms own results are improved.
  arXiv  Detail & Related papers  (2023-05-28T11:39:51Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Robust Multi-Object Tracking by Marginal Inference [92.48078680697311]
  Multi-object tracking in videos requires to solve a fundamental problem of one-to-one assignment between objects in adjacent frames. We present an efficient approach to compute a marginal probability for each pair of objects in real time. It achieves competitive results on MOT17 and MOT20 benchmarks.
  arXiv  Detail & Related papers  (2022-08-07T14:04:45Z)
• DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search [8.25574589820305]
  We present an algorithm called Density Estimation from Approximate Nearest Neighbors (DEANN) We apply ANN algorithms as a black box subroutine to compute an unbiased Density Estimation (KDE) We show that our implementation outperforms state of the art implementations in all high dimensional datasets we considered.
  arXiv  Detail & Related papers  (2021-07-06T17:11:28Z)
• Adaptive Nearest Neighbor Machine Translation [60.97183408140499]
  kNN-MT combines pre-trained neural machine translation with token-level k-nearest-neighbor retrieval. Traditional kNN algorithm simply retrieves a same number of nearest neighbors for each target token. We propose Adaptive kNN-MT to dynamically determine the number of k for each target token.
  arXiv  Detail & Related papers  (2021-05-27T09:27:42Z)
• Leveraging Reinforcement Learning for evaluating Robustness of KNN Search Algorithms [0.0]
  The problem of finding K-nearest neighbors in the given dataset for a given query point has been worked upon since several years. In this paper, we survey some novel K-Nearest Neighbor Search approaches that tackles the problem of Search from the perspectives of computations. In order to evaluate the robustness of a KNNS approach against adversarial points, we propose a generic Reinforcement Learning based framework for the same.
  arXiv  Detail & Related papers  (2021-02-10T16:10:58Z)
• Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of Them All? [17.514226416388475]
  We study the $r$-NN problem in the light of individual fairness and providing equal opportunities. All points that are within distance $r$ from the query should have the same probability to be returned. We propose several efficient data structures for the exact and approximate variants of the fair NN problem.
  arXiv  Detail & Related papers  (2021-01-26T16:13:07Z)
• Query Complexity of k-NN based Mode Estimation [4.821253146561989]
  We study the problem of identifying the point with the minimum k-th nearest neighbor distance for a given dataset of n points. We design a sequential learning algorithm, based on the idea of confidence intervals, which adaptively decides which queries to send to the oracle and is able to correctly solve the problem with high probability.
  arXiv  Detail & Related papers  (2020-10-26T11:32:08Z)
• Non-Local Spatial Propagation Network for Depth Completion [82.60915972250706]
  We propose a robust and efficient end-to-end non-local spatial propagation network for depth completion. The proposed network takes RGB and sparse depth images as inputs and estimates non-local neighbors and their affinities of each pixel. We show that the proposed algorithm is superior to conventional algorithms in terms of depth completion accuracy and robustness to the mixed-depth problem.
  arXiv  Detail & Related papers  (2020-07-20T12:26:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.