Yanhong Annie Liu
[ Research Interests | Selected Publications | Research Projects | Courses and Seminars | Pointers]
Y. Annie Liu, Assistant Professor
Computer Science Department
Indiana University
201E Lindley Hall
Bloomington, IN 47405-7104
U. S. A.
(812) 855-4373 (Office)
(812) 855-4829 (Fax)
(812) 337-0426 (Home)
liu@cs.indiana.edu
http://www.cs.indiana.edu/~liu/
Ph.D., Cornell University, 1996
My primary research interests are in the areas of programming
languages, compilers, and software systems. I am particularly
interested in general and systematic approaches to improving the
efficiency of computations. This includes (1) program analysis and
transformation techniques for incremental computation and
parallel/concurrent computation, (2) applications in optimizing
compilers, language-based interactive systems, real-time and reactive
systems, algorithm design, program development, and software
maintenance, and (3) supporting tools and user interfaces that allow
convenient and efficient implementation of program analyses and
transformations. My major research project, Incrementalization for
Efficiency Improvement, together with a number of derived projects,
encompasses all three aspects above.
I have strong other interests in database management, document
processing, information management, and distributed computing. These
include, in particular, database query optimization, incremental
database view maintenance, efficient document processing techniques,
and systematic approaches to improving system fault-tolerance. I have
also worked on uncertainty reasoning methods and expert systems.
Recent technical reports: Pervasive, intensive, and critical computations today require computer
software to be highly efficient and reliable. Studies on this topic
span almost all branches of computer science but have been isolated in
each area. The goal of this work has been to bring all techniques
together in order to develop general systematic approaches and
supporting tools for improving the efficiency of computations. This
has involved exploring program analysis and transformation techniques
and domain-specific knowledge for incrementalization.
Incrementalization transforms batch programs into efficient and
correct incremental programs that exploit (1) the result of, (2) the
intermediate results computed in, and (3) auxiliary information about
a previous computation. Since every non-trivial computation proceeds
by iteration (or recursion), the approach is used for achieving
efficient computations in general by incrementalizing over iterations.
This method has been applied to problems in list processing, graph
algorithms, interactive systems, image processing, and VLSI design,
which were previously solved in ad hoc and often error-prone ways. A
prototype system for incrementalization is under development. A more
detailed description can be found here.
Work is in progress on refining the approach to provide compiler
technologies and programming methods for drastic program
optimizations. Based on techniques of the Synthesizer Generator,
which was originally developed by the group of Professor Tim
Teitelbaum at Cornell, we are also working on extending language-based
interactive systems to support efficient complex program analyses and
transformations. In addition, based on the study of Polya, a
programming language being implemented at Cornell by the group of
Professor David Gries, we are investigating the interplay between
program optimization and modularity (or abstraction), which is crucial
for generating efficient code in program refinement and
object-oriented programming. Another goal of this research is to
develop methods for parallel/concurrent computations by
incrementalizing across processors and analyzing asynchronous
computations.
Specific projects within the last year
include: Automating incrementalization, in a
language-based programming environment; Dynamic programming via
incrementalization, based on static analysis for caching;
Transforming recursion into iteration, also via
incrementalization; Loop optimization for aggregate array
computations; Dependence analysis for recursive data, using
regular tree grammars; Efficient algorithms for regular tree
grammars; Eliminating dead code on recursive data, via
constraints construction and simplification; Automatic time and
space analysis, by combining static analysis, complexity analysis,
and performance evaluation methods; and System performance
monitoring survey. These projects are supported by Motorola, NSF,
and ONR. Some of them are performed jointly with colleagues Scott
Stoller, Bob Paige, and Jeffrey Tsai and Ph.D. students Gustavo Gomez,
Leena Unnikrishnan, Ning Li, Yuchen Zhang, and Byron Long.
Computer Science Department
Research Interests
Selected Publications
Solving Regular Tree Grammar Based Constraints. Liu, Li, and Stoller, 7/00)
(ps)
Automatic accurate stack space and heap space analysis for high-level
languages (Unnikrishnan, Stoller, and Liu, 2/00). (ps)
Automatic time-bound analysis for a higher-order language (Gomez and
Liu, 11/99). (ps)
Project: Incrementalization for Efficiency Improvement
Courses and Seminars
Pointers
Last updated December 1, 1999.
I have moved in August 2000 to
SUNY Stony Brook
Stony Brook, NY 11794-4400
631-632-8463 (Office)
631-632-8334 (Fax)
631-476-4392 (Home)
liu@cs.sunysb.edu
http://www.cs.sunysb.edu/~liu