42699164
Computation-Tuple Sequences and Object Histories: Extended Abstract
Recently, much attention has been focussed on database aspects of office automation and their associated research problems [A,EN,PFK,SIGMOD,SSLKG]. One major component in this area is a facility to manage historical data for many “objects”, namely, an object history (management) system. Examples of such systems are those for personal checking account, salary reviews and schedules. However, there has been little widely accepted mathematical formalism which captures major aspects of the historical data for the objects (here called object histories) and permits the identification and analysis of relevant issues. The purpose of the present paper is to introduce a mathematical model allowing such an investigation1.
46335278
Tree-Structured Data Organization with Consecutive Retrieval Property
COMP2011 Aleksandar Ignjatovic 2005 c 2 Figure 1: A medieval copy of arguably the most influential textbook ever written, Eu-clid's Elements (Στoι χε´ια), from about 300 BC. It contains the oldest known algorithm recorded, Euclid's algorithm for computing the Greatest Common Divisor (GCD) of two natural numbers. Figure 2: First data structures: a Mesopotamian cuneiform tablet from about 3000 BC with an inventory list. Preface This booklet is not meant to be a textbook, but only a companion to the textbook that we use in this course, Cormen, Leiserson, Rivest and Stein's Introduction to Algorithms, the second edition. Its purpose is to help you read the appropriate sections of the textbook, and integrate it better with the rest of the course. It also adds a number of exercises not present in the textbook. Please read the textbook and do not rely on this supplement only.
18193868
Interval Queries on Object Histories: Extended Abstract
This extended abstract introduces the notion of ’ interval queries ’ on historical data for objects (here, called ‘object histories’) and explores a certain closure property. As for describing historical data for objects, we use our mathematical model introduced in our earlier paper. The major construct in the model is a ‘computation-tuple sequence scheme’ (abbreviated CSS), which specifies the set of all possible ‘valid’ object histories for the same type of object. Interval queries are those queries which return an interval (history) from a given object history. We provide conditions under which an interval query applied to object histories described by one CSS yields, as its answers. the set of all object histories which can be described by another CSS.
5408151
Alternative Objects in Object-oriented Databases
1810071
Testing of Join Dependency Preserving by a Modified Chase Method
205099974
Organization of quasi-consecutive retrieval files
Abstract In 1972, Ghosh introduced the consecutive retrieval (CR) file organization. It is an efficient file organization in which all records pertinent to a query are consecutively stored on linear storage locations. In this paper, we introduce the quasi-consecutive retrieval (QCR) file organization. The QCR file organization is an extension of Ghosh's CR file organization and normally offers less redundancy. In the QCR file, all the records pertinent to each query are not necessarily stored consecutively, but rather they are stored within an area of the buffer size. In this paper, we discuss graph theoretic properties of CR files and QCR files by using the properties of interval graphs well known in graph theory. We provide a basic condition for the existence of a QCR file without redundancy for a given buffer size. By introducing redundant queries, such a condition is simplified. Furthermore, a heuristic computer algorithm is given to organize a QCR file with less redundancy for a given buffer size.
120935286
Automatic hyperparameter estimation in probabilistic image restoration algorithm based on Gibbs microcanonical distribution
For an original image given as an 8-gray-level image, the framework for image restoration is composed of Bayes statistics for the a priori probability distribution based on the microcanonical distribution. In this process, the a priori probability distribution serving as the microcanonical distribution is formulated on the basis of the variables characterizing the spatial flatness and smoothness of the image in terms of the number of nearest pixel pairs with different gray levels and the number of nearest pixel pairs with gray levels differing by 1. In the present paper, we propose a new method of estimation, from a degraded image, of the number of nearest pixel pairs with different gray levels and the number of nearest pixel pairs with gray levels differing by 1 in the original image. Then, based on that formulation, an iterative computation algorithm for the restoration of a 256-gray-level image is presented from the viewpoint of statistical mechanics. Through some numerical experiments, we investigate how the proposed method can improve the quality of the restored image. © 2004 Wiley Periodicals, Inc. Syst Comp Jpn, 36(1): 68–78, 2005; Published online in Wiley InterScience (). DOI 10.1002sscj.10365
8895020
The strong soundness theorem for real closed fields and Hilbert’s Nullstellensatz in second order arithmetic
Abstract.By RCA0, we denote a subsystem of second order arithmetic based on Δ01 comprehension and Δ01 induction. We show within this system that the real number system R satisfies all the theorems (possibly with non-standard length) of the theory of real closed fields under an appropriate truth definition. This enables us to develop linear algebra and polynomial ring theory over real and complex numbers, so that we particularly obtain Hilbert’s Nullstellensatz in RCA0.
7133208
Statistical Learning Procedure in Loopy Belief Propagation for Probabilistic Image Processing
We give a fast and practical algorithm for statistical learning hyperparameters from observable data in probabilistic image processing, which is based on Gaussian graphical model and maximum likelihood estimation. Although hyperparameters in the probabilistic model are determined so as to maximize a marginal likelihood, a practical algorithm is described for the EM algorithm with the loopy belief propagation which is one of approximate inference algorithms in artificial intelligence
11983347
Linear Response Formula in Generalized Belief Propagation for Probabilistic Inference
Linear response formulas for the generalized belief propagation in approximate inference are derived by using generalized belief propagation. The linear response formulas can give us the marginal probability between every pair of nodes and we obtain good accuracy in some examples of practical probabilistic inferences
3247078
Individual Level Analysis Using Decision Making Features in Multiagent Based Simulation
We introduce a set of evaluation tools in the framework of individual level analysis for multiagent based simulations. These tools are intended to overcome the weak points of multiagent systems: that it is difficult to avoid mistakes in description and arbitrary modeling; and to find reliable explanations of causal relationships between the model and its result. We analyze some artificial market models using an evaluation process that consists of the evaluation of initial learning maturity, discrimination between models, and the visualization of attention tendency in a group. We conclude that these analytical methods are useful for the evaluation of multiagent based simulations in terms of validation and finding causal relations.