OpenRaiser/Intern-Atlas huggingface dataset:
Characterizing predictable classes of processes
Venue: arXiv cs.AI 2009
Year: 2009

The problem is sequence prediction in the following setting. A sequence $x_1,...,x_n,...$ of discrete-valued observations is generated according to some unknown probabilistic law (measure) $μ$. After observing each outcome, it is required to give the conditional probabilities of the next observation. The measure $μ$ belongs to an arbitrary class $\C$ of stochastic processes. We are interested in predictors $ρ$ whose conditional probabilities converge to the "true" $μ$-conditional probabilities if any $μ\in\C$ is chosen to generate the data. We show that if such a predictor exists, then a predictor can also be obtained as a convex combination of a countably many elements of $\C$. In other words, it can be obtained as a Bayesian predictor whose prior is concentrated on a countable set. This result is established for two very different measures of performance of prediction, one of which is very strong, namely, total variation, and the other is very weak, namely, prediction in expected average Kullback-Leibler divergence.
Automating Quantified Multimodal Logics in Simple Type Theory -- A Case Study
Venue: arXiv cs.AI 2009
Year: 2009

In a case study we investigate whether off the shelf higher-order theorem provers and model generators can be employed to automate reasoning in and about quantified multimodal logics. In our experiments we exploit the new TPTP infrastructure for classical higher-order logic.
Analysis of Sorting Algorithms by Kolmogorov Complexity (A Survey)
Venue: arXiv cs.DS 2009
Year: 2009

Recently, many results on the computational complexity of sorting algorithms were obtained using Kolmogorov complexity (the incompressibility method). Especially, the usually hard average-case analysis is ammenable to this method. Here we survey such results about Bubblesort, Heapsort, Shellsort, Dobosiewicz-sort, Shakersort, and sorting with stacks and queues in sequential or parallel mode. Especially in the case of Shellsort the uses of Kolmogorov complexity surprisingly easily resolved problems that had stayed open for a long time despite strenuous attacks.
Designing a Framework to Develop WEB Graphical Interfaces for ORACLE Databases - Web Dialog
Venue: arXiv cs.OH 2009
Year: 2009

The present article aims to describe a project consisting in designing a framework of applications used to create graphical interfaces with an Oracle distributed database. The development of the project supposed the use of the latest technologies: database Oracle server, Tomcat web server, JDBC (Java library used for accessing a database), JSP and Tag Library (for the development of graphical interfaces).
Straight-line instruction sequence completeness for total calculation on cancellation meadows
Venue: arXiv cs.LO 2009
Year: 2009

A combination of program algebra with the theory of meadows is designed leading to a theory of computation in algebraic structures which use in addition to a zero test and copying instructions the instruction set $\{x \Leftarrow 0, x \Leftarrow 1, x\Leftarrow -x, x\Leftarrow x^{-1}, x\Leftarrow x+y, x\Leftarrow x\cdot y\}$. It is proven that total functions on cancellation meadows can be computed by straight-line programs using at most 5 auxiliary variables. A similar result is obtained for signed meadows.
CoPhIR: a Test Collection for Content-Based Image Retrieval
Venue: arXiv cs.MM 2009
Year: 2009

The scalability, as well as the effectiveness, of the different Content-based Image Retrieval (CBIR) approaches proposed in literature, is today an important research issue. Given the wealth of images on the Web, CBIR systems must in fact leap towards Web-scale datasets. In this paper, we report on our experience in building a test collection of 100 million images, with the corresponding descriptive features, to be used in experimenting new scalable techniques for similarity searching, and comparing their results. In the context of the SAPIR (Search on Audio-visual content using Peer-to-peer Information Retrieval) European project, we had to experiment our distributed similarity searching technology on a realistic data set. Therefore, since no large-scale collection was available for research purposes, we had to tackle the non-trivial process of image crawling and descriptive feature extraction (we used five MPEG-7 features) using the European EGEE computer GRID. The result of this effort is CoPhIR, the first CBIR test collection of such scale. CoPhIR is now open to the research community for experiments and comparisons, and access to the collection was already granted to more than 50 research groups worldwide.
Derivation of UML Based Performance Models for Design Assessment in a Reuse Based Software Development Approach
Venue: arXiv cs.SE 2009
Year: 2009

