Posted by: atri | April 23, 2010

Lecture 40: Hot Items Problem

In Wednesday’s lecture, we saw a data stream algorithm for the “hot items” problem based on group testing due to Cormode and Muthukrishnan. We saw that the existing strongly explicit construction of d-disjunct matrix based on Reed-Solomon codes (see lecture 29) was enough to give three out of the four things we wanted in our algorithm:

  • One pass
  • Poly-log space
  • Poly-log update time.

The only missing part was poly-log reporting time, which we tackled in Friday’s lecture.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: