36409029
Object testing in ITEE
To assure the quality of software by running test cases and evaluating the results is one of the difficult parts of the entire software development project. The difficulty usually comes from the lack of appropriate supporting tools and the complexity of the software. In the past ad hoc supporting tools were made for each project and test results were usually not used across projects. This conventional way of test and evaluation (T & E) is time consuming, and the most important decision "When is this software ready to ship?" is left to the engineers depending on his/her experience. Our objective is to build a knowledge-based T & E environment such that test cases, test results, object snapshots and other information are accumulated in a database. These longitudinal data can be automatically tracked and analyzed to provide decision support information. As a result, test results can be reviewed repeatedly and software quality can be assured by analyzing these data from various perspectives. We describe the details of object testing in our testing environment.
42266951
TMO-structured cluster-based real-time management of location data on massive volume of moving items
A major challenge in the field of location based service (LBS) system engineering, is to establish a highly scalable system architecture which can be instantiated in moderate-size configurations handling thousands of moving items as well as in upper-end configurations handling millions of moving items. We are exploring an approach of using a cluster of database server nodes and effecting efficient distributed and parallel computing in both real-time update of location records of moving items and processing of location-related queries. The approach of developing efficient middleware which is layered on a cluster of nodes running commercial off-the-shelf database servers, has been adopted. The middleware design is substantially based on the TMO scheme for real-time distributed object programming and real-time distributed computing system design, which enables low-overhead coordination of distributed computations and highly abstract distributed programming styles.
207130153
A Software Test and Evaluation Environment Based on Longitudinal Database
To assure the quality of software by running test cases and evaluating the results is one of the difficult parts of the entire software development project. The difficulty usually comes from the lack of appropriate supporting tools and the complexity of the software. In the past ad hoc supporting tools were made for each project and test results were usually not used across projects. This conventional way of test and evaluation (T&E) is time consuming, and the most important decision "When is this software ready to ship?" is left to the engineers depending on their experiences. Our objective is to build a knowledge-based T&E environment such that tests cases, test results, object snapshots and other information are accumulated in a database. These longitudinal data can be automatically tracked and analyzed to provide decision support information. As a result, test results can be reviewed repeatedly and software quality can be assured by analyzing these data from various perspectives.
9564557
An Object-Oriented Approach to Shadow Generation in Computer Graphics
This paper presents an object-oriented shadow generation algorithm for a large number of convex polyhedra (objects) in a 3-D scene. In the past, the shadow volume binary space partitioning (SVBSP) tree algorithm is known to be efficient in a static environment in which the point light source can be changed. However, if a scene consists of many objects and each object consists of many polygons, the time complexity for generating and traversing an SVBSP tree increases rapidly because the SVBSP tree algorithm only deals with polygons which are components of objects. Furthermore, the SVBSP tree algorithm suffers from polygon-splitting problems resulting in a high cost as the number of polygons increases. Our approach is object-oriented in the sense that an object is used as the basic logical unit instead of polygons. In the preprocessing stage the object ordering for shadow generation is determined for all possible light source positions. At the run time, the shadow detection algorithm is executed, and if nec...
5688593
A Cluster-Based TMO-Structured Scalable Approach for Location Information Systems
Location-based service (LBS) systems have recently become a subject of active research and development. A key issue in such systems is efficient management of current and past location information of moving items. In the past two years, we have been establishing a new LBS system architecture, named the GALIS (Gracefully Aging Location Information System), which is based on the new approach of using a cluster of database server nodes and effecting efficient distributed and parallel computing in both real-time update of location records of moving items and processing of location-related queries. Each server node is dedicated to keeping records relevant to a different geographical zone and a different temporal zone. Each subsystem in GALIS is structured as a TMO network for the sake of easy analysis and expansion. A prototype implementation of GALIS has been realized only partially, and its full implementation is under way. In this paper, major features of GALIS are presented together with discussions on trade-off considerations which led to the adoption of those features. Issues remaining for further research are also briefly discussed.
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.
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. >
12394125
Using compressed bytecode traces for slicing Java programs
Dynamic slicing is a well-known program debugging technique. Given a program P and input I, it finds all program statements which directly/indirectly affect the values of some variables' occurrences when P is executed with I. Dynamic slicing algorithms often proceed by traversing the execution trace of P produced by input I (or a dependence graph which captures control/data flow in the execution trace). Consequently, it is important to develop space efficient representations of the execution trace. In this paper, we use results from data compression to compactly represent bytecode traces of sequential Java programs. The major space savings come from the optimized representation of data (instruction) addresses used by memory reference (branch) bytecodes as operands. We give detailed experimental results on the space efficiency and time overheads for our compact trace representation. We then show how dynamic slicing algorithms can directly traverse our compact traces without resorting to costly decompression. We also develop an extension of dynamic slicing which allows us to explain omission errors (i.e. why some events did not happen during program execution).
33246096
Optimal net assignment
We study in this paper the net assignment problem subject to the capacity constraint, selection constraint and routing constraint. Given two adjacent channels separated by a cell row, and a set of nets in each of the two channels, this problem is to assign to the cell row a subset of nets in each channel such that without violating any given constraint, the sum of the remaining densities of the two channels is minimized. The capacity constraint requires the density caused by the nets, which are assigned to the cell row, to be no more than a user-specified number k, where k is no more than the number of tracks available for routing over that cell row. The selection constraint specifies in each channel the subset of nets which are candidates to be assigned to the cell row. The routing constraint requires each net to be either completely assigned to the cell row or to stay in its channel. This problem can find its application in modeling a practical over-the-cell routing problem in which the whole region over the cell row is two-layer routable for the nets in the two adjacent channels. We present an optimal algorithm to solve this problem and provide experimental results to support our algorithm. >
15147164
Balanced incomplete designs for 3D perceptual quality estimation
Many factors, such as the number of vertices and the resolution of texture, can affect the display quality of 3D objects. When the resources of a graphics system are not sufficient to render the ideal image, degradation is inevitable. It is therefore important to study how individual factors affect the overall quality, and how the degradation can be controlled given limited resources. The essential factors determining the display quality are reviewed and a 3D perceptual estimation method is described. One of the major concerns in designing perceptual experiments is the large number of evaluations to be performed by judges, which results in fatigue and errors in judgement. To reduce judging fatigue and increase reliability of evaluations we propose using a statistical approach, following the design of experiments technique of balanced incomplete block design (BIBD). We develop models following BIBD for perceptual experiments and validate our model with experimental results. Even though the BIBD framework for perceptual evaluations is described in the context of 3D quality estimation, the approach can be used in other perceptual evaluation scenarios as well.
566237
Regularized discriminant analysis for high dimensional, low sample size data
Linear and Quadratic Discriminant Analysis have been used widely in many areas of data mining, machine learning, and bioinformatics. Friedman proposed a compromise between Linear and Quadratic Discriminant Analysis, called Regularized Discriminant Analysis (RDA), which has been shown to be more flexible in dealing with various class distributions. RDA applies the regularization techniques by employing two regularization parameters, which are chosen to jointly maximize the classification performance. The optimal pair of parameters is commonly estimated via cross-validation from a set of candidate pairs. It is computationally prohibitive for high dimensional data, especially when the candidate set is large, which limits the applications of RDA to low dimensional data.In this paper, a novel algorithm for RDA is presented for high dimensional data. It can estimate the optimal regularization parameters from a large set of parameter candidates efficiently. Experiments on a variety of datasets confirm the claimed theoretical estimate of the efficiency, and also show that, for a properly chosen pair of regularization parameters, RDA performs favorably in classification, in comparison with other existing classification methods.