OpenRaiser/Intern-Atlas huggingface dataset:
Rule-Based Semantic Sensing
Venue: arXiv cs.AI 2011
Year: 2011

Rule-Based Systems have been in use for decades to solve a variety of problems but not in the sensor informatics domain. Rules aid the aggregation of low-level sensor readings to form a more complete picture of the real world and help to address 10 identified challenges for sensor network middleware. This paper presents the reader with an overview of a system architecture and a pilot application to demonstrate the usefulness of a system integrating rules with sensor middleware.
Advancing Multi-Context Systems by Inconsistency Management
Venue: arXiv cs.AI 2011
Year: 2011

Multi-Context Systems are an expressive formalism to model (possibly) non-monotonic information exchange between heterogeneous knowledge bases. Such information exchange, however, often comes with unforseen side-effects leading to violation of constraints, making the system inconsistent, and thus unusable. Although there are many approaches to assess and repair a single inconsistent knowledge base, the heterogeneous nature of Multi-Context Systems poses problems which have not yet been addressed in a satisfying way: How to identify and explain a inconsistency that spreads over multiple knowledge bases with different logical formalisms (e.g., logic programs and ontologies)? What are the causes of inconsistency if inference/information exchange is non-monotonic (e.g., absent information as cause)? How to deal with inconsistency if access to knowledge bases is restricted (e.g., companies exchange information, but do not allow arbitrary modifications to their knowledge bases)? Many traditional approaches solely aim for a consistent system, but automatic removal of inconsistency is not always desireable. Therefore a human operator has to be supported in finding the erroneous parts contributing to the inconsistency. In my thesis those issues will be adressed mainly from a foundational perspective, while our research project also provides algorithms and prototype implementations.
Semantic-ontological combination of Business Rules and Business Processes in IT Service Management
Venue: arXiv cs.AI 2011
Year: 2011

IT Service Management deals with managing a broad range of items related to complex system environments. As there is both, a close connection to business interests and IT infrastructure, the application of semantic expressions which are seamlessly integrated within applications for managing ITSM environments, can help to improve transparency and profitability. This paper focuses on the challenges regarding the integration of semantics and ontologies within ITSM environments. It will describe the paradigm of relationships and inheritance within complex service trees and will present an approach of ontologically expressing them. Furthermore, the application of SBVR-based rules as executable SQL triggers will be discussed. Finally, the broad range of topics for further research, derived from the findings, will be presented.
Speed Scaling on Parallel Processors with Migration
Venue: arXiv cs.DS 2011
Year: 2011

We study the problem of scheduling a set of jobs with release dates, deadlines and processing requirements (or works), on parallel speed-scaled processors so as to minimize the total energy consumption. We consider that both preemption and migration of jobs are allowed. An exact polynomial-time algorithm has been proposed for this problem, which is based on the Ellipsoid algorithm. Here, we formulate the problem as a convex program and we propose a simpler polynomial-time combinatorial algorithm which is based on a reduction to the maximum flow problem. Our algorithm runs in $O(nf(n)logP)$ time, where $n$ is the number of jobs, $P$ is the range of all possible values of processors' speeds divided by the desired accuracy and $f(n)$ is the complexity of computing a maximum flow in a layered graph with O(n) vertices. Independently, Albers et al. \cite{AAG11} proposed an $O(n^2f(n))$-time algorithm exploiting the same relation with the maximum flow problem. We extend our algorithm to the multiprocessor speed scaling problem with migration where the objective is the minimization of the makespan under a budget of energy.
Strong Solutions of the Fuzzy Linear Systems
Venue: arXiv cs.NA 2011
Year: 2011

We consider a fuzzy linear system with crisp coefficient matrix and with an arbitrary fuzzy number in parametric form on the right-hand side. It is known that the well-known existence and uniqueness theorem of a strong fuzzy solution is equivalent to the following: The coefficient matrix is the product of a permutation matrix and a diagonal matrix. This means that this theorem can be applicable only for a special form of linear systems, namely, only when the system consists of equations, each of which has exactly one variable. We prove an existence and uniqueness theorem, which can be use on more general systems. The necessary and sufficient conditions of the theorem are dependent on both the coefficient matrix and the right-hand side. This theorem is a generalization of the well-known existence and uniqueness theorem for the strong solution.
Lower bounds in differential privacy
Venue: arXiv cs.CR 2011
Year: 2011

This is a paper about private data analysis, in which a trusted curator holding a confidential database responds to real vector-valued queries. A common approach to ensuring privacy for the database elements is to add appropriately generated random noise to the answers, releasing only these {\em noisy} responses. In this paper, we investigate various lower bounds on the noise required to maintain different kind of privacy guarantees.
Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure
Venue: arXiv cs.GT 2011
Year: 2011

