International Telemetering Conference Proceedings / October 28-31, 1996 / Town and Country Hotel and Convention Center, San Diego, California / The emergence of encrypted PCM as a standard within DOD makes possible the correction of time skews between diverse data sources. Time alignment of data streams can be accomplished before decryption and so is independent of specific format. Data quality assessment in order to do a best-source selection remains problematic, but workable.

Large software projects are characterized by distributed environments consisting of teams at different organizations and geographical locations. These teams typically build multiple overlapping models, representing different perspectives, different versions across time, different variants in a product family, different development concerns, etc. Keeping track of the relationships between these models, constructing a global view, and managing consistency are major challenges. Model Management is concerned with describing the relationships between distributed models, i.e., models built in a distributed development environment, and providing systematic operators to manipulate these models and their relationships. Such operators include, among others, Match, for finding relationships between disparate models, Merge, for combining models with respect to known or hypothesized relationships between them, Slice, for producing projections of models and relationships based on given criteria, and Check-Consistency, for verifying models and relationships against the consistency properties of interest. In this thesis, we provide automated solutions for two key model management operators, Merge and Check-Consistency. The most novel aspects of our work on model merging are (1) the ability to combine arbitrarily large collections of interrelated models and (2) support for toleration of incompleteness and inconsistency. Our consistency checking technique employs model merging to reduce the problem of checking inter-model consistency to checking intra-model consistency of a merged model. This enables a flexible way of verifying global consistency properties that is not possible with other existing approaches. We develop a prototype tool, TReMer+, implementing our merge and consistency checking approaches. We use TReMer+ to demonstrate that our contributions facilitate understanding and refinement of the relationships between distributed models.

Large software projects are characterized by distributed environments consisting of teams at different organizations and geographical locations. These teams typically build multiple overlapping models, representing different perspectives, different versions across time, different variants in a product family, different development concerns, etc. Keeping track of the relationships between these models, constructing a global view, and managing consistency are major challenges. Model Management is concerned with describing the relationships between distributed models, i.e., models built in a distributed development environment, and providing systematic operators to manipulate these models and their relationships. Such operators include, among others, Match, for finding relationships between disparate models, Merge, for combining models with respect to known or hypothesized relationships between them, Slice, for producing projections of models and relationships based on given criteria, and Check-Consistency, for verifying models and relationships against the consistency properties of interest. In this thesis, we provide automated solutions for two key model management operators, Merge and Check-Consistency. The most novel aspects of our work on model merging are (1) the ability to combine arbitrarily large collections of interrelated models and (2) support for toleration of incompleteness and inconsistency. Our consistency checking technique employs model merging to reduce the problem of checking inter-model consistency to checking intra-model consistency of a merged model. This enables a flexible way of verifying global consistency properties that is not possible with other existing approaches. We develop a prototype tool, TReMer+, implementing our merge and consistency checking approaches. We use TReMer+ to demonstrate that our contributions facilitate understanding and refinement of the relationships between distributed models.

Lazy replication with snapshot isolation (SI) has emerged as a popular choice for distributed databases. However, lazy replication requires the execution of update transactions at one (master) site so that it is relatively easy for a total SI order to be determined for consistent installation of updates in the lazily replicated system. We propose a set of techniques that support update transaction execution over multiple partitioned sites, thereby allowing the master to scale. Our techniques determine a total SI order for update transactions over multiple master sites without requiring global coordination in the distributed system, and ensure that updates are installed in this order at all sites to provide consistent and scalable replication with SI. We have built our techniques into PostgreSQL and demonstrate their effectiveness through experimental evaluation.

Geometric models, such as for use in CAD/CAM or animation, are often constructed in a piece-wise fashion. Historically, these models have been made of NURBS surfaces. For various reasons it is problematic and often times mathematically impossible to combine several NURBS models into one continuous surface. The recent invention of a surface type called T-splines has made the combining of NURBS surfaces into a single continuous surface possible, but much of the mathematics has yet to be explored. This thesis explores the mathematics and algorithms necessary to merge multiple NURBS, T-spline, or T-NURCC surfaces into a single continuous surface. This thesis addresses two main problems. The first problem is merging surfaces with different parameterizations. In order to merge surfaces with different parameterizations, it is often necessary to modify the parameter values of the surface, which can change the shape of the surface. This change can be alleviated through shape control methods. The second problem is merging surfaces that meet at extraordinary points, or points with a valence other than four. Results show that the merging algorithm is able to successfully convert models composed of multiple NURBS, T-spline, or T-NURCCS surfaces into models composed of a single T-spline or T-NURCC surface. The resulting models are gap-free and contain little distortion in the parameterization.

