OpenRaiser/Intern-Atlas huggingface dataset:
Sparse approximate inverses of Gramians and impulse response matrices of large-scale interconnected systems
Venue: arXiv cs.SY 2014
Year: 2014

In this paper we show that inverses of well-conditioned, finite-time Gramians and impulse response matrices of large-scale interconnected systems described by sparse state-space models, can be approximated by sparse matrices. The approximation methodology established in this paper opens the door to the development of novel methods for distributed estimation, identification and control of large-scale interconnected systems. The novel estimators (controllers) compute local estimates (control actions) simply as linear combinations of inputs and outputs (states) of local subsystems. The size of these local data sets essentially depends on the condition number of the finite-time observability (controllability) Gramian. Furthermore, the developed theory shows that the sparsity patterns of the system matrices of the distributed estimators (controllers) are primarily determined by the sparsity patterns of state-space matrices of large-scale systems. The computational and memory complexity of the approximation algorithms are $O(N)$, where $N$ is the number of local subsystems of the interconnected system. Consequently, the proposed approximation methodology is computationally feasible for interconnected systems with an extremely large number of local subsystems.
Comparison of the language networks from literature and blogs
Venue: arXiv cs.CL 2014
Year: 2014

In this paper we present the comparison of the linguistic networks from literature and blog texts. The linguistic networks are constructed from texts as directed and weighted co-occurrence networks of words. Words are nodes and links are established between two nodes if they are directly co-occurring within the sentence. The comparison of the networks structure is performed at global level (network) in terms of: average node degree, average shortest path length, diameter, clustering coefficient, density and number of components. Furthermore, we perform analysis on the local level (node) by comparing the rank plots of in and out degree, strength and selectivity. The selectivity-based results point out that there are differences between the structure of the networks constructed from literature and blogs.
Dynamic Tags for Security Protocols
Venue: arXiv cs.CR 2014
Year: 2014

The design and verification of cryptographic protocols is a notoriously difficult task, even in symbolic models which take an abstract view of cryptography. This is mainly due to the fact that protocols may interact with an arbitrary attacker which yields a verification problem that has several sources of unboundedness (size of messages, number of sessions, etc. In this paper, we characterize a class of protocols for which deciding security for an unbounded number of sessions is decidable. More precisely, we present a simple transformation which maps a protocol that is secure for a bounded number of protocol sessions (a decidable problem) to a protocol that is secure for an unbounded number of sessions. The precise number of sessions that need to be considered is a function of the security property and we show that for several classical security properties a single session is sufficient. Therefore, in many cases our results yields a design strategy for security protocols: (i) design a protocol intended to be secure for a {single session}; and (ii) apply our transformation to obtain a protocol which is secure for an unbounded number of sessions.
S-AMP: Approximate Message Passing for General Matrix Ensembles
Venue: arXiv cs.IT 2014
Year: 2014

In this work we propose a novel iterative estimation algorithm for linear observation systems called S-AMP whose fixed points are the stationary points of the exact Gibbs free energy under a set of (first- and second-) moment consistency constraints in the large system limit. S-AMP extends the approximate message-passing (AMP) algorithm to general matrix ensembles. The generalization is based on the S-transform (in free probability) of the spectrum of the measurement matrix. Furthermore, we show that the optimality of S-AMP follows directly from its design rather than from solving a separate optimization problem as done for AMP.
A Relevant Reduction Method for Dynamic Modeling of a Seven-linked Humanoid Robot in the Three-dimensional Space
Venue: arXiv cs.RO 2014
Year: 2014

In this paper, the dynamic modeling of a seven linked humanoid robot, is accurately developed, in the three dimensional space using the Newton-Euler formalism. The aim of this study is to provide a clear and a systematic approach so that starting from generalized motion equations of all rigid bodies of the humanoid robot one can establish a reduced dynamical model. The resulting model can be expended either for simulation propositions or implemented for any given control law. In addition, transformations and developments, proposed here, can be exploited for modeling any other three-dimensional humanoid robot with a different morphology and variable number of rigid bodies and degrees of freedom.
Fare Evasion in Transit Networks
Venue: arXiv cs.GT 2014
Year: 2014

Public transit systems in urban areas usually require large state subsidies, primarily due to high fare evasion rates. In this paper, we study new models for optimizing fare inspection strategies in transit networks based on bilevel programming. In the first level, the leader (the network operator) determines probabilities for inspecting passengers at different locations, while in the second level, the followers (the fare-evading passengers) respond by optimizing their routes given the inspection probabilities and travel times. To model the followers' behavior we study both a non-adaptive variant, in which passengers select a path a priori and continue along it throughout their journey, and an adaptive variant, in which they gain information along the way and use it to update their route. For these problems, which are interesting in their own right, we design exact and approximation algorithms and we prove a tight bound of 3/4 on the ratio of the optimal cost between adaptive and non-adaptive strategies. For the leader's optimization problem, we study a fixed-fare and a flexible-fare variant, where ticket prices may or may not be set at the operator's will. For the latter variant, we design an LP based approximation algorithm. Finally, using a local search procedure that shifts inspection probabilities within an initially determined support set, we perform an extensive computational study for all variants of the problem on instances of the Dutch railway and the Amsterdam subway network. This study reveals that our solutions are within 95% of theoretical upper bounds drawn from the LP relaxation.
Query Rewriting and Optimization for Ontological Databases
Venue: arXiv cs.DB 2014
Year: 2014

Ontological queries are evaluated against a knowledge base consisting of an extensional database and an ontology (i.e., a set of logical assertions and constraints which derive new intensional knowledge from the extensional database), rather than directly on the extensional database. The evaluation and optimization of such queries is an intriguing new problem for database research. In this paper, we discuss two important aspects of this problem: query rewriting and query optimization. Query rewriting consists of the compilation of an ontological query into an equivalent first-order query against the underlying extensional database. We present a novel query rewriting algorithm for rather general types of ontological constraints which is well-suited for practical implementations. In particular, we show how a conjunctive query against a knowledge base, expressed using linear and sticky existential rules, that is, members of the recently introduced Datalog+/- family of ontology languages, can be compiled into a union of conjunctive queries (UCQ) against the underlying database. Ontological query optimization, in this context, attempts to improve this rewriting process so to produce possibly small and cost-effective UCQ rewritings for an input query.
A Simple and Efficient Lock-Free Hash Trie Design for Concurrent Tabling
Venue: arXiv cs.PL 2014
Year: 2014

A critical component in the implementation of a concurrent tabling system is the design of the table space. One of the most successful proposals for representing tables is based on a two-level trie data structure, where one trie level stores the tabled subgoal calls and the other stores the computed answers. In this work, we present a simple and efficient lock-free design where both levels of the tries can be shared among threads in a concurrent environment. To implement lock-freedom we took advantage of the CAS atomic instruction that nowadays can be widely found on many common architectures. CAS reduces the granularity of the synchronization when threads access concurrent areas, but still suffers from low-level problems such as false sharing or cache memory side-effects. In order to be as effective as possible in the concurrent search and insert operations over the table space data structures, we based our design on a hash trie data structure in such a way that it minimizes potential low-level synchronization problems by dispersing as much as possible the concurrent areas. Experimental results in the Yap Prolog system show that our new lock-free hash trie design can effectively reduce the execution time and scale better than previous designs.
Mapping the UK Webspace: Fifteen Years of British Universities on the Web
Venue: arXiv cs.DL 2014
Year: 2014

This paper maps the national UK web presence on the basis of an analysis of the .uk domain from 1996 to 2010. It reviews previous attempts to use web archives to understand national web domains and describes the dataset. Next, it presents an analysis of the .uk domain, including the overall number of links in the archive and changes in the link density of different second-level domains over time. We then explore changes over time within a particular second-level domain, the academic subdomain .ac.uk, and compare linking practices with variables, including institutional affiliation, league table ranking, and geographic location. We do not detect institutional affiliation affecting linking practices and find only partial evidence of league table ranking affecting network centrality, but find a clear inverse relationship between the density of links and the geographical distance between universities. This echoes prior findings regarding offline academic activity, which allows us to argue that real-world factors like geography continue to shape academic relationships even in the Internet age. We conclude with directions for future uses of web archive resources in this emerging area of research.
Location-Aware Cross-Tier Coordinated Multipoint Transmission in Two-Tier Cellular Networks
Venue: arXiv cs.NI 2014
Year: 2014

Multi-tier cellular networks are considered as an effective solution to enhance the coverage and data rate offered by cellular systems. In a multi-tier network, high power base stations (BSs) such as macro BSs are overlaid by lower power small cells such as femtocells and/or picocells. However, co-channel deployment of multiple tiers of BSs gives rise to the problem of cross-tier interference that significantly impacts the performance of wireless networks. Multicell cooperation techniques, such as coordinated multipoint (CoMP) transmission, have been proposed as a promising solution to mitigate the impact of the cross-tier interference in multi-tier networks. In this paper, we propose a novel scheme for Location-Aware Cross-Tier Cooperation (LA-CTC) between BSs in different tiers for downlink CoMP transmission in two-tier cellular networks. On one hand, the proposed scheme only uses CoMP transmission to enhance the performance of the users who suffer from high cross-tier interference due to the co-channel deployment of small cells such as picocells. On the other hand, users with good signal-to-interference-plus-noise ratio (${\rm SINR}$) conditions are served directly by a single BS from any of the two tiers. Thus, the data exchange between the cooperating BSs over the backhaul network can be reduced when compared to the traditional CoMP transmission scheme. We use tools from stochastic geometry to quantify the performance gains obtained by using the proposed scheme in terms of outage probability, achievable data rate, and load per BS. We compare the performance of the proposed scheme with that of other schemes in the literature such as the schemes which use cooperation to serve all users and schemes that use range expansion to offload users to the small cell tier.
Massively Parallel Processor Architectures for Resource-aware Computing
Venue: arXiv cs.AR 2014
Year: 2014

We present a class of massively parallel processor architectures called invasive tightly coupled processor arrays (TCPAs). The presented processor class is a highly parameterizable template, which can be tailored before runtime to fulfill costumers' requirements such as performance, area cost, and energy efficiency. These programmable accelerators are well suited for domain-specific computing from the areas of signal, image, and video processing as well as other streaming processing applications. To overcome future scaling issues (e.g., power consumption, reliability, resource management, as well as application parallelization and mapping), TCPAs are inherently designed in a way to support self-adaptivity and resource awareness at hardware level. Here, we follow a recently introduced resource-aware parallel computing paradigm called invasive computing where an application can dynamically claim, execute, and release resources. Furthermore, we show how invasive computing can be used as an enabler for power management. Finally, we will introduce ideas on how to realize fault-tolerant loop execution on such massively parallel architectures through employing on-demand spatial redundancies at the processor array level.
Emulated ASIC Power and Temperature Monitor System for FPGA Prototyping of an Invasive MPSoC Computing Architecture
Venue: arXiv cs.AR 2014
Year: 2014

In this contribution the emulation of an ASIC temperature and power monitoring system (TPMon) for FPGA prototyping is presented and tested to control processor temperatures under different control targets and operating strategies. The approach for emulating the power monitor is based on an instruction-level energy model. For emulating the temperature monitor, a thermal RC model is used. The monitoring system supplies an invasive MPSoC computing architecture with hardware status information (power and temperature data of the processors within the system). These data are required for resource-aware load distribution. As a proof of concept different operating strategies and control targets were evaluated for a 2-tile invasive MPSoC computing system.
Energy-Efficient Scheduling and Power Allocation in Downlink OFDMA Networks with Base Station Coordination
Venue: arXiv cs.IT 2014
Year: 2014

This paper addresses the problem of energy-efficient resource allocation in the downlink of a cellular OFDMA system. Three definitions of the energy efficiency are considered for system design, accounting for both the radiated and the circuit power. User scheduling and power allocation are optimized across a cluster of coordinated base stations with a constraint on the maximum transmit power (either per subcarrier or per base station). The asymptotic noise-limited regime is discussed as a special case. %The performance of both an isolated and a non-isolated cluster of coordinated base stations is examined in the numerical experiments. Results show that the maximization of the energy efficiency is approximately equivalent to the maximization of the spectral efficiency for small values of the maximum transmit power, while there is a wide range of values of the maximum transmit power for which a moderate reduction of the data rate provides a large saving in terms of dissipated energy. Also, the performance gap among the considered resource allocation strategies reduces as the out-of-cluster interference increases.
Multicell Coordinated Beamforming with Rate Outage Constraint--Part I: Complexity Analysis
Venue: arXiv cs.IT 2014
Year: 2014

This paper studies the coordinated beamforming (CoBF) design in the multiple-input single-output interference channel, assuming only channel distribution information given a priori at the transmitters. The CoBF design is formulated as an optimization problem that maximizes a predefined system utility, e.g., the weighted sum rate or the weighted max-min-fairness (MMF) rate, subject to constraints on the individual probability of rate outage and power budget. While the problem is non-convex and appears difficult to handle due to the intricate outage probability constraints, so far it is still unknown if this outage constrained problem is computationally tractable. To answer this, we conduct computational complexity analysis of the outage constrained CoBF problem. Specifically, we show that the outage constrained CoBF problem with the weighted sum rate utility is intrinsically difficult, i.e., NP-hard. Moreover, the outage constrained CoBF problem with the weighted MMF rate utility is also NP-hard except the case when all the transmitters are equipped with single antenna. The presented analysis results confirm that efficient approximation methods are indispensable to the outage constrained CoBF problem.
Closing the loop of SIEM analysis to Secure Critical Infrastructures
Venue: arXiv cs.CR 2014
Year: 2014

Critical Infrastructure Protection is one of the main challenges of last years. Security Information and Event Management (SIEM) systems are widely used for coping with this challenge. However, they currently present several limitations that have to be overcome. In this paper we propose an enhanced SIEM system in which we have introduced novel components to i) enable multiple layer data analysis; ii) resolve conflicts among security policies, and discover unauthorized data paths in such a way to be able to reconfigure network devices. Furthermore, the system is enriched by a Resilient Event Storage that ensures integrity and unforgeability of events stored.
Phonetic based SoundEx & ShapeEx algorithm for Sindhi Spell Checker System
Venue: arXiv cs.CL 2014
Year: 2014

