Spring 2005 Data and Information Ph.D.
Qualifying Examination

Examining Faculty
- Csaba Egyhazy
- Roger Ehrich
- Chang-Tien Lu
Philosophy of Examination
- Since students vary in their abilities regarding written and oral communication,
and since doctoral students are expected to have some skill with each media
type, students will explain their solutions both in writing and orally. Solutions
will be graded based on their clarity as a result of the union of these modes
of expression.
- Students are expected to have studied all works in the reading list. Any
pre-requisite or background knowledge required to understand the works in
the reading list are also expected to be acquired by the student.
- Students are expected to understand those works at the level of a doctoral
student who has taken the equivalent of courses such as CS5604 and CS5614.
- Students are expected to be able to understand a real situation/context/problem
in the information/data area, to be able to synthesize/apply the findings
of multiple papers from the reading list to such problems, and to be able
to formulate an answer outlining how they would approach and solve that problem.
Process and Format
- The examination will be a takehome examination and is expected to be administered
in the beginning of 2005.
- At the beginning of the examination period, all students will receive a
document that contains three questions.
- By the end of the examination period, each student must turn in a written
solution to one of those questions, i.e., the student must choose one out
of three. It is expected that the solutions will be no longer than about 15
double spaced typed pages (excluding references) at 11 point or larger. Specific
details about format and length will be provided along with the questions.
- Also at this time, each student must turn in a PowerPoint presentation or
equivalent that will be used for an oral explanation of the written solution.
Oral explanations, lasting no longer than 30 minutes, will be scheduled as
soon after the end of the exam week as feasible, using VTEL or equivalent
as needed to ensure coverage by students and/or faculty in either Blacksburg
or N. Virginia.
- Written solutions might be expected to have the following approximate format
(although detailed guidelines will be provided during the exam):
- a motivation section making clear the context of the problem/situation
- a clear statement of the problem in terms of concepts and terminology
in the information/data area, that addresses the situation/context
- a review of related literature, drawn mostly from multiple relevant
works in the reading list
- a statement of how the problem can be approached
- a description of the approach to solve the problem
It is important that any assumptions made be clearly stated in the written
solution.
- Oral presentations must follow what is given in the previously turned-in
PowerPoint file or equivalent. They must be completed within a 30 minute period,
in which roughly 20 minutes are for presentation and 10 minutes for answering
questions posed by faculty examiners.
- Each solution will be graded by at least 2 faculty members. A combined grade
will then be assigned for each student based on all faculty input by the area
committee, on a scale of 0-3, as is called for by GPC policies.
Schedule
- 1/15 (Saturday), 2005 : Written Examination Available.
- 1/28 (Friday) 5PM, 2005: Written Examination Due.
- 1/31 (Monday) 5PM, 2005: PowerPoint Presentation Slide Due.
- 2/7(M) - 2/11(F), 2005 : Oral Examination.
Oral Examination Schedule
- 2/11(F) 9:20 - 10:00AM Zhiyi Li
- 2/11(F) 10:00 - 10:40AM Yi Zhang
- 2/11(F) 10:40 - 11:20AM Uma Murthy
- 2/11(F) 11:20 - 12:00AM Naga Srinivas Vemuri
Reading List
(Note: Some of the hyperlinks below lead to web pages maintained by the
respective publishers. You may or may not be able to download the articles directly
from these web pages - this depends on the host computer from which the access
is made. To access the articles, we recommend that you go through the VT-subscribed
ACM digital library or IEEE Explore interface).
- Bookstein, A., Klein, S., and Raita, T., Markov
Models for Clusters in Concordance Compression. In Proc. IEEE Data Compression
Conference, 116-125, March 1994.
- Moffat, A. and Stuiver, L., Exploiting Clustering
in Inverted File Compression. In Proc. IEEE Data Compression Conference,
82-91,
March 1996.
- Blandford, D. and Blelloch, G., Index
Compression through Document Reordering. In Proc. IEEE Data Compression
Conference, 342-351, April 2002.
- Witten, I., Moffat, A., and Bell, T., Managing gigabytes (general reference),
New York: Morgan Kaufman, 1999.
- J. Peckham, F. Maryanski, Semantic Data
Models, September 1988 ACM Computing Surveys (CSUR) , Volume 20 Issue
3
- G . Weddell, Reasoning about Functional
Dependencies Generalized for Semantic Data Models, March 1992, ACM Transactions
on Database Systems (TODS) , Volume 17 Issue 1
- W. Al-Khatib, Y.F Day, A. Ghafoor, P.B Berra, Semantic
Modeling and Knowledge Representation in Multimedia Databases, IEEE Transactions
on Knowledge and Data Engineering ,Volume: 11 , Issue: 1 , Jan.-Feb. 1999,
Pages: 64 - 80
- T. Andreasen and J. Fischer Nilsson, Grammatical
Specification of Domain Ontologies, Data & Knowledge Engineering,
Volume 48, Issue 2, February 2004, Pages 221-230.
- Brian Babcock, Shivnath Babu, Mayur Datar, Rajeev Motwani, Jennifer Widom,
Models and Issues in Data Stream Systems,
ACM Symposium on Principles of Database Systems(PODS), pages1-16,
2002.
- Sudipto Guha, Adam Meyerson, Nina Mishra, Rajeev Motwani, Liadan O'Callaghan,
Clustering Data Streams: Theory
and Practice, IEEE Transactions on Knowledge and Data Engineering,
Vol. 15, No.3, pages 515-528, May/June 2003.
- W.G. Teng, M.S. Chen, P.S. Yu, A
Regression-Based Temporal Pattern Mining Scheme for Data Streams, Proceedings
of 29th International Conference on Very Large Data Bases, pages 93-104,
2003.
- H. Wang, W. Fan, P.S. Yu, J. Han, Mining
Concept-Drifting Data Streams Using Ensemble Classifiers, Proceedings
of the ninth ACM SIGKDD International Conference on Knowledge Discovery and
Data Mining, pages 226-235, 2003.