We consider structural and algorithmic questions related to the Nash dynamics of weighted congestion games. In weighted congestion games with linear latency functions, the existence of (pure Nash) equilibria is guaranteed by potential function arguments. Unfortunately, this proof of existence is inefficient and computing equilibria is such games is a {\sf PLS}-hard problem. The situation gets worse when superlinear latency functions come into play; in this case, the Nash dynamics of the game may contain cycles and equilibria may not even exist. Given these obstacles, we consider approximate equilibria as alternative solution concepts. Do such equilibria exist? And if so, can we compute them efficiently? We provide positive answers to both questions for weighted congestion games with polynomial latency functions by exploiting an "approximation" of such games by a new class of potential games that we call $Ψ$-games. This allows us to show that these games have $d!$-approximate equilibria, where $d$ is the maximum degree of the latency functions. Our main technical contribution is an efficient algorithm for computing O(1)-approximate equilibria when $d$ is a constant. For games with linear latency functions, the approximation guarantee is $\frac{3+\sqrt{5}}{2}+O(γ)$ for arbitrarily small $γ>0$; for latency functions with maximum degree $d\geq 2$, it is $d^{2d+o(d)}$. The running time is polynomial in the number of bits in the representation of the game and $1/γ$. As a byproduct of our techniques, we also show the following structural statement for weighted congestion games with polynomial latency functions of maximum degree $d\geq 2$: polynomially-long sequences of best-response moves from any initial state to a $d^{O(d^2)}$-approximate equilibrium exist and can be efficiently identified in such games as long as $d$ is constant.
Computing the Distance between Piecewise-Linear Bivariate Functions
Venue: arXiv cs.CG 2011
Year: 2011

We consider the problem of computing the distance between two piecewise-linear bivariate functions $f$ and $g$ defined over a common domain $M$. We focus on the distance induced by the $L_2$-norm, that is $\|f-g\|_2=\sqrt{\iint_M (f-g)^2}$. If $f$ is defined by linear interpolation over a triangulation of $M$ with $n$ triangles, while $g$ is defined over another such triangulation, the obvious naïve algorithm requires $Θ(n^2)$ arithmetic operations to compute this distance. We show that it is possible to compute it in $Ø(n\log^4 n)$ arithmetic operations, by reducing the problem to multi-point evaluation of a certain type of polynomials. We also present an application to terrain matching.
Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
Venue: arXiv cs.DM 2011
Year: 2011

In a seminal paper (Weitz, 2006), Weitz gave a deterministic fully polynomial approximation scheme for count- ing exponentially weighted independent sets (equivalently, approximating the partition function of the hard-core model from statistical physics) on graphs of degree at most d, up to the critical activity for the uniqueness of the Gibbs measure on the infinite d-regular tree. More recently Sly (Sly, 2010) showed that this is optimal in the sense that if there is an FPRAS for the hard-core partition function on graphs of maximum degree d for activities larger than the critical activity on the infinite d-regular tree then NP = RP. In this paper, we extend Weitz's approach to derive a deterministic fully polynomial approx- imation scheme for the partition function of the anti-ferromagnetic Ising model with arbitrary field on graphs of maximum degree d, up to the corresponding critical point on the d-regular tree. The main ingredient of our result is a proof that for two-state anti-ferromagnetic spin systems on the d-regular tree, weak spatial mixing implies strong spatial mixing. This in turn uses a message-decay argument which extends a similar approach proposed recently for the hard-core model by Restrepo et al (Restrepo et al, 2011) to the case of the anti-ferromagnetic Ising model with arbitrary field. By a standard correspondence, these results translate to arbitrary two-state anti-ferromagnetic spin systems with soft constraints.
Private Data Release via Learning Thresholds
Venue: arXiv cs.CC 2011
Year: 2011

This work considers computationally efficient privacy-preserving data release. We study the task of analyzing a database containing sensitive information about individual participants. Given a set of statistical queries on the data, we want to release approximate answers to the queries while also guaranteeing differential privacy---protecting each participant's sensitive data. Our focus is on computationally efficient data release algorithms; we seek algorithms whose running time is polynomial, or at least sub-exponential, in the data dimensionality. Our primary contribution is a computationally efficient reduction from differentially private data release for a class of counting queries, to learning thresholded sums of predicates from a related class. We instantiate this general reduction with a variety of algorithms for learning thresholds. These instantiations yield several new results for differentially private data release. As two examples, taking {0,1}^d to be the data domain (of dimension d), we obtain differentially private algorithms for: (*) Releasing all k-way conjunctions. For any given k, the resulting data release algorithm has bounded error as long as the database is of size at least d^{O(\sqrt{k\log(k\log d)})}. The running time is polynomial in the database size. (*) Releasing a (1-γ)-fraction of all parity queries. For any γ\geq \poly(1/d), the algorithm has bounded error as long as the database is of size at least \poly(d). The running time is polynomial in the database size. Several other instantiations yield further results for privacy-preserving data release. Of the two results highlighted above, the first learning algorithm uses techniques for representing thresholded sums of predicates as low-degree polynomial threshold functions. The second learning algorithm is based on Jackson's Harmonic Sieve algorithm [Jackson 1997].
Routing in Undirected Graphs with Constant Congestion
Venue: arXiv cs.DS 2011
Year: 2011

