Faculty
Affiliated Faculty
Senior Research Specialist
Graduate Students
Recent Projects
- Interconnection networks and parallel
programming and the study of limits of computation and
communication on various interconnection networks. Specific
topics of interest are determination of the bisection width
for classes of graphs, computation of isoperimetric numbers
of arrays and tori, placement and communication on the torus
network.
- Approximation techniques for various
database operations including multiple join and similarity.
The methods we are developing are a byproduct of work related
to query optimization, which is concerned with the selection the
most efficient way among all the possible ways of executing a
query. They include techniques based on the DFT, metric
properties of vectors, and nonparametric density estimation.
- Edit distance
calculation with a normalization factor. This is a
special case of fractional programming using Dinkelbach's
algorithm. The analysis of the behavior of this algorithm
for a given class of combinatorial problems and restricted
cost functions is interesting and may have applications in
computational biology.
- Load balancing strategies for multiprocessor digital library servers, compact storage for wavelet-based multiresolution image browsing.
- The focus here is on three problem areas concerning
linear constraint query languages. Constraint database systems integrate database technology with constraint solving techniques to deal with
applications involving spatial or geographical datasets and arithmetic computations. The first part of this project aims at developing efficient query evaluation algorithms for linear or dense order constraint queries and syntactic forms for representing
constraint databases so that efficient query evaluation becomes possible. The second part aims at showing the complexity of decision problems concerning constraint query languages including query containment, equivalence, satisfiability, and disjointness
using a new technique based on abstract machines. The third part aims at developing incremental evaluation techniques for recursive (non-first-order) and topological queries.
- Applications of the unsolvability of Hilbert's Tenth Problem to
decision questions concerning programs and abstract machines.
- Parallel complexity of loops.
- Complexity of commutativity analysis techniques for program
parallelization.
- Alexandria Digital Library (ADL) project system design and development
with concentration in the database development issues.