Reuse-based software development provides an opportunity for better quality and increased productivity in the software products. One of the most critical aspects of the quality of a software system is its performance. The systematic application of software performance engineering techniques throughout the development process can help to identify design alternatives that preserve desirable qualities such as extensibility and reusability while meeting performance objectives. In the present scenario, most of the performance failures are due to a lack of consideration of performance issues early in the development process, especially in the design phase. These performance failures results in damaged customer relations, lost productivity for users, cost overruns due to tuning or redesign, and missed market windows. In this paper, we propose UML based Performance Models for design assessment in a reuse based software development scenario.
On Some Manipulations with Fuzzy Processes
Venue: arXiv cs.LO 2009
Year: 2009

The paper starts from the observation on the complexity of the manipulation of fuzzy processes that increases very rapidly with the extents of the processes representation. Therefore, a productive approach is to divide the problem into smaller parts, treated separately and then the results combined. Some algebraic results obtained by the authors are presented.
Reverse method for labeling the information from semi-structured web pages
Venue: arXiv cs.IR 2009
Year: 2009

We propose a new technique to infer the structure and extract the tokens of data from the semi-structured web sources which are generated using a consistent template or layout with some implicit regularities. The attributes are extracted and labeled reversely from the region of interest of targeted contents. This is in contrast with the existing techniques which always generate the trees from the root. We argue and show that our technique is simpler, more accurate and effective especially to detect the changes of the templates of targeted web pages.
Mitigating the ICA Attack against Rotation Based Transformation for Privacy Preserving Clustering
Venue: arXiv cs.CR 2009
Year: 2009

The rotation based transformation (RBT) for privacy preserving data mining (PPDM) is vulnerable to the independent component analysis (ICA) attack. This paper introduces a modified multiple rotation based transformation (MRBT) technique for special mining applications mitigating the ICA attack while maintaining the advantages of the RBT.
MORA: an Energy-Aware Slack Reclamation Scheme for Scheduling Sporadic Real-Time Tasks upon Multiprocessor Platforms
Venue: arXiv cs.OS 2009
Year: 2009

In this paper, we address the global and preemptive energy-aware scheduling problem of sporadic constrained-deadline tasks on DVFS-identical multiprocessor platforms. We propose an online slack reclamation scheme which profits from the discrepancy between the worst- and actual-case execution time of the tasks by slowing down the speed of the processors in order to save energy. Our algorithm called MORA takes into account the application-specific consumption profile of the tasks. We demonstrate that MORA does not jeopardize the system schedulability and we show by performing simulations that it can save up to 32% of energy (in average) compared to execution without using any energy-aware algorithm.
Curse of Dimensionality in Pivot-based Indexes
Venue: arXiv cs.DS 2009
Year: 2009

We offer a theoretical validation of the curse of dimensionality in the pivot-based indexing of datasets for similarity search, by proving, in the framework of statistical learning, that in high dimensions no pivot-based indexing scheme can essentially outperform the linear scan. A study of the asymptotic performance of pivot-based indexing schemes is performed on a sequence of datasets modeled as samples $X_d$ picked in i.i.d. fashion from metric spaces $Ω_d$. We allow the size of the dataset $n=n_d$ to be such that $d$, the ``dimension'', is superlogarithmic but subpolynomial in $n$. The number of pivots is allowed to grow as $o(n/d)$. We pick the least restrictive cost model of similarity search where we count each distance calculation as a single computation and disregard the rest. We demonstrate that if the intrinsic dimension of the spaces $Ω_d$ in the sense of concentration of measure phenomenon is $O(d)$, then the performance of similarity search pivot-based indexes is asymptotically linear in $n$.
A stabilized finite element formulation of non-smooth contact
Venue: arXiv cs.NA 2009
Year: 2009

