OpenRaiser/Intern-Atlas huggingface dataset:
Matchmaking Semantic Based for Information System Interoperability
Venue: arXiv cs.NI 2011
Year: 2011

Unlike the traditional model of information pull, matchmaking is base on a cooperative partnership between information providers and consumers, assisted by an intelligent facilitator (the matchmaker). Refer to some experiments, the matchmaking to be most useful in two different ways: locating information sources or services that appear dynamically and notification of information changes. Effective information and services sharing in distributed such as P2P based environments raises many challenges, including discovery and localization of resources, exchange over heterogeneous sources, and query processing. One traditional approach for dealing with some of the above challenges is to create unified integrated schemas or services to combine the heterogeneous sources. This approach does not scale well when applied in dynamic distributed environments and has many drawbacks related to the large numbers of sources. The main issues in matchmaking are how to represent advertising and request, and how to calculate possibility matching between advertising and request. The advertising and request can represent data or services by using many model of representation. In this paper, we address an approach of matchmaking by considering semantic agreement between sources.
Finitary Deduction Systems
Venue: arXiv cs.LO 2011
Year: 2011

Cryptographic protocols are the cornerstone of security in distributed systems. The formal analysis of their properties is accordingly one of the focus points of the security community, and is usually split among two groups. In the first group, one focuses on trace-based security properties such as confidentiality and authentication, and provides decision procedures for the existence of attacks for an on-line attackers. In the second group, one focuses on equivalence properties such as privacy and guessing attacks, and provides decision procedures for the existence of attacks for an offline attacker. In all cases the attacker is modeled by a deduction system in which his possible actions are expressed. We present in this paper a notion of finitary deduction systems that aims at relating both approaches. We prove that for such deduction systems, deciding equivalence properties for on-line attackers can be reduced to deciding reachability properties in the same setting.
Estimating Bernoulli trial probability from a small sample
Venue: arXiv cs.DC 2011
Year: 2011

The standard textbook method for estimating the probability of a biased coin from finite tosses implicitly assumes the sample sizes are large and gives incorrect results for small samples. We describe the exact solution, which is correct for any sample size.
Generating Dependent Random Variables Over Networks
Venue: arXiv cs.IT 2011
Year: 2011

In this paper we study the problem of generation of dependent random variables, known as the "coordination capacity" [4,5], in multiterminal networks. In this model $m$ nodes of the network are observing i.i.d. repetitions of $X^{(1)}$, $X^{(2)}$,..., $X^{(m)}$ distributed according to $q(x^{(1)},...,x^{(m)})$. Given a joint distribution $q(x^{(1)},...,x^{(m)},y^{(1)},...,y^{(m)})$, the final goal of the $i^{th}$ node is to construct the i.i.d. copies of $Y^{(i)}$ after the communication over the network where $X^{(1)}$, $X^{(2)}$,..., $X^{(m)}, Y^{(1)}$, $Y^{(2)}$,..., $Y^{(m)}$ are jointly distributed according to $q(x^{(1)},...,x^{(m)},y^{(1)},...,y^{(m)})$. To do this, the nodes can exchange messages over the network at rates not exceeding the capacity constraints of the links. This problem is difficult to solve even for the special case of two nodes. In this paper we prove new inner and outer bounds on the achievable rates for networks with two nodes.
Linear Analog Codes: The Good and The Bad
Venue: arXiv cs.IT 2011
Year: 2011

This paper studies the theory of linear analog error correction coding. Since classical concepts of minimum Hamming distance and minimum Euclidean distance fail in the analog context, a new metric, termed the "minimum (squared Euclidean) distance ratio," is defined. It is shown that linear analog codes that achieve the largest possible value of minimum distance ratio also achieve the smallest possible mean square error (MSE). Based on this achievability, a concept of "maximum distance ratio expansible (MDRE)" is established, in a spirit similar to maximum distance separable (MDS). Existing codes are evaluated, and it is shown that MDRE and MDS can be simultaneously achieved through careful design.
A New Class of MDS Erasure Codes Based on Graphs
Venue: arXiv cs.IT 2011
Year: 2011

Maximum distance separable (MDS) array codes are XOR-based optimal erasure codes that are particularly suitable for use in disk arrays. This paper develops an innovative method to build MDS array codes from an elegant class of nested graphs, termed \textit{complete-graph-of-rings (CGR)}. We discuss a systematic and concrete way to transfer these graphs to array codes, unveil an interesting relation between the proposed map and the renowned perfect 1-factorization, and show that the proposed CGR codes subsume B-codes as their "contracted" codes. These new codes, termed \textit{CGR codes}, and their dual codes are simple to describe, and require minimal encoding and decoding complexity.
Complex Adaptive Digital EcoSystems
Venue: arXiv cs.MA 2011
Year: 2011

