On-the-fly, incremental, consistent reading of entire databases

We describe an algorithm to read entire databases with locking concurrency control allowing multiple readersor an exclusive writer. The algorithm runs concurrently with the normal transaction processing (on-the-fly), and locks the entities in the database one by one (incremental). We prove that the algorithm produces consistent pictures of the database. We also show that conflicts between the algorithm and some updates, although necessary, can be resolved.Reading entire databases consistently, on-the-fly, incremental algorithms can avoid the database downtime trade-off between frequent checkpoints and crash recovery delay, thus improving system availability and reliability. Our algorithm reads the database once and writes only to sequential output, lowering its implementation and execution costs. A simple extension runs in parallel on several processors and produces consistent pictures of entire distributed databases.This work was partially supported by the National Science Foundation under Grant No. MCS-8004111.     

On-the-fly,incremental, consistent reading of entire databases

We describe an algorithm to read entire databases with locking concurrency control allowing multiple readersor an exclusive writer. The algorithm runs concurrently with the normal transaction processing (on-the-fly), and locks the entities in the database one by one (incremental). We prove that the algorithm produces consistent pictures of the database. We also show that conflicts between the algorithm and some updates, although necessary, can be resolved. Reading entire databases consistently, on-the-fly, incremental algorithms can avoid the database downtime trade-off between frequent checkpoints and crash recovery delay, thus improving system availability and reliability. Our algorithm reads the database once and writes only to sequential output, lowering its implementation and execution costs. A simple extension runs in parallel on several processors and produces consistent pictures of entire distributed databases.     

On-the-fly Curve-skeleton Computation for 3D Shapes

The curve-skeleton of a 3D object is an abstract geometrical and topological representation of its 3D shape. It maps the spatial relation of geometrically meaningful parts to a graph structure. Each arc of this graph represents a part of the object with roughly constant diameter or thickness, and approximates its centerline. This makes the curve-skeleton suitable to describe and handle articulated objects such as characters for animation. We present an algorithm to extract such a skeleton on-the-fly, both from point clouds and polygonal meshes. The algorithm is based on a deformable model evolution that captures the object's volumetric shape. The deformable model involves multiple competing fronts which evolve inside the object in a coarse-to-fine manner. We first track these fronts' centers, and then merge and filter the resulting arcs to obtain a curve-skeleton of the object. The process inherits the robustness of the reconstruction technique, being able to cope with noisy input, intricate geometry and complex topology. It creates a natural segmentation of the object and computes a center curve for each segment while maintaining a full correspondence between the skeleton and the boundary of the object.     

On-the-fly garbage collection for several mutators

Summary An algorithm is given for on-the-fly garbage collection in the presence of several mutators. It uses two colours and is a generalization of Ben-Ari's algorithm (1984). The correctness proof is based on the lexical orderings of several tuples of state space functions. It is shown that in a certain sense the algorithm is optimal. Three variations of the algorithm are given and proved correct. In the case that there is only one mutator one of these variations closely resembles a well-known incorrect algorithm. Jan E. Jonker was born in 1943. He received his Master's degree in Theoretical Physics in 1968 and his Master's degree in Computing Science in 1989, both from the University of Groningen. From 1968 until 1976 he did research on the electronic structure of dilute impurities in iron. From 1976 until 1989 he did research on the medical aspects of road accidents. Currently, he is assistant professor at the University of Groningen. His main research interests are programming methodology, parallel computations and delay-insensitive circuit design.     

On-the-fly calibrating strategies for evolutionary algorithms

The issue of controlling values of various parameters of an evolutionary algorithm is one of the most important and interesting areas of research in evolutionary computation. In this paper we propose two new parameter control strategies for evolutionary algorithms based on the ideas of reinforcement learning. These strategies provide efficient and low-cost adaptive techniques for parameter control and they preserve the original design of the evolutionary algorithm, as they can be included without changing either the structure of the algorithm nor its operators design.     

一种面向攻击图的即时验证方法

攻击图将原本孤立的攻击行为关联起来,描述潜在攻击路径,是一种网络脆弱性分析技术.现有方法通常从攻击目标节点开始进行反向搜索,找出所有可能的攻击路径,从而对网络进行安全分析.本文在攻击图的基础上,提出了一种基于正向搜索的即时验证方法.该方法快速搜索网络中的一条完整攻击路径,通常只需构造网络系统的部分状态空间,从而减轻了内...     

Stuttering-Insensitive Automata for On-the-fly Detection of Livelock Properties

