OpenRaiser/Intern-Atlas huggingface dataset:
Analysis of the flooding search algorithm with OPNET
Venue: arXiv cs.NI 2012
Year: 2012

In this work, we consider the popular OPNET simulator as a tool for performance evaluation of algorithms operating in peer-to-peer (P2P) networks. We created simple framework and used it to analyse the flooding search algorithm which is a popular technique for searching files in an unstructured P2P network. We investigated the influence of the number of replicas and time to live (TTL) of search queries on the algorithm performance. Preparing the simulation we did not reported the problems which are commonly encountered in P2P dedicated simulators although the size of simulated network was limited.
Joint Sparsity with Different Measurement Matrices
Venue: arXiv cs.IT 2012
Year: 2012

We consider a generalization of the multiple measurement vector (MMV) problem, where the measurement matrices are allowed to differ across measurements. This problem arises naturally when multiple measurements are taken over time, e.g., and the measurement modality (matrix) is time-varying. We derive probabilistic recovery guarantees showing that---under certain (mild) conditions on the measurement matrices---l2/l1-norm minimization and a variant of orthogonal matching pursuit fail with a probability that decays exponentially in the number of measurements. This allows us to conclude that, perhaps surprisingly, recovery performance does not suffer from the individual measurements being taken through different measurement matrices. What is more, recovery performance typically benefits (significantly) from diversity in the measurement matrices; we specify conditions under which such improvements are obtained. These results continue to hold when the measurements are subject to (bounded) noise.
Towards Multi-Threaded Local Tabling Using a Common Table Space
Venue: arXiv cs.PL 2012
Year: 2012

Multi-threading is currently supported by several well-known Prolog systems providing a highly portable solution for applications that can benefit from concurrency. When multi-threading is combined with tabling, we can exploit the power of higher procedural control and declarative semantics. However, despite the availability of both threads and tabling in some Prolog systems, the implementation of these two features implies complex ties to each other and to the underlying engine. Until now, XSB was the only Prolog system combining multi-threading with tabling. In XSB, tables may be either private or shared between threads. While thread-private tables are easier to implement, shared tables have all the associated issues of locking, synchronization and potential deadlocks. In this paper, we propose an alternative view to XSB's approach. In our proposal, each thread views its tables as private but, at the engine level, we use a common table space where tables are shared among all threads. We present three designs for our common table space approach: No-Sharing (NS) (similar to XSB's private tables), Subgoal-Sharing (SS) and Full-Sharing (FS). The primary goal of this work was to reduce the memory usage for the table space but, our experimental results, using the YapTab tabling system with a local evaluation strategy, show that we can also achieve significant reductions on running time.
Distributed Formal Concept Analysis Algorithms Based on an Iterative MapReduce Framework
Venue: arXiv cs.DC 2012
Year: 2012

While many existing formal concept analysis algorithms are efficient, they are typically unsuitable for distributed implementation. Taking the MapReduce (MR) framework as our inspiration we introduce a distributed approach for performing formal concept mining. Our method has its novelty in that we use a light-weight MapReduce runtime called Twister which is better suited to iterative algorithms than recent distributed approaches. First, we describe the theoretical foundations underpinning our distributed formal concept analysis approach. Second, we provide a representative exemplar of how a classic centralized algorithm can be implemented in a distributed fashion using our methodology: we modify Ganter's classic algorithm by introducing a family of MR* algorithms, namely MRGanter and MRGanter+ where the prefix denotes the algorithm's lineage. To evaluate the factors that impact distributed algorithm performance, we compare our MR* algorithms with the state-of-the-art. Experiments conducted on real datasets demonstrate that MRGanter+ is efficient, scalable and an appealing algorithm for distributed problems.
Interface Simulation Distances
Venue: arXiv cs.SE 2012
Year: 2012

The classical (boolean) notion of refinement for behavioral interfaces of system components is the alternating refinement preorder. In this paper, we define a distance for interfaces, called interface simulation distance. It makes the alternating refinement preorder quantitative by, intuitively, tolerating errors (while counting them) in the alternating simulation game. We show that the interface simulation distance satisfies the triangle inequality, that the distance between two interfaces does not increase under parallel composition with a third interface, and that the distance between two interfaces can be bounded from above and below by distances between abstractions of the two interfaces. We illustrate the framework, and the properties of the distances under composition of interfaces, with two case studies.
Learn with SAT to Minimize Büchi Automata
Venue: arXiv cs.FL 2012
Year: 2012

