Structure
Multi-layer graph. Top: sparse, long-range edges. Bottom: dense, short-range. Search: greedy descend, refine at bottom.
Advertisement
Insertion
Choose max layer by exponential distribution. Connect to M nearest neighbors at each layer. Layer probabilities decay geometrically.
Advertisement
Query
Start at top entrypoint. Greedy walk to closest neighbor. Descend layer. Repeat. Refine at bottom with beam search.
Complexity
Build: O(N log N · M). Query: O(log N) with high accuracy.