The research examines liveness and progress properties of concurrent systems and their on-the-fly verification. An alternative formalism to Büchi automata, called testing automata, is developed. The basic idea of testing automata is to observe changes in the values of state propositions instead of the values. Therefore, the testing automata are able to accept only stuttering-insensitive languages. Testing automata can accept the same stuttering-insensitive languages as (state-labelled) Büchi automata, and they have at most the same number of states. They are also more often deterministic. Moreover, on-the-fly verification using testing automata can often (but not always) use an algorithm performing only one search in the state space, whereas on-the-fly verification with Büchi automata requires two searches. Experimental results illustrating the benefits of testing automata are presented.     

On-the-fly texture computation for real-time surface shading

Standard texture mapping hardware enables rapid rendering of color mapped surfaces with interpolated surface shading. New algorithms extend this to bump mapping, Phong shading, and reflection mapping. We first introduce the bidirectional reflectance function we wish to optimize, split into diffuse, specular and environment terms. Casting the diffuse term as a table lookup, we introduce lighting tables and efficient ways to compute them for distant lights. We also revisit the geometry of bump mapping, extending Blinn's (1978) results. We consider caching intermediate results for rendering animated rigid bodies, generalizing this to animated surfaces using a technique called parametric rasterization. Finally, we describe efficient reflection mapping and discuss implications for bump-mapped surfaces. We present a fast method for rendering Phong highlights and discuss a special case of a planar surface with simulated water ripples     

On-the-fly feature importance mining for person re-identification

State-of-the-art person re-identification methods seek robust person matching through combining various feature types. Often, these features are implicitly assigned with generic weights, which are assumed to be universally and equally good for all individuals, independent of people's different appearances. In this study, we show that certain features play more important role than others under different viewing conditions. To explore this characteristic, we propose a novel unsupervised approach to bottom-up feature importance mining on-the-fly specific to each re-identification probe target image, so features extracted from different individuals are weighted adaptively driven by their salient and inherent appearance attributes. Extensive experiments on three public datasets give insights on how feature importance can vary depending on both the viewing condition and specific person's appearance, and demonstrate that unsupervised bottom-up feature importance mining specific to each probe image can facilitate more accurate re-identification especially when it is combined with generic universal weights obtained using existing distance metric learning methods.     

On-the-fly and background data filtering system for database architectures

The discrepancy between the capacities of mass storage devices and main memory of computing systems is here to stay. The article introduces the concept of cost effective filtering with various options such as basic filter for selections, concurrent filtering extension for selections and projections, and concurrent filtering extension incorporating dynamic filtering for join, projection, and selection. After presenting these, detailed performance modeling of the filtering options is provided. Based on these performance models, a simulator is constructed and experiments for comparative filtering performance assessments are conducted. The results showed performance gains on the part of the systems employing filtering, especially in environments where high selectivities and concurrency are involved.     

On-the-fly program modification: systems for dynamic updating

Several dynamic software-based updating systems that are in the research and production stages are described. In particular, the procedure-oriented dynamic updating system (PODUS) is discussed. In PODUS, a program is updated by loading the new version of the program and replacing each old procedure with its corresponding new procedure during execution. Updating a procedure involves changing the binding from its current version to the new version. When all procedures have been replaced by their corresponding new versions, the program update is completed     

Object databases as generalizations of relational databases

One attractive approach to object databases is to see them as potentially an evolutionary development from relational databases. This paper concentrates on substantiating the technical basis for this claim, and illustrates it in some detail with an upwards-compatible extension of ANSI SQL2 for conventional objects. This could serve as a foundation for the development of higher-level facilities for more complex objects.     

XML数据库和关系数据库之比较

XML已经成为数据表示和交换的数据格式标准。随着大量XML文档的出现,应用数据库技术实现对XML数据的管理引起了越来越多研究者的兴趣。作为研究XML数据库技术的一个开始点,通过与关系数据库比较,可以深刻理解XML数据库与关系数据库的异同,进而为解决XML数据库所面临的问题,如为数据冗余控制、并发访问控制等提供必要的基础。两种数据库的比较是从数据模型、查询路径、完整性约束和规范化5个方面进行的,由于数据模型是数据库的基石,二者的数据模型从构造机制、名字的惟一性、空值、实体标识、实体问关系、文档顺序、数据结构的规则性、递归、数据自描述性等9个方面进行了详细讨论。     

On-the-fly verification and optimization of DTA-properties for large Markov chains