We investigate an abstract conceptualisation of DigitalEcosystems from a computer science perspective. We then provide a conceptual framework for the cross pollination of ideas, concepts and understanding between different classes of ecosystems through the universally applicable principles of Complex Adaptive Systems (CAS) modelling. A framework to assist the cross-disciplinary collaboration of research into Digital Ecosystems, including Digital BusinessEcosystems (DBEs) and Digital Knowledge Ecosystems (DKEs). So, we have defined the key steps towards a theoretical framework for Digital Ecosystems, that is compatible with the diverse theoretical views prevalent. Therefore, a theoretical edifice that can unify the diverse efforts within Digital Ecosystems research.
Computation of WCET using Program Slicing and Real-Time Model-Checking
Venue: arXiv cs.SE 2011
Year: 2011

Computing accurate WCET on modern complex architectures is a challenging task. This problem has been devoted a lot of attention in the last decade but there are still some open issues. First, the control flow graph (CFG) of a binary program is needed to compute the WCET and this CFG is built using some internal knowledge of the compiler that generated the binary code; moreover once constructed the CFG has to be manually annotated with loop bounds. Second, the algorithms to compute the WCET (combining Abstract Interpretation and Integer Linear Programming) are tailored for specific architectures: changing the architecture (e.g. replacing an ARM7 by an ARM9) requires the design of a new ad hoc algorithm. Third, the tightness of the computed results (obtained using the available tools) are not compared to actual execution times measured on the real hardware. In this paper we address the above mentioned problems. We first describe a fully automatic method to compute a CFG based solely on the binary program to analyse. Second, we describe the model of the hardware as a product of timed automata, and this model is independent from the program description. The model of a program running on a hardware is obtained by synchronizing (the automaton of) the program with the (timed automata) model of the hardware. Computing the WCET is reduced to a reachability problem on the synchronised model and solved using the model-checker UPPAAL. Finally, we present a rigorous methodology that enables us to compare our computed results to actual execution times measured on a real platform, the ARM920T.
The Hidden Web, XML and Semantic Web: A Scientific Data Management Perspective
Venue: arXiv cs.AI 2011
Year: 2011

The World Wide Web no longer consists just of HTML pages. Our work sheds light on a number of trends on the Internet that go beyond simple Web pages. The hidden Web provides a wealth of data in semi-structured form, accessible through Web forms and Web services. These services, as well as numerous other applications on the Web, commonly use XML, the eXtensible Markup Language. XML has become the lingua franca of the Internet that allows customized markups to be defined for specific domains. On top of XML, the Semantic Web grows as a common structured data source. In this work, we first explain each of these developments in detail. Using real-world examples from scientific domains of great interest today, we then demonstrate how these new developments can assist the managing, harvesting, and organization of data on the Web. On the way, we also illustrate the current research avenues in these domains. We believe that this effort would help bridge multiple database tracks, thereby attracting researchers with a view to extend database technology.
Analytical Classification of Multimedia Index Structures by Using a Partitioning Method-Based Framework
Venue: arXiv cs.MM 2011
Year: 2011

Due to the advances in hardware technology and increase in production of multimedia data in many applications, during the last decades, multimedia databases have become increasingly important. Contentbased multimedia retrieval is one of an important research area in the field of multimedia databases. Lots of research on this field has led to proposition of different kinds of index structures to support fast and efficient similarity search to retrieve multimedia data from these databases. Due to variety and plenty of proposed index structures, we suggest a systematic framework based on partitioning method used in these structures to classify multimedia index structures, and then we evaluated these structures based on important functional measures. We hope this proposed framework will lead to empirical and technical comparison of multimedia index structures and development of more efficient structures at future.
Capacity of Discrete Molecular Diffusion Channels
Venue: arXiv cs.IT 2011
Year: 2011

In diffusion-based molecular communications, messages can be conveyed via the variation in the concentration of molecules in the medium. In this paper, we intend to analyze the achievable capacity in transmission of information from one node to another in a diffusion channel. We observe that because of the molecular diffusion in the medium, the channel possesses memory. We then model the memory of the channel by a two-step Markov chain and obtain the equations describing the capacity of the diffusion channel. By performing a numerical analysis, we obtain the maximum achievable rate for different levels of the transmitter power, i.e., the molecule production rate.
On relaxing the constraints in pairwise compatibility graphs
Venue: arXiv cs.DM 2011
Year: 2011

