Amos Fiat (email@example.com)
1st Semester, 2005/2006 - Tuesday 1500-1800
School of Computer Science,
John Kleinberg: The Structure of Information Networks
Computer Science (Class at Cornell)
Rajeev Motwani: Advanced Algorithms for Internet Applications (Class at Stanford)
Yishay Mansour: Machine Learning: Foundations (Class
at Tel Aviv)
Moses Charikar: Algorithms for Massive Data Sets
Avrim Blum: Machine learning theory
Manoel Mendonca, Nancy L. Sunderhaft: Mining Software Engineering Data: A Survey
Computing the Support Vector Machines in Maple, see examples of using the Lagrange Multiplier Method in Maplesoft.
- The Hub/Authority and PageRank algorithms
- Eigenvector/Singular Vector Analysis
- Deerwester, S., Dumais, S. T., Landauer, T. K., Furnas, G. W. and
Harshman, R. A.
Indexing by latent semantic analysis. Journal of the Society for
Information Science, 41(6), 391-407 (1990).
- Christos Papadimitriou, Prabhakar Raghavan Hisao Tamaki, Santosh
Vempala. Latent Semantic
Indexing: A Probabilistic Analysis. 17th ACM Symposium on the Principles
of Database Systems, 1998.
- D. Gibson, J. Kleinberg, P. Raghavan.
Inferring Web communities from link topology. Proc. 9th ACM Conference
on Hypertext and Hypermedia, 1998.
- P. Drineas, Ravi Kannan, Alan Frieze, Santosh Vempala and V. Vinay
in large graphs and matrices." Proc. of the 10th ACM-SIAM Symposium
on Discrete Algorithms, Baltimore, 1999.
- Yossi Azar, Amos Fiat, Anna Karlin, Frank McSherry and Jared Saia.
of Data. 33rd ACM Symposium on Theory of Computing, 2001.
- Dimitris Achlioptas, Amos Fiat, Anna Karlin, Frank McSherry,
Web Search via Hub Synthesis. 42nd IEEE Symposium on Foundations
of Computer Science, 2001, p.611-618.
- Association Rules
- Data Streams
- Brian Babcock, Shivnath Babu, Mayur Datar, Rajeev Motwani, Jennifer
Models and Issues in Data Stream Systems, Proceedings of the 21st
ACM Symposium on Principles of Database Systems, 2002.
- M. Datar, A. Gionis, P. Indyk, AND R. Motwani, Maintaiing
Stream Statistics Over Sliding Windows., SICOMP, 2002, Vol. 31,
No. 6, pp. 1794–1813.
- Brian Babcock, Mayur Datar, Rajeev Motwani, and Liadan O'Callaghan,
Variance and k-Medians over Data Stream Windows, Proceedings of
the 22nd ACM Symposium on Principles of Database Systems, 2003.
- See Yossi Matias list
of publications on massive Data Sets
- Privacy Preserving Data Mining
Homework Assignments 1:
Take the census-income
dataset from the UCI machine learning depository
and try to derive if the income is above $50K using the other fields of
Part 1: Perform an SVD of 1000 records, and take a low rank approximation
(for various small values of the rank). Then, take an additional 1000 records
(setting this coordinate to zero) and project the record onto the lower
dimensional subspace spanned by the singular vectors. See how well this
Part 2: Construct a decision tree for this problem using 1000 records to
derive a tree and test it on the next 1000. Explain how you are constructing
the tree, what you do about errors, etc. Read all about pruing the tree.
Part 3: Do itemset mining on this data and try to derive association rules
whose consequent is the income field.
Part 4: Build a support vector machine for this dataset.
Final Project: Due March 10, 2006
- Read Rank Aggregation
Methods for the Web by C. Dwork, R. Kumar, M. Naor and D. Sivakumar.
- Kemeny optimal aggregation
- Extended Condorcet criterion
- Footrule optimal aggregation
- Locally Kemeny optimal aggregation
- Borda ordering
- Scaled footrule aggregation
- What are the connections between the above? What can be computed efficiently?
- Read What's
New: Finding Significant Differences in Network Data Streams by G.
Cormode and S. Muthukrishnan.
- Absolute, relative and variational differences
- Exact deltoids
- Approximate deltoids
- In your own words, and explained as simply as possible, how does
the paper test for absolute deltoids?
- Read A
Divide-and-Merge Methodology for Clustering, by David Cheng, Ravi Kannan, Santosh Vempala, and Grant Wang.
- In your own words, explain the Divide and Merge approach.
- Describe the spectral partitioning algorithm used in the Divide phase.
- What can you say about the complexity of this method?
- Cite the relevant references in Privacy preserving Data mining.
- What are the open problems from the above papers?
- Test files parsed by Lior Kapelushnik:
of class of 2002:
notes, Lecture 1
notes, Lecture 2
notes, Lecture 3
notes, Lecture 4
notes, Lecture 5
notes, Lecture 6
notes, Lecture 7
notes, Lecture 8
notes, Lecture 9
notes, Lecture 10