Data structures and algorithms for ML

KD-trees prune subtrees when the splitting hyperplane is farther than the current best distance, but in high dimensions the distance contrast collapses and almost every cell intersects the query hypersphere, so pruning fails and the tree must visit nearly all leaves. Empirically KD-trees lose their advantage once dimensionality exceeds roughly 20-30, behaving like brute force. This is a manifestation of the curse of dimensionality on spatial partitioning.

Ball trees partition data into nested hyperspheres defined by a centroid and radius rather than axis-aligned boxes, so their pruning bound (triangle inequality on distances) does not depend on aligning splits with coordinate axes. This makes them more effective than KD-trees for moderately high-dimensional or non-axis-aligned data and for arbitrary metrics. They still suffer in very high dimensions but typically degrade more gracefully than KD-trees.

HNSW builds a hierarchy of proximity graphs where upper layers contain exponentially fewer nodes with long-range links, acting like an express skip-list over the data manifold; search starts at the top layer, greedily descends, and refines at the bottom dense layer. This yields approximately O(log n) expected hops to reach the neighborhood of a query. The layered long-range edges let the search escape local minima and converge quickly to true nearest neighbors.

LSH uses hash families where the collision probability of two points increases with their similarity, so similar items map to the same bucket with high probability while dissimilar ones rarely collide. A query only compares against candidates in its bucket(s), reducing the search from O(n) to roughly the bucket size, and multiple hash tables (amplification via AND/OR constructions) trade recall against query cost. The guarantee is probabilistic, returning a (1+epsilon)-approximate neighbor.

PQ splits each D-dimensional vector into m subvectors and independently k-means-quantizes each subspace into 256 centroids, encoding a vector as m bytes (one centroid id per subspace). Distances are then approximated using precomputed lookup tables (asymmetric distance computation), giving massive memory compression (e.g. 128 floats to 16 bytes) while preserving ranking quality. It is the backbone of FAISS IVF-PQ indexes.

IVF clusters vectors into Voronoi cells (coarse centroids); nprobe is the number of nearest cells searched at query time. Larger nprobe scans more cells, raising recall but increasing latency, while small nprobe is fast but may miss neighbors that fell into an unsearched cell. It is the primary recall/speed knob alongside the number of centroids nlist.

A min-heap of fixed size k: push each element and, once the heap exceeds k, pop the minimum, so the heap always holds the current top-k and its root is the kth largest. This processes n elements in O(n log k) time and O(k) space, ideal for streaming where the full data cannot be sorted. Python's heapq.nlargest uses this approach.

import heapq
# top-k largest from a stream
heap = []
for x in stream:
    if len(heap) < k:
        heapq.heappush(heap, x)
    elif x > heap[0]:
        heapq.heapreplace(heap, x)  # pop min, push x