A graph $G$ is called a pairwise compatibility graph (PCG) if there exists an edge weighted tree $T$ and two non-negative real numbers $d_{min}$ and $d_{max}$ such that each leaf $l_u$ of $T$ corresponds to a vertex $u \in V$ and there is an edge $(u,v) \in E$ if and only if $d_{min} \leq d_T (l_u, l_v) \leq d_{max}$ where $d_T (l_u, l_v)$ is the sum of the weights of the edges on the unique path from $l_u$ to $l_v$ in $T$. In this paper we analyze the class of PCG in relation with two particular subclasses resulting from the the cases where $\dmin=0$ (LPG) and $\dmax=+\infty$ (mLPG). In particular, we show that the union of LPG and mLPG does not coincide with the whole class PCG, their intersection is not empty, and that neither of the classes LPG and mLPG is contained in the other. Finally, as the graphs we deal with belong to the more general class of split matrogenic graphs, we focus on this class of graphs for which we try to establish the membership to the PCG class.
LP-Based Approximation Algorithms for Traveling Salesman Path Problems
Venue: arXiv cs.DS 2011
Year: 2011

This paper has been merged into 1110.4604.
Workflows for the Management of Change in Science, Technologies, Engineering and Mathematics
Venue: arXiv cs.DL 2011
Year: 2011

Mathematical knowledge is a central component in science, engineering, and technology (documentation). Most of it is represented informally, and -- in contrast to published research mathematics -- subject to continual change. Unfortunately, machine support for change management has either been very coarse grained and thus barely useful, or restricted to formal languages, where automation is possible. In this paper, we report on an effort to extend change management to collections of semi-formal documents which flexibly intermix mathematical formulas and natural language and to integrate it into a semantic publishing system for mathematical knowledge. We validate the long-standing assumption that the semantic annotations in these flexiformal documents that drive the machine-supported interaction with documents can support semantic impact analyses at the same time. But in contrast to the fully formal setting, where adaptations of impacted documents can be automated to some degree, the flexiformal setting requires much more user interaction and thus a much tighter integration into document management workflows.
Comparing webometric with web-independent rankings: a case study with German universities
Venue: arXiv cs.SI 2011
Year: 2011

In this paper we examine if hyperlink-based (webometric) indicators can be used to rank academic websites. Therefore we analyzed the interlinking structure of German university websites and compared our simple hyperlink-based ranking with official and web-independent rankings of universities. We found that link impact could not easily be seen as a prestige factor for universities.
Garbage Collection for Multicore NUMA Machines
Venue: arXiv cs.PL 2011
Year: 2011

Modern high-end machines feature multiple processor packages, each of which contains multiple independent cores and integrated memory controllers connected directly to dedicated physical RAM. These packages are connected via a shared bus, creating a system with a heterogeneous memory hierarchy. Since this shared bus has less bandwidth than the sum of the links to memory, aggregate memory bandwidth is higher when parallel threads all access memory local to their processor package than when they access memory attached to a remote package. This bandwidth limitation has traditionally limited the scalability of modern functional language implementations, which seldom scale well past 8 cores, even on small benchmarks. This work presents a garbage collector integrated with our strict, parallel functional language implementation, Manticore, and shows that it scales effectively on both a 48-core AMD Opteron machine and a 32-core Intel Xeon machine.
A Compressed Sensing Wire-Tap Channel
Venue: arXiv cs.IT 2011
Year: 2011

A multiplicative Gaussian wire-tap channel inspired by compressed sensing is studied. Lower and upper bounds on the secrecy capacity are derived, and shown to be relatively tight in the large system limit for a large class of compressed sensing matrices. Surprisingly, it is shown that the secrecy capacity of this channel is nearly equal to the capacity without any secrecy constraint provided that the channel of the eavesdropper is strictly worse than the channel of the intended receiver. In other words, the eavesdropper can see almost everything and yet learn almost nothing. This behavior, which contrasts sharply with that of many commonly studied wiretap channels, is made possible by the fact that a small number of linear projections can make a crucial difference in the ability to estimate sparse vectors.
A Flexible LDPC code decoder with a Network on Chip as underlying interconnect architecture
Venue: arXiv cs.AR 2011
Year: 2011

LDPC (Low Density Parity Check) codes are among the most powerful and widely adopted modern error correcting codes. The iterative decoding algorithms required for these codes involve high computational complexity and high processing throughput is achieved by allocating a sufficient number of processing elements (PEs). Supporting multiple heterogeneous LDPC codes on a parallel decoder poses serious problems in the design of the interconnect structure for such PEs. The aim of this work is to explore the feasibility of NoC (Network on Chip) based decoders, where full flexibility in terms of supported LDPC codes is obtained resorting to an NoC to connect PEs. NoC based LDPC decoders have been previously considered unfeasible because of the cost overhead associated to packet management and routing. On the contrary, the designed NoC adopts a low complexity routing, which introduces a very limited cost overhead with respect to architectures dedicated to specific classes of codes. Moreover the paper proposes an efficient configuration technique, which allows for fast on--the--fly switching among different codes. The decoder architecture is scalable and VLSI synthesis results are presented for several cases of study, including the whole set of WiMAX LDPC codes, WiFi codes and DVB-S2 standard.
Amplify-and-Forward in Wireless Relay Networks
Venue: arXiv cs.IT 2011
Year: 2011

