estudy 한국어/English

Approximate Search Algorithms, HNSW (ANN & FAISS)

1,333 단어·7 분·원문(.md)

Let's delve into the core algorithms that power vector databases like Elasticsearch and high-speed search libraries like FAISS.

This indexing architecture sacrifices 100% perfect accuracy to prevent server crashes, instead achieving hundreds of times faster search speeds while maintaining 99% accuracy.

  • ANN (Approximate Nearest Neighbor): A general term for algorithms that quickly find approximately the K nearest vectors to a query vector in a vector space.
  • HNSW (Hierarchical Navigable Small World): An algorithm that has dominated the ANN ecosystem, exploring node data connected in a multi-layered graph.
  • FAISS (Facebook AI Similarity Search): An ultra-high-speed dense vector search library developed in C++ by the Meta AI research team. It allows easy use of various ANN algorithms, including HNSW.

Origin of the Names #

  • Approximate: A trade-off that allows for a slight error margin to gain search performance (throughput) and memory efficiency, instead of performing an exhaustive (exact) search.
  • HNSW (Hierarchical Navigable Small World): Hierarchical means it's structured in multiple layers, like apartment floors. Navigable means it's possible to find paths because neighboring nodes are connected by links or edges. Small World borrows from the small-world network theory, which states that anyone in the world can be connected through six degrees of separation, implying that even distant data can be reached with just a few jumps.

The Problem #

Exact k-NN: Traditionally, when a single query vector came in, it required a brute-force calculation of cosine similarity with each of the million product vectors in the database. If traffic surged, the CPU couldn't handle it, leading to search times exceeding 1-2 seconds, making real-world service impossible.

LSH's accuracy limitations also existed. The LSH previously used involved simply truncating vectors into short 16-bit or 32-bit strings and placing them into hash tables. While fast, it compressed precise float values crudely. For detailed items like home shopping products, this meant a critical problem: the true answer might be placed in the wrong hash bucket and never found. This resulted in an accuracy of around 70% and only slightly faster search times.

Solution #

Solved with graph-based search. HNSW doesn't just shove data into hash tables; it builds a graph that weaves together relationships between data like a spiderweb.

It uses multiple layers, from high-speed "highway" layers for long jumps to precise "alleyway" layers for detailed exploration, to find the optimal path.

Let's take an intuitive example.

Imagine you need to find a red linen shirt in a giant warehouse with a million pieces of clothing.

  • Exact k-NN: This would be an exhaustive search. An employee would pull out and compare each of the million clothes from the warehouse entrance. Accuracy would be 100%, but it would take a long time.
  • LSH: Similar to a postal code, clothes are thrown into bins by similar colors. The employee would search the red bin, which is fast. However, if they mistakenly put a linen shirt in the orange bin, it would never be found. This means accuracy is around 70%, and search time is only slightly shorter.
  • HNSW (Navigation Graph): The employee has drawn a map of the warehouse by floor.
    • 3rd floor (Highway): A big jump to the summer clothes section.
    • 2nd floor (National Road): Within summer clothes, the shirt section.
    • 1st floor (Alleyway): Within the shirt section, compare only 10 red clothes near me. Even comparing only 10 items, accuracy is high (98% accuracy, search time around 0.01 seconds).

Detailed Operating Principles and Structure #

HNSW's internal architecture is a multi-layer graph navigation system, divided into spatial layers.

1. Indexing Phase #

In the bottom-most layer (layer 0), all million data points are densely connected with their neighbors.

As you move up, only a sparse number of "hubs" that survived through probability are connected (layer 1, layer 2...).

2. Search Phase #

The search begins at the entry point, from the topmost layer with fewer nodes.

It performs a greedy search: moving to the node closest to the query vector within the current layer. If there are no closer neighbors, it moves down to the layer below.

Upon reaching the bottom-most layer (layer 0), it's already in a location very close to the query. It then sorts the surrounding neighbors and returns the final top-k. In this process, the complexity converges to O(log(N)).

Example #

This is the basic logic for taking vectors generated by PyTorch, inserting them into a FAISS HNSW index, and performing ultra-fast searches. The key point is that FAISS only handles numpy, float32 types.

import faiss
import numpy as np
import torch

