Skip to content

data-structures.md

Latest commit

 

History

History
698 lines (590 loc) · 28.2 KB

data-structures.md

File metadata and controls

698 lines (590 loc) · 28.2 KB
Raw

Data structures

Array

  • https://en.wikipedia.org/wiki/Array_data_structure
  • implemented in: 'C++ std::vector', 'Python list, tuple'
  • continuous list of elements in memory. fast to iterate, fast to access by index. slow to find by value, slow to insert/delete within the array (as memory always need to be continuous, they need to be reallocated)
  • usually fast to append/delete at the end or beginning (if there is free memory and depending on exact implementation)

Linked list

  • https://en.wikipedia.org/wiki/Linked_list
  • single elements in memory which contain a pointer to the next element in the sequence
  • double linked list also contain pointers back to the previous element int the sequence (XOR linked list is a clever optimization)
  • insert and delete can be constant time if pointers are already found. iteration is slow. access by index is not possible, search by value in linear.
  • implemented in: 'C++ std::list, std::forward_list'
  • can be: 'Persistent data structure'

Rope

Threaded binary tree

AVL tree

Gap buffer

Piece table

Hash table

  • https://en.wikipedia.org/wiki/Hash_table
  • implements: 'Set', 'Multiset', 'Map'
  • used to implement: 'Python dict', 'C++ std::unordered_set', 'C++ std::unordered_multiset', 'C++ std::unordered_map'
  • probably the most important data structure in Python
  • has basically perfect complexity for a good hash function. (Minimal) perfect hashing can be used if the keys are known in advance.
  • ordering depends on implementation (python 3.7 garuantees preservation of insertion order, whereas C++ as the name says does not define any ordering)
  • even though hashing is constant in time, it might still be slow. also the hash consumes space.
  • time complexity (search, insert, delete) (average): O(1)
  • time complexity (search, insert, delete) (worst): O(n)
  • space complexity (average): O(n)
  • space complexity (worst): O(n) # often a lot of padding space is needed...

Binary search tree

Zipper

Fibonacci heap

Pairing heap

Binary heap

Segment tree

Interval tree

  • https://en.wikipedia.org/wiki/Interval_tree
  • variants: 'centered interval tree', 'augmented interval tree'
  • applications: 'windowing queries'
  • properties: 'output-sensitive'
  • implemented in (libraries): 'Python intervaltree'

Range query tree (?)

Nested Containment List

  • paper: 'Nested Containment List (NCList): a new algorithm for accelerating interval query of genome alignment and interval databases' (2007) https://doi.org/10.1093/bioinformatics/btl647
  • implemented in (libraries): 'Python ncls'
  • applications: 'interval overlap queries'

Longest common prefix array

Binary decision diagram

  • also called: 'BDD'
  • https://en.wikipedia.org/wiki/Binary_decision_diagram
  • compressed representation of sets or relations
  • implements: 'Boolean function'
  • is a: 'rooted, directed, acyclic graph'
  • applications: 'Computer-aided design', 'Formal verification', 'Fault tree analysis', 'Private information retrieval'

Zero-suppressed decision diagram

Propositional directed acyclic graph

Trie

  • also called: 'digital tree'
  • paper: 'File searching using variable length keys' (1959) https://doi.org/10.1145/1457838.1457895
  • https://en.wikipedia.org/wiki/Trie
  • tree structure
  • set and map characteristics
  • keys are sequences (eg. strings)
  • allow for prefix search (eg. find all strings that start with 'a', or find the longest prefix of 'asd')
  • if implemented with hashmaps, indexing by key can be done in O(sequence-length) independent of tree size
  • not very space efficient. common prefixed only have to be stored once, but pointers to next element of sequence uses more memory than what is saved.
  • for a more space efficient data structure see MAFST

WPL tree

PQ tree

Radix tree

Adaptive radix tree

X-fast trie

Y-fast trie

Quadtree

  • https://en.wikipedia.org/wiki/Quadtree
  • is a: 'Tree', 'Space-partitioning tree'
  • can be implemented as: 'Implicit data structure'
  • variant: 'Region quadtree'
  • applications: 'Image processing', 'Connected-component labeling', 'Mesh generation'

Red-black tree

AVL tree

Treap

Implicit treap

Fenwick tree

Scapegoat tree

BK-tree

