Fall 2008 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]
- ARCube: Supporting
Ranking Aggregate Queries in Partially Materialized Data Cubes. Wu,
Xin, and Han. SIGMOD 2008. [pdf]
- Data Mining:
- Mining Colossal Frequent
Patterns by Core Pattern Fusion. Zhu et al. ICDE 2007. [pdf]
- SCAN: A Structural
Clustering Algorithm for Networks. Xu et al. KDD 2007. [acm]
- Direct
Discriminative Pattern Mining for Effective Classification. Cheng,
Yan, Han, and Yu. ICDE 2008. [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.
- 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 Core
- Scalable
Approximate Query Processing with the DBO Engine. Jermaine, Arumugam,
Pol, and Dobra. SIGMOD 2007. [acm]
- Compiling Mappings
to Bridge Applications and Databases. Melnik, Adya, and
Bernstein. SIGMOD 2007. [acm]
- Information Systems
- Scalable Semantic
Web Data Management Using Vertical Partitioning. Abadi, Marcus, Madden, and
Hollenbach. VLDB 2007. [pdf]
- iTrails: Pay-as-you-go Information
Integration in Dataspaces. Salles et al. VLDB 2007. [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 8.1-8.5 (Probabilistic approaches
to phylogeny).
- More advanced topics
- Combining
phylogenetic and hidden Markov models in biosequence analysis. Siepel and
Haussler. RECOMB 2003. [acm]
- Predicting
expression patterns from regulatory sequence in Drosophila segmentation.
Segal, Raveh-Sadka, Schroeder, Unnerstall & Gaul. Nature 451, pp. 535-540 (31
January 2008). [html]
- Informative
priors based on transcription factor structural class improve de novo
motif discovery. Narlikar et al. Bioinformatics.
2006. [pdf]
|
