2001 technical reports

Compressed PostScript:
Finding Hidden Independent Sets in Interval Graphs (PS.Z)

Appears in:

Tony Abou-Assaleh, Jianna Zhang, and Nick Cercone. 2001. "Evolution of Recurrent Neural Networks to Control Autonomous Life Agents." Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2001. San Francisco, CA: Morgan Kaufmann Publishers. Page 903.

Please direct all comments and suggestions to the author

The paper will be submitted to WABI 2001.

Conference presentation: Tenth Copper Mountain Conference on Multigrid Methods

Also appear in virtual proceedings at MGNET.

Many of the functions of a video decoder can be mapped to the capabilities of a graphics card. However, for the graphics work involved with digital video a graphics card is required while a video decoder card is not. This thesis proposes a method to use common graphics cards, through the OpenGL API, for the task of video streaming.

MPEG/* - MPEG1 encoded versions of animations
BFI/* - MPOG encoded versions using brute force search
Hier/* - MPOG encoded versions using hierarchical search
thesis.pdf - PDF version of thesis

We argue that existing solutions have usability and efficiency problems for this application and propose an alternative approach based on the type of region algebra that is often used as a query language for text databases. This is an appropriate interface for incremental development, but has no efficient batch parsing model such as those that exist for grammars. In this thesis, we propose an efficient batch parsing model and characterize the region algebras to which it applies.

We describe and formally define modularity for an HPSG-type grammar, and we illustrate its application on an example.

An Interval routing scheme (IRS) is a well-known, space efficient routing strategy for routing messages in a distributed network. In this scheme, each node of the network is assigned an integer label and each link at each node is labeled with an interval. The interval assigned to a link l at a node v indicates the set of destination addresses which should be forwarded through l from v. A Multi-dimensional Interval Routing Scheme (MIRS) is a generalization of IRS in which each node is assigned a multi-dimensional label (which is a list of d integers for the d-dimensional case). The labels assigned to the links of the network are also multi-dimensional (a list of d one-dimensional intervals). The class of networks supporting linear IRS (in which the intervals are not cyclic) is already known for the one-dimensional case [FG94]. In this paper, we generalize this result and completely characterize the class of networks supporting linear MIRS (or MLIRS) for a given number of dimensions d. We show that by increasing d, the class of networks supporting MLIRS is strictly expanded. We also give a characterization of the class of networks supporting strict MLIRS, which is a modified version of MLIRS.

Key words:Computer networks, interval routing schemes, graph theory, multi-dimensional, characterization.

A data warehouse consists of materialized views, which contain derived data from several data sources. The advantage of using materialized views is that they contain the results of standard queries and therefore when such queries are posed, the data sources those queries are based on, which are usually costly to access because of their size and remoteness, don't have to be accessed. However in order for the materialized views to contain up-to-data data they have to be updated periodically. Such synchronization of the materialized views with the data sources could be slow if the later have to be queries for a correct update to be done - i.e. if just the data for the changes done to the data sources is insufficient. A way querying the data sources during materialized view update can be avoided is by storing any data from the data sources, which could be relevant to an update of the materialized views, on the data warehouse site. Such auxiliary data is stored in auxiliary views and has the characteristic that it makes the data stored at the data warehouse self-maintainable, i.e. it can be update correctly from the log of changes done to the the data sources.

In this paper we propose unique algorithms for keeping the size of such auxiliary views relatively small. This is achieved by using the additional information about the integrity constraints that hold on the data sources. More specifically we use an object-oriented model to describe a database schema and a subset of OQL as our query language. The proposed in the paper algorithms produce auxiliary views that make a materialized view self-maintainable relative to the three possible operations on a datbase: addition, deletion and object update.