LogoLogo
Continuum WebsiteContinuum ApplicationsContinuum KnowledgeAxolotl Platform
Continuum Knowledge
Continuum Knowledge
  • Continuum
  • Data
    • Datasets
      • Pre Training Data
      • Types of Fine Tuning
      • Self Instruct Paper
      • Self-Alignment with Instruction Backtranslation
      • Systematic Evaluation of Instruction-Tuned Large Language Models on Open Datasets
      • Instruction Tuning
      • Instruction Fine Tuning - Alpagasus
      • Less is More For Alignment
      • Enhanced Supervised Fine Tuning
      • Visualising Data using t-SNE
      • UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction
      • Training and Evaluation Datasets
      • What is perplexity?
  • MODELS
    • Foundation Models
      • The leaderboard
      • Foundation Models
      • LLama 2 - Analysis
      • Analysis of Llama 3
      • Llama 3.1 series
      • Google Gemini 1.5
      • Platypus: Quick, Cheap, and Powerful Refinement of LLMs
      • Mixtral of Experts
      • Mixture-of-Agents (MoA)
      • Phi 1.5
        • Refining the Art of AI Training: A Deep Dive into Phi 1.5's Innovative Approach
      • Phi 2.0
      • Phi-3 Technical Report
  • Training
    • The Fine Tuning Process
      • Why fine tune?
        • Does Fine-Tuning LLMs on New Knowledge Encourage Hallucinations?
        • Explanations in Fine Tuning
      • Tokenization
        • Tokenization Is More Than Compression
        • Tokenization - SentencePiece
        • Tokenization explore
        • Tokenizer Choice For LLM Training: Negligible or Crucial?
        • Getting the most out of your tokenizer for pre-training and domain adaptation
        • TokenMonster
      • Parameter Efficient Fine Tuning
        • P-Tuning
          • The Power of Scale for Parameter-Efficient Prompt Tuning
        • Prefix-Tuning: Optimizing Continuous Prompts for Generation
        • Harnessing the Power of PEFT: A Smarter Approach to Fine-tuning Pre-trained Models
        • What is Low-Rank Adaptation (LoRA) - explained by the inventor
        • Low Rank Adaptation (Lora)
        • Practical Tips for Fine-tuning LMs Using LoRA (Low-Rank Adaptation)
        • QLORA: Efficient Finetuning of Quantized LLMs
        • Bits and Bytes
        • The Magic behind Qlora
        • Practical Guide to LoRA: Tips and Tricks for Effective Model Adaptation
        • The quantization constant
        • QLORA: Efficient Finetuning of Quantized Language Models
        • QLORA and Fine-Tuning of Quantized Language Models (LMs)
        • ReLoRA: High-Rank Training Through Low-Rank Updates
        • SLoRA: Federated Parameter Efficient Fine-Tuning of Language Models
        • GaLora: Memory-Efficient LLM Training by Gradient Low-Rank Projection
      • Hyperparameters
        • Batch Size
        • Padding Tokens
        • Mixed precision training
        • FP8 Formats for Deep Learning
        • Floating Point Numbers
        • Batch Size and Model loss
        • Batch Normalisation
        • Rethinking Learning Rate Tuning in the Era of Language Models
        • Sample Packing
        • Gradient accumulation
        • A process for choosing the learning rate
        • Learning Rate Scheduler
        • Checkpoints
        • A Survey on Efficient Training of Transformers
        • Sequence Length Warmup
        • Understanding Training vs. Evaluation Data Splits
        • Cross-entropy loss
        • Weight Decay
        • Optimiser
        • Caching
      • Training Processes
        • Extending the context window
        • PyTorch Fully Sharded Data Parallel (FSDP)
        • Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation
        • YaRN: Efficient Context Window Extension of Large Language Models
        • Sliding Window Attention
        • LongRoPE
        • Reinforcement Learning
        • An introduction to reinforcement learning
        • Reinforcement Learning from Human Feedback (RLHF)
        • Direct Preference Optimization: Your Language Model is Secretly a Reward Model
  • INFERENCE
    • Why is inference important?
      • Grouped Query Attention
      • Key Value Cache
      • Flash Attention
      • Flash Attention 2
      • StreamingLLM
      • Paged Attention and vLLM
      • TensorRT-LLM
      • Torchscript
      • NVIDIA L40S GPU
      • Triton Inference Server - Introduction
      • Triton Inference Server
      • FiDO: Fusion-in-Decoder optimised for stronger performance and faster inference
      • Is PUE a useful measure of data centre performance?
      • SLORA
  • KNOWLEDGE
    • Vector Databases
      • A Comprehensive Survey on Vector Databases
      • Vector database management systems: Fundamental concepts, use-cases, and current challenges
      • Using the Output Embedding to Improve Language Models
      • Decoding Sentence-BERT
      • ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT
      • SimCSE: Simple Contrastive Learning of Sentence Embeddings
      • Questions Are All You Need to Train a Dense Passage Retriever
      • Improving Text Embeddings with Large Language Models
      • Massive Text Embedding Benchmark
      • RocketQAv2: A Joint Training Method for Dense Passage Retrieval and Passage Re-ranking
      • LLM2Vec: Large Language Models Are Secretly Powerful Text Encoders
      • Embedding and Fine-Tuning in Neural Language Models
      • Embedding Model Construction
      • Demystifying Embedding Spaces using Large Language Models
      • Fine-Tuning Llama for Multi-Stage Text Retrieval
      • Large Language Model Based Text Augmentation Enhanced Personality Detection Model
      • One Embedder, Any Task: Instruction-Finetuned Text Embeddings
      • Vector Databases are not the only solution
      • Knowledge Graphs
        • Harnessing Knowledge Graphs to Elevate AI: A Technical Exploration
        • Unifying Large Language Models and Knowledge Graphs: A Roadmap
      • Approximate Nearest Neighbor (ANN)
      • High Dimensional Data
      • Principal Component Analysis (PCA)
      • Vector Similarity Search - HNSW
      • FAISS (Facebook AI Similarity Search)
      • Unsupervised Dense Retrievers
    • Retrieval Augmented Generation
      • Retrieval-Augmented Generation for Large Language Models: A Survey
      • Fine-Tuning or Retrieval?
      • Revolutionising Information Retrieval: The Power of RAG in Language Models
      • A Survey on Retrieval-Augmented Text Generation
      • REALM: Retrieval-Augmented Language Model Pre-Training
      • Retrieve Anything To Augment Large Language Models
      • Generate Rather Than Retrieve: Large Language Models Are Strong Context Generators
      • Active Retrieval Augmented Generation
      • DSPy: LM Assertions: Enhancing Language Model Pipelines with Computational Constraints
      • DSPy: Compiling Declarative Language Model Calls
      • DSPy: In-Context Learning for Extreme Multi-Label Classification
      • Optimizing Instructions and Demonstrations for Multi-Stage Language Model Programs
      • HYDE: Revolutionising Search with Hypothetical Document Embeddings
      • Enhancing Recommender Systems with Large Language Model Reasoning Graphs
      • Retrieval Augmented Generation (RAG) versus fine tuning
      • RAFT: Adapting Language Model to Domain Specific RAG
      • Summarisation Methods and RAG
      • Lessons Learned on LLM RAG Solutions
      • Stanford: Retrieval Augmented Language Models
      • Overview of RAG Approaches with Vector Databases
      • Mastering Chunking in Retrieval-Augmented Generation (RAG) Systems
    • Semantic Routing
    • Resource Description Framework (RDF)
  • AGENTS
    • What is agency?
      • Rephrase and Respond: Let Large Language Models Ask Better Questions for Themselves
      • Types of Agents
      • The risk of AI agency
      • Understanding Personality in Large Language Models: A New Frontier in AI Psychology
      • AI Agents - Reasoning, Planning, and Tool Calling
      • Personality and Brand
      • Agent Interaction via APIs
      • Bridging Minds and Machines: The Legacy of Newell, Shaw, and Simon
      • A Survey on Language Model based Autonomous Agents
      • Large Language Models as Agents
      • AI Reasoning: A Deep Dive into Chain-of-Thought Prompting
      • Enhancing AI Reasoning with Self-Taught Reasoner (STaR)
      • Exploring the Frontier of AI: The "Tree of Thoughts" Framework
      • Toolformer: Revolutionising Language Models with API Integration - An Analysis
      • TaskMatrix.AI: Bridging Foundational AI Models with Specialised Systems for Enhanced Task Completion
      • Unleashing the Power of LLMs in API Integration: The Rise of Gorilla
      • Andrew Ng's presentation on AI agents
      • Making AI accessible with Andrej Karpathy and Stephanie Zhan
  • Regulation and Ethics
    • Regulation and Ethics
      • Privacy
      • Detecting AI Generated content
      • Navigating the IP Maze in AI: The Convergence of Blockchain, Web 3.0, and LLMs
      • Adverse Reactions to generative AI
      • Navigating the Ethical Minefield: The Challenge of Security in Large Language Models
      • Navigating the Uncharted Waters: The Risks of Autonomous AI in Military Decision-Making
  • DISRUPTION
    • Data Architecture
      • What is a data pipeline?
      • What is Reverse ETL?
      • Unstructured Data and Generatve AI
      • Resource Description Framework (RDF)
      • Integrating generative AI with the Semantic Web
    • Search
      • BM25 - Search Engine Ranking Function
      • BERT as a reranking engine
      • BERT and Google
      • Generative Engine Optimisation (GEO)
      • Billion-scale similarity search with GPUs
      • FOLLOWIR: Evaluating and Teaching Information Retrieval Models to Follow Instructions
      • Neural Collaborative Filtering
      • Federated Neural Collaborative Filtering
      • Latent Space versus Embedding Space
      • Improving Text Embeddings with Large Language Models
    • Recommendation Engines
      • On Interpretation and Measurement of Soft Attributes for Recommendation
      • A Survey on Large Language Models for Recommendation
      • Model driven recommendation systems
      • Recommender AI Agent: Integrating Large Language Models for Interactive Recommendations
      • Foundation Models for Recommender Systems
      • Exploring the Impact of Large Language Models on Recommender Systems: An Extensive Review
      • AI driven recommendations - harming autonomy?
    • Logging
      • A Taxonomy of Anomalies in Log Data
      • Deeplog
      • LogBERT: Log Anomaly Detection via BERT
      • Experience Report: Deep Learning-based System Log Analysis for Anomaly Detection
      • Log-based Anomaly Detection with Deep Learning: How Far Are We?
      • Deep Learning for Anomaly Detection in Log Data: A Survey
      • LogGPT
      • Adaptive Semantic Gate Networks (ASGNet) for log-based anomaly diagnosis
  • Infrastructure
    • The modern data centre
      • Enhancing Data Centre Efficiency: Strategies to Improve PUE
      • TCO of NVIDIA GPUs and falling barriers to entry
      • Maximising GPU Utilisation with Kubernetes and NVIDIA GPU Operator
      • Data Centres
      • Liquid Cooling
    • Servers and Chips
      • The NVIDIA H100 GPU
      • NVIDIA H100 NVL
      • Lambda Hyperplane 8-H100
      • NVIDIA DGX Servers
      • NVIDIA DGX-2
      • NVIDIA DGX H-100 System
      • NVLink Switch
      • Tensor Cores
      • NVIDIA Grace Hopper Superchip
      • NVIDIA Grace CPU Superchip
      • NVIDIA GB200 NVL72
      • Hopper versus Blackwell
      • HGX: High-Performance GPU Platforms
      • ARM Chips
      • ARM versus x86
      • RISC versus CISC
      • Introduction to RISC-V
    • Networking and Connectivity
      • Infiniband versus Ethernet
      • NVIDIA Quantum InfiniBand
      • PCIe (Peripheral Component Interconnect Express)
      • NVIDIA ConnectX InfiniBand adapters
      • NVMe (Non-Volatile Memory Express)
      • NVMe over Fabrics (NVMe-oF)
      • NVIDIA Spectrum-X
      • NVIDIA GPUDirect
      • Evaluating Modern GPU Interconnect
      • Scalable Hierarchical Aggregation and Reduction Protocol (SHARP)
      • Next-generation networking in AI environments
      • NVIDIA Collective Communications Library (NCCL)
    • Data and Memory
      • NVIDIA BlueField Data Processing Units (DPUs)
      • Remote Direct Memory Access (RDMA)
      • High Bandwidth Memory (HBM3)
      • Flash Memory
      • Model Requirements
      • Calculating GPU memory for serving LLMs
      • Transformer training costs
      • GPU Performance Optimisation
    • Libraries and Complements
      • NVIDIA Base Command
      • NVIDIA AI Enterprise
      • CUDA - NVIDIA GTC 2024 presentation
      • RAPIDs
      • RAFT
    • Vast Data Platform
      • Vast Datastore
      • Vast Database
      • Vast Data Engine
      • DASE (Disaggregated and Shared Everything)
      • Dremio and VAST Data
    • Storage
      • WEKA: A High-Performance Storage Solution for AI Workloads
      • Introduction to NVIDIA GPUDirect Storage (GDS)
        • GDS cuFile API
      • NVIDIA Magnum IO GPUDirect Storage (GDS)
      • Vectors in Memory
