> if a skiplist is a probabilistic alternative to a B+-tree, what's HNSW a probabilistic alternative to? I don't think that analogy is accurate. A prolly tree

> if a skiplist is a probabilistic alternative to a B+-tree, what's HNSW a probabilistic alternative to? I don't think that analogy is accurate. A prolly tree could also be considered a probabilistic version of a b-tree and a skiplist could be considered a probabilistic version of a trie, so you certainly have probabilistic vs. non-probabilistic datastructures, but there isn't really a 1-to-1 correspondence, so your inference of a missing X doesn't make that much sense. Here's a better dichotomy imho. Both of these probabilistic and non-probabilistic datastructures share a commonality. They operate on totally ordered data. So a skiplist is actually 1D. HNSW and other approximate k-nearesr neighbour algorithms however operate over metric spaces, where elements have a distance/similiarity but no meaningful order.[1] Now if you ask for the deterministic equivalent of a approximate-kNN algorithm/datastructure, then that would simply be anything in the kNN category. 1: https://math.stackexchange.com/questions/1429373/why-is-there-no-order-in-metric-spaces https://math.stackexchange.com/questions/1429373/why-is-ther...