Analytics Vasiliki (Vasia) Kalavri
 vkalavri@bu.edu Spring 2020 4/23: Cardinality and frequency estimation ??? Vasiliki Kalavri | Boston University 2020 Counting distinct elements 2 ??? Vasiliki probability • Counter overestimation is almost certain for very large data streams with high-frequency elements Counting Bloom Filter ??? Vasiliki Kalavri | Boston University 2020 20 • A space-efficient 6 2 3 2 2 9 7 3 0 5 8 5 0 9 0 … ??? Vasiliki Kalavri | Boston University 2020 23 Estimating frequency 0 0 0 6 9 3 3 1 5 0 0 3 8 2 7 9 m counters h1 h2 hp 3 0 0 3 0 5 8 2 0 0 2 9 2 4 5 2 7 6 2

subgraph of G with fewer edges and the same set of vertices: . E(H) ⊆ E(G), V(H) = V(G) Distance estimation ??? Vasiliki Kalavri | Boston University 2020 48 A k-spanner is a graph synopsis that preserves

tuples from the dataset • Providing an estimate via a sample can be much more expensive than estimation via other methods: • Evaluating a query over a 5% sample of a dataset may take 5% of the time

δ*N, where N is the number of stream elements • The solution will not contain any item y with frequency: • freq(y) < (δ - ε)*N, for a user-chosen value ε
 4 (δ - ε)*Ν δ*Ν not included may be included true frequency of the item e in the input stream f: estimated frequency of item δ: user-defined threshold, so that freq(x)≥ δ*N,δ∈(0,1) ε: user-defined error
 Output: All items with frequency greater greater than or equal to δ*N. No item with frequency less than (δ-ε)*N. 5 ??? Vasiliki Kalavri | Boston University 2020 Notation (II) • We define windows of size w = 1/ε with increasing numeric ids

▶ countByValue • Returns a new DStream of (K, Long) pairs where the value of each key is its frequency in each RDD of the source DStream. 23 / 79 Transformations (4/4) ▶ reduce • Returns a new DStream ▶ countByValue • Returns a new DStream of (K, Long) pairs where the value of each key is its frequency in each RDD of the source DStream. 23 / 79 Transformations (4/4) ▶ reduce • Returns a new DStream ▶ countByValue • Returns a new DStream of (K, Long) pairs where the value of each key is its frequency in each RDD of the source DStream. 23 / 79 Window Operations (1/3) ▶ Spark provides a set of

URL access frequency (k2, list(v2)) → list(v2) (k1, v1) → list(k2, v2) map() reduce() 25 ??? Vasiliki Kalavri | Boston University 2020 MapReduce combiners example: URL access frequency 26 map() com, 1 ??? Vasiliki Kalavri | Boston University 2020 MapReduce combiners example: URL access frequency 27 map() reduce() GET /dumprequest HTTP/1.1 Host: rve.org.uk Connection: keep-alive Accept:

• Monitor cell tower load • Continuously maintain call signatures for fraud detection • call frequency • top-K cell towers used 25 Vasiliki Kalavri | Boston University 2020 Web activity analysis

Vasiliki Kalavri | Boston University 2020 Traditional DW vs. SDW Traditional DW SDW Update Frequency low high Update propagation synchronized asynchronous Data historical recent and historical ETL