Powered by GitBook
LogoLogo

Continuum - Accelerated Artificial Intelligence

  • Continuum Website
  • Axolotl Platform

Copyright Continuum Labs - 2023

On this page
  • Understanding ANN Search
  • Trade-off Between Query Time and Space
  • Nearest Neighbour
  • Approximate Nearest Neighbour
  • Locality-Sensitive Hashing (LSH)
  • LSH for ANN
  • Categories of ANN Algorithms
  • Vector Databases vs. ANN Libraries
  • Conclusion

Was this helpful?

  1. KNOWLEDGE
  2. Vector Databases

Approximate Nearest Neighbor (ANN)

PreviousUnifying Large Language Models and Knowledge Graphs: A RoadmapNextHigh Dimensional Data

Last updated 11 months ago

Was this helpful?

Approximate Nearest Neighbor (ANN) is a search algorithms used for extracting high-dimensional unstructured data such as images, text, and audio from vector databases.

These algorithms, by focusing on approximation rather than exact matches, strike a balance between speed and accuracy, enabling efficient similarity searches in vast datasets.

ANN search algorithms operate on the principle that in many applications, an exact nearest neighbor search is unnecessarily precise and computationally expensive.

Understanding ANN Search

Trade-off Between Query Time and Space

Early solutions to the nearest neighbour problem demonstrated a trade-off between the time it takes to answer a query (query time) and the amount of memory used (space).

