I begin with a brief read of some lecture notes about Streaming Algorithms. The links to the documents are also added for completeness. I have only read the first couple of chapters of these to get an idea into thought processes and styles in this field.
Lecture Notes by Muthu Muthukrishna
http://www.cs.mcgill.ca/~denis/notes09.pdf
Talks initially about some streaming algorithms; estimating the minimum frequency item in a stream. Hash functions seem prevalent in this field so will need some work, and also some probability in the analysis of bounds. Will need to do a bit of work on these two aspects (particularly hashing) if I continue down this path.
Then talks about counting elements in a stream, again using hashing. Very good.
Lecture Notes from Dartmouth
http://www.cs.dartmouth.edu/~ac/Teach/CS85-Fall09/Notes/lecnotes.pdf
Gives a more precise model of computation for streaming algorithms.
Lecture from Stanford
http://theory.stanford.edu/~rajeev/cs361.html#read-massive
Starts with naive approach, and discusses memory issues when you stream data. The lecture notes above explain this all a bit better really, but I read it so the link is here.
Lectures (and paper) from Wisconsin
http://pages.cs.wisc.edu/~shuchi/courses/787-F07/
First of these lectures (17) just recaps briefly on model including frequency moments, and then moves to counting distinct elements (continued in Lecture 18). Median of means to take result after many trials.
Paper is the book below.
Book by S. Muthukrishnan
http://scholar.google.co.uk/scholar?hl=en&q=Data+Streams%3A+Algorithms+and+Applications&btnG=Search&as_sdt=0%2C5&as_ylo=&as_vis=1
Applications and motivations for the thoughts.
No comments:
Post a Comment