The computational modeling of many engineering problems using the Finite Element method involves the modeling of two or more bodies that meet through an interface. The interface can be physical, as in multi-physics and contact problems, or purely numerical, as in the coupling of non-conforming meshes. The most critical part of the modeling process is to ensure geometric compatibility and a complete transfer of surface tractions between the different components at the connecting interfaces. Popular contact modeling techniques rely on geometric projections to detect and resolve overlapping or mass interpenetration between two or more contacting bodies. Such approaches have been shown to have two major drawbacks: they are not suitable for contact at highly nonlinear surfaces and sharp corners where smooth normal projections are not feasible, and they fail to guarantee a complete and accurate transfer of pressure across the interface. This dissertation presents a novel formulation for the modeling of contact problems that possesses the ability to resolve complicated contact scenarios effectively, while being simpler to implement and more widely applicable than currently available methods. We show that the formulation boils down to a node-to-surface gap function that works effectively for non-smooth contact. The numerical implementation using the midpoint rule shows the need to guarantee the conservation of the total energy during impact, for which a Lagrange multiplier method is used. We propose a local enrichment of the interface and a simple stabilization procedure based on the discontinuous Galerkin method to guarantee an accurate transfer of the pressure field. The result is a robust interface formulation for contact problems and the coupling of non-conforming meshes.
An Axiomatic Theory of Fairness in Network Resource Allocation
Venue: arXiv cs.NI 2009
Year: 2009

We present a set of five axioms for fairness measures in resource allocation. A family of fairness measures satisfying the axioms is constructed. Well-known notions such as alpha-fairness, Jain's index, and entropy are shown to be special cases. Properties of fairness measures satisfying the axioms are proven, including Schur-concavity. Among the engineering implications is a generalized Jain's index that tunes the resolution of the fairness measure, a new understanding of alpha-fair utility functions, and an interpretation of "larger alpha is more fair". We also construct an alternative set of four axioms to capture efficiency objectives and feasibility constraints.
Optimal Byzantine Resilient Convergence in Asynchronous Robot Networks
Venue: arXiv cs.DC 2009
Year: 2009

We propose the first deterministic algorithm that tolerates up to $f$ byzantine faults in $3f+1$-sized networks and performs in the asynchronous CORDA model. Our solution matches the previously established lower bound for the semi-synchronous ATOM model on the number of tolerated Byzantine robots. Our algorithm works under bounded scheduling assumptions for oblivious robots moving in a uni-dimensional space.
Quality assessment of the MPEG-4 scalable video CODEC
Venue: arXiv cs.MM 2009
Year: 2009

In this paper, the performance of the emerging MPEG-4 SVC CODEC is evaluated. In the first part, a brief introduction on the subject of quality assessment and the development of the MPEG-4 SVC CODEC is given. After that, the used test methodologies are described in detail, followed by an explanation of the actual test scenarios. The main part of this work concentrates on the performance analysis of the MPEG-4 SVC CODEC - both objective and subjective.
2D cellular automata: dynamics and undecidability
Venue: arXiv cs.FL 2009
Year: 2009

In this paper we introduce the notion of quasi-expansivity for 2D CA and we show that it shares many properties with expansivity (that holds only for 1D CA). Similarly, we introduce the notions of quasi-sensitivity and prove that the classical dichotomy theorem holds in this new setting. Moreover, we show a tight relation between closingness and openness for 2D CA. Finally, the undecidability of closingness property for 2D CA is proved.
A Partial Order on Bipartite Graphs with n Vertices
Venue: arXiv cs.DM 2009
Year: 2009

The paper examines a partial order on bipartite graphs (X1, X2, E) with n vertices, X1UX2={1,2,...,n}. This partial order is a natural partial order of subobjects of an object in a triangular category with bipartite graphs as morphisms.
Web Publishing of the Files Obtained by Flash
Venue: arXiv cs.MM 2009
Year: 2009