The challenge has been to develop data structures that reduce both these factors effectively.

Dimension Reduction: One key strategy for ANN involves reducing the dimensionality of the data before applying nearest neighbour algorithms. This can significantly decrease space and time complexity, as seen in the Johnson-Lindenstrauss lemma, which facilitates this reduction while preserving distance relationships to a certain degree.

Locality-Sensitive Hashing (LSH): LSH is a method in constructing efficient ANN data structures, characterised by hashing that ensures closer points have a higher probability of colliding in the hashed space. This method balances the space and query time more favourably and is adaptable to various metric spaces.

Here are some key equations representing how Approximate Nearest Neighbour (ANN) works:

Nearest Neighbour

Approximate Nearest Neighbour

These equations encapsulate the core mathematical concepts underpinning the ANN search methodology, illustrating the trade-offs between accuracy and computational efficiency inherent in the problem.

By accepting a degree of approximation, ANN searches significantly reduce the time and resources required to find similar items within large datasets. This trade-off is particularly valuable in real-world applications where speed and efficiency are paramount, and an exact match is not strictly necessary.

Locality-Sensitive Hashing (LSH)

Locality-Sensitive Hashing (LSH) is a technique used to solve the Approximate Nearest Neighbour (ANN) search problem efficiently, especially in high-dimensional spaces.

