28214269
Active rule processing in the BioCompose database
BioCompose is an object-relational database query tool that runs on top of any relational database and provides an intelligent and complete object-relational interface to the user. Unlike the traditional approach, which is completely table driven, queries in BioCompose are structured along the lines of natural language and sentences. In BioCompose, the database server continuously monitors the triggers and integrity constraints which are expressed as logical rules and are evaluated based on incoming events which include real time events, value events, transaction events, abstract events, and message events. The paper presents a novel approach that compiles triggers and integrity constraints into an asynchronous network to minimize the rule evaluation effort under different kinds of events.
32386430
An Object-Oriented BSP Tree Algorithm for Hidden Surface Removal
Since the BSP tree algorithm was introduced, many extended or applied algorithms for the original BSP tree algorithm have been reported. Most of the previous work dealt with polygons that are components of polyhedra. If a scene consists of many polyhedra and they are allowed to move, the management cost of a BSP tree becomes expensive and the size of the tree becomes large. This paper presents an object-oriented BSP tree algorithm that can more efficiently deal with a large number of moving polyhedra.
206985371
Framework and network based multimedia object management environment
Because multimedia objects are becoming more prevalent, on ever increasing volume, inventing an efficient multimedia object management environment is a matter of increasing urgency. In recognition of this crisis, we developed the multimedia object management environment (MOME) that includes a suite of tools such as the Vortex framework, and network file indexer (NFI). MOME also includes a fully featured graphical user interface for maximum user control and flexibility. With meta data, it automatically generates indexes and paths for different types of multimedia objects and allows users to quickly find what they are looking for. In this paper, we address the background, architecture, and performance of MOME in detail.
30326495
Performance-driven channel pin assignment algorithms
In this paper we consider two channel pin assignment problems which take circuit performance into account. The first one is the module implementation selection problem. We are given a net span bound for each critical net and each module has several possible placements of its pins. Our objective is to minimize channel density while satisfying net span constraints. We proved that this problem is NP-complete. For the case when each module has at most 2 pin placements, the problem can be transformed to the 2-SAT problem and hence is polynomial time solvable. We present a heuristic based on this algorithm to solve the general case. The second problem we consider is the module shifting problem. We are given a set of modules whose relative ordering is fixed on each side of the channel but their exact positions are not fixed. We present a polynomial time algorithm to test the feasibility of satisfying the net span constraints by shifting the modules. The algorithm is based on formulating the problem as a special integer linear programming problem which is solvable in polynomial time. We also extend our algorithms to handle multiple channels. >
5669766
Automatic Estimation of 3D Transformations using Skeletons for Object Alignment
An algorithm for automatic estimation of 3D transformations between two objects is presented in this paper. Skeletons of the 3D objects are created using a fully parallel thinning technique, feature point pairs (land markers) are automatically extracted from skeletons, and a least squares method is applied to solve an over determined linear system to estimate the 3D transformation matrix. Experiments show that this method is quite accurate when the translations and rotation angles are small, even when there is some noise in the data. The estimation process requires about 2 seconds on an Intel Centrino Laptop with 512 MB memory, for a complex model with about 37,000 object points and 500 object points for its skeletons
195349922
Routing for symmetric FPGAs and FPICs
9613111
Strategies for distributed search
The problem of locating information among cooperating agents within a distributed computing environment is considered. Such collections of agents can be collectively thought of as a single distributed application providing a single set of services; the X.500 distributed directory is an example of such an application. A central problem in such applications is the cooperative search for certain information which might be located at one of the agents. One approach to this problem relies on flooding messages throughout the distributed environment, such as that which might be used in routing algorithms to locate entries. Although the use of such algorithms, in principle, takes advantage of reaching many different agents via parallel data communication paths, the additional number of messages may be a distinct disadvantage in “higher layer” applications. This paper presents a variant of such approaches which rely on a depth-first method of distributing messages. Results of simulations illustrating the savings in messages of this approach to one relying on traditional flooding are presented for different network configurations.
6023729
Accurately Choosing Execution Runs for Software Fault Localization
Software fault localization involves locating the exact cause of error for a “failing” execution run – a run which exhibits an unexpected behavior. Given such a failing run, fault localization often proceeds by comparing the failing run with a “successful” run, that is, a run which does not exhibit the unexpected behavior. One important issue here is the choice of the successful run for such a comparison. In this paper, we propose a control flow based difference metric for this purpose. The difference metric takes into account the sequence of statement instances (and not just the set of these instances) executed in the two runs, by locating branch instances with similar contexts but different outcomes in the failing and the successful runs. Given a failing run πf and a pool of successful runs S, we choose the successful run πs from S whose execution trace is closest to πf in terms of the difference metric. A bug report is then generated by returning the difference between πf and πs. We conduct detailed experiments to compare our approach with previously proposed difference metrics. In particular, we evaluate our approach in terms of (a) effectiveness of bug report for locating the bug, (b) size of bug report and (c) size of successful run pool required to make a decent choice of successful run.