Spring 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
- Learning to estimate query difficulty: including
applications to missing content detection and distributed
information retrieval,
Elad Yom-Tov, Shai Fine, David Carmel, Adam Darlow,
SIGIR 2005.
[acm]
- Linear discriminant model for information retrieval,
Jianfeng Gao, Haoliang Qi, Xinsong Xia, Jian-Yun Nie,
SIGIR 2005.
[acm]
- Context-sensitive information retrieval using implicit
feedback, Xuehua Shen, Bin Tan, ChengXiang Zhai, SIGIR
2005
[acm]
- Simple BM25 extension to multiple weighted fields,
Stephen Robertson, Hugo Zaragoza, Michael Taylor, CIKM 2004
[acm]
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 2005.
(Prepublication chapters can be found as CS412Han Class Notes.)
- More advanced topics
- Data Warehousing:
- B.-C. Chen, L. Chen,
Y. Lin, and R. Ramakrishnan, Prediction
cubes, VLDB 2005. [pdf]
- X. Li, J. Han, and H. Gonzalez,
High-dimensional
OLAP: A minimal cubing approach, VLDB 2004.
[pdf]
- Data Mining:
- G. S. Manku and R. Motwani,
Approximate
frequency counts over data streams, VLDB 2002. [pdf]
-
J. Pei, J. Han, B. Mortazavi-Asl,
J. Wang, H. Pinto, Q. Chen, U. Dayal, and M.-C. Hsu,
Mining
sequential patterns by pattern-growth: The PrefixSpan
approach, IEEE Transactions on Knowledge and Data Engineering,
16(10), 2004.
[pdf]
- X. Yin, J. Han, and
P.S. Yu, Cross-sectional
clustering with user's guidance, KDD 2005.
[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.
-
Query processing
- AutoAdmin 'What-if' Index Analysis Utility, Chaudhuri and Narasayya, SIGMOD 1998 and RDS. [acm]
- Optimal Aggregation Algorithms for Middleware, Fagin et al., PODS 2001. [pdf]
- Security trends
- Hippocratic Databases, Agrawal et al., VLDB 2002. [pdf]
- Information integration
-
Valter Crescenzi, Giansalvatore Mecca, Paolo Merialdo: RoadRunner: Towards Automatic Data Extraction from Large Web Sites. VLDB 2001: 109-118 [pdf]
-
The BINGO! System for Information Portal Generation and Expert Web Searc,
Sergej Sizov, Martin Theobald, Stefan Siersdorfer, Gerhard Weikum, Jens
Graupmann Michael Biwer, and Patrick Zimmer
[pdf]
|