We describe a minimization procedure for nondeterministic Büchi automata (NBA). For an automaton A another automaton A_min with the minimal number of states is learned with the help of a SAT-solver. This is done by successively computing automata A' that approximate A in the sense that they accept a given finite set of positive examples and reject a given finite set of negative examples. In the course of the procedure these example sets are successively increased. Thus, our method can be seen as an instance of a generic learning algorithm based on a "minimally adequate teacher" in the sense of Angluin. We use a SAT solver to find an NBA for given sets of positive and negative examples. We use complementation via construction of deterministic parity automata to check candidates computed in this manner for equivalence with A. Failure of equivalence yields new positive or negative examples. Our method proved successful on complete samplings of small automata and of quite some examples of bigger automata. We successfully ran the minimization on over ten thousand automata with mostly up to ten states, including the complements of all possible automata with two states and alphabet size three and discuss results and runtimes; single examples had over 100 states.
A decidable quantified fragment of set theory with ordered pairs and some undecidable extensions
Venue: arXiv cs.LO 2012
Year: 2012

In this paper we address the decision problem for a fragment of set theory with restricted quantification which extends the language studied in [4] with pair related quantifiers and constructs, in view of possible applications in the field of knowledge representation. We will also show that the decision problem for our language has a non-deterministic exponential time complexity. However, for the restricted case of formulae whose quantifier prefixes have length bounded by a constant, the decision problem becomes NP-complete. We also observe that in spite of such restriction, several useful set-theoretic constructs, mostly related to maps, are expressible. Finally, we present some undecidable extensions of our language, involving any of the operators domain, range, image, and map composition. [4] Michael Breban, Alfredo Ferro, Eugenio G. Omodeo and Jacob T. Schwartz (1981): Decision procedures for elementary sublanguages of set theory. II. Formulas involving restricted quantifiers, together with ordinal, integer, map, and domain notions. Communications on Pure and Applied Mathematics 34, pp. 177-195
Performance Analysis of Two-Step Bi-Directional Relaying with Multiple Antennas
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we study decode-and-forward multi-antenna relay systems that achieve bi-directional communication in two time slots. We investigate different downlink broadcast schemes which employ binary or analog network coding at the relay. We also analyze and compare their performances in terms of diversity order and symbol error probability. It is shown that if exact downlink channel state information is available at the relay, using analog network coding in the form of multi-antenna maximal-ratio transmit beamforming to precode the information vectors at the relay gives the best performance. Then, we propose a Max-Min antenna selection with binary network coding scheme that can approach this performance with only partial channel state information.
Degrees of Freedom Region of the MIMO X channel with an Arbitrary Number of Antennas
Venue: arXiv cs.IT 2012
Year: 2012

We characterize the total degrees of freedom (DoF) of the full-rank MIMO X channel with arbitrary number of antennas at each node. We elucidate that the existing outer bound is tight for any antenna configuration and provide transmit and receive filter designs that attain this outer bound. The proposed achievable scheme exploits channel extensions in terms of both, symbol and asymmetric complex signaling when the communication is carried out over a constant channel case, and is also applicable to time varying channels. The proposed scheme represents a general framework for the derivation of the total DoF of any two-by-two multiuser channels. Furthermore, the rank-deficient MIMO channels case is naturally addressed, and it is shown that the total DoF of the interference (IC) and MIMO X channels are in general superior to the full rank MIMO case
Measuring the Influence of Observations in HMMs through the Kullback-Leibler Distance
Venue: arXiv cs.IT 2012
Year: 2012

We measure the influence of individual observations on the sequence of the hidden states of the Hidden Markov Model (HMM) by means of the Kullback-Leibler distance (KLD). Namely, we consider the KLD between the conditional distribution of the hidden states' chain given the complete sequence of observations and the conditional distribution of the hidden chain given all the observations but the one under consideration. We introduce a linear complexity algorithm for computing the influence of all the observations. As an illustration, we investigate the application of our algorithm to the problem of detecting outliers in HMM data series.
Carrier Sense Multiple Access Tuning Parameters using Game Theory
Venue: arXiv cs.GT 2012
Year: 2012

Ad Hoc and Mesh networks are good samples of multi agent systems, where their nodes access the channel through carrier sense multiple access method, while a node channel access influence the access of neighbor nodes to the channel. Hence, game theory is a strong tool for studying this kind of networks. Carrier sense multiple access parameters such as minimum and maximum size of contention window and persistence factor can be modified based on game theoretic methods. In this study different games for tuning the parameters is investigated and different challenges are examined.
Auditory Steady-State Response Stimuli based BCI Application - The Optimization of the Stimuli Types and Lengths
Venue: arXiv cs.HC 2012
Year: 2012

