Streams Course Blog

A quick survey of graph mining

Posted in Uncategorized by amitc1 on November 18, 2009

We have now seen a number of algorithms for processing “graph streams.” This quick survey by McGregor is a great resource collecting together many state-of-the-art results (as of 2008). Thanks to Joe Cooley for bringing this to my attention.

Advertisements

Next homework

Posted in Uncategorized by amitc1 on November 13, 2009

The next homework set has been posted to the course website. Four problems as usual. This set builds on quite a few of the techniques we have learnt so far, so there’s going to be considerable work involved. Those taking the course for credit are urged to begin working on these problems right away.

Tagged with:

Notes further updated

Posted in Uncategorized by amitc1 on November 12, 2009

The lecture notes have been updated some more. Thanks to all who have provided me timely scribe notes. Please read what other scribes have written and if this gives you ideas for improving your own notes, please send me a new version of your notes. It would be most welcome.

Tagged with:

Homework review

Posted in Uncategorized by amitc1 on November 3, 2009

I plan to spend a good portion of the Nov 3 lecture discussing the homework, including some of HW1. Non-creditors might want to arrive mid-way into tomorrow’s class. We won’t start the planned material for the class (algorithms for matching) until 11:05am.

LaTeX reference

Posted in Uncategorized by amitc1 on November 1, 2009

No matter what your level of expertise with LaTeX, I think you will find this wikibook to be a useful reference or guide. Scribes, especially, take note!

References galore

Posted in Uncategorized by amitc1 on October 30, 2009

The last few lectures have covered algorithms for which the best reference remains the original research paper describing the algorithm. Here are the relevant pointers, collected. If I have forgotten to add a reference for a result recently covered in class, please notify me and I’ll update this post.

For future work (including homework problems), do not be scared to dig into these papers, if you need to understand one of these algorithms at a deeper level than we managed to cover in class.

Tagged with:

New homework is up

Posted in Uncategorized by amitc1 on October 22, 2009

Homework 2 is ready and is now available on the course website. This one is 100% about designing algorithms, and it is designed to get you thinking more deeply about what you have learned so far and coming up with creative solutions.

Start brainstorming ASAP, for these problems will not be solved in one sitting. You’ll need to sleep over them a couple of times and let the necessary ideas come to you over time.

X-hour update

Posted in Uncategorized by amitc1 on October 20, 2009

Just a heads-up that we will be using the X-hour, 3:00-4:10pm, next Wednesday (Oct 28). Also, Amit will be out of town next Tuesday (Oct 27), so we will not have regular class. Instead, you can use the opportunity to discuss HW2 with Chrisil.

Reference for today’s lecture

Posted in Uncategorized by amitc1 on October 15, 2009

Today’s lecture was more technically heavy than usual. I hope it didn’t bring back any “calculus nightmares” for anyone! In any case, here is Indyk’s paper, which includes the algorithms and ideas we discussed today, plus quite a bit more.

We’re not quite done discussing all the higher-level issues raised by this, and some other recent algorithms we have seen. Next Tuesday, I want to spend approximately the first half discussing these things, and then the second half talking about the MEDIAN problem. As you’ll note, we’re continuing to tweak the lecture plan slightly as we go. For instance, today we ended up discussing stable distributions earlier than planned.

More lecture notes

Posted in Uncategorized by amitc1 on October 15, 2009

I have added a new chapter to the lecture notes, which covers the Flajolet-Martin DISTINCT-ELEMENTS algorithm. I also made small tweaks to the earlier parts. As always, the link from the course website will get you to the latest version of the notes.

Please notify me if you find any typos or errors in the notes. With 20-odd eagle-eyed readers reading these, it would be a shame if something got away!

The LaTeX sources to these notes have been distributed (by email) to all registered students, who can use them while scribing. If you are a registered student and did not get my email about this, please notify me at once.