Algorithms for Big Data Lecture Notes (Harvard CS229r)
需积分: 10 195 浏览量
2017-03-07
17:49:19
上传
评论
收藏 4.95MB PDF 举报
CS 229r: Algorithms for Big Data Fall 2015
Lecture 1 — September 3, 2015
Prof. Jelani Nelson Scribes: Zhengyu Wang
1 Course Information
• Professor: Jelani Nelson
• TF: Jaros law B lasiok
2 Topic Overview
1. Sketching/Streaming
• “Sketch” C(X) with respect to some function f is a compression of data X. It allows
us computing f(X) (with approximation) given access only to C(X).
• Sometimes f has 2 arguments. For data X and Y , we want to compute f(X, Y ) given
C(X), C(Y ).
• Motivation: maybe you have some input data and I have some input data, and we want
to compute some similarity measure of these two databases across the data items. One
way is that I can just send you the database, and you can compute locally the similarity
measure, and vise versa. But image these are really big data sets, and I don’t want to
send the entire data across the wire, rather what I will do is to compute the sketch of my
data, and then send the sketch to you, which is something very small after compression.
Now the sketch C(X) is much smaller than X, and given the sketch you can compute
the function.
• Trivial example: image you have a batch of numbers, and I also have a batch of numbers.
We want to compute their sum. The sketch I can do is just locally sum all my input
data, and send you the sum.
• Streaming: we want to maintain a sketch C(X) on the fly as x is updated. In previous
example, if numbers come on the fly, I can keep a running sum, which is a streaming
algorithm. The streaming setting appears in a lot of places, for example, your router can
monitor online traffic. You can sketch the number of traffic to find the traffic pattern.
2. Dimensionality Reduction
• Input data is high-dimensional. Dimensionality reduction transforms high-dimensional
data into lower-dimensional version, such that for the computational problem you are
considering, once you solve the problem on the lower-dimensional transformed data, you
can get approximate solution on original data. Since the data is in low dimension, your
algorithm can run faster.
• Application: speed up clustering, nearest neighbor, etc.
1
剩余148页未读，继续阅读
资源评论
