Tensor-Train Point Cloud Compression and Efficient Approximate Nearest-Neighbor Search

• URL: http://arxiv.org/abs/2410.04462v1
• Date: Sun, 6 Oct 2024 12:25:41 GMT
• Title: Tensor-Train Point Cloud Compression and Efficient Approximate Nearest-Neighbor Search
• Authors: Georgii Novikov, Alexander Gneushev, Alexey Kadeishvili, Ivan Oseledets,
• Abstract summary: This paper introduces a novel method using tensor-train (TT) low-rank tensor decomposition to efficiently represent point clouds. We propose a probabilistic interpretation and utilize density estimation losses like Sliced Wasserstein to train TT decompositions. We reveal an inherent hierarchical structure within TT point clouds, facilitating efficient approximate nearest-neighbor searches.
• Score: 45.79272321017838
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Nearest-neighbor search in large vector databases is crucial for various machine learning applications. This paper introduces a novel method using tensor-train (TT) low-rank tensor decomposition to efficiently represent point clouds and enable fast approximate nearest-neighbor searches. We propose a probabilistic interpretation and utilize density estimation losses like Sliced Wasserstein to train TT decompositions, resulting in robust point cloud compression. We reveal an inherent hierarchical structure within TT point clouds, facilitating efficient approximate nearest-neighbor searches. In our paper, we provide detailed insights into the methodology and conduct comprehensive comparisons with existing methods. We demonstrate its effectiveness in various scenarios, including out-of-distribution (OOD) detection problems and approximate nearest-neighbor (ANN) search tasks.

Related papers

• Experimental comparison of graph-based approximate nearest neighbor search algorithms on edge devices [1.5495593104596401]
  We present an experimental comparison of various graph-based approximate nearest neighbor (ANN) search algorithms deployed on edge devices for real-time nearest neighbor search applications.
  arXiv  Detail & Related papers  (2024-11-21T10:41:24Z)
• Early Exit Strategies for Approximate k-NN Search in Dense Retrieval [10.48678957367324]
  We build upon state-of-the-art for early exit A-kNN and propose an unsupervised method based on the notion of patience. We show that our techniques improve the A-kNN efficiency with up to 5x speedups while achieving negligible effectiveness losses.
  arXiv  Detail & Related papers  (2024-08-09T10:17:07Z)
• Multimodal Learned Sparse Retrieval with Probabilistic Expansion Control [66.78146440275093]
  Learned retrieval (LSR) is a family of neural methods that encode queries and documents into sparse lexical vectors. We explore the application of LSR to the multi-modal domain, with a focus on text-image retrieval. Current approaches like LexLIP and STAIR require complex multi-step training on massive datasets. Our proposed approach efficiently transforms dense vectors from a frozen dense model into sparse lexical vectors.
  arXiv  Detail & Related papers  (2024-02-27T14:21:56Z)
• Point Cloud Classification via Deep Set Linearized Optimal Transport [51.99765487172328]
  We introduce Deep Set Linearized Optimal Transport, an algorithm designed for the efficient simultaneous embedding of point clouds into an $L2-$space. This embedding preserves specific low-dimensional structures within the Wasserstein space while constructing a classifier to distinguish between various classes of point clouds. We showcase the advantages of our algorithm over the standard deep set approach through experiments on a flow dataset with a limited number of labeled point clouds.
  arXiv  Detail & Related papers  (2024-01-02T23:26:33Z)
• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB) Existing methods in the R-CPE-MAB can be seen as a special case of the so-called transductive linear bandits. We propose an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity matches the lower bound.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search [20.928821121591493]
  We propose FINGER, a fast inference method to achieve efficient graph search. FINGER approximates the distance function by estimating angles between neighboring residual vectors with low-rank bases and distribution matching. Empirically, accelerating a popular graph-based method named HNSW by FINGER is shown to outperform existing graph-based methods by 20%-60% across different benchmark datasets.
  arXiv  Detail & Related papers  (2022-06-22T22:30:46Z)
• Learning Semantic Segmentation of Large-Scale Point Clouds with Random Sampling [52.464516118826765]
  We introduce RandLA-Net, an efficient and lightweight neural architecture to infer per-point semantics for large-scale point clouds. The key to our approach is to use random point sampling instead of more complex point selection approaches. Our RandLA-Net can process 1 million points in a single pass up to 200x faster than existing approaches.
  arXiv  Detail & Related papers  (2021-07-06T05:08:34Z)
• How to Design Robust Algorithms using Noisy Comparison Oracle [12.353002222958605]
  Metric based comparison operations are fundamental to studying various clustering techniques. In this paper, we study various problems that include finding maximum, nearest/farthest neighbor search. We give robust algorithms for k-center clustering and agglomerative hierarchical clustering.
  arXiv  Detail & Related papers  (2021-05-12T16:58:09Z)
• 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)

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.