← Back
Home › Systems › Databases and storage engines

vector-db

vector database for similarity search

pgvector, Milvus

SystemTechniques · 8Primitives · 27 vector-db Scatter-gather querydistributed · medium: Send a query only to shards that can match, merge their small partial results, and bound the wait for stragglers.›Diskann vamanasearch-sort · medium: Vamana graph index on SSD with compressed vectors in RAM for billion-scale ANNNearest-neighbour search with filte…search-sort · medium: Combine approximate nearest-neighbour search with attribute predicates by pre-filtering, post-filtering or filter-aware graph traversal, chosen by how many items pass.›HNSWsearch-sort · medium: Hierarchical Navigable Small World: a layered proximity graph searched greedily from a sparse top layer; the default in-memory approximate nearest-neighbour index.›IVF-PQsearch-sort · medium: 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.›Inverted indexstorage · medium: Map each term to a sorted, compressed list of the documents containing it; the core of full-text search and other fast set queries.›LSM compactionstorage · medium: Compaction policies (leveled, tiered, time-window, FIFO) decide which sorted files to merge and when, trading write, read and space amplification and purging tombstones.›Top-k selectionsearch-sort · low: 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.›Roaring bitmapscompression · low: Compressed set of 32-bit integers in 64K-value chunks, each a sorted array, bitmap or run list; fast intersections, the standard for bitmap indexes.›SIMD programminghardware-os · low: Process 4-16 lanes per instruction with AVX2, AVX-512 or NEON via Rust std::arch, with runtime dispatch and a portable fallback.›Scalar quantizationsearch-sort · low: Per-dimension int8/binary quantization of vectors with rescoringk-means clusteringmachine-learning · low: Partition points into k clusters by alternating nearest-centroid assignment and centroid averaging; k-means++ seeding makes it dependable.›BM25 rankingsearch-sort · low: The standard lexical relevance score: IDF-weighted term frequency with saturation (k1) and length normalization (b); default in Lucene, Elasticsearch and SQLite FTS5.›mmap and the page cachehardware-os · low: How read() and mmap reach file data through the kernel page cache, what readahead and madvise do, and why databases use their own buffer pool instead.›Hybrid search and rank fusionsearch-sort · low: Merge a keyword (BM25) result list and a vector (ANN) list into one ranking, by ranks (RRF) or by normalized scores (convex combination).›Write-ahead logstorage · low: Append each change to a checksummed sequential log and fsync it before touching data pages; the basis of crash durability in nearly every database.›K way mergesearch-sort · low: Merge k sorted streams with a heap or loser tree (merging iterators)Deadline propagationsystems · low: Carry an absolute deadline and cancellation along a call chainHedged requestssystems · low: Sending a backup request after a latency percentile and taking the first answer to cut tail latencyVector quantizationcompression · low: Codebook and pyramid vector quantization of coefficient vectorsd-ary heapdata-structures · low: Array heap with d children per node (d = 4 typical): half the binary heap's depth, siblings in one cache line, faster priority queues.›io_uringnetworking · low: Linux async I/O through two shared-memory rings (submissions in, completions out), batching or eliminating syscalls for sockets and files alike.›PRNGs (PCG, xoshiro)numerics · low: Small, fast, statistically strong non-cryptographic generators: PCG32 and xoshiro256**, with seeding, parallel streams and unbiased ranges.›+ 1 more techniques+ 11 more primitives

Similar systems

Share the most building blocks with this one.

search-engine 25 %rag 23 %code-search 23 %timeseries-db 21 %product-search 21 %