A 3-way Merging Algorithm for Synchronizing Ordered Trees - the 3DM merging and differencing tool for XML
- A -way Merging Algorithm For; Instructor M. Sc; Mervi Ranta; Tancred Lindholm; Tancred Lindholm
In the thesis, we find that the requirements of synchronizing structural data call for a tool capable of performing a 3-way merge of general ordered trees without any additional tree metadata, such as edit histories or unique node identifiers, that describe how the trees participating in the merge are related. The main research problem of the thesis is to design such an algorithm, given that no suitable algorithms exist. The design of the algorithm is preceded by stating a definition of desired merging behaviour derived from use cases as well as a relatively large number of small hand-written merging examples....
Query Localization Techniques for On-demand Routing Protocols in Ad Hoc Networks
- Robert Castañeda; Samir R. Das
Mobile ad hoc networks are characterized by multi-hop wireless links, absence of any cellular infrastructure, and frequent host mobility. Design of efficient routing protocols in such networks is a challenging issue. A class of routing protocols called on-demand protocols has recently found attention because of their low routing overhead. We propose a technique that can reduce the routing overhead even further. The on-demand protocols depend on query floods to discover routes whenever a new route is needed. Our technique utilizes prior routing histories to localize the query flood to a limited region of the network. Simulation results demonstrate excellent reduction...
Modeling Medical Trials in Pharmacoeconomics using a Temporal Object Model
- Iqbal Goralwalla Tamer; M. Tamer Ozsu; Duane Szafron
Time is an inherent feature of many medical applications. These applications can also benefit from the support of object database management systems which better capture the semantics of the complex objects that arise in the medical domain. In this paper, wepresent a uniform behavioral temporal object model which includes a rich and extensible set of types and behaviors to support the various features of a medical application. We concentrate here on the application of pharmacoeconomic medical trials. Pharmacoeconomics is a field of medical economics in which the costs and outcomes of alternative treatments are assessed and compared, in order to...
Managing Schema Evolution using a Temporal Object Model
- Iqbal A. Goralwalla; Duane Szafron; M. Tamer Özsu; Randal J. Peters
The issues of schema evolution and temporal object models are generally considered to be orthogonal and are handled independently. This is unrealistic because to properly model applications that need incremental design and experimentation (such as CAD, software design process), the evolutionary histories of the schema objects should be traceable. In this paper we propose a method for managing schema changes by exploiting the functionality of a temporal object model. The result is a uniform treatmentofschema evolution and temporal support for many object database management systems applications that require both.
AFamily of Speculative Concurrency Control Algorithms for Real-Time Databases
- Azer Bestavros; Spyridon Braoudakis
Speculative Concurrency Control (SCC) was proposed in [Best92b] as a new concurrency control approach especially suited for real-time database applications. SCC relies on the use of redundancy to ensure that serializable schedules are discovered and adopted as early as possible, thus increasing the likelihood of the timely commitment of transactions with strict timing constraints. Using SCC, several shadow transactions execute on behalf of a given uncommitted transaction so as to protect against the hazards of blockages and restarts, whichare characteristics of Pessimistic and Optimistic Concurrency Control algorithms, respectively. We present SCC-nS, a generic algorithm that characterizes a family of SCCbased...
What is a structural representation
- Lev Goldfarb; Oleg Golubitsky; Dmitry Korkin
We outline a formal foundation for a \structural " (or \symbolic") object/event representation, the necessity of which is acutely felt in all sciences, including mathematics and computer science. The proposed foundation incorporates two hypotheses: 1) the object's formative history must be an integral part of the object representation and 2) the process of object construction is irreversible, i.e. the \trajectory " of the object's formative evolution does not intersect itself. The last hypothesis is equivalent to the generalized axiom of (structural) induction. Some of the main diculties associated with the transition from the classical numeric to the structural representations appear...
Handling Temporal Grouping and Pattern-Matching Queries in a Temporal Object Model
- Marlon Dumas; Marie-Christine Fauvet; Pierre-claude Scholl
This paper presents a language for expressing temporal pattern-matching queries, and a set of temporal grouping operators for structuring histories following calendar-based criteria. Pattern-matching queries are shown to be useful for reasoning about successive events in time while temporal grouping may be either used to aggregate data along the time dimension or to display histories. The combination of these capabilities allows to express complex queries involving succession in time and calendar-based conditions simultaneously. These operators are embedded into the TEMPOS temporal data model and their use is illustrated through examples taken from a geographical application. The proposal has been validated...
A representation-independent temporal extension of ODMG's Object Query Language
- Marie-Christine Fauvet; Marlon Dumas; Pierre-claude Scholl
TEMPOS is a set of models providing a framework for extending database systems with temporal functionalities. Based on this framework, an extension of the ODMG's object database standard has been defined. This extension includes a hierarchy of abstract datatypes for managing temporal values and histories, as well as temporal extensions of ODMG's object model, schema definition language and query language. This paper focuses on the latter, namely TEMPOQL. With respect to related proposals, the main originality of TEMPOQL is that it allows to manipulate histories regardless of their representations, by composition of functional constructs. Thereby, the abstraction principle of object-orientation...
Modeling Histories in Object DBMS
- Marie-Christine Fauvet; Jean-François Canavaggio; Pierre-claude Scholl
. Temporal DBMS offer concepts and functionalities related to data timestamping and history management. Analyzing the numerous approaches in this field demonstrate a significant lack of unification of the main results, thus postponing the emergence of commercial products. This problem is about to be solved for the relational approach, e.g. through the definition of the TSQL2 language. However, there is still much to be done in the context of object DBMS. This paper proposes an historical model integrating the main functionalities needed by an object DBMS to cope with the data historical dimensions. Key words: temporal databases, data history, temporal...
Real-Time Transactions with Execution Histories: Priority Assignment and Load Control
- Erdogan Dogdu; Gültekin Özsoyoglu; Ozsoyo Glu
In this paper, we consider new priority assignment and load control policies for real-time transactions. We assume that execution histories of transactions under different load conditions are available, and propose a number of priority assignment techniques based on execution histories and evaluate them through simulation. A widely used priority assignment technique, Earliest Deadline First, is shown to be biased towards scheduling short transactions favorably. We introduce the notion of "fair scheduling" of transactions in which the goal is to have "similar" success ratios for all transaction classes (short to long in sizes). 1 Introduction In this paper, we consider real-time...
Visual Exploration of Temporal Object Databases
- Chaouki Daassi; Marlon Dumas; Marie-Christine Fauvet; Laurence Nigay; Pierre-claude Scholl
Two complementary families of users' tasks may be identified during database visualization: data browsing and data analysis. On the one hand, data browsing involves extensively exploring a subset of the database using navigational interaction techniques. Classical object database browsers provide means for navigating within a collection of objects and amongst objects by way of their relationships. In temporal object databases, these techniques are not sufficient to adequately support time-related tasks, such as studying a snapshot of a collection of objects at a given instant, or detecting changes within temporal attributes and relationships. Visual data analysis on the other hand, is...
Modeling Video Temporal Relationships in an Object Database Management System
- John Z. Li; Iqbal A. Goralwalla; M. Tamer Özsu; Duane Szafron
One of the key aspects of videos is the temporal relationship between video frames. In this paper we propose a tree-based model for specifying the temporal semantics of video data. We present a unique wayofintegrating our video model into an object database management system which has richmultimedia temporal operations. We further showhow temporal histories are used to model video data, explore the video objectbase using object-oriented techniques. Such a seamless integration gives a uniform interface to end users. The integrated video objectbase management system supports a broad range of temporal queries.
HIV/AIDS and Fertility
- Jane G. Fortson
This paper studies the response of fertility to the HIV/AIDS epidemic in sub-Saharan Africa. Standard models of fertility have ambiguous predictions in this context. Because childbirth requires unprotected sex (which increases the risk of contracting HIV), we might expect HIV/AIDS to reduce fertility through an infection avoidance motive. Adding to this decline, HIV infection may itself reduce fecundity among infected women. However, because HIV/AIDS affects the expected longevity of children, a quantity-quality model of childbearing would predict an increase in fertility. I use repeated cross-sections of the Demographic and Health Surveys for twelve countries in sub-Saharan Africa to examine this...
Untangling Tanglegrams: Comparing Trees by their Drawings ∗
- Balaji Venkatachalam; Katherine St. John; Dan Gusfield
A tanglegram is a pair of trees on the same set of leaves with matching leaves in the two trees joined by an edge. Tanglegrams are widely used in biology – to compare evolutionary histories of host and parasite species and to analyze genes of species in the same geographical area. We consider optimizations problems in tanglegram drawings. We show a linear time algorithm to decide if a tanglegram admits a planar embedding by a reduction to the planar graph drawing problem. This problem was also studied by Fernau, Kauffman and Poths (FSTTCS 2005). A similar reduction to a graph...
Educational Data Mining 2009 Edu-mining for Book Recommendation for Pupils
- Ryo Nagata; Keigo Takeda; Koji Suda; Junichi Kakegawa; Koichiro Morihiro
Abstract. This paper proposes a novel method for recommending books to pupils based on a framework called Edu-mining. One of the properties of the proposed method is that it uses only loan histories (pupil ID, book ID, date of loan) whereas the conventional methods require additional information such as
Lumpy Capital, Labor Market Search and Employment Dynamics over Business Cycles
- Zhe Li; Jianfei Sun; Aloysius Siow; Aubhik Khan; Gueorgui Kambourov; Xiaodong Zhu; Elena Capatina
This paper incorporates labor search frictions into a model with lumpy capital to explain a set of stylized facts about the United States labor market dynamics over business cycles. All of these facts are related to …rm size: (1) job creation is procyclical in both small and large …rms; (2) job destruction is countercyclical in large …rms, but, paradoxically, it is procyclical in small …rms; and (3) job creation and job destruction are more volatile in large …rms than in small …rms. The model is calibrated to US data and its predictions are broadly consistent with the facts. The success...
Automatic Selection of Radiological Protocols using Machine Learning
- Akshay Bhat; George Shih Md; Ramin Zabih
Medical imaging modalities, such as computed tomography (CT), have a large number of parameters that must be correctly set to produce a diagnostic image. In current clinical practice this is done with input from a radiologist, relying on the patient history provided in textual form by the referring physician. Since the set of parameters is so extensive, radiologists choose from a limited number of protocols, each of which is suited to a group of diseases. We propose a machine learning approach automate to this process, relying on the free-form textual input provided by the referring physician. We exploit an ontology...
Analysis of Google Logs Retention Policies
- Vincent Toubiana; Helen Nissenbaum
Abstract. To preserve search log data utility, Google groups search queries in log bundles by deleting the last octet of logged IP address. Because these bundles still contain identifying information, part of these search logs can be de-anonymized . Without an external audit of these search logs, it is currently impossible to evaluate their robustness against de-anonymizing attacks. In this paper, we leverage log retention policy ambiguities to show that quasi-identifiers could be stored in sanitized search query logs and could help to de-anonymize user searches. This paper refers to Google Search and Google Suggest log retention policies and shows...
16.851 Assignment #1, 2003-09-17 Problem Statement
The design of a spacecraft power subsystem is an important driver for the mass, size, and capability of the spacecraft. Every other spacecraft subsystem is affected by the power subsystem, and in particular, important issues such as communications bandwidth, thermal regulation, and structural design are largely influenced by the capabilities and limitations of the power system. The motivation for this problem is the broad applicability of a power-system design tool to a wide range of future design problems. Requirements Given time histories of the power load and power source, design a power subsystem that optimizes with respect to some specified...
Repeatability of Full-Scale Crash Tests and a Criteria for Validating Simulation Result’s
- Malcolm H. Ray
This paper describes a method of comparing two acceleration time histories to determine if they describe similar physical events. The method can be used to assess the repeatability of full-scale crash tests and it can also be used as a criterion for assessing how well a finite element analysis of a collision event simulates a corresponding full-scale crash test. The method is used to compare a series of six identical crash tests and then is used to compare a finite element analysis to a fullscale crash test.