Given an undirected graph G=(V,E), a collection (s_1,t_1),...,(s_k,t_k) of k source-sink pairs, and an integer c, the goal in the Edge Disjoint Paths with Congestion problem is to connect maximum possible number of the source-sink pairs by paths, so that the maximum load on any edge (called edge congestion) does not exceed c. We show an efficient randomized algorithm to route $Ω(OPT/\poly\log k)$ source-sink pairs with congestion at most 14, where OPT is the maximum number of pairs that can be simultaneously routed on edge-disjoint paths. The best previous algorithm that routed $Ω(OPT/\poly\log n)$ pairs required congestion $\poly(\log \log n)$, and for the setting where the maximum allowed congestion is bounded by a constant c, the best previous algorithms could only guarantee the routing of $OPT/n^{O(1/c)}$ pairs.
Topographic Feature Extraction for Bengali and Hindi Character Images
Venue: arXiv cs.CV 2011
Year: 2011

Feature selection and extraction plays an important role in different classification based problems such as face recognition, signature verification, optical character recognition (OCR) etc. The performance of OCR highly depends on the proper selection and extraction of feature set. In this paper, we present novel features based on the topography of a character as visible from different viewing directions on a 2D plane. By topography of a character we mean the structural features of the strokes and their spatial relations. In this work we develop topographic features of strokes visible with respect to views from different directions (e.g. North, South, East, and West). We consider three types of topographic features: closed region, convexity of strokes, and straight line strokes. These features are represented as a shape-based graph which acts as an invariant feature set for discriminating very similar type characters efficiently. We have tested the proposed method on printed and handwritten Bengali and Hindi character images. Initial results demonstrate the efficacy of our approach.
Restructuring Compressed Texts without Explicit Decompression
Venue: arXiv cs.DS 2011
Year: 2011

We consider the problem of {\em restructuring} compressed texts without explicit decompression. We present algorithms which allow conversions from compressed representations of a string $T$ produced by any grammar-based compression algorithm, to representations produced by several specific compression algorithms including LZ77, LZ78, run length encoding, and some grammar based compression algorithms. These are the first algorithms that achieve running times polynomial in the size of the compressed input and output representations of $T$. Since most of the representations we consider can achieve exponential compression, our algorithms are theoretically faster in the worst case, than any algorithm which first decompresses the string for the conversion.
A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis
Venue: arXiv cs.LO 2011
Year: 2011

Although the notion of a concept as a collection of objects sharing certain properties, and the notion of a conceptual hierarchy are fundamental to both Formal Concept Analysis and Description Logics, the ways concepts are described and obtained differ significantly between these two research areas. Despite these differences, there have been several attempts to bridge the gap between these two formalisms, and attempts to apply methods from one field in the other. The present work aims to give an overview on the research done in combining Description Logics and Formal Concept Analysis.
An Ontology-driven Framework for Supporting Complex Decision Process
Venue: arXiv cs.AI 2011
Year: 2011

The study proposes a framework of ONTOlogy-based Group Decision Support System (ONTOGDSS) for decision process which exhibits the complex structure of decision-problem and decision-group. It is capable of reducing the complexity of problem structure and group relations. The system allows decision makers to participate in group decision-making through the web environment, via the ontology relation. It facilitates the management of decision process as a whole, from criteria generation, alternative evaluation, and opinion interaction to decision aggregation. The embedded ontology structure in ONTOGDSS provides the important formal description features to facilitate decision analysis and verification. It examines the software architecture, the selection methods, the decision path, etc. Finally, the ontology application of this system is illustrated with specific real case to demonstrate its potentials towards decision-making development.
Performance Guarantee under Longest-Queue-First Schedule in Wireless Networks
Venue: arXiv cs.IT 2011
Year: 2011

