Sorting, searching & vector search

Non-comparison sort that distributes keys by 8-bit digits; several times faster than comparison sorts on large arrays of integers, floats or fixed-size keys.

Introsort successor: quicksort with adaptive pivots, linear on sorted and equal-heavy input, heapsort fallback; the unstable sort of Go and (until 1.81) Rust.

Sort data larger than RAM: write memory-sized sorted runs, then k-way merge them with large sequential buffers; terabytes in one merge pass.

Sorted array stored in BFS order so binary search walks an implicit tree with prefetchable addresses; 2-2.5x faster than binary search beyond cache.

Find bytes or substrings by comparing 16-64 haystack positions per instruction against the needle's first and last byte, then verifying the rare candidates.

Sorted array of all suffix start positions of a text; finds every occurrence of any substring by binary search, at 4-5 bytes per text byte.

Keep the k best of n items without sorting all n - bounded min-heap for streams, quickselect for arrays, threshold pruning to skip most items.

Hierarchical Navigable Small World: a layered proximity graph searched greedily from a sparse top layer; the default in-memory approximate nearest-neighbour index.

Inverted file plus product quantization: cluster vectors into lists, store each as a few bytes of codes, scan only the nearest lists via table lookups.

Combine approximate nearest-neighbour search with attribute predicates by pre-filtering, post-filtering or filter-aware graph traversal, chosen by how many items pass.

Merge a keyword (BM25) result list and a vector (ANN) list into one ranking, by ranks (RRF) or by normalized scores (convex combination).

Re-score the top-k candidates of a cheap first stage with a model that reads query and candidate together; more accurate than separate embeddings, but one model call per pair.

Turn multilingual text into index terms: segment words (UAX 29 style, CJK bigrams), normalize, case-fold and accent-fold, identically at index and query time.

The standard lexical relevance score: IDF-weighted term frequency with saturation (k1) and length normalization (b); default in Lucene, Elasticsearch and SQLite FTS5.

Find all occurrences of many fixed patterns in one pass over the text, in time independent of the pattern count, using a trie with failure links.

Match a regular expression in O(pattern x text) worst case by tracking all live parse positions at once, then cache the state sets as a lazily built DFA for speed.

Skip documents that provably cannot enter the top-k, using per-list and per-block maximum scores against the current k-th best score (WAND, Block-Max WAND, MaxScore).

Intersect sorted id lists by merging, galloping from the short list into the long one, and skipping whole compressed blocks, shortest list first.

Greedy O(ND) shortest edit script between two sequences, the default of git and GNU diff; fast when the inputs are similar.

Charikar's random-hyperplane sketch: a 64-bit fingerprint per document whose Hamming distance tracks cosine similarity, searchable in sub-linear time by exact block matches.

Compact fingerprints (64 to 256 bits) of an image that stay close under resizing and recompression, compared by Hamming distance; pHash, dHash and Meta's PDQ.

Decide per URL whether a crawler may fetch it from a host's robots.txt (RFC 9309): status-code rules, group choice, longest-match Allow/Disallow, 24 h cache.

Rewrite a URL to one canonical key, in safe RFC 3986 steps plus lossy, site-dependent ones (tracking parameters, query order, fragments), and keep the original beside the key.

Dynamic programming that finds the highest-scoring pair of similar substrings of two sequences under a substitution score and affine gap penalties, in O(nm) time.

Aligns N sequences into columns by merging them pairwise up a guide tree as profiles, optionally refined or guided by consistency; exact search is NP-hard.