Fundamentals of LSH

Hashing Families: LSH uses a family of hash functions designed so that closer points in the space are more likely to collide (have the same hash value) than points that are far apart.

where:

Below is a great article on LSH:

LSH for ANN

Data Structure Construction: LSH-based data structures for ANN are built by using multiple hash tables. Each table uses a hash function (or a composite hash function) drawn from the LSH family.

Enhancing Accuracy: By using multiple hash tables (each with potentially a composite hash function created by concatenating multiple LSH functions), the probability of missing the true nearest neighbour is reduced. Essentially, even if a neighbor is missed in one table, it might be caught in another.

Limitations: The effectiveness of LSH is inherently tied to the dimensionality and intrinsic structure of the data. While LSH offers a powerful framework for ANN, its performance can degrade in ultra-high-dimensional spaces or when the data does not align well with the chosen LSH family.

LSH provides a scalable and efficient framework for performing approximate nearest neighbour searches in high-dimensional spaces, balancing the trade-offs between space, accuracy, and computational time.

Categories of ANN Algorithms

ANN algorithms can be categorized based on their underlying mechanisms and structures. Each category has its unique advantages and is suited to particular types of data or applications.

Tree-based Methods

Tree-based algorithms, such as k-d trees, ball trees, and ANNOY, use tree data structures to partition the search space, facilitating efficient navigation and search. While these methods are effective for lower-dimensional data, they tend to struggle with the "curse of dimensionality," making them less suitable for very high-dimensional spaces.

Quantization-based Methods

Quantization involves compressing the search space to reduce both storage and computational demands.

Techniques like IVF_FLAT, IVF_SQ8, and IVF_PQ work by first dividing the vector space into clusters using a predefined number of centroids.

During the encoding process, each vector is assigned to its nearest centroid, and the vectors within each cluster are encoded using different quantization strategies.

IVF_FLAT stores vectors directly, IVF_SQ8 applies scalar quantization to reduce dimension size, and IVF_PQ uses product quantization to split vectors into subspaces.

This clustering and encoding reduce both storage requirements and search complexity, enabling efficient retrieval in high-dimensional spaces.

Graph-based Methods