The aim of this article is to familiarize the user with the Web publishing of the files obtained by Flash. The article contains an overview of Macromedia Flash 5, as well as the running of a Playing Flash movie, information on Flash and Generator, the publishing of Flash movies, a HTLM publishing for Flash Player files and publishing by Generator templates.
Mining Compressed Repetitive Gapped Sequential Patterns Efficiently
Venue: arXiv cs.DB 2009
Year: 2009

Mining frequent sequential patterns from sequence databases has been a central research topic in data mining and various efficient mining sequential patterns algorithms have been proposed and studied. Recently, in many problem domains (e.g, program execution traces), a novel sequential pattern mining research, called mining repetitive gapped sequential patterns, has attracted the attention of many researchers, considering not only the repetition of sequential pattern in different sequences but also the repetition within a sequence is more meaningful than the general sequential pattern mining which only captures occurrences in different sequences. However, the number of repetitive gapped sequential patterns generated by even these closed mining algorithms may be too large to understand for users, especially when support threshold is low. In this paper, we propose and study the problem of compressing repetitive gapped sequential patterns. Inspired by the ideas of summarizing frequent itemsets, RPglobal, we develop an algorithm, CRGSgrow (Compressing Repetitive Gapped Sequential pattern grow), including an efficient pruning strategy, SyncScan, and an efficient representative pattern checking scheme, -dominate sequential pattern checking. The CRGSgrow is a two-step approach: in the first step, we obtain all closed repetitive sequential patterns as the candidate set of representative repetitive sequential patterns, and at the same time get the most of representative repetitive sequential patterns; in the second step, we only spend a little time in finding the remaining the representative patterns from the candidate set. An empirical study with both real and synthetic data sets clearly shows that the CRGSgrow has good performance.
Eliminating Human Insight: An Algorithmic Proof of Stembridge's TSPP Theorem
Venue: arXiv cs.SC 2009
Year: 2009

We present a new proof of Stembridge's theorem about the enumeration of totally symmetric plane partitions using the methodology suggested in the recent Koutschan-Kauers-Zeilberger semi-rigorous proof of the Andrews-Robbins q-TSPP conjecture. Our proof makes heavy use of computer algebra and is completely automatic. We describe new methods that make the computations feasible in the first place. The tantalizing aspect of this work is that the same methods can be applied to prove the q-TSPP conjecture (that is a q-analogue of Stembridge's theorem and open for more than 25 years); the only hurdle here is still the computational complexity.
Enabling and Optimizing Pilot Jobs using Xen based Virtual Machines for the HPC Grid Applications
Venue: arXiv cs.DC 2009
Year: 2009

The primary motivation for uptake of virtualization have been resource isolation, capacity management and resource customization: isolation and capacity management allow providers to isolate users from the site and control their resources usage while customization allows end-users to easily project the required environment onto a variety of sites. Various approaches have been taken to integrate virtualization with Grid technologies. In this paper, we propose an approach that combines virtualization on the existing software infrastructure such as Pilot Jobs with minimum change on the part of resource providers.
Similarity Analysis in Automatic Performance Debugging of SPMD Parallel Programs
Venue: arXiv cs.DC 2009
Year: 2009

Different from sequential programs, parallel programs possess their own characteristics which are difficult to analyze in the multi-process or multi-thread environment. This paper presents an innovative method to automatically analyze the SPMD programs. Firstly, with the help of clustering method focusing on similarity analysis, an algorithm is designed to locate performance problems in parallel programs automatically. Secondly a Rough Set method is used to uncover the performance problem and provide the insight into the micro-level causes. Lastly, we have analyzed a production parallel application to verify the effectiveness of our method and system.
Améliorer les performances de l'industrie logicielle par une meilleure compréhension des besoins
Venue: arXiv cs.SE 2009
Year: 2009