This paper presents a novel combinational phonetic algorithm for Sindhi Language, to be used in developing Sindhi Spell Checker which has yet not been developed prior to this work. The compound textual forms and glyphs of Sindhi language presents a substantial challenge for developing Sindhi spell checker system and generating similar suggestion list for misspelled words. In order to implement such a system, phonetic based Sindhi language rules and patterns must be considered into account for increasing the accuracy and efficiency. The proposed system is developed with a blend between Phonetic based SoundEx algorithm and ShapeEx algorithm for pattern or glyph matching, generating accurate and efficient suggestion list for incorrect or misspelled Sindhi words. A table of phonetically similar sounding Sindhi characters for SoundEx algorithm is also generated along with another table containing similar glyph or shape based character groups for ShapeEx algorithm. Both these are first ever attempt of any such type of categorization and representation for Sindhi Language.
Categories from scratch
Venue: arXiv cs.LO 2014
Year: 2014

The concept of category from mathematics happens to be useful to computer programmers in many ways. Unfortunately, all "good" explanations of categories so far have been designed by mathematicians, or at least theoreticians with a strong background in mathematics, and this makes categories especially inscrutable to external audiences. More specifically, the common explanatory route to approach categories is usually: "here is a formal specification of what a category is; then look at these known things from maths and theoretical computer science, and admire how they can be described using the notions of category theory." This approach is only successful if the audience can fully understand a conceptual object using only its formal specification. In practice, quite a few people only adopt conceptual objects by abstracting from two or more contexts where the concepts are applicable, instead. This is the road taken below: reconstruct the abstractions from category theory using scratches of understanding from various fields of computer engineering.
The Correctness of Launchbury's Natural Semantics for Lazy Evaluation
Venue: arXiv cs.PL 2014
Year: 2014

