Alexander Dekhtyar
department of Computer Science
University of Maryland , College Park, MD, 20742

Research Statement

Current Research

My current research deals with probabilistic information in Databases and Logic Programming.

Probabilistic Temporal Databases.
(joint work with Robert Ross and V.S. Subrahmanian )

A number of database applications (e.g., scheduling databases for transportation providers, time-series stock databases, video extraction applications) require the ability to make statements of the following kind: Data tuple d from relation R is true at some point of time in the interval [t,t'] with probability between p and p'. For example, a tuple in a scheduling database may contain information that a package shipped from Washington, DC to New York via UPS arrives at the destination between 12 and 36 hours after being sent with probability 95% - 100%. Additionally, the database may contain information that the probability of arrival at a particular hour for that time interval is distributed uniformly. Until now, such information could be only represented in either purely temporal or purely probabilistic databases. Such representations had a number of problems:

We have introduced the concept of Probabilistic Temporal Databases, which are designed to address these problems. Our main contributions are summarized as follows.

Temporal Probabilistic Logic Programs.
(joint work with V.S. Subrahmanian)

Concurrently with our research on Probabilistic Temporal Databases, we have been studying logical reasoning in situations involving temporal uncertainty. We have proposed the concept of a Temporal Probabilistic Logic Program (or TPLP for short). We have defined the syntax of TPLPs and provided a formal model theoretic and fixpoint semantics that are shown to coincide. In this work we considered three types of statements:

Our syntax allows the user to explicitly state the type of each statement (formula) found in a TP-program and our model theory captures reasoning about the temporal probabilities of events of all three types. The fixpoint semantics uses linear programming to compute the tightest probability intervals possible.

We have also studied a subset of the general language where only statements about uniquely occurring events were allowed and established a more efficient fixpoint procedure which does not employ linear programming for this subclass of TP-programs.

We are currently working on query processing procedures for TP-programs, and on finding other subclasses of TP-programs for which the fixpoint semantics will not need linear programming, therefore making more efficient query processing possible.

Optimal Status Sets For Heterogeneous Active Agents ( joint work with Thomas Eiter, Thomas Schwentick and V.S. Subrahmanian )

This work is a part of the ongoing IMPACT (Interactive Maryland Platform for Agents Collaborating Together) project. A part of the framework is a declarative language for Agent Programs which allows agents express their ``operating principles'' and to determine the actions they must take in order to satisfy them.

The semantics of Agent Programs is given in terms of Status Sets - sets of actions which satisfy the rules of the program. Different semantics are possible, and Eiter and Subrahmanian describe a number of semantics.

However, only in very simple cases are we guaranteed that the status set is unique (i.e., that the agent's choice of actions at each step will be deterministic).

Our current work we proposes a way to overcome this. We assume that an agent has an objective function which allows it to evaluate each status set that satisfies its program for a given semantics. Out of all such status sets, we will select the one(s) which optimize this objective function.

The goals of this work are:

Hybrid Probabilistic Logic Programs.
(joint work with V.S. Subrahmanian and M.I. Dekhtyar)

Most current work on probabilistic logic programming, assumes the existence of a simple apiori relationship between the events described (e.g., independence or ignorance). However, this severely limits the applicability of the frameworks.

We have proposed a hybrid probabilistic logic programming language which was designed to allow the programmer to reason about the probabilities of event under any assumption about their relationship. In particular, our contributions are:

Though we have not implemented it, it should be mentioned that since our original results have been published, two implementations of Hybrid Probabilistic Logic programs appeared. One implementation, by Terrence Swift at University of Maryland uses the XSB system (developed at SUNY at Stony Brook) to implement hp-programs with atomic heads. This implementation has been used to solve some data mining problems. A somewhat different fragment of HPPs had been implemented by Stoffel at the University of Neuchatel in Switzerland.

Previous Research

During my undergraduate study, my research had been in the area of finite model theory and Linear Logic. I have studied Resource Transformation Nets (RT-nets) - a model of computation in which a number of resources can be stored, and transformed at the nodes of a graph and transferred from node to node. I showed that a logic based on the fragment of Multiplicative Linear Logic describes exactly the behavior of RT-nets.

Future Research

My future research will proceed in the following areas:

  1. N-Dimensional Probabilistic Reasoning.

    I am planning to extend our results for Probabilistic Temporal Databases and Temporal Probabilistic Logic Programs to the case when the probability is distributed over an N-dimensional (and possibly continuous) set, such 2D or 3D space, or 2D/3D space with time. This work will require the generalization of many notions, used in the TP-databases and TP-programs. Database design will also involve work with different spatial data structures such as quadtrees, R-trees etc...

  2. Intelligent Agents.

    I propose to continue working on the theory and implementation of heterogeneous software agents. I intend to study how an agent can make decisions when it is reasoning about uncertain temporal events. For instance, an agent may wish to predict certain events in the future. While such predictions are (inevitably) likely to be uncertain, the agent may still base its actions and schedules on such predictions. I propose to develop methods by which an agent can represent information about multiple possible uncertain future works, and can make decisions based on such information based on one or more objective functions the agent has.

  3. Application of probabilistic methods.
  4. Probabilistic Updates.

    Given a body of probabilistic data (e.g., probabilistic database, probabilistic deductive database), and a collection of ``newly discovered'' probabilistic information, the question of updating the data with the new information arises. While working on Probabilistic Temporal Databases and Hybrid Probabilistic Programs, we have found that

    1. there is no unique ``correct'' way to update the probabilistic information,

    2. probabilistic updates are not local, i.e., updating a probability of one event, may result in a chain of updates of probabilities of other events in some cases and

    3. may require application of non-probabilistic methods to preserve consistency of the data.
My goal is to study the general properties of probabilistic updates in detail.