Actual organization are structured and act with the help of their information systems. In spite of considerable progresses made by computer technology, we note that actors are very often critical on their information systems. Difficulties to product specifications enough detailed for functional profile and interpretable by information system expert is one of reason of this gap between hopes and reality. Our proposition wants to get over this obstacle by organizing user requirements in a common language of operational profile and technical expert.-- Les organisations actuelles se structurent et agissent en s'appuyant sur leurs systèmes d'information. Malgré les progrès considérables réalisés par la technologie informatique, on constate que les acteurs restent très souvent critiques par rapport à leur systèmes d'information. Une des causes de cet écart entre les espoirs et la réalité trouve sa source dans la difficulté à produire un cahier des charges suffisamment détaillé pour les opérationnels et interprétable par les spécialistes des systèmes d'information. Notre proposition vise à surmonter cet obstacle en organisant l'expression des besoins dans un langage commun aux opérationnels et aux experts techniques. Pour cela, le langage proposé pour exprimer les besoins est basé sur la notion de but. L'ingénierie dirigée par les modèles est présente à toute les étapes, c'est-à-dire au moment de la capture et de l'interprétation.
Toward a Category Theory Design of Ontological Knowledge Bases
Venue: arXiv cs.AI 2009
Year: 2009

I discuss (ontologies_and_ontological_knowledge_bases / formal_methods_and_theories) duality and its category theory extensions as a step toward a solution to Knowledge-Based Systems Theory. In particular I focus on the example of the design of elements of ontologies and ontological knowledge bases of next three electronic courses: Foundations of Research Activities, Virtual Modeling of Complex Systems and Introduction to String Theory.
Feature Reinforcement Learning: Part I: Unstructured MDPs
Venue: arXiv cs.LG 2009
Year: 2009

General-purpose, intelligent, learning agents cycle through sequences of observations, actions, and rewards that are complex, uncertain, unknown, and non-Markovian. On the other hand, reinforcement learning is well-developed for small finite state Markov decision processes (MDPs). Up to now, extracting the right state representations out of bare observations, that is, reducing the general agent setup to the MDP framework, is an art that involves significant effort by designers. The primary goal of this work is to automate the reduction process and thereby significantly expand the scope of many existing reinforcement learning algorithms and the agents that employ them. Before we can think of mechanizing this search for suitable MDPs, we need a formal objective criterion. The main contribution of this article is to develop such a criterion. I also integrate the various parts into one learning algorithm. Extensions to more realistic dynamic Bayesian networks are developed in Part II. The role of POMDPs is also considered there.
Creating Textual Language Dialects Using Aspect-like Techniques
Venue: arXiv cs.PL 2009
Year: 2009

Here we present a work aimed on efficiently creating textual language dialects and supporting tools for them (e.g. compiler front-ends, IDE support, pretty-printers, etc.). A dialect is a language which may be described with a (relatively small) set of changes to some other language (a parent language). For example we can consider SQL dialects used in DB-management systems. We propose to use aspects for grammars to define different features of the anguage and to transform grammars. A dialect is created by defining a syntactical spect which modifies the parent language. This technique is not dependent on any particular language design, AST structure or parsing technology and provides a uniform way for creating dialects, which extend or restrict languages.
Managing Requirement Volatility in an Ontology-Driven Clinical LIMS Using Category Theory. International Journal of Telemedicine and Applications
Venue: arXiv cs.AI 2009
Year: 2009

Requirement volatility is an issue in software engineering in general, and in Web-based clinical applications in particular, which often originates from an incomplete knowledge of the domain of interest. With advances in the health science, many features and functionalities need to be added to, or removed from, existing software applications in the biomedical domain. At the same time, the increasing complexity of biomedical systems makes them more difficult to understand, and consequently it is more difficult to define their requirements, which contributes considerably to their volatility. In this paper, we present a novel agent-based approach for analyzing and managing volatile and dynamic requirements in an ontology-driven laboratory information management system (LIMS) designed for Web-based case reporting in medical mycology. The proposed framework is empowered with ontologies and formalized using category theory to provide a deep and common understanding of the functional and nonfunctional requirement hierarchies and their interrelations, and to trace the effects of a change on the conceptual framework.