Final Algorithm 2

Loading...

來自 University of California San Diego 的課程

Advanced Algorithms and Complexity

202 個評分

University of California San Diego

Advanced Algorithms and Complexity

202 個評分

課程 5（共 6 門，Specialization 数据结构与算法）

You've learned the basic algorithms now and are ready to step into the area of more complex problems and algorithms to solve them. Advanced algorithms build upon basic ones and use new ideas. We will start with networks flows which are used in more typical applications such as optimal matchings, finding disjoint paths and flight scheduling as well as more surprising ones like image segmentation in computer vision. We then proceed to linear programming with applications in optimizing budget allocation, portfolio optimization, finding the cheapest diet satisfying all requirements and many others. Next we discuss inherently hard problems for which no exact good solutions are known (and not likely to be found) and how to solve them in practice. We finish with a soft introduction to streaming algorithms that are heavily used in Big Data processing. Such algorithms are usually designed to be able to process huge datasets without being able even to store a dataset.

從本節課中

Streaming Algorithms (Optional)

In most previous lectures we were interested in designing algorithms with fast (e.g. small polynomial) runtime, and assumed that the algorithm has random access to its input, which is loaded into memory. In many modern applications in big data analysis, however, the input is so large that it cannot be stored in memory. Instead, the input is presented as a stream of updates, which the algorithm scans while maintaining a small summary of the stream seen so far. This is precisely the setting of the streaming model of computation, which we study in this lecture. The streaming model is well-suited for designing and reasoning about small space algorithms. It has received a lot of attention in the literature, and several powerful algorithmic primitives for computing basic stream statistics in this model have been designed, several of them impacting the practice of big data analysis. In this lecture we will see one such algorithm (CountSketch), a small space algorithm for finding the top k most frequent items in a data stream.

Introduction5:23

Heavy Hitters Problem7:33

Reduction 14:35

Reduction 26:30

Basic Estimate 18:04

Basic Estimate 27:14

Final Algorithm 15:27

Final Algorithm 212:57

與講師見面

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

Well, we're now in a position to state the final algorithm for

a proximal point query and hence the count sketch algorithm.

The algorithm proceeds by first choosing two parameters.

We choose the parameter t which is the number of repetitions of the hashing

scheme that we'll perform to boost the confidence of our estimates.

And one should think of t as logarithmic in the length of the stream.

We will set these parameters later in this lecture.

The other parameter is b,

which is the number of buckets that we will hash our universe of data items into.

And b should be thought of as a large constant times k,

the number of heavy hitters that we would like to approximately find.

So the algorithm starts by selecting t uniformly random hash functions that map

our universe of data items into b buckets.

And also, t uniformly random sign functions that associate uniformly

random signs with every data element in our universe.

Now this can be conveniently visualized as an array C shown on the slide.

This array contains t rows, corresponding to the t independent repetitions,

will index the rows by a parameter r, little r.

And b columns, every column corresponds to a hash bucket

Now the pseudo code for the algorithm is as follows.

The algorithm will maintain this array C of numbers, of counters and

every cell in the array C will correspond to an invocation of

the basic approximate point query primitive that we just designed.

Specifically, the update process looks like this.

During a data item C, data item i, we run over all the rows r from 1 to t.

And for each row r, we use the rth hash function

to figure out the column that our element i has to contribute to.

And we increment the corresponding counter, that is,

the cell in r throw and H of ith column,

by the sign that the sign that the rth sign function assigns to our element i.

Now the pseudocode is given on the slide and

it should be noted that this simply amounts to running for

each row r our simple approximate point query primitive that we just designed

on the stream of data items that hashed into the same bucket as i itself.

Okay, so this is the update process.

Now the estimation process works as follows.

At the end of the stream, if we are given an item i whose frequency we want

to approximate, what we do is we run over all the r rows in our hash table.

And for each row, we take the product off the counter

in row r, and the column that I hash to with a sine of r,

under the r sine function, which is exactly the estimator that we designed for

our basic approximate point query primitive.

Except that now we have r independent copies of these approximate primitives,

and we take the median of the answers at the output as the final result.

So for example, the data item 5 hashes into three distinct

buckets in every of the three rows of array C shown on the slide.

So it will contribute to these three buckets when we

perform the update process.

And then the answer will be computed as a median of the three

values found in these buckets, multiplied by its sine.

Okay, well, this is the algorithm.

Now the question is why does this algorithm provide precise estimates for

every single item in the stream with high probability.

Well, the first observation here is that, by our previous analysis of the basic

estimation primitive, basic version of approximate point query a few slides back,

the mean of every of these t estimators that we use,

that we take the median of in our new version, is exactly correct.

The mean of every of these estimators,

for every r between 1 and t, is exactly the frequency of the i'th item.

Okay, well, this is reassuring, but as of now this doesn't mean that

our algorithm is any better than the basic primitive that we designed before.

The distinguishing factor comes in the variance of our estimate.

Recall that the variance of the basic primitive that we designed before

was equal to the summation over all data items j that were different from i of

the frequency of the jth item squared.

Now it is possible to show that the variance of our new estimator

is the summation only over those data items j different from i that

hashed to the same bucket as i of their frequency squared.

Now our hash functions map the data items to b buckets, so we

should expect the variance to be a factor of one or will be smaller than before.

And indeed, it is possible to prove that this is the case.

Now what this means is that if we choose the number of buckets that we hash

into to be sufficiently large, we can drive the standard deviation of

every of those t estimates to blow our precision parameter epsilon times

the frequency of the kth most frequent item, fk.

Now this is exactly the additive precision of our estimates that we're shooting for

for our approximate pointquery primitive.

So choosing the number of buckets large enough fixes the precision issue.

Now we also have to ensure that our estimates work with high probability for

all data items, and this is what we fix by taking medians of algorithmic

number of independent estimates.

Okay, so the formal statement about the position and

success probability of our scheme is given by the following lemma.

This lemma says that if we choose the number of buckets to hash into to be at

least the following quantity, which is the maximum of two numbers, well,

first the number of buckets has to be bigger than a large constant times k,

which is the number of heavy hitters that we're shooting for approximating.

At the same time,

it also should be larger than our large constant times the following ratio.

This ratio of the l2 squared norm of the frequencies of the tail of the stream,

divided by epsilon squared,

times the frequency of the kth largest element squared.

Okay, so if the number of buckets b is chosen to be sufficiently large

in the following way, and if we choose the number of repetitions

of our hashing scheme to be logarithmic in the length of the stream,

then we have that our median estimator is at most epsilon times fk far from

the true answer for every data point i and from every position in the stream.

Okay, now this is exactly the additive precision that we wanted to get,

and it remains to understand what our sample complexity is.

Now recall that the algorithm stores this array C which has t rows and b columns.

Now the parameter t was chosen to be logarithmic in n, and the parameter b,

however, depends in non-trivial ways on the actual structure of the stream.

So now the question is, how large is b?

This is possible to show that for every stream,

b is on the order of k over epsilon squared, for example.

This would be very nice.

Now unfortunately, this is not true.

Indeed, imagine a stream where every item appears exactly once.

Then all of the fjs are exactly 1 and we get that we

need to set b to be omega of n over epsilon squared.

Okay, now this is really terrible because in space order

n we could have stored the entire stream anyway and solved the problem exactly.

However, note that in the importance case where the stream is actually dominated

by the top k elements, b turns out to be very small.

Specifically, suppose that if we sum the frequency squared over all the elements

jamming the tail of the signal, or rather of the stream, and divide this by k.

So think of summing the squared frequencies over the tail of the stream,

and then spreading this equally among the top k elements, the heavy hitters.

And if this turns out to be on the order of the frequency squared of the kth

largest element, then hashing into b on the order of k over epsilon

squared buckets turns out to be sufficient to find the heavy hitters.

And this is exactly the sense in which we

said that we were going to solve the problem for

streams where heavy hitters dominate the stream in a certain sense.

And the actual formal sense is the l2 sense shown on this slide.

Now of course, in practice we don't know what the stream looks like, so

we cannot choose b according to this formula.

What we can do, though,

is choose b as large as possible subject to space constraints because hashing into

more buckets only improves the precision guarantees of our l.

Okay, so now I would like to spend a little bit more time talking about

the number of buckets that we have to hash into and showing that actually

this number is surprisingly small for some very interesting cases.

And for simplicity let's think of k equal to 1.

That is, we have a stream and

we want to find the most frequent element in the stream.

Now suppose further that this most frequent element,

and by our assumption it's element one, appears square root N times in the stream.

And all the other elements appear exactly once.

So they're N minus root N elements in the tail of this tree.

Okay, so now this means that f1 is equal to square of N, and for

every i between 2 and N minus root N, fi equals exactly 1.

So all of the other elements appear once.

Now, the lemma shows that if we set b to be the following quantity,

the sum of frequency squared over the tail of the signal,

divided by epsilon squared, fk squared, then we're able to find our heavy hitter.

Now all the fjs in the tail of the signal are one, so

the summation of their squares is bounded by n.

On the other hand, f1 is equal to root N, so f1 squared is N as well.

Now what this means is that setting b to be a constant divided by epsilon squared

suffices to find our heavy hitter, the most frequent element in the stream.

And I would like to stress that this a very remarkable result.

because if we think about this, the element 1, that is,

the heavy hitter, appears only in square root N positions in the stream.

So that's a vanishingly small number of positions.

If we were to sample a constant number of locations we would never see this element.

This means that the algorithm that we have just constructed is quite powerful.

Okay, well, to summarize, we started this lecture

with the goal of designing a small space data structure that can scan a stream of

data items arriving one after another, maintain a small amount of space.

And at the end of the stream,

output an approximation to the top k most frequent coefficient scene in the stream.

We showed that this problem can reduce to the problem of designing

a different data structure which we'll call approximate point query.

This data structure, again, uses a very small amount of space,

scans the stream of data items one after another.

And at any point, this data structure can be stopped and asked to return a good

approximation to the number of times any given data item has been seen so far.

Now we gave a very powerful primitive for the approximate pointquery data structure.

It gives very precise estimates with high probability for all data items.

Now this primitive also uses a small amount of space on the order of k log N,

assuming that the top k elements actually dominate the stream in a certain l2 sense.

Now putting these two pieces together gives us the CountSketch algorithm.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2018 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取