We propose a method for an improvement of auditory BCI (aBCI) paradigm based on a combination of ASSR stimuli optimization by choosing the subjects' best responses to AM-, flutter-, AM/FM and click-envelope modulated sounds. As the ASSR response features we propose pairwise phase-locking-values calculated from the EEG and next classified using binary classifier to detect attended and ignored stimuli. We also report on a possibility to use the stimuli as short as half a second, which is a step forward in ASSR based aBCI. The presented results are helpful for optimization of the aBCI stimuli for each subject.
The Spatial Real and Virtual Sound Stimuli Optimization for the Auditory BCI
Venue: arXiv cs.HC 2012
Year: 2012

The paper presents results from a project aiming to create horizontally distributed surround sound sources and virtual sound images as auditory BCI (aBCI) stimuli. The purpose is to create evoked brain wave response patterns depending on attended or ignored sound directions. We propose to use a modified version of the vector based amplitude panning (VBAP) approach to achieve the goal. The so created spatial sound stimulus system for the novel oddball aBCI paradigm allows us to create a multi-command experimental environment with very encouraging results reported in this paper. We also present results showing that a modulation of the sound image depth changes also the subject responses. Finally, we also compare the proposed virtual sound approach with the traditional one based on real sound sources generated from the real loudspeaker directions. The so obtained results confirm the hypothesis of the possibility to modulate independently the brain responses to spatial types and depths of sound sources which allows for the development of the novel multi-command aBCI.
Petri Net Reachability Graphs: Decidability Status of First Order Properties
Venue: arXiv cs.LO 2012
Year: 2012

We investigate the decidability and complexity status of model-checking problems on unlabelled reachability graphs of Petri nets by considering first-order and modal languages without labels on transitions or atomic propositions on markings. We consider several parameters to separate decidable problems from undecidable ones. Not only are we able to provide precise borders and a systematic analysis, but we also demonstrate the robustness of our proof techniques.
Learning Onto-Relational Rules with Inductive Logic Programming
Venue: arXiv cs.AI 2012
Year: 2012

Rules complement and extend ontologies on the Semantic Web. We refer to these rules as onto-relational since they combine DL-based ontology languages and Knowledge Representation formalisms supporting the relational data model within the tradition of Logic Programming and Deductive Databases. Rule authoring is a very demanding Knowledge Engineering task which can be automated though partially by applying Machine Learning algorithms. In this chapter we show how Inductive Logic Programming (ILP), born at the intersection of Machine Learning and Logic Programming and considered as a major approach to Relational Learning, can be adapted to Onto-Relational Learning. For the sake of illustration, we provide details of a specific Onto-Relational Learning solution to the problem of learning rule-based definitions of DL concepts and roles with ILP.
Computationally Efficient Implementation of Convolution-based Locally Adaptive Binarization Techniques
Venue: arXiv cs.CV 2012
Year: 2012

One of the most important steps of document image processing is binarization. The computational requirements of locally adaptive binarization techniques make them unsuitable for devices with limited computing facilities. In this paper, we have presented a computationally efficient implementation of convolution based locally adaptive binarization techniques keeping the performance comparable to the original implementation. The computational complexity has been reduced from O(W2N2) to O(WN2) where WxW is the window size and NxN is the image size. Experiments over benchmark datasets show that the computation time has been reduced by 5 to 15 times depending on the window size while memory consumption remains the same with respect to the state-of-the-art algorithmic implementation.
On Online Labeling with Polynomially Many Labels
Venue: arXiv cs.DS 2012
Year: 2012

In the online labeling problem with parameters n and m we are presented with a sequence of n keys from a totally ordered universe U and must assign each arriving key a label from the label set {1,2,...,m} so that the order of labels (strictly) respects the ordering on U. As new keys arrive it may be necessary to change the labels of some items; such changes may be done at any time at unit cost for each change. The goal is to minimize the total cost. An alternative formulation of this problem is the file maintenance problem, in which the items, instead of being labeled, are maintained in sorted order in an array of length m, and we pay unit cost for moving an item. For the case m=cn for constant c>1, there are known algorithms that use at most O(n log(n)^2) relabelings in total [Itai, Konheim, Rodeh, 1981], and it was shown recently that this is asymptotically optimal [Bulánek, Koucký, Saks, 2012]. For the case of m=Θ(n^C) for C>1, algorithms are known that use O(n log n) relabelings. A matching lower bound was claimed in [Dietz, Seiferas, Zhang, 2004]. That proof involved two distinct steps: a lower bound for a problem they call prefix bucketing and a reduction from prefix bucketing to online labeling. The reduction seems to be incorrect, leaving a (seemingly significant) gap in the proof. In this paper we close the gap by presenting a correct reduction to prefix bucketing. Furthermore we give a simplified and improved analysis of the prefix bucketing lower bound. This improvement allows us to extend the lower bounds for online labeling to the case where the number m of labels is superpolynomial in n. In particular, for superpolynomial m we get an asymptotically optimal lower bound Ω((n log n) / (log log m - log log n)).
Galois correspondence for counting quantifiers
Venue: arXiv cs.LO 2012
Year: 2012

