Fall 2006 Reading List for the DAIS Qualifying
Examination
I. Information Retrieval
- Basic concepts
- Vector-space
retrieval model, TF-IDF weighting, relevance/pseudo feedback,
(non-interpolated) average precision, query-likelihood retrieval model,
language model smoothing, PageRank, inverted
index
- Background
- Modern Information
Retrieval: A Brief Overview, Singhal, IEEE
Data Engineering Bulletin 24(4), pages 35-43, 2001. [ps]
- Link Analysis in
Web Information Retrieval, Henzinger, IEEE
Data Engineering Bulletin 23 (3), pages 3-8, 2000. [pdf]
- Probabilistic
relevance models based on document and query generation, Lafferty and
Zhai, Language Modeling and Information Retrieval, Kluwer
International Series on Information Retrieval, Vol. 13, 2003. [pdf]
- A study of
smoothing methods for language models applied to information retrieval,
Zhai and Lafferty, ACM Transactions on Information Systems, Vol. 2, No.
2, pp. 179-214, April 2004. [acm]
- More advanced topics
-
Optimizing Web Search Using Social Annotations, S. Bao, X. Wu, B. Fei, G. Xue,
Z. Su, Y. Yu, Proceedings of WWW 2007, pp. 501-510. [pdf]
-
Latent Concept Expansion Using Markov Random Fields, D. Metzler and W. B.
Croft, Proceedings of ACM SIGIR 2007. [pdf]
-
Sentiment Retrieval using Generative Models, K. Eguchi and V. Lavrenko,
Proceedings of EMNLP 2006, pp. 345-354. [pdf]
-
Extracting Product Features and Opinions from Reviews, A. Popescu and O.
Etzioni,, Proceedings of HLT/EMNLP 2005, pp. 339-346.[pdf]
II. Data Mining and Data Warehousing
- Basic Concepts
- Data warehousing:
star schema, data cube (be able to list half a dozen typical data cube computation
methods), multi-dimensional analysis (OLAP)
- Data mining:
frequent pattern mining (be able to list half a dozen typical methods),
sequential pattern mining (be able to list at four or five typical
methods), correlation analysis, classification (be able to list half a
dozen typical methods), clustering (be able to list half a dozen
typical methods)
- Background
- J. Han and M. Kamber, Data Mining: Concepts and Techniques, 2nd
edition. Chapters 3 & 4 (for data warehousing); Chapters 2, 5-7
(for data mining). Morgan Kaufmann 2006.
- More advanced topics
- Data Warehousing:
- Prediction cubes,
Chen, Chen, Lin, and Ramakrishnan, VLDB 2005. [pdf]
- High-dimensional
OLAP: A minimal cubing approach, Li, Han, and Gonzalez, VLDB 2004. [pdf]
- Data Mining:
- Approximate
frequency counts over data streams, Manku
and Motwani, VLDB 2002. [pdf]
- Graphs over time:
Densification laws, shrinking diameters and possible explanations, Leskovec, Kleinberg, and Faloutsos, KDD 2005. [pdf]
- Discriminative
Frequent Pattern Analysis for Effective Classification, Cheng, Yan, Han,
and Hsu, ICDE 2007. [pdf]
III. Database Management Systems
- Basic concepts
- Hardware: disk
sector, track, block, seek, latency, how to lay out a database page
- Data modeling: ER,
OO, and Object-Relational approaches
- Concurrency control
and recovery: ACID, serializability,
two-phase locking, two-phase commit, logging and recovery, the impact
of data replication
- Theory:
normalization, dependencies
- Queries: access
methods (hashing, B-trees, multidimensional access methods), how to
optimize a query, SQL
- Benchmarks: TPC-C
and TPC-H
- Background
You can use any database textbook you like to
study the most basic of the concepts listed above; for example, CS411
teaches these concepts. (Note that you will be expected to be able to
demonstrate your understanding of the concepts by applying them (as
opposed to simply being able to define them).) In the remaining entries,
"RDS" refers to Stonebraker's Readings in
Database Systems, currently in its 4th edition.
- Generalized Search
Trees for Database Systems, Hellerstein et al., VLDB 1995 and RDS. [pdf] We include this paper as the reference for
multidimensional access methods; access methods based on B-trees and
hashing should be covered in any database textbook.
- New TPC Benchmarks
for Decision Support and Web Commerce, Poess
and Floyd, SIGMOD Record 29(4), December 2000. [pdf]
- Inclusion of New
Types in Relational Data Base Systems, Stonebraker,
ICDE 1986 and RDS. [acm]
We include this paper as your reference for understanding the impact of
extensibility (as, for example, intended by the object-relational
model) on a DBMS.
- More advanced topics
Please note that databases are a very broad field. The papers listed
here will be changed frequently, to reflect this breadth.
- Database Cores
- Graph-based synopses for relational selectivity
estimation. Joshua Spiegel, Neoklis Polyzotis. SIGMOD 2006.[acm]
- Context-sensitive
ranking. Rakesh Agrawal, Ralf Rantzau, Evimaria Terzi. SIGMOD 2006. [acm]
- Information Systems
- To search or to
crawl?: towards a query optimizer for text-centric tasks. Panagiotis G.
Ipeirotis, Eugene Agichtein, Pranay Jain, Luis Gravano. SIGMOD 2006 [acm]
-
Complex Queries over Web
Repositories.Sriram Raghavan, Hector Garcia-Molina. VLDB 2003. [pdf]
IV. Bioinformatics
- Basic Concepts
- Sequence alignment
- Motif finding and regulatory
sequence analysis
- Gene prediction
- DNA sequencing
- Phylogenetic tree
reconstruction
- Gene expression analysis
- Clustering of biological data
- Background
- Biological sequence analysis - probabilistic
models of proteins and nucleic acids, by Durbin, Eddy, Krogh, and Mitchison. Read Chapters 2 (Pairwise
alignment), 3 (Markov chains and hidden Markov models), and 7.1-7.4 (Building phylogenetic
trees).
- More advanced topics
- De novo cis-regulatory
module elicitation for eukaryotic genomes. Gupta and Liu, PNAS 2005. [paper]
-
Evolutionarily
conserved elements in vertebrate, insect, worm, and yeast genomes. Siepel et
al. Genome Research 2005. [paper]
-
Informative
priors based on transcription factor structural class improve de novo motif
discovery. Narlikar et al. Bioinformatics. 2006 [paper]
|