This thesis addresses the problem of tool support for semi-automatic ontology mapping and merging. Solving this problem contributes to ontology creation and evolution by relieving users from tedious and time-consuming work. This thesis shows that a tool can be built that will take a “mini-ontology” and a “growing ontology” as input and make it possible to produce manually, semi-automatically, or automatically an extended growing ontology as output. Characteristics of this tool include: (1) a graphical, interactive user interface with features that will allow users to map and merge ontologies, and (2) a framework supporting pluggable, semi-automatic, and automatic mapping and merging algorithms.

In this thesis we investigate some global desiderata for probabilistic knowledge merging given several possibly jointly inconsistent, but individually consistent knowledge bases. We show that the most naive methods of merging, which combine applications of a single expert inference process with the application of a pooling operator, fail to satisfy certain basic consistency principles. We therefore adopt a different approach. Following recent developments in machine learning where Bregman divergences appear to be powerful, we define several probabilistic merging operators which minimise the joint divergence between merged knowledge and given knowledge bases. In particular we prove that in many cases the result of applying such operators coincides with the sets of fixed points of averaging projective procedures - procedures which combine knowledge updating with pooling operators of decision theory. We develop relevant results concerning the geometry of Bregman divergences and prove new theorems in this field. We show that this geometry connects nicely with some desirable principles which have arisen in the epistemology of merging. In particular, we prove that the merging operators which we define by means of convex Bregman divergences satisfy analogues of the principles of merging due to Konieczny and Pino-Perez. Additionally, we investigate how such merging operators behave with respect to principles concerning irrelevant information, independence and relativisation which have previously been intensively studied in case of single-expert probabilistic inference. Finally, we argue that two particular probabilistic merging operators which are based on Kullback-Leibler divergence, a special type of Bregman divergence, have overall the most appealing properties amongst merging operators hitherto considered. By investigating some iterative procedures we propose algorithms to practically compute them.

Master of Science / Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programming is a field of mathematical optimization that has applications across a wide variety of industries and fields including business, government, health care and military. A commonly studied integer program is the knapsack problem, which has applications including project and portfolio selection, production planning, inventory problems, profit maximization applications and machine scheduling. Integer programs are computationally difficult and currently require exponential effort to solve. Adding cutting planes is a way of reducing the solving time of integer programs. These cutting planes eliminate linear relaxation space. The theoretically strongest cutting planes are facet defining inequalities. This thesis introduces a new class of cutting planes called multiple variable merging cover inequalities (MVMCI). The thesis presents the multiple variable merging cover algorithm (MVMCA), which runs in linear time and produces a valid MVMCI. Under certain conditions, an MVMCI can be shown to be a facet defining inequality. An example demonstrates these advancements and is used to prove that MVMCIs could not be identified by any existing techniques. A small computational study compares the computational impact of including MVMCIs. The study shows that finding an MVMCI is extremely fast, less than .01 seconds. Furthermore, including an MVMCI improved the solution time required by CPLEX, a commercial integer programming solver, by 6.3% on average.

ITC/USA 2005 Conference Proceedings / The Forty-First Annual International Telemetering Conference and Technical Exhibition / October 24-27, 2005 / Riviera Hotel & Convention Center, Las Vegas, Nevada / Multiple receiver telemetry systems are common in the aeroballistics test and evaluation community. These systems typically record telemetry data independently, requiring post-flight data processing to produce the most accurate combination of the available data. This paper addresses the issues of time synchronization between multiple data sources and determination of the best choice for each data word. Additional filtering is also developed for the case when all available data are corrupted. The performance of the proposed algorithms is presented.

International Telemetering Conference Proceedings / October 18-21, 2004 / Town & Country Resort, San Diego, California / Multiple receiver telemetry systems are common in the aeroballistics test and evaluation community. These systems typically record telemetry data independently, requiring post-flight data processing to produce the most accurate combination of the available data. This paper addresses the issues of time synchronization between multiple data sources and determination of the best choice for each data word. Additional filtering is also developed for the case when all available data are corrupted. The performance of the proposed algorithms is presented.