Splay tree

  • paper: 'Self-adjusting binary search trees' (1985) https://doi.org/10.1145/3828.3835
  • https://en.wikipedia.org/wiki/Splay_tree
  • is a: 'Binary search tree'
  • properties: 'self-optimizing'
  • applications: 'Caching', 'Garbage collection'
  • disadvantages: even concurrent reads require synchronization
  • unsolved problem: 'Do splay trees perform as well as any other binary search tree algorithm?'

k-d tree

  • also called: 'k-dimensional tree'
  • paper: 'Multidimensional binary search trees used for associative searching' (1975) https://doi.org/10.1145/361002.361007
  • https://en.wikipedia.org/wiki/K-d_tree
  • is a: 'Space-partitioning tree'
  • applications: 'Range searching', 'Nearest neighbor search', 'Kernel density estimation'
  • for high dimensions should be: N >> 2^k, where N is the number of nodes and k is the number of dimensions
  • solves 'Recursive partitioning', 'Klee's measure problem', 'Guillotine problem'
  • implemented in: 'Python scipy.spatial.KDTree, sklearn.neighbors.KDTree, Bio.PDB.kdtrees.KDTree'

Range tree

Compressed range trees

  • paper: 'A Functional Approach to Data Structures and Its Use in Multidimensional Searching' (1988) https://doi.org/10.1137/0217026
  • applications: 'Range searching'
  • space complexity: O(n)
  • query complexity: O(log n + k*log^ε n)

Cartesian tree

Iliffe vector

Dope vector

van Emde Boas tree

Skip list

  • paper: 'Concurrent Maintenance of Skip Lists' (1998)
  • https://en.wikipedia.org/wiki/Skip_list
  • https://xlinux.nist.gov/dads/HTML/skiplist.html
  • is a: 'probabilistic data structure', 'ordered linked list'
  • basically binary trees converted to linked lists with additional information
  • allows for fast search of sorted sequences
  • implemented by: 'Lucence', 'Redis'
  • implemented in: 'Java ConcurrentSkipListMap'
  • applications: 'Moving median'
  • space complexity (average): O(n)
  • space complexity (worst): O(n log n)
  • time complexity (search, insert, delete) (average): O(log n)
  • time complexity (search, insert, delete) (worst): O(n)

Interval Skip List

  • paper: 'The interval skip list: A data structure for finding all intervals that overlap a point' (1991) https://doi.org/10.1007/BFb0028258
  • implemented in (libraries): 'CGAL::Interval_skip_list', 'Dart kseo/interval_skip_list'
  • applications: 'stabbing queries'

AABB tree

Finite-state machine

Finite-state transducer

Deterministic finite automaton

Deterministic acyclic finite state automaton

Minimal acyclic finite state automaton

  • also called: 'MAFSA', 'Minimal acyclic finite state acceptor'
  • https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton
  • https://blog.burntsushi.net/transducers/
  • minimal: 'Deterministic acyclic finite state automaton'
  • space optimized version of tries, with missing map characteristics
  • allow for prefix (and possibly suffix) search
  • more space efficient than tries as common prefixes and suffixes are only stored once and thus the number of pointers is reduced as well
  • for a version with map characteristics see: 'Minimal acyclic finite state transducer'
  • implemented in: 'C++ dawgdic'

Deterministic acyclic finite state transducer

Minimal acyclic finite state transducer

B-tree

B+ tree

UB-tree

SS-Tree (Similarity search tree)

Cover tree

M-tree

Vantage-point tree

  • original paper: 'Satisfying general proximity / similarity queries with metric trees' (1991)
  • paper: 'Data structures and algorithms for nearest neighbor search in general metric spaces' (1993)
  • https://en.wikipedia.org/wiki/Vantage-point_tree
  • is a: 'Space-partitioning tree', 'Metric tree'
  • specialisation of: 'Multi-vantage-point tree'

Ball tree

  • https://en.wikipedia.org/wiki/Ball_tree
  • is a: 'Space-partitioning tree', 'Metric tree', 'Binary tree'
  • applications: nearest neighbor search, kernel density estimation, N-point correlation function calculations, generalized N-body Problems.
  • specialisation of: M-Tree
  • similar: Vantage-point tree
  • implemented in: 'sklearn.neighbors.BallTree'
  • algorithms for construction: 'Five Balltree Construction Algorithms'

Winged edge

Adjacency list

Incidence matrix

R-tree

R+ tree

R* tree

Hash tree

Hash array mapped trie

Merkle tree

Generalized suffix tree

Disjoint-set data structure

  • also called: 'union–find data structure'
  • https://en.wikipedia.org/wiki/Disjoint-set_data_structure
  • book: 'Introduction to Algorithms'
  • is a: 'Multiway tree'
  • applications: connected components of an undirected graph
  • implemented in: 'boost::graph::incremental_components'
  • used for: 'Kruskal's algorithm'

HAT-trie

  • paper: 'HAT-trie: a cache-conscious trie-based data structure for strings' (2007)
  • https://en.wikipedia.org/wiki/HAT-trie
  • implemented in: 'Python pytries/hat-trie'
  • implements: 'Ordered map'
  • variant of: 'Radix tree'
  • properties: 'cache friendly'

Double-Array Trie

  • also called: 'DATrie'
  • paper: 'An Efficient Digital Search Algorithm by Using a Double-Array Structure' (1989)
  • implemented in: 'pytries/datrie', 'libdatrie'

Ternary search tree

  • also called: 'TST'
  • paper: 'Fast algorithms for sorting and searching strings' (1997)
  • https://en.wikipedia.org/wiki/Ternary_search_tree
  • type of: 'Trie'
  • applications: 'Nearest neighbor search', 'spell-checking', 'auto-completion'
  • implements: 'Map'

Hierarchical Navigable Small world graphs

  • also called: 'Hierarchical NSW', 'HNSW'
  • paper: 'Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs' (2018) https://doi.org/10.1109/TPAMI.2018.2889473
  • applications: 'Approximate nearest Neighbor Search'

Corner Stitching

  • paper: 'Corner Stitching: a Data Structuring Technique for VLSI Layout Tools (1982)'
  • applications: 'Very Large Scale Integration'

Difference list

Soft heap

Binomial heap

Brodal queue

Bloom filter

  • paper: 'Space/time trade-offs in hash coding with allowable errors (1970)'
  • https://en.wikipedia.org/wiki/Bloom_filter
  • properties: 'probabilistic'
  • implements: 'Set'
  • applications: 'caching strategies', 'database query optimization', 'rate-limiting', 'data synchronization', 'chemical structure searching'
  • is a: 'probabilistic data structure'

Count–min sketch

Optimal binary search tree

Order statistic tree

  • https://en.wikipedia.org/wiki/Order_statistic_tree
  • variant of: 'Binary search tree'
  • additional interface: find the i'th smallest element stored in the tree, find the rank of element x in the tree, i.e. its index in the sorted list of elements of the tree

Exponential tree

Log-structured merge-tree

Wavelet tree

GADDAG

  • paper: 'A faster scrabble move generation algorithm' (1994)
  • https://en.wikipedia.org/wiki/GADDAG
  • uses: 'Directed acyclic graph'
  • applications: 'Scrabble'
  • implemented in (applications): 'Quackle'

BD-tree

MD-tree

  • also called: 'Multidimensional tree'
  • original paper: 'A Balanced Hierarchical Data Structure for Multidimensional Data with Highly Efficient Dynamic Characteristics' (1993)
  • properties: 'height balanced'

Bounded deformation tree

Chord

Kademlia

  • paper: 'Kademlia: A Peer-to-Peer Information System Based on the XOR Metric (2002)'
  • https://en.wikipedia.org/wiki/Kademlia
  • is a: 'Peer-to-peer distributed hash table', 'Protocol'
  • uses: 'xor metric'

Koorde

  • paper: 'Koorde: A Simple Degree-Optimal Distributed Hash Table (2003)'
  • https://en.wikipedia.org/wiki/Koorde
  • is a: 'Peer-to-peer distributed hash table', 'Protocol'
  • based on: 'Chord'
  • uses: 'De Bruijn graph'

G-Counter

PN-Counter

G-Set

  • also called: 'Grow-only Set'
  • is a: 'Conflict-free replicated data type'

2P-Set

  • also called: 'Two-Phase Set'
  • is a: 'Conflict-free replicated data type'

LWW-Element-Set

  • also called: 'Last-Write-Wins-Element-Set'
  • is a: 'Conflict-free replicated data type'
  • implemented in: 'soundcloud/roshi'

OR-Set

  • also called: 'Observed-Removed Set'
  • is a: 'Conflict-free replicated data type'

Index data structures

Inverted index

n-gram index

  • applications: 'indexed regex queries'
  • common variant: '3-gram index'
  • used by: 'Google Code Search'

Sparse index

FM-index