A general class of wireless relay networks with a single source-destination pair is considered. Intermediate nodes in the network employ an amplify-and-forward scheme to relay their input signals. In this case the overall input-output channel from the source via the relays to the destination effectively behaves as an intersymbol interference channel with colored noise. Unlike previous work we formulate the problem of the maximum achievable rate in this setting as an optimization problem with no assumption on the network size, topology, and received signal-to-noise ratio. Previous work considered only scenarios wherein relays use all their power to amplify their received signals. We demonstrate that this may not always maximize the maximal achievable rate in amplify-and-forward relay networks. The proposed formulation allows us to not only recover known results on the performance of the amplify-and-forward schemes for some simple relay networks but also characterize the performance of more complex amplify-and-forward relay networks which cannot be addressed in a straightforward manner using existing approaches. Using cut-set arguments, we derive simple upper bounds on the capacity of general wireless relay networks. Through various examples, we show that a large class of amplify-and-forward relay networks can achieve rates within a constant factor of these upper bounds asymptotically in network parameters.
$\ell_0$ Minimization for Wavelet Frame Based Image Restoration
Venue: arXiv cs.CV 2011
Year: 2011

The theory of (tight) wavelet frames has been extensively studied in the past twenty years and they are currently widely used for image restoration and other image processing and analysis problems. The success of wavelet frame based models, including balanced approach and analysis based approach, is due to their capability of sparsely approximating piecewise smooth functions like images. Motivated by the balanced approach and analysis based approach, we shall propose a wavelet frame based $\ell_0$ minimization model, where the $\ell_0$ "norm" of the frame coefficients is penalized. We adapt the penalty decomposition (PD) method to solve the proposed optimization problem. Numerical results showed that the proposed model solved by the PD method can generate images with better quality than those obtained by either analysis based approach or balanced approach in terms of restoring sharp features as well as maintaining smoothness of the recovered images. Some convergence analysis of the PD method will also be provided.
A Multi-Purpose Scenario-based Simulator for Smart House Environments
Venue: arXiv cs.AI 2011
Year: 2011

Developing smart house systems has been a great challenge for researchers and engineers in this area because of the high cost of implementation and evaluation process of these systems, while being very time consuming. Testing a designed smart house before actually building it is considered as an obstacle towards an efficient smart house project. This is because of the variety of sensors, home appliances and devices available for a real smart environment. In this paper, we present the design and implementation of a multi-purpose smart house simulation system for designing and simulating all aspects of a smart house environment. This simulator provides the ability to design the house plan and different virtual sensors and appliances in a two dimensional model of the virtual house environment. This simulator can connect to any external smart house remote controlling system, providing evaluation capabilities to their system much easier than before. It also supports detailed adding of new emerging sensors and devices to help maintain its compatibility with future simulation needs. Scenarios can also be defined for testing various possible combinations of device states; so different criteria and variables can be simply evaluated without the need of experimenting on a real environment.
An Energy Efficient Protocol for Gateway-Centric Federated Residential Access Networks
Venue: arXiv cs.NI 2011
Year: 2011

The proliferation of overlapping, always-on IEEE 802.11 Access Points (APs) in urban areas can cause spectrum sharing conflicts, inefficient bandwidth usage and power waste. Cooperation among APs could address these problems (i) by allowing under-used devices to hand over their clients to nearby APs and temporarily switch off, (ii) by balancing the load of clients among APs and thus offloading congested APs. The federated houses model provides an appealing backdrop to implement cooperation among APs. In this paper, we outline a framework that, assuming the presence of a multipurpose gateway with AP capabilities in every household, allows such cooperation through the monitoring of local wireless resources and the triggering of offloading requests toward other federated gateways. We then present simulation results in realistic settings that provide some insight on the capabilities of our framework.
Collinearities in Kinetic Point Sets
Venue: arXiv cs.CG 2011
Year: 2011

Let $P$ be a set of $n$ points in the plane, each point moving along a given trajectory. A {\em $k$-collinearity} is a pair $(L,t)$ of a line $L$ and a time $t$ such that $L$ contains at least $k$ points at time $t$, the points along $L$ do not all coincide, and not all of them are collinear at all times. We show that, if the points move with constant velocity, then the number of 3-collinearities is at most $2\binom{n}{3}$, and this bound is tight. There are $n$ points having $Ω(n^3/k^4 + n^2/k^2)$ distinct $k$-collinearities. Thus, the number of $k$-collinearities among $n$ points, for constant $k$, is $O(n^3)$, and this bound is asymptotically tight. In addition, there are $n$ points, moving in pairwise distinct directions with different speeds, such that no three points are ever collinear.