CS345A, Winter 2009: Data Mining.

Course Info | Handouts | Assignments | Project | Course Outline | Resources and Reading

Course Information

NEW NEW ROOM: 200-002. This is the big auditorium in the basement of the History Corner. It seats 163, so there should be plenty of room for us to spread out.

Instructors: Anand Rajaraman (anand @ kosmix dt com), Jeffrey D. Ullman (ullman @ gmail dt com).

TA: Anish Johnson (ajohna @ stanford dt edu).

Staff Mailing List: cs345a-win0809-staff@mailman.stanford.edu

Meeting: MW 4:15 - 5:30PM; Room: History Corner basement 200-002.

Office Hours:
Anand Rajaraman: MW 5:30-6:30pm (after the class in the same room)
Jeff Ullman 2-4PM on the days I teach, in 433 Gates.
TA: Anish Johnson Tuesdays: 9:15-10:45am in B26A Gates
Thursdays: 1-3pm in B24B Gates

Prerequisites: CS145 or equivalent.

Materials: There is no text. However, if you have the second edition of Database Systems: The Complete Book (Garcia-Molina, Ullman, Widom), you will find Section 20.2 and Chapters 22 and 23 relevant. Slides from the lectures will be made available in PPT and PDF formats.

Students will use the Gradiance automated homework system for which a fee will be charged. Note: if you already have Gradiance (GOAL) privileges from CS145 or CS245 within the past year, you should also have access to the CS345A homework without paying an additional fee. Notes and/or slides will be posted on-line.

You can see earlier versions of the notes and slides covering Data Mining. Not all these topics will be covered this year.

Requirements: There will be periodic homeworks (some on-line, using the Gradiance system), a final exam, and a project on web-mining. The homework will count just enough to encourage you to do it, about 20%. The project and final will account for the bulk of the credit, in roughly equal proportions.


DateTopicPowerPoint SlidesPDF Document
1/7Introductory Remarks (JDU)PPTPDF
1/7Introductory Remarks (AR)PPTPDF
1/14Frequent Itemsets 1PPTPDF
1/14-1/21Frequent Itemsets 2PPTPDF
1/16Peter Pawlowski's Talk on Aster DataPPTXPDF
1/16Nanda Kishore's Talk on ShareThisPPTPDF
1/26Recommendation SystemsPPTPDF
1/28Shingling, Minhashing, Locality-Sensitive HashingPPTPDF
2/2Applications and Variants of LSHPPTPDF
2/2-2/4Distance Measures, Generalizations of Minhashing and LSHPPTPDF
2/4High-Similarity AlgorithmsPPTPDF
2/11Link Spam, Hubs & AuthoritiesPPTPDF
2/18Generalization of Map-ReducePPTPDF
2/23Streaming DataPPTPDF
2/25Relation ExtractionPPTPDF
3/2On-Line Algorithms, Advertising OptimizationPPTPDF
3/4Algorithms on StreamsPPTPDF


There will be assignments of two kinds.

Gradiance Assignments

Some of the homework will be on the Gradiance system. You should go there to open your account, and enter the class token 83769DC9. If you have taken CS145 or CS245 within the past year, your account for that class should grant you free access for CS345. If not, you will have to purchase the access on-line. Note: If you have to purchase access, use either Garcia-Widom-Ullman, 2nd Edition or Ullman-Widom 3rd Edition (the books used for 145 and 245). Do not purchase access to the Tan-Steinbach-Kumar materials, even though the title is "Data Mining."

You can try the work as many times as you like, and we hope everyone will eventually get 100%. The secret is that each of the questions involves a "long-answer" problem, which you should work. The Gradiance system gives you random right and wrong answers each time you open it, and thus samples your knowledge of the full problem. While there are ways to game the system, we group several questions at a time, so it is hard to get 100% without actually working the problems. Also notice that you have to wait 10 minutes between openings, so brute-force random guessing will not work.

Solutions appear after the problem-set is due. However, you must submit at least once, so your most recent solution appears with the solutions embedded.

Challenge Problems

These are more complex problems for which written solutions are requested. They will be "lightly graded," meaning that we shall accept any reasonable attempt, and those doing exceptionally well will get "extra credit," but there will not be exact numerical grades assigned.

AssignmentDue Date
Gradiance HW #1Monday, January 26 (11:59PM)
Challenge Problems #1 SolutionWednesday, January 28 (In class)
Gradiance HW #2Wednesday, January 28 (11:59PM)
Challenge Problems #2 SolutionWednesday, February 4 (In class)
Gradiance HW #3Wednesday, February 4 (11:59PM)
Project ProposalMonday, February 9 (11:59PM)
Gradiance HW #4Wednesday, February 11 (11:59PM)
Gradiance HW #5Wednesday, February 18 (11:59PM)
Gradiance HW #6Monday, March 9 (11:59PM)
Gradiance HW #7Wednesday, March 11 (11:59PM)
Final Project Report DueWednesday March 11 (In class)


CS345A Project specification:

Course Outline

Here is a tentative schedule of topics:

1/7IntroductionJDU, AR
1/14Frequent ItemsetsJDU
1/16Special Lecture on Aster/Map-Reduce, ShareThis5:15PM in B12 Gates
1/21Frequent ItemsetsJDU
1/26Recommendation SystemsAR
1/28Similarity SearchJDU
2/2Similarity SearchJDU
2/4Similarity SearchJDU
2/9Link AnalysisAR
2/11Spam DetectionAR
2/18Generalizing Map-Reduce
2/23Clustering, Streaming DataJDU
2/25Extracting Structured Data from the WebAR
3/2Advertising on the WebAR
3/4Stream MiningJDU
3/9Stream SamplingDEK
3/11Project Reportsstudents
3/12Project Reportsstudents; Rm. 260-012
3/13Project Reportsstudents; Rm. 260-012
3/19Final Exam12:15-3:15PM, Rm. 200-002 (regular classroom)

References and Resources