Efficient link scheduling in a wireless network is challenging. Typical optimal algorithms require solving an NP-hard sub-problem. To meet the challenge, one stream of research focuses on finding simpler sub-optimal algorithms that have low complexity but high efficiency in practice. In this paper, we study the performance guarantee of one such scheduling algorithm, the Longest-Queue-First (LQF) algorithm. It is known that the LQF algorithm achieves the full capacity region, $Λ$, when the interference graph satisfies the so-called local pooling condition. For a general graph $G$, LQF achieves (i.e., stabilizes) a part of the capacity region, $σ^*(G) Λ$, where $σ^*(G)$ is the overall local pooling factor of the interference graph $G$ and $σ^*(G) \leq 1$. It has been shown later that LQF achieves a larger rate region, $Σ^*(G) Λ$, where $Σ^ (G)$ is a diagonal matrix. The contribution of this paper is to describe three new achievable rate regions, which are larger than the previously-known regions. In particular, the new regions include all the extreme points of the capacity region and are not convex in general. We also discover a counter-intuitive phenomenon in which increasing the arrival rate may sometime help to stabilize the network. This phenomenon can be well explained using the theory developed in the paper.
Large Formal Wikis: Issues and Solutions
Venue: arXiv cs.DL 2011
Year: 2011

We present several steps towards large formal mathematical wikis. The Coq proof assistant together with the CoRN repository are added to the pool of systems handled by the general wiki system described in \cite{DBLP:conf/aisc/UrbanARG10}. A smart re-verification scheme for the large formal libraries in the wiki is suggested for Mizar/MML and Coq/CoRN, based on recently developed precise tracking of mathematical dependencies. We propose to use features of state-of-the-art filesystems to allow real-time cloning and sandboxing of the entire libraries, allowing also to extend the wiki to a true multi-user collaborative area. A number of related issues are discussed.
A Temporal Neuro-Fuzzy Monitoring System to Manufacturing Systems
Venue: arXiv cs.AI 2011
Year: 2011

Fault diagnosis and failure prognosis are essential techniques in improving the safety of many manufacturing systems. Therefore, on-line fault detection and isolation is one of the most important tasks in safety-critical and intelligent control systems. Computational intelligence techniques are being investigated as extension of the traditional fault diagnosis methods. This paper discusses the Temporal Neuro-Fuzzy Systems (TNFS) fault diagnosis within an application study of a manufacturing system. The key issues of finding a suitable structure for detecting and isolating ten realistic actuator faults are described. Within this framework, data-processing interactive software of simulation baptized NEFDIAG (NEuro Fuzzy DIAGnosis) version 1.0 is developed. This software devoted primarily to creation, training and test of a classification Neuro-Fuzzy system of industrial process failures. NEFDIAG can be represented like a special type of fuzzy perceptron, with three layers used to classify patterns and failures. The system selected is the workshop of SCIMAT clinker, cement factory in Algeria.
Compressive Mechanism: Utilizing Sparse Representation in Differential Privacy
Venue: arXiv cs.DS 2011
Year: 2011

Differential privacy provides the first theoretical foundation with provable privacy guarantee against adversaries with arbitrary prior knowledge. The main idea to achieve differential privacy is to inject random noise into statistical query results. Besides correctness, the most important goal in the design of a differentially private mechanism is to reduce the effect of random noise, ensuring that the noisy results can still be useful. This paper proposes the \emph{compressive mechanism}, a novel solution on the basis of state-of-the-art compression technique, called \emph{compressive sensing}. Compressive sensing is a decent theoretical tool for compact synopsis construction, using random projections. In this paper, we show that the amount of noise is significantly reduced from $O(\sqrt{n})$ to $O(\log(n))$, when the noise insertion procedure is carried on the synopsis samples instead of the original database. As an extension, we also apply the proposed compressive mechanism to solve the problem of continual release of statistical results. Extensive experiments using real datasets justify our accuracy claims.
Object Oriented Information Computing over WWW
Venue: arXiv cs.IR 2011
Year: 2011

Traditional search engines on World Wide Web (WWW) focus essentially on relevance ranking at the page level. But this lead to missing innumerable structured information about real-world objects embedded in static Web pages and online Web databases. Page-level information retrieval (IR) can unfortunately lead to highly inaccurate relevance ranking in answering object-oriented queries. On the other hand, Object Oriented Information Computing (OOIC) is promising and greatly reduces the complexity of the system while improving reusability and manageability. The most distinguishing requirement of today's complex heterogeneous systems is the need of the computing system to instantly adapt to vigorously changing conditions. OOIC allows reflecting the dynamic characteristics of the applications by instantiating objects dynamically. In this paper, major challenges of OOIC as well as its rudiments are recapped. The review includes the insight to PopRank Model and comparison analysis of conventional page rank based IR with OOIC
On Consensus under Polynomial Protocols
Venue: arXiv cs.SC 2011
Year: 2011

In this paper we explore the possibility of using computational algebraic methods to analyze a class of consensus protocols. We state some necessary conditions for convergence under consensus protocols that are polynomials.