We introduce a new type of closure operator on the set of relations, max-implementation, and its weaker analog max-quantification. Then we show that approximation preserving reductions between counting constraint satisfaction problems (#CSPs) are preserved by these two types of closure operators. Together with some previous results this means that the approximation complexity of counting CSPs is determined by partial clones of relations that additionally closed under these new types of closure operators. Galois correspondence of various kind have proved to be quite helpful in the study of the complexity of the CSP. While we were unable to identify a Galois correspondence for partial clones closed under max-implementation and max-quantification, we obtain such results for slightly different type of closure operators, k-existential quantification. This type of quantifiers are known as counting quantifiers in model theory, and often used to enhance first order logic languages. We characterize partial clones of relations closed under k-existential quantification as sets of relations invariant under a set of partial functions that satisfy the condition of k-subset surjectivity. Finally, we give a description of Boolean max-co-clones, that is, sets of relations on {0,1} closed under max-implementations.
Digital Network Coding Aided Two-way Relaying: Energy Minimization and Queue Analysis
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we consider a three node, two-way relay system with digital network coding over static channels where all link gains are assumed to be constant during transmission. The aim is to minimize total energy consumption while ensuring queue stability at all nodes, for a given pair of random packet arrival rates. Specifically, we allow for a set of transmission modes and solve for the optimal fraction of resources allocated to each mode, including multiaccess uplink transmission mode and network coding broadcasting mode. In addition, for the downlink, we find the condition to determine whether superposition coding with excess data over the better link and network coded data for both users is energy efficient and the corresponding optimization is formulated and solved. To tackle the queue evolution in this network, we present a detailed analysis of the queues at each node using a random scheduling method that closely approximates the theoretical design, through a two-dimensional Markov chain model.
Inferring the Underlying Structure of Information Cascades
Venue: arXiv cs.SI 2012
Year: 2012

In social networks, information and influence diffuse among users as cascades. While the importance of studying cascades has been recognized in various applications, it is difficult to observe the complete structure of cascades in practice. Moreover, much less is known on how to infer cascades based on partial observations. In this paper we study the cascade inference problem following the independent cascade model, and provide a full treatment from complexity to algorithms: (a) We propose the idea of consistent trees as the inferred structures for cascades; these trees connect source nodes and observed nodes with paths satisfying the constraints from the observed temporal information. (b) We introduce metrics to measure the likelihood of consistent trees as inferred cascades, as well as several optimization problems for finding them. (c) We show that the decision problems for consistent trees are in general NP-complete, and that the optimization problems are hard to approximate. (d) We provide approximation algorithms with performance guarantees on the quality of the inferred cascades, as well as heuristics. We experimentally verify the efficiency and effectiveness of our inference algorithms, using real and synthetic data.
Le droit du numérique : une histoire à préserver
Venue: arXiv cs.GL 2012
Year: 2012

Although the history of informatics is recent, this field poses unusual problems with respect to its preservation. These problems are amplified by legal issues, digital law being in itself a subject matter whose history is also worth presenting in a computer science museum. The purpose of this paper is to present a quick overview of the evolution of law regarding digital matters, from an historical perspective as well as with respect to the preservation and presentation of the works.
A New Analysis of the DS-CDMA Cellular Downlink Under Spatial Constraints
Venue: arXiv cs.IT 2012
Year: 2012

The direct-sequence code-division multiple access (DS-CDMA) cellular downlink is modeled by a constrained random spatial model involving a fixed number of base stations placed over a finite area with a minimum separation. The analysis is driven by a new closed-form expression for the conditional outage probability at each mobile, where the conditioning is with respect to the network realization. The analysis features a flexible channel model, accounting for path loss, Nakagami fading, and shadowing. By generating many random networks and applying a given resource allocation policy, the distribution of the rates provided to each user is obtained. In addition to determining the average rate, the analysis can determine the transmission capacity of the network and can characterize fairness in terms of the fraction of users that achieve a specified rate. The analysis is used to compare a rate-control policy against a power-control policy and investigate the influence of the minimum base-station separation.