In his seminal paper "A Natural Semantics for Lazy Evaluation", John Launchbury proves his semantics correct with respect to a denotational semantics. We machine-checked the proof and found it to fail, and provide two ways to fix it: One by taking a detour via a modified natural semantics with an explicit stack, and one by adjusting the denotational semantics of heaps.
GREEND: An Energy Consumption Dataset of Households in Italy and Austria
Venue: arXiv cs.OH 2014
Year: 2014

Home energy management systems can be used to monitor and optimize consumption and local production from renewable energy. To assess solutions before their deployment, researchers and designers of those systems demand for energy consumption datasets. In this paper, we present the GREEND dataset, containing detailed power usage information obtained through a measurement campaign in households in Austria and Italy. We provide a description of consumption scenarios and discuss design choices for the sensing infrastructure. Finally, we benchmark the dataset with state-of-the-art techniques in load disaggregation, occupancy detection and appliance usage mining.
A New Trust Reputation System for E-Commerce Applications
Venue: arXiv cs.CR 2014
Year: 2014

Robust Trust Reputation Systems (TRS) provide a most trustful reputation score for a specific product or service so as to support relying parties taking the right decision while interacting with an e-commerce application. Thus, TRS must rely on an appropriate architecture and suitable algorithms that are able to improve the selection, storage, generation and classification of textual feedbacks. In this work, we propose a new architecture for TRS in e-commerce applications. In fact, we propose an intelligent layer which displays to each feedback provider, who has already given his recommendation on a product, a collection of prefabricated feedbacks related to the same product. The proposed reputation algorithm generates better trust degree of the user, trust degree of the feedback and a better global reputation score of the product.
An Alternating KMF Algorithm to Solve the Cauchy Problem for Laplaces Equation
Venue: arXiv cs.NA 2014
Year: 2014

This work concerns the use of the iterative algorithm (KMF algorithm) proposed by Kozlov, Mazya and Fomin to solve the Cauchy problem for Laplaces equation. This problem consists to recovering the lacking data on some part of the boundary using the over specified conditions on the other part of the boundary. We describe an alternating formulation of the KMF algorithm and its relationship with a classical formulation. The implementation of this algorithm for a regular domain is performed by the finite element method using the software Freefem. The numerical tests developed show the effectiveness of the proposed algorithm since it allows to have more accurate results as well as reducing the number of iterations needed for convergence.