This is a simple simulation of the Hierarchical Navigable Small World (HNSW) algorithm,
used for Approximate Nearest Neighbor (ANN) search.
Step 0/0
Explanation
Welcome to the HNSW simulation. Use the controls to add points and run queries.
Skip List Navigation
How HNSW Works
The HNSW algorithm creates a multi-layered graph structure:
Layers: Points are assigned to layers with decreasing probability
Insertion: When a new point is added, it's connected to nearest neighbors in each layer
Search: Queries start at the top layer, moving to lower layers while improving accuracy
Benefits include logarithmic search complexity and high recall rates, making it suitable for large-scale ANN search.
Understanding Layers
In HNSW, the same point can appear in multiple layers:
Layer 0 (bottom): Contains ALL points - provides highest accuracy but slow to search entirely
Higher layers: Contain fewer points - act like "highways" for faster navigation
Layer assignment: Each point is randomly assigned a maximum layer (with decreasing probability for higher layers)
Navigation strategy: Start at highest layer with few points, then move down to more detailed layers
Think of it like a transportation system: highways (top layers) for long distances, then local roads (bottom layers) to reach the exact destination.
Algorithm Parameters
Max Layers: The maximum number of hierarchy levels in the graph. Increasing this parameter can improve search speed for large datasets but uses more memory. Higher values work better for larger datasets.
M (connections): The maximum number of connections per node. Higher values create a denser graph with better search accuracy but slower insertion times and more memory usage. Typical values range from 5-48.
ef Construction: Controls how thoroughly HNSW explores the graph during insertion. Higher values result in higher-quality connections (better recall) but slower construction. This has a significant impact on the final graph quality.
The best parameter values depend on your dataset size and the trade-off between speed and accuracy you need.
How to Use This Simulation
Add Random Point: Adds a point at a random position in the space
Find Nearest to Random Point: Creates a random query point (shown in red) and finds its nearest neighbor
Click Mode: Switch between adding points by clicking or searching by clicking
Parameters: Adjust the number of layers and connections to see how they affect the graph structure
Step-by-Step Controls: Use the navigation buttons to walk through the algorithm process one step at a time