← Back
Home › Systems › AI applications

knowledge-graph

knowledge graph

Wikidata, Google Knowledge Graph

SystemTechniques · 15Primitives · 36 knowledge-graph Pagerankgraphs · medium: Power-iteration PageRank on a sparse graph with damping and dangling nodesEntity linkingmachine-learning · medium: Map each mention to a knowledge-base id, or to NIL, by generating candidates from an alias table, scoring them on prior and context, and thresholding.›Knowledge graph embeddingsmachine-learning · medium: Embedding entities and relations (TransE, RotatE, ComplEx) for link predictionNamed entity recognitionmachine-learning · medium: Find the character spans of entities in text and give each a type, by labelling every token and decoding a valid label sequence.›Relation extractionmachine-learning · medium: Extracting (subject, relation, object) triples from text with classifiers or LLMsEntity resolutionstorage · medium: Decide which records describe the same real-world thing: block to cut the pair space, score pairs with a probabilistic model, cluster the matches transitively.›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.›Dictionary encodingcompression · low: Map values to small integer codes via a dictionary for compact, comparable columnsB+ treestorage · low: Balanced high-fanout search tree with all values in linked leaves; the default on-disk index for point lookups and range scans.›BFS and DFSgraphs · low: The two basic graph traversals; BFS gives hop distances and levels, DFS gives discovery/finish order for cycles, components and topological order.›Edit distancesearch-sort · low: Levenshtein/Damerau distance by DP, bit-parallel Myers variantHash joinstorage · low: Build a hash table on the smaller input's join key and probe it with every row of the larger one; the linear-time workhorse for equi-joins.›Reproducible reductionnumerics · low: Order-independent floating-point sums (fixed order, Kahan, binned) for bit-for-bit reproducibilitySparse matrices (CSR)numerics · low: Compressed sparse row stores only nonzeros as row pointers, column indices and values; SpMV streams them once, so it is memory-bandwidth bound.›Embeddingsmachine-learning · low: A learned table mapping discrete ids to dense vectors: gather forward, sparse scatter-add backward, row-wise optimizers to keep huge tables cheap.›Loss functionsmachine-learning · low: The scalar a model minimizes: cross-entropy for classes and tokens, MSE or Huber for values, each with a stable form and simple gradient.›Negative samplingmachine-learning · low: Train by contrasting each observed positive with a few sampled negatives instead of normalising over every candidate; the choice of sampler decides bias and quality.›Byte-pair encoding (BPE) tokenizati…machine-learning · low: Learn a subword vocabulary by repeatedly merging the most frequent adjacent pair; byte-level BPE encodes any input losslessly with 32k-200k tokens.›Transformer blockml-training · low: The decoder-only pre-norm block (attention plus MLP on a residual stream) behind every modern LLM, with exact shapes, parameter, FLOP and KV-cache counts.›Convolutional codes and the Viterbi…signal-processing · low: Streaming error-correcting code: each output bit is a parity of the last K input bits; the Viterbi decoder finds the most likely path through a 2^(K-1)-state trellis.›Union-findgraphs · low: Disjoint-set forest with union by size and path compression; merges sets and answers same-set queries in effectively constant time.›Bit packing and PFORcompression · low: Store blocks of integers with exactly b bits each and patch rare outliers separately (PFOR); the fastest integer codec family, billions of values per second.›Delta encodingcompression · low: Store differences between consecutive values instead of the values, turning sorted IDs, timestamps and counters into small numbers that pack into few bits.›+ 8 more techniques+ 20 more primitives

Similar systems

Share the most building blocks with this one.

graph-db 24 %sanctions-screening 19 %threat-intel-platform 18 %