Sketches :
cash-register, always >= 0
turnstile, most general case
time-series, replace old value

landmark => keep everything
sliding window, decay model( => importance decreases)

time / number of updates
requirements : single pass, small space, real-time (and delete proof, composable)

CS422 sketch => nothing interesting
Bloom filter => m x k, no removal, can be upgraded to counting bloom filters, which support removal
Count Min Sketch => w x d, weight always positive, estimate by taking min of all slots, easily composable (same dim and hash functions)
Dydactic intervals, max 2Log2(n) queries

Sliding / Jumping windows

exponential histograms : estimate = (1 +- epsilon) * answer
at most k/2 + 1 and at least k/2 buckets of the same size (except for last one), k = 1/epsilon

Column store :
virtual / explicit ids
Write Optimized Storage : keep updates in RAM, flush batches
Jive Join
Aggregates => simply hash key and 'merge' results
Compression => RunLengthEncoding, BitVectorEncoding, Dictionary, Frequency partitioning (1 dic per page)
Simple operations over compressed data
Late(=> faster, less IO) / Early(=> access only once, need to store all intermediary results, which can be useless) materializations
Redundant representations => named "projection"
Cracking => adaptive indexing, by product of queries, continous
Vectorized processing => next() operator returns a vector of tuples, better cache, better CPU utilization
Row store => better updates, Column => better queries
H2O => create groups of columns for attributes accessed together

Data warehouse and Decision Support System
OLTP : On-Line Transaction Processing => traditional DB
DSS : long running queries over all (static) data
OLAP : On-Line Analytic Processing => complex queries (aggregates and group by)
Data warehousing : great volume, static
Need to remove noise, different source formats, keep sources (metadata), queries complex to describe and optimize => one may not know what he wants
Multidimensional data model => Fact table, Dimension tables, dimension hierarchies
RollUp, DrillDown, Pivoting (= cross tabulation)
Slicing = adding range on dimensions => multiple slices create dices, Cube => compute all combinations
Bitmap indexes
Views : 2 types => computed on demand (Like adding an alias in unix-style systems), materialized (more or less a special table, but need to maintain them => lazy, periodic, forced (after a certain number of update, update table))
Top-N => need scoring function => FAIL
Skyline queries => comparison of attributes, only remove tuples that are dominated by others
Algorithms => nested loop, block nested loop, divide and conquer

Big Data - scale out
5Vs => Volume, Velocity, Variety, Variability, Veracity
MapReduce / Dataflow
Architecture => Distributed File System(hidden to user), Processing Engine, and Programming Languages
HDFS => partition files into blocks (replicated at some nodes) => lots of IO
RDD => exploit RAM as much as possible, immutable, lazily evaluated, replicated (contain data & history)
MapReduce prog model => everything is <key, value> => 2 fcts : Map(key, value), and Reduce(key, listValues)
In practice, Map and Reduce phases overlap
Master Slave archi => namenode and datanode
Transformations (ex map) create new RDDs (lazily), Actions (ex : count, collect (collects and shows the RDD), save (writes RDD))
Move code to the data, FIFO schedulers, Fair scheduler (all jobs => same time), Capacity scheduler (all users => same time), Delay scheduler (wait until you decide to move the data)
Optimizations, HadoopToSQL => transform in SQL, then use sql optimizer, Spark => fully exploit lazy evaluation
DryadLINQ : decompose UDF in associative decomposable
Data locality
Speculate that some nodes will take a really long time, and transfert the data to other noes or use existing replications and start the task => take the first that finishes
Resource Management
Job recovery in map reduce => intermediary results saved in replicated files
RDD => resilient & keep track of history

Big Data - systems and algorithms
Spark SQL => add schema to RDDs and SQL syntax
Dataframe ~= Structured RDD, can be created from RDD, relational table (can keep indexes on them), csv ...
can create UDF that can be used in SQL
Optimizations : declarative language, lazy, code generation
Users queries represented using AST
1st Step : analysis : verify types, map attributes to input
2nd Step : logical = optimizer in relational DB
3rd Step : choose algo for operators (ex joins), use indexes
4th Step : generate bytecode
Rules to optimize ASTs (compilo), first filter, and then join, optimize batch as a whole
Optimize UDFs => create UDAFs : init, update, merge, evaluate
Approximations : BlinkDB, supports standard queries + desired accuracy + confidence + desired performance
Uniform (same weight) or Stratified (fixed number per category) samples
Recovery => replication(duplicate => expensive + fast), upstream backup(=> cheap + slow)
Chop the task into small micro batches (a few seconds)
DStreams (Discretized Streams) => sequence of RDDs