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.


Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s


%d bloggers like this: