Found in
analytics
Articles
SYS
Data structure
Count-Min Sketch
Frequencies of stream items in fixed memory: the minimum of d counters, with an error only upwards.
O(d) per item and per query
2 problems
SYS
Data structure
HyperLogLog
The number of distinct elements of a stream in a kilobyte of memory: long runs of zeros in hashes and an average over registers.
O(1) per element, O(m) per estimate
2 problems
ML
Algorithm
k-means
Splits points into k groups so that points sit close to the centre of their group.
O(n · k · d) per step
2 problems
ML
Algorithm
DBSCAN
Gathers dense regions of points of any shape into clusters and marks lone points as noise.
O(n·Q + Σ|N(p)|)
2 problems
ML
Algorithm
Decision tree
Answers with a chain of questions “feature ≤ threshold?”; each question is chosen so that uncertainty falls the most.
O(h · F · n log n) to build; O(h) to answer
2 problems
Problems
Often together
hashing 3 classic 3 interviews 3 sketch 2 streaming 2 probabilistic 2 in production 2 clustering 2 points 2 science and physics 2 frequencies 1 networks 1