Graph-based algorithms represent the search space as a graph, with nodes corresponding to vectors and edges linking similar vectors.

Techniques like HNSW and NGT leverage graph traversal to efficiently locate nearest neighbours. These methods are known for their rapid search capabilities and resilience against the curse of dimensionality.

Deep Learning-based Methods

Deep learning approaches, including autoencoders and specialized neural networks, learn compact vector representations for efficient similarity searches. While offering high accuracy, these methods require significant computational resources and training time.

Vector Databases vs. ANN Libraries

The distinction between vector databases and ANN libraries lies in their scope and functionality.

Vector databases provide a comprehensive solution for managing unstructured data, featuring capabilities like cloud-nativity, multi-tenancy, and scalability.

These platforms offer a robust environment for data ingestion, indexing, querying, and persistence, alongside advanced functionalities such as data sharding and hybrid search.

Conversely, ANN libraries like FAISS, ScaNN, and HNSW focus on constructing efficient vector indices to expedite the nearest neighbour search.

These libraries are optimised for performance, offering fast search capabilities with minimal resource usage. While sufficient for smaller, less complex datasets, ANN libraries may not adequately address the scaling challenges posed by larger datasets and multi-user environments.

Conclusion

The debate between the comprehensive features of vector databases and the focused efficiency of ANN libraries underscores the diverse needs of modern data applications.

While vector databases excel in providing a full-fledged environment for managing and querying unstructured data at scale, ANN libraries offer streamlined, efficient solutions for specific nearest neighbour search tasks.

The choice between the two depends on the specific requirements of the application, including dataset size, complexity, and operational scalability.

The nearest neighbour problem involves finding the closest point in a set PPP to a given query point qqq in a metric space.

To enhance efficiency in terms of computation and memory usage, the concept of approximate nearest neighbour (ANN) is introduced, where the goal is to find a point ′p′′p′′p′ in PPP such that its distance to qqq is within a factor ccc (approximation factor) of the actual nearest neighbour's distance.

Data-independent Approaches: These approaches do not rely on the specific dataset PPP but instead use methods like dimension reduction and randomized space partitions to pre-process the space, making the search for nearest neighbours more efficient.

For a set PPP of nnn points in a metric space (X,D)(X,D)(X,D), and a query point q∈Xq∈Xq∈X, the nearest neighbour is defined as: (NN(q)=arg⁡min⁡p∈PD(q,p))( \text{NN}(q) = \arg\min_{p \in P} D(q, p) )(NN(q)=argminp∈P​D(q,p))

The goal in ANN is to find a point p∈Pp∈Pp∈P such that: (D(q,p′)≤ccdotminpinPD(q,p))( D(q, p') \leq c cdot min_{p in P} D(q, p) ) (D(q,p′)≤ccdotminpinP​D(q,p)) where ≥1c≥1≥1c≥1≥1c≥1 is the approximation factor.

This family is defined by four parameters (r,cr,p1​,p2​)(r,cr,p1​,p2​)(r,cr,p1​,p2​)

If the distance (D(x,y)≤r)( D(x, y) \leq r )(D(x,y)≤r) then (Pr⁡[h(x)=h(y)]≥p1)( \Pr[h(x) = h(y)] \geq p_1 )(Pr[h(x)=h(y)]≥p1​)

If the distance (D(x,y)>cr)( D(x, y) > cr )(D(x,y)>cr), then (Pr⁡[h(x)=h(y)]≤p2)( \Pr[h(x) = h(y)] \leq p_2 )(Pr[h(x)=h(y)]≤p2​)

Here, >1c>1>1c>1>1c>1 is the approximation factor, and >0r>0>0r>0>0r>0 is a scale parameter.

Quality Parameter ρρρ: The effectiveness of an LSH family is often measured by the parameter [ρ=log⁡(1/p2)log⁡(1/p1)][ \rho = \frac{\log(1/p_2)}{\log(1/p_1)} ][ρ=log(1/p1​)log(1/p2​)​], where ρ<1ρ<1ρ<1. The smaller ρρρ is, the more effective the LSH family is at distinguishing between close and distant neighbours.

Query Processing: To find the approximate nearest neighbours of a query point qqq, LSH computes the hash values of qqq using the same hash functions and looks up points in the corresponding buckets across the hash tables. The points in these buckets are then considered as candidate nearest neighbours.

LogoApproximate Nearest Neighbor Search in High DimensionsarXiv.org
Approximate Nearest Neighbor (ANN)
LogoSimilarity Search, Part 5: Locality Sensitive Hashing (LSH)Towards Data Science
Page cover image