Exploring the Meaningfulness of Nearest Neighbor Search in High-Dimensional Space

• URL: http://arxiv.org/abs/2410.05752v1
• Date: Tue, 8 Oct 2024 07:28:17 GMT
• Title: Exploring the Meaningfulness of Nearest Neighbor Search in High-Dimensional Space
• Authors: Zhonghan Chen, Ruiyuan Zhang, Xi Zhao, Xiaojun Cheng, Xiaofang Zhou,
• Abstract summary: "Dense high dimensional vectors" are becoming increasingly vital in fields such as computer vision, machine learning, and large language models (LLMs) Despite the nearest neighbor search (NNS) over these dense high dimensional vectors have been widely used for retrieval augmented generation (RAG) and many other applications. Our study shows the effectiveness of the embedding-based data representation method and can offer opportunity for further optimization of dense vector-related applications.
• Score: 11.006299554632461
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Dense high dimensional vectors are becoming increasingly vital in fields such as computer vision, machine learning, and large language models (LLMs), serving as standard representations for multimodal data. Now the dimensionality of these vector can exceed several thousands easily. Despite the nearest neighbor search (NNS) over these dense high dimensional vectors have been widely used for retrieval augmented generation (RAG) and many other applications, the effectiveness of NNS in such a high-dimensional space remains uncertain, given the possible challenge caused by the "curse of dimensionality." To address above question, in this paper, we conduct extensive NNS studies with different distance functions, such as $L_1$ distance, $L_2$ distance and angular-distance, across diverse embedding datasets, of varied types, dimensionality and modality. Our aim is to investigate factors influencing the meaningfulness of NNS. Our experiments reveal that high-dimensional text embeddings exhibit increased resilience as dimensionality rises to higher levels when compared to random vectors. This resilience suggests that text embeddings are less affected to the "curse of dimensionality," resulting in more meaningful NNS outcomes for practical use. Additionally, the choice of distance function has minimal impact on the relevance of NNS. Our study shows the effectiveness of the embedding-based data representation method and can offer opportunity for further optimization of dense vector-related applications.

Related papers

• GleanVec: Accelerating vector search with minimalist nonlinear dimensionality reduction [1.1599570446840546]
  Cross-modal retrieval (e.g., where a text query is used to find images) is gaining momentum rapidly. It is challenging to achieve high accuracy as the queries often have different statistical distributions than the database vectors. We present new linear and nonlinear methods for dimensionality reduction to accelerate high-dimensional vector search.
  arXiv  Detail & Related papers  (2024-10-14T21:14:27Z)
• Improved Generalization of Weight Space Networks via Augmentations [56.571475005291035]
  Learning in deep weight spaces (DWS) is an emerging research direction, with applications to 2D and 3D neural fields (INRs, NeRFs) We empirically analyze the reasons for this overfitting and find that a key reason is the lack of diversity in DWS datasets. To address this, we explore strategies for data augmentation in weight spaces and propose a MixUp method adapted for weight spaces.
  arXiv  Detail & Related papers  (2024-02-06T15:34:44Z)
• Interpreting the Curse of Dimensionality from Distance Concentration and Manifold Effect [0.6906005491572401]
  We first summarize five challenges associated with manipulating high-dimensional data. We then delve into two major causes of the curse of dimensionality, distance concentration and manifold effect. By interpreting the causes of the curse of dimensionality, we can better understand the limitations of current models and algorithms.
  arXiv  Detail & Related papers  (2023-12-31T08:22:51Z)
• From Alexnet to Transformers: Measuring the Non-linearity of Deep Neural Networks with Affine Optimal Transport [32.39176908225668]
  We introduce the concept of the non-linearity signature of DNN, the first theoretically sound solution for measuring the non-linearity of deep neural networks. We provide extensive experimental results that highlight the practical usefulness of the proposed non-linearity signature.
  arXiv  Detail & Related papers  (2023-10-17T17:50:22Z)
• Learning in latent spaces improves the predictive accuracy of deep neural operators [0.0]
  L-DeepONet is an extension of standard DeepONet, which leverages latent representations of high-dimensional PDE input and output functions identified with suitable autoencoders. We show that L-DeepONet outperforms the standard approach in terms of both accuracy and computational efficiency across diverse time-dependent PDEs.
  arXiv  Detail & Related papers  (2023-04-15T17:13:09Z)
• Unifying Voxel-based Representation with Transformer for 3D Object Detection [143.91910747605107]
  We present a unified framework for multi-modality 3D object detection, named UVTR. The proposed method aims to unify multi-modality representations in the voxel space for accurate and robust single- or cross-modality 3D detection. UVTR achieves leading performance in the nuScenes test set with 69.7%, 55.1%, and 71.1% NDS for LiDAR, camera, and multi-modality inputs, respectively.
  arXiv  Detail & Related papers  (2022-06-01T17:02:40Z)
• UnProjection: Leveraging Inverse-Projections for Visual Analytics of High-Dimensional Data [63.74032987144699]
  We present NNInv, a deep learning technique with the ability to approximate the inverse of any projection or mapping. NNInv learns to reconstruct high-dimensional data from any arbitrary point on a 2D projection space, giving users the ability to interact with the learned high-dimensional representation in a visual analytics system.
  arXiv  Detail & Related papers  (2021-11-02T17:11:57Z)
• Pure Exploration in Kernel and Neural Bandits [90.23165420559664]
  We study pure exploration in bandits, where the dimension of the feature representation can be much larger than the number of arms. To overcome the curse of dimensionality, we propose to adaptively embed the feature representation of each arm into a lower-dimensional space.
  arXiv  Detail & Related papers  (2021-06-22T19:51:59Z)
• Deep Representational Similarity Learning for analyzing neural signatures in task-based fMRI dataset [81.02949933048332]
  This paper develops Deep Representational Similarity Learning (DRSL), a deep extension of Representational Similarity Analysis (RSA) DRSL is appropriate for analyzing similarities between various cognitive tasks in fMRI datasets with a large number of subjects.
  arXiv  Detail & Related papers  (2020-09-28T18:30:14Z)
• SOLAR: Sparse Orthogonal Learned and Random Embeddings [45.920844071257754]
  We argue that high-dimensional and ultra-sparse embedding is a significantly superior alternative to dense low-dimensional embedding for both query efficiency and accuracy. We train 500K dimensional SOLAR embeddings for the tasks of searching through 1.6M books and multi-label classification on the three largest public datasets. We achieve superior precision and recall compared to the respective state-of-the-art baselines for each of the tasks with up to 10 times faster speed.
  arXiv  Detail & Related papers  (2020-08-30T17:35:35Z)
• NCVis: Noise Contrastive Approach for Scalable Visualization [79.44177623781043]
  NCVis is a high-performance dimensionality reduction method built on a sound statistical basis of noise contrastive estimation. We show that NCVis outperforms state-of-the-art techniques in terms of speed while preserving the representation quality of other methods.
  arXiv  Detail & Related papers  (2020-01-30T15:43:50Z)

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.