We consider continuous-time Markov chains (CTMC) with very large or infinite state spaces which are, for instance, used to model biological processes or to evaluate the performance of computer and communication networks. We propose a numerical integration algorithm to approximate the probability that a process conforms to a specification that belongs to a subclass of deterministic timed automata (DTAs). We combat the state space explosion problem by using a dynamic state space that contains only the most relevant states. In this way we avoid an explicit construction of the state-transition graph of the composition of the DTA and the CTMC. We also show how to maximize the probability of acceptance of the DTA for parametric CTMCs and substantiate the usefulness of our approach with experimental results from biological case studies.     

On-the-fly generation of multi-robot team formation strategies based on game conditions

This paper describes a new model to automatically generating dynamic formation strategies for robotic soccer applications based on game conditions, regarded to as favorable or unfavorable for a robotic team. Decisions are distributedly computed by the players of a multi-agent team. A game policy is defined and applied by a human coach who establishes the attitude of the team for defending or attacking. A simple neural net model is applied using current and previous game experience to classify the game’s parameters so that the new game conditions can be determined so that a robotic team can modify its strategy on-the-fly. Experiments and results of the proposed model for a robotic soccer team show the promise of the approach.     

On-the-fly repair of structural and lexical ontology mismatches in multi-agent systems

In a Semantic-Web-like multi-agent environment, ontology mismatch is inevitable: we can’t realistically expect agents created at different times and places by different people to commit to one unchanging universal ontology. Ontology matching seems to be the only solution to such a problem. However, standard techniques for aligning heterogeneous ontologies are based on time-consuming, off-line and often semi-automated processes and pre-suppose full access to the interacting agents’ ontologies. This is far from ideal in situations where agents meet for the first time, interact quickly and have restricted access to other agents’ private information. In this paper we present the Ontology Repair System (ORS), which attempts to match fully-fledged first-order ontologies automatically using incomplete information. Particular emphasis is laid on its semantic matching module, the Semantic Matcher, which provides a solution for lexical mismatches, which are the most common and the most challenging to address. ORS and the Semantic Matcher have been implemented and evaluated, with very promising results.     

Semantic sampling of existing databases through informative Armstrong databases

Functional dependencies (FDs) and inclusion dependencies (INDs) convey most of data semantics in relational databases and are very useful in practice since they generalize keys and foreign keys. Nevertheless, FDs and INDs are often not available, obsolete or lost in real-life databases. Several algorithms have been proposed for mining these dependencies, but the output is always in the same format: a simple list of dependencies, hard to understand for the user. In this paper, we define informative Armstrong databases (IADBs) from databases as being small subsets of an existing database, satisfying exactly the same FDs and INDs. They are an extension of the classical notion of Armstrong databases, but more suitable for the understanding of dependencies, since tuples are real-world tuples. The main result of this paper is to bound the size of an IADB in the case of non-circular INDs. A constructive proof of this result is given, from which an algorithm has been devised. An implementation and experiments against a real-life database were performed; the obtained database contains 0.6% of the initial database tuples only. More importantly, such semantic sampling of databases appear to be a key feature for the understanding of existing databases at the logical level.     

VORD: A Versatile On-the-fly Race Detection Tool in OpenMP Programs

Shared-memory based parallel programming with OpenMP and Posix-thread APIs becomes more common to fully take advantage of multiprocessor computing environments. One of the critical risks in multithreaded programming is data races that are hard to debug and greatly damaging to parallel applications if they are uncaught. Although ample effort has been made in building specialized data race detection techniques, the state of art tools such as the Intel Thread Checker still have various functionality and performance problems. In this paper, we present a Versatile On-the-fly Race Detection (VORD) tool that provides an agile, efficient, and scalable race detection environment for various parallel programming models. VORD can automatically construct an empirically optimal set of race engines by utilizing classification and adaptation mechanisms. A Race-Detection Classification (RDC) table is created to categorize adequate engines in the aspect of labeling, detecting, and filtering. An Engine Code Property Selector (ECPS) uses the RDC table to adapt optimal engines for the given target programming models. In addition to RDC and ECPS, we have also implemented an OpenMP parser and a source instrumentor. The functionality and efficiency of VORD were compared with those of the Intel Thread Checker by using a set of OpenMP based kernel programs. The experimental results show that VORD can detect data races in more challenging programming models such as nested thread and synchronization models, and can achieve a couple of orders of a magnitude faster processing time than the Intel Thread Checker in the large parallel programs.