Quickselect (Hoare's selection) partitions the array like quicksort but recurses only into the side containing the k-th element, giving expected O(n) time versus O(n log k) for a heap, and is preferred when the entire array is in memory and you can mutate/copy it. Its worst case is O(n^2), mitigated by median-of-medians pivoting (deterministic O(n)) or randomized pivots. Heaps remain better for streaming data that does not fit in memory.

A Count-Min Sketch is a sublinear probabilistic structure of d hash functions over w counters that estimates frequencies of items in a stream; each query returns the minimum counter across the d rows. It never underestimates a count but can overestimate due to hash collisions, with error bounded by epsilon*N (N = total count) with probability 1-delta given w=ceil(e/epsilon), d=ceil(ln(1/delta)). It is widely used for heavy-hitter and feature-frequency estimation.

HyperLogLog estimates the number of distinct elements (cardinality) of a multiset in a single pass using the position of the leading 1-bit in hashed values across registers. With about 1.5 KB of memory it estimates cardinalities into the billions with a standard error around 2% (error ~1.04/sqrt(m) for m registers). It supports mergeable union, making it ideal for distributed unique-count analytics.

A Bloom filter is a bit array with k hash functions supporting insert and probabilistic membership queries: a 'not present' answer is always correct (no false negatives), but 'present' may be a false positive whose rate rises as the filter fills. It cannot delete elements (standard variant) and trades a small false-positive probability for large memory savings, common in caching, DB joins, and dedup pipelines.

Keep the first k items; for the i-th item (i>k), include it with probability k/i, and if included, replace a uniformly chosen reservoir slot. This guarantees every element seen so far has equal probability k/n of being in the final sample, using O(k) memory and O(n) time without knowing n in advance. It is foundational for sampling minibatches or logs from unbounded streams.

import random
res = []
for i, x in enumerate(stream):
    if i < k:
        res.append(x)
    else:
        j = random.randint(0, i)
        if j < k:
            res[j] = x

Union-Find efficiently maintains connected components under merges, used in single-linkage/agglomerative clustering, connected-component labeling, and graph-based segmentation. With union by rank and path compression, m operations on n elements run in O(m alpha(n)) where alpha is the inverse Ackermann function, effectively constant per operation. This makes it the standard structure for building clusters from edges sorted by similarity.

A Fenwick tree supports both point updates and prefix-sum (range-sum) queries in O(log n), whereas a static prefix-sum array gives O(1) queries but O(n) updates. It is ideal when data changes dynamically, e.g. maintaining cumulative counts for online ranking, weighted sampling, or AUC computation with updates. It uses O(n) space and exploits the low-bit (i & -i) trick for traversal.

A trie stores strings by shared prefixes so lookup, insert, and prefix enumeration take O(L) time in the key length L, independent of vocabulary size, enabling fast longest-prefix matching for tokenizers and instant autocomplete suggestions. They also make it cheap to find all keys sharing a prefix (autocomplete) and to do greedy maximal-munch tokenization. The tradeoff is higher memory than a hash map, often mitigated by compressed/radix tries.

Classic DTW fills an n-by-m dynamic-programming cost matrix with O(nm) time and space, computing the optimal monotonic alignment. In practice it is sped up with Sakoe-Chiba band or Itakura constraints (limiting the warping window) and with lower bounds like LB_Keogh plus early abandoning, and FastDTW gives approximate O(n) behavior. These prune the search so large time-series datasets become tractable.

Viterbi is a dynamic-programming algorithm that finds the single most probable hidden state sequence (MAP path) given observations, by recursively keeping the best path probability into each state and backpointers. It runs in O(T*N^2) time and O(T*N) space, far better than the exponential O(N^T) brute-force enumeration. It underlies decoding in HMM taggers, speech recognition, and CRF inference.

At each of T steps, beam search expands B hypotheses by scoring all V next tokens and keeps the top B, costing O(T*B*V) for scoring (the top-B selection is O(B*V) per step, often via a partial sort/heap). Memory is O(B*T) to store the candidate sequences. Increasing B improves search quality with diminishing returns and risks favoring shorter sequences without length normalization.

The computation is a directed acyclic graph (DAG) of operations; reverse-mode autodiff must process nodes so that a node's gradient is computed only after all its consumers, which is exactly a reverse topological order of the forward graph. Frameworks record the forward order (a valid topological order) and traverse it in reverse to accumulate gradients via the chain rule. This guarantees each node's upstream gradients are fully available before backprop visits it.

Feature hashing maps high-cardinality or unbounded categorical features into a fixed-size vector by hashing each feature to an index (often with a signed hash to reduce bias), avoiding storing an explicit vocabulary and enabling O(1) online encoding with bounded memory. The tradeoff is hash collisions that conflate distinct features into the same dimension, introducing noise that is usually tolerable when the hash dimension is large enough. It is popular for streaming/online learning and very wide sparse feature spaces.

CSR stores three arrays: nonzero values, their column indices, and row pointers marking where each row's entries begin, using O(nnz + rows) space instead of O(rows*cols). This layout gives contiguous per-row access so sparse matrix-vector products (SpMV) iterate only over nonzeros with good cache locality, which is critical for large sparse linear algebra in ML (e.g. TF-IDF, graphs). It is fast for row slicing and SpMV but slow for incremental structural changes.

Standard attention computes an n-by-n score matrix, costing O(n^2 * d) time and O(n^2) memory, which dominates for long sequences. FlashAttention keeps the same O(n^2*d) compute but reorganizes it with tiling and online softmax so it never materializes the full n-by-n matrix, reducing memory to O(n) and cutting HBM traffic for large speedups. Sparse/linear-attention variants instead reduce the asymptotic compute below quadratic.

For each of k random permutations (or hash functions), MinHash records the minimum hashed element of a set; the probability that two sets share the same min-hash equals their Jaccard similarity, so the fraction of matching signatures across the k hashes is an unbiased estimator of Jaccard. This compresses sets into fixed-length signatures of size k, enabling fast similarity estimation and, combined with LSH banding, near-duplicate detection at scale. Variance shrinks as O(1/k).

SimHash produces a compact bit fingerprint such that the Hamming distance between fingerprints approximates the angular (cosine) distance between the original feature vectors, so similar documents get fingerprints differing in few bits. Near-duplicates are found by detecting fingerprints within a small Hamming radius, which can be indexed for fast lookup, making it efficient for web-scale dedup. It contrasts with MinHash, which targets Jaccard similarity of sets.

A skip list is a probabilistic layered linked list giving expected O(log n) search, insert, and delete by using randomized express lanes over a sorted base list. It is simpler to implement lock-free/concurrently than rotation-based balanced trees because updates touch only local pointers, which is why systems like RocksDB memtables and concurrent ordered maps use it. Its bounds are expected rather than worst-case.

PageRank repeatedly multiplies the current rank vector by the (damped) column-stochastic transition matrix until it converges to the dominant eigenvector (stationary distribution). Each iteration costs O(nnz) using sparse matrix-vector multiplication, and the convergence rate is governed by the spectral gap, i.e. the ratio of the second to first eigenvalue, which the damping factor (typically 0.85) bounds. Smaller damping converges faster but spreads rank more uniformly.

Full-neighborhood aggregation suffers neighbor explosion: the receptive field grows multiplicatively with depth, so an L-layer GNN can touch O(d^L) nodes per target, making memory and compute infeasible on large graphs. GraphSAGE samples a fixed number of neighbors per layer, bounding the per-node computation to a constant fan-out and enabling minibatch training. This trades exactness for scalability and acts as a regularizer.

Space-Saving maintains only m counters to approximate the top frequent items (heavy hitters) in a stream; when a new item arrives and all counters are used, it overwrites the item with the smallest count and increments that counter, recording the overestimate. With m=O(1/epsilon) counters it guarantees that any item with frequency above epsilon*N is reported, with bounded overestimation error. It uses O(1/epsilon) memory regardless of stream length.

Cuckoo hashing uses two (or more) hash functions and tables so each key lives in one of a small constant number of candidate slots, giving worst-case O(1) lookup and deletion (not just amortized). Insertions may trigger a chain of evictions ('kicking out') and, if a cycle forms, require a rehash, so high load factors raise insertion cost and failure risk. It is favored when read latency must be tightly bounded.

Dijkstra repeatedly extracts the unsettled node with the smallest tentative distance and relaxes its edges; a min-priority queue makes extracting that minimum and updating neighbor keys efficient. With a binary heap it runs in O((V+E) log V); a Fibonacci heap improves the amortized bound to O(E + V log V) by making decrease-key O(1) amortized. This matters for graph-based ML such as manifold/geodesic distance (Isomap) and routing.

Naive recursive edit distance recomputes overlapping subproblems exponentially; memoizing (or bottom-up DP filling an (n+1)x(m+1) table) reuses each subproblem once, yielding O(nm) time. Space can be reduced to O(min(n,m)) by keeping only the previous row, since each cell depends only on its left, top, and top-left neighbors. This DP underlies fuzzy string matching, spell correction, and sequence alignment.

Tiling partitions the matrices into sub-blocks that fit in cache so each loaded element is reused many times before eviction, dramatically improving the compute-to-memory-traffic ratio and reducing cache misses. The arithmetic operation count stays O(n^3), but wall-clock time drops because memory bandwidth, not FLOPs, is the bottleneck on modern hardware. This locality principle is the basis of optimized BLAS GEMM kernels central to deep learning.

LSM trees buffer writes in an in-memory structure and flush them as sorted immutable runs, turning random writes into sequential ones and merging via background compaction, which gives high write throughput and good compression. B-trees instead update in place, causing random I/O and write amplification on writes but offering lower read amplification. LSM stores (e.g. RocksDB backends) thus suit write-heavy ingestion of features/embeddings, at the cost of read-side merge work.