def understand_faiss_hnsw(query_tensor, db_tensors):
    """
    Inserts PyTorch vectors of dimension (d) 512 into a FAISS HNSW index and searches.
    """
    # 1. Convert PyTorch Tensor -> Numpy Array (FAISS requirement)
    # Move to CPU memory and cast to contiguous float32 array.
    db_vectors = db_tensors.cpu().numpy().astype('float32')
    query_vector = query_tensor.cpu().numpy().astype('float32')
    
    d = db_vectors.shape[1] # Number of vector dimensions (e.g., 512)
    
    # 2. Create HNSW index
    # 32 represents the maximum number of neighbors (M) to connect per node. (Parameter tuning factor)
    index = faiss.IndexHNSWFlat(d, 32)
    
    # Set distance metric to L2 distance (dot product) which has the same effect as cosine similarity.
    index.hnsw.efConstruction = 40 # Search depth during indexing (accuracy vs. build speed)
    
    # 3. Index data (build graph in memory)
    index.add(db_vectors)
    print(f"Total {index.ntotal} vectors indexed in HNSW graph.")
    
    # 4. Set search parameters and search
    index.hnsw.efSearch = 64 # Search depth during search (accuracy vs. search speed)
    k = 5 # Top 5
    
    # distances: Returns distance values of nodes closest to the query
    # indices: Returns array indices (IDs) of those nodes in the DB
    distances, indices = index.search(query_vector, k)
    
    print(f"Found Top-{k} IDs   : {indices[0]}")
    print(f"Distances for these IDs : {distances[0]}")

Let's look at another example: a wrapper class that performs pre-normalization for cosine similarity search, allowing the index to be written to disk (write_index) and loaded (read_index) without re-indexing vectors every time in a real server environment.

import faiss
import numpy as np

class HNSWSearchEngine:
    """FAISS-based vector storage/search engine used in production environments"""
    
    def __init__(self, dimension: int = 512, m: int = 32, ef_search: int = 128):
        self.dimension = dimension
        # Create HNSW index based on L2 distance (for cosine similarity)
        self.index = faiss.IndexHNSWFlat(dimension, m)
        self.index.hnsw.efConstruction = 100
        self.index.hnsw.efSearch = ef_search
        
    def _normalize(self, vectors: np.ndarray) -> np.ndarray:
        """
        [Very Important] FAISS's built-in cosine similarity search is tricky.
        However, if you L2-normalize vectors (make their length 1) and then calculate L2 distance (Euclidean),
        it mathematically becomes perfectly equivalent to the cosine similarity ranking.
        """
        norms = np.linalg.norm(vectors, axis=1, keepdims=True)
        # Prevent division by zero
        norms = np.where(norms == 0, 1e-10, norms)
        return vectors / norms

    def build_index(self, product_ids: list, vectors: np.ndarray, save_path: str = "hnsw.index"):
        """Normalizes all product vectors, adds them to the graph, and saves to a file."""
        assert len(product_ids) == vectors.shape[0]
        
        normalized_vecs = self._normalize(vectors).astype('float32')
        self.index.add(normalized_vecs)
        
        # In production, you need to store a separate dictionary mapping index (0, 1, 2...) to actual product IDs (item_99).
        self.id_map = {i: pid for i, pid in enumerate(product_ids)}
        
        # Dump the index to disk for 1-second recovery on restart
        faiss.write_index(self.index, save_path)
        print(f"✅ HNSW index saved: {save_path} (Total {self.index.ntotal} items)")

    def load_index(self, load_path: str = "hnsw.index"):
        """Loads the index from disk into memory on server startup."""
        self.index = faiss.read_index(load_path)
        print(f"✅ HNSW index loaded (Total {self.index.ntotal} items)")

    def search(self, query_vector: np.ndarray, top_k: int = 10):
        """Handles real-time search queries."""
        # Query vector must also be normalized
        query_normalized = self._normalize(query_vector).astype('float32')
        
        # Perform search (takes a few milliseconds)
        distances, indices = self.index.search(query_normalized, top_k)
        
        results = []
        for dist, idx in zip(distances[0], indices[0]):
            if idx != -1: # -1 means not found
                results.append({
                    "product_id": self.id_map.get(idx, "Unknown"),
                    # Convert L2 distance to an intuitive score (shorter distance = higher score)
                    "score": round(float(1 / (1 + dist)), 4) 
                })
        return results

# --- Example of use in a production API server ---
# hnsw_db = HNSWSearchEngine(dimension=512)
# hnsw_db.load_index()
#
# @app.post("/search/vector")
# def vector_search(query: str):
#     query_vec = clip_encoder.get_vector(query) # CLIP object created in Step 2
#     results = hnsw_db.search(np.array([query_vec]), top_k=20)
#     return {"items": results}
AI/hnsw.md