Reduction 1

Loading...

來自 University of California San Diego 的課程

Advanced Algorithms and Complexity

291 個評分

University of California San Diego

Advanced Algorithms and Complexity

291 個評分

課程 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

So we would like to solve the heavy hitters problem in a data stream.

So once you design a small space data structure,

you can scan a stream of data items, i1, i2 through iN.

And at the end of the stream, output the k most frequent items that occurred.

We also want this data structure to have a small space complexity.

We want space requirements at most, order k log N.

Well formally, we would like to design a small space

data structure that solves the following problem.

We call it FindTop.

FindTop scans an input stream S of items, and has a parameter k in hand.

At the end of the stream,

it outputs the top k most frequent items that it saw in this tree.

Well it turns out to be useful to first design a primitive for

the following related problem.

We call it PointQuery.

PointQuery is a small space data structure hopefully, that scans the stream S.

And at the end of the stream gets a query i.

i is a data item.

And in response, outputs the frequency fi.

That is the number of terms that i occurred in the stream.

Well for simplicity, we'll assume that the data items are ordered in descending order

of their current frequency of occurrence in the stream.

So, item one is the most frequent item.

Item two is somewhat less frequent, etc., etc.

What we want to design is a data structure that can solve PointQuery,

scan the stream, and then answer queries at the end.

And we want this data structure to use small space,

space on the order of k log N.

Where k is the number of items we will be ultimately looking for in the stream.

Well unfortunately this turns out to be impossible in general.

And this is because, as stated, we require this PointQuery and

FindTop to output exact answers.

Well, imagine a stream where every data item occurs with

roughly the same probability, or rather roughly the same frequency.

It seems very hard to design a small space data structure to figure out

which items were exactly the top k.

And this can be proved formally that one essentially needs to store

the entire stream.

So what we definitely need is a notion of approximation

if we want to get sublinear space complexity.

To that effect, we define the following approximate version of the problem.

We call it find approximate top.

So this has two parameters k, the number of items that we're looking for,

and the precision parameter epsilon.

At the end of the stream, this procedure needs to return a set of k elements,

such that for every data item i that we report at the end of the stream,

the frequency that i occurred within the stream is not much smaller

than the frequency of the actual kth most frequent element.

So fi should be at least (1- epsilon)fk,

where fk is the number of times the kth most frequent element occurred.

And now again it turns out to be very useful to design a procedure for

the following approximate version of the PointQuery problem.

So here we want to scan the stream.

At the end of the stream, if given a query i, we want to report an approximation

at hat i to the number of times item item i occurred in the stream.

This approximation should be off by at most an additive epsilon fk term.

Or again, if k is the number of times, the kth dominant element occurred.

Okay, so this looks better.

At least we have a notion for approximation.

Now unfortunately, as stated, this is still a hard problem.

And indeed, if we still imagine a stream where all the items occur roughly with

the same frequency, maybe up to 1 plus minus epsilon,

this is still a hard problem to solve.

One essentially needs to store most of the stream.

So in fact, in this lecture, we will design a small space primitive for

both of these problems.

That will allow us to find these top k elements,

top k most frequent elements in the stream,

assuming that they actually contribute a bulk of the stream in a certain sense.

And we will see the formal formulation of what this means to

contribute the bulk of the stream later in this lecture.

探索我們的目錄

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

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

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

通過 App Store 下載

通過 Google Play 獲取