University:
Amherst College
Course:
COSC 257 | Databases
Academic year:

2021
Views:

319

Pages:

26
Author:

theewokf6v

Data Stream Algorithmics Finding out more about me… Type in Adorisms Lezione 1 Overview • Sublinear Methods: – Sublinear time – Sublinear space – Streaming. • Data Stream Algorithms – Model – Applications • Rest of the course Sublinear Time • Problem: – Given distinct integers A[1,..,n], determine a number in their top half in sorted rank. • Algorithm: – Pick k numbers uniformly randomly. Determine their MAX and return as the solution. • Analysis: – Probability that the solution is incorrect is the prob that all k sampled numbers are in the lower half which is at most (1/2)^k. To get prob of error δ, uses log (1/δ) samples. MIN or MAX is hard using this method. Psuedo-Sublinear Space: Lights out puzzle • One switch initially in OFF position in a room. People 1, …, n each in different rooms. • Paul picks people to go into the switch room: – Randomly – Each is unaware of everyone else. • Goal: Design a protocol so someone can declare when everyone has been into the switch room at Solution: least once. – 1 common bit, – log n bits with the leader, Sublinear Space: Metric Embeddings • Space of objects A with distance C(.,.) and space B with distance D(.,.). • Consider mappings f : PA → PB Contraction & • For any p, q in PA Expansion (1 / l ) C ( p, q ) ≤ D( f ( p ), f (q )) ≤ u C ( p, q ) • Often, f is linear, f is oblivious. • Say A and B are L_p norms in dimension d and d’ resp. d’< retrieve each item precisely. Lezione 1 Overview • Sublinear: – Sublinear time – Sublinear space – Streaming. • Data Stream Algorithms – Model – Applications • Rest of the course and Details Rest of the course • Sketches: AMS, CCC, CM. Relationship to embeddings, k-wise ind. rv’s. • Heavy Hitters: Manku+Motwani, CM, Deltoids. (Non) adaptive Code construction. • Quantiles: Rangesum rv, GK, CM, Other statistical quantities eg histograms, wavelets. • Distinct Elements: stable distributions. FM. • Inverse distribution: Summarizing. Rarity. Minwise hashing. Maximum likelihood methods MLE/EM. Rest of the course • Advanced topics – – – – – Semi-streaming and graph algorithms. Streaming geometry problems. Streaming text processing problems. Clustering and facility location Property testing, privacy-preserving data mining, etc.

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock