OpenRaiser/Intern-Atlas huggingface dataset:
An Algorithm for Odd Gracefulness of the Tensor Product of Two Line Graphs
Venue: arXiv cs.DM 2011
Year: 2011

An odd graceful labeling of a graph G=(V,E) is a function f:V(G)->[0,1,2,...,2|E(G)|-1} such that |f(u)-f(v)| is odd value less than or equal to 2|E(G)-1| for any u, v in V(G). In spite of the large number of papers published on the subject of graph labeling, there are few algorithms to be used by researchers to gracefully label graphs. This work provides generalized odd graceful solutions to all the vertices and edges for the tensor product of the two paths P_n and P_m denoted P_n^P_m . Firstly, we describe an algorithm to label the vertices and the edges of the vertex set V(P_n^P_m) and the edge set E(P_n^P_m) respectively. Finally, we prove that the graph P_n^P_m is odd graceful for all integers n and m.
An implementation of range trees with fractional cascading in C++
Venue: arXiv cs.DS 2011
Year: 2011

Range trees are multidimensional binary trees which are used to perform d-dimensional orthogonal range searching. In this technical report we study the implementation issues of range trees with fractional cascading, named layered range trees. We also document our implementation of range trees with fractional cascading in C++ using STL and generic programming techniques.
An Identity Based Key Management Scheme in Wireless Sensor Networks
Venue: arXiv cs.CR 2011
Year: 2011

Pairwise key establishment is one of the fundamental security services in sensor networks which enables sensor nodes in a sensor network to communicate securely with each other using cryptographic techniques. It is not feasible to apply traditional public key management techniques in resource-constrained sensor nodes, and also because the sensor nodes are vulnerable to physical capture. In this paper, we introduce a new scheme called the identity based key pre-distribution using a pseudo random function (IBPRF), which has better trade-off between communication overhead, network connectivity and resilience against node capture compared to the other key pre-distribution schemes. Our scheme can be easily adapted in mobile sensor networks. This scheme supports the addition of new sensor nodes after the initial deployment and also works for any deployment topology. In addition, we propose an improved version of our scheme to support large sensor networks.
Vector Broadcast Channels: Optimal Threshold Selection Problem
Venue: arXiv cs.IT 2011
Year: 2011

Threshold feedback policies are well known and provably rate-wise optimal selective feedback techniques for communication systems requiring partial channel state information (CSI). However, optimal selection of thresholds at mobile users to maximize information theoretic data rates subject to feedback constraints is an open problem. In this paper, we focus on the optimal threshold selection problem, and provide a solution for this problem for finite feedback systems. Rather surprisingly, we show that using the same threshold values at all mobile users is not always a rate-wise optimal feedback strategy, even for a system with identical users experiencing statistically the same channel conditions. By utilizing the theory of majorization, we identify an underlying Schur-concave structure in the rate function and obtain sufficient conditions for a homogenous threshold feedback policy to be optimal. Our results hold for most fading channel models, and we illustrate an application of our results to familiar Rayleigh fading channels.
TiA -- Documentation of TOBI Interface A
Venue: arXiv cs.NI 2011
Year: 2011

This document contains the documentation of TOBI (Tools for BCI) Interface A (TiA). TiA is a standardized interface to transmit raw biosignals. It is able to deal with multirate and block-oriented data transmission. Data is distinguished by different signal types (e.g., EEG, EOG, NIRS,...), whereby those signals can be acquired at the same time from different acquisition devices. TiA is built as a client-server model. Multiple clients can connect to one server. Information is exchanged via a control- and a separated data connection. Control commands and meta information are transmitted over the control connection. Raw biosignal data is delivered using the data connection in a unidirectional way. For this purpose a standardized handshaking protocol and raw data packet have been developed. Thus, an abstraction layer between hardware devices and data processing was evolved facilitating standardization.
Automatic Open Space Area Extraction and Change Detection from High Resolution Urban Satellite Images
Venue: arXiv cs.CV 2011
Year: 2011

In this paper, we study efficient and reliable automatic extraction algorithm to find out the open space area from the high resolution urban satellite imagery, and to detect changes from the extracted open space area during the period 2003, 2006 and 2008. This automatic extraction and change detection algorithm uses some filters, segmentation and grouping that are applied on satellite images. The resultant images may be used to calculate the total available open space area and the built up area. It may also be used to compare the difference between present and past open space area using historical urban satellite images of that same projection, which is an important geo spatial data management application.
On the Certification of the Restricted Isometry Property
Venue: arXiv cs.CC 2011
Year: 2011

Compressed sensing is a technique for finding sparse solutions to underdetermined linear systems. This technique relies on properties of the sensing matrix such as the restricted isometry property. Sensing matrices that satisfy the restricted isometry property with optimal parameters are mainly obtained via probabilistic arguments. Given any matrix, deciding whether it satisfies the restricted isometry property is a non-trivial computational problem. In this paper, we give reductions from dense subgraph problems to the certification of the restricted isometry property. This gives evidence that certifying the restricted isometry property is unlikely to be feasible in polynomial-time. Moreover, on the positive side we propose an improvement on the brute-force enumeration algorithm for checking the restricted isometry property. Another contribution of independent interest is a spectral algorithm for certifying that a random graph does not contain any dense k-subgraph. This "skewed spectral algorithm" performs better than the basic spectral algorithm in a certain range of parameters.
Model Checking CTL is Almost Always Inherently Sequential
Venue: arXiv cs.LO 2011
Year: 2011

The model checking problem for CTL is known to be P-complete (Clarke, Emerson, and Sistla (1986), see Schnoebelen (2002)). We consider fragments of CTL obtained by restricting the use of temporal modalities or the use of negations---restrictions already studied for LTL by Sistla and Clarke (1985) and Markey (2004). For all these fragments, except for the trivial case without any temporal operator, we systematically prove model checking to be either inherently sequential (P-complete) or very efficiently parallelizable (LOGCFL-complete). For most fragments, however, model checking for CTL is already P-complete. Hence our results indicate that, in cases where the combined complexity is of relevance, approaching CTL model checking by parallelism cannot be expected to result in any significant speedup. We also completely determine the complexity of the model checking problem for all fragments of the extensions ECTL, CTL+, and ECTL+.
From Linked Data to Relevant Data -- Time is the Essence
Venue: arXiv cs.IR 2011
Year: 2011

The Semantic Web initiative puts emphasis not primarily on putting data on the Web, but rather on creating links in a way that both humans and machines can explore the Web of data. When such users access the Web, they leave a trail as Web servers maintain a history of requests. Web usage mining approaches have been studied since the beginning of the Web given the log's huge potential for purposes such as resource annotation, personalization, forecasting etc. However, the impact of any such efforts has not really gone beyond generating statistics detailing who, when, and how Web pages maintained by a Web server were visited.
Progress of concepts and processes in library information system: towards Library 2.0
Venue: arXiv cs.DL 2011
Year: 2011

The main principle of the Library 2.0 is in the fact that the information has to be spread from the library to the user and viceversa, to allow fast and permanent adaptation of the library services. Within the framework of the implementation of the "Departmental Plan of the Public Services Reading" by the "General Council of Moselle", the division of the public reading develops a departmental portal as main vector of the information with various users' profile. The context of this research work takes a part of a Master degree training Diploma in STI-Economic Intelligence (Nancy2 University), combining facets of R&D in a professional context at the "Conseil Général de la Moselle" in France.
Distributed k-Core Decomposition
Venue: arXiv cs.OH 2011
Year: 2011

Among the novel metrics used to study the relative importance of nodes in complex networks, k-core decomposition has found a number of applications in areas as diverse as sociology, proteinomics, graph visualization, and distributed system analysis and design. This paper proposes new distributed algorithms for the computation of the k-core decomposition of a network, with the purpose of (i) enabling the run-time computation of k-cores in "live" distributed systems and (ii) allowing the decomposition, over a set of connected machines, of very large graphs, that cannot be hosted in a single machine. Lower bounds on the algorithms complexity are given, and an exhaustive experimental analysis on real-world graphs is provided.
Context-free ordinals
Venue: arXiv cs.FL 2011
Year: 2011

We consider context-free languages equipped with the lexicographic ordering. We show that when the lexicographic ordering of a context-free language is scattered, then its Hausdorff rank is less than $ω^ω$. As a corollary of this result we obtain that an ordinal is the order type of a well-ordered context-free language iff it is less than $ω^{ω^ω}$.
Multifaceted Faculty Network Design and Management: Practice and Experience Report
Venue: arXiv cs.NI 2011
Year: 2011

We report on our experience on multidimensional aspects of our faculty's network design and management, including some unique aspects such as campus-wide VLANs and ghosting, security and monitoring, switching and routing, and others. We outline a historical perspective on certain research, design, and development decisions and discuss the network topology, its scalability, and management in detail; the services our network provides, and its evolution. We overview the security aspects of the management as well as data management and automation and the use of the data by other members of the IT group in the faculty.
Proof of the outage probability conjecture for MISO channels
Venue: arXiv cs.IT 2011
Year: 2011

In Telatar 1999, it is conjectured that the covariance matrices minimizing the outage probability for MIMO channels with Gaussian fading are diagonal with either zeros or constant values on the diagonal. In the MISO setting, this is equivalent to conjecture that the Gaussian quadratic forms having largest tale probability correspond to such diagonal matrices. We prove here the conjecture in the MISO setting.
Use of Devolved Controllers in Data Center Networks
Venue: arXiv cs.NI 2011
Year: 2011

In a data center network, for example, it is quite often to use controllers to manage resources in a centralized man- ner. Centralized control, however, imposes a scalability problem. In this paper, we investigate the use of multiple independent controllers instead of a single omniscient controller to manage resources. Each controller looks after a portion of the network only, but they together cover the whole network. This therefore solves the scalability problem. We use flow allocation as an example to see how this approach can manage the bandwidth use in a distributed manner. The focus is on how to assign components of a network to the controllers so that (1) each controller only need to look after a small part of the network but (2) there is at least one controller that can answer any request. We outline a way to configure the controllers to fulfill these requirements as a proof that the use of devolved controllers is possible. We also discuss several issues related to such implementation.
Symmetry of information and bounds on nonuniform randomness extraction via Kolmogorov extractors
Venue: arXiv cs.CC 2011
Year: 2011

We prove a strong Symmetry of Information relation for random strings (in the sense of Kolmogorov complexity) and establish tight bounds on the amount on nonuniformity that is necessary for extracting a string with randomness rate 1 from a single source of randomness. More precisely, as instantiations of more general results, we show: (1) For all n-bit random strings x and y, x is random conditioned by y if and only if y is random conditioned by x, and (2) while O(1) amount of advice regarding the source is not enough for extracting a string with randomness rate 1 from a source string with constant random rate, ω(1) amount of advice is. The proofs use Kolmogorov extractors as the main technical device.
Codeco: A Grammar Notation for Controlled Natural Language in Predictive Editors
Venue: arXiv cs.CL 2011
Year: 2011

Existing grammar frameworks do not work out particularly well for controlled natural languages (CNL), especially if they are to be used in predictive editors. I introduce in this paper a new grammar notation, called Codeco, which is designed specifically for CNLs and predictive editors. Two different parsers have been implemented and a large subset of Attempto Controlled English (ACE) has been represented in Codeco. The results show that Codeco is practical, adequate and efficient.
Binary words avoiding a pattern and marked succession rule
Venue: arXiv cs.DM 2011
Year: 2011

In this paper we study the enumeration and the construction of particular binary words avoiding the pattern $1^{j+1}0^j$. By means of the theory of Riordan arrays, we solve the enumeration problem and we give a particular succession rule, called jumping and marked succession rule, which describes the growth of such words according to their number of ones. Moreover, the problem of associating a word to a path in the generating tree obtained by the succession rule is solved by introducing an algorithm which constructs all binary words and then kills those containing the forbidden pattern.
Agent Based Processing of Global Evaluation Function
Venue: arXiv cs.DC 2011
Year: 2011

Load balancing across a networked environment is a monotonous job. Moreover, if the job to be distributed is a constraint satisfying one, the distribution of load demands core intelligence. This paper proposes parallel processing through Global Evaluation Function by means of randomly initialized agents for solving Constraint Satisfaction Problems. A potential issue about the number of agents in a machine under the invocation of distribution is discussed here for securing the maximum benefit from Global Evaluation and parallel processing. The proposed system is compared with typical solution that shows an exclusive outcome supporting the nobility of parallel implementation of Global Evaluation Function with certain number of agents in each invoked machine.
A Parametric Level Set Approach to Simultaneous Object Identification and Background Reconstruction for Dual Energy Computed Tomography
Venue: arXiv cs.CV 2011
Year: 2011

Dual energy computerized tomography has gained great interest because of its ability to characterize the chemical composition of a material rather than simply providing relative attenuation images as in conventional tomography. The purpose of this paper is to introduce a novel polychromatic dual energy processing algorithm with an emphasis on detection and characterization of piecewise constant objects embedded in an unknown, cluttered background. Physical properties of the objects, specifically the Compton scattering and photoelectric absorption coefficients, are assumed to be known with some level of uncertainty. Our approach is based on a level-set representation of the characteristic function of the object and encompasses a number of regularization techniques for addressing both the prior information we have concerning the physical properties of the object as well as fundamental, physics-based limitations associated with our ability to jointly recover the Compton scattering and photoelectric absorption properties of the scene. In the absence of an object with appropriate physical properties, our approach returns a null characteristic function and thus can be viewed as simultaneously solving the detection and characterization problems. Unlike the vast majority of methods which define the level set function non-parametrically, i.e., as a dense set of pixel values), we define our level set parametrically via radial basis functions (RBF's) and employ a Gauss-Newton type algorithm for cost minimization. Numerical results show that the algorithm successfully detects objects of interest, finds their shape and location, and gives a adequate reconstruction of the background.
Automatic Performance Debugging of SPMD-style Parallel Programs
Venue: arXiv cs.DC 2011
Year: 2011

The simple program and multiple data (SPMD) programming model is widely used for both high performance computing and Cloud computing. In this paper, we design and implement an innovative system, AutoAnalyzer, that automates the process of debugging performance problems of SPMD-style parallel programs, including data collection, performance behavior analysis, locating bottlenecks, and uncovering their root causes. AutoAnalyzer is unique in terms of two features: first, without any apriori knowledge, it automatically locates bottlenecks and uncovers their root causes for performance optimization; second, it is lightweight in terms of the size of performance data to be collected and analyzed. Our contributions are three-fold: first, we propose two effective clustering algorithms to investigate the existence of performance bottlenecks that cause process behavior dissimilarity or code region behavior disparity, respectively; meanwhile, we present two searching algorithms to locate bottlenecks; second, on a basis of the rough set theory, we propose an innovative approach to automatically uncovering root causes of bottlenecks; third, on the cluster systems with two different configurations, we use two production applications, written in Fortran 77, and one open source code-MPIBZIP2 (http://compression.ca/mpibzip2/), written in C++, to verify the effectiveness and correctness of our methods. For three applications, we also propose an experimental approach to investigating the effects of different metrics on locating bottlenecks.
Capacity of Byzantine Consensus with Capacity-Limited Point-to-Point Links
Venue: arXiv cs.DC 2011
Year: 2011

We consider the problem of maximizing the throughput of Byzantine consensus, when communication links have finite capacity. Byzantine consensus is a classical problem in distributed computing. In existing literature, the communication links are implicitly assumed to have infinite capacity. The problem changes significantly when the capacity of links is finite. We define the throughput and capacity of consensus, and identify upper bound of achievable consensus throughput. We propose an algorithm that achieves consensus capacity in complete four-node networks with at most 1 failure with arbitrary distribution of link capacities.
Adaptive Audio Watermarking via the Optimization Point of View on the Wavelet-Based Entropy
Venue: arXiv cs.CR 2011
Year: 2011

This study aims to present an adaptive audio watermarking method using ideas of wavelet-based entropy (WBE). The method converts low-frequency coefficients of discrete wavelet transform (DWT) into the WBE domain, followed by the calculations of mean values of each audio as well as derivation of some essential properties of WBE. A characteristic curve relating the WBE and DWT coefficients is also presented. The foundation of the embedding process lies on the approximately invariant property demonstrated from the mean of each audio and the characteristic curve. Besides, the quality of the watermarked audio is optimized. In the detecting process, the watermark can be extracted using only values of the WBE. Finally, the performance of the proposed watermarking method is analyzed in terms of signal to noise ratio, mean opinion score and robustness. Experimental results confirm that the embedded data are robust to resist the common attacks like re-sampling, MP3 compression, low-pass filtering, and amplitude-scaling
U-Sem: Semantic Enrichment, User Modeling and Mining of Usage Data on the Social Web
Venue: arXiv cs.IR 2011
Year: 2011

With the growing popularity of Social Web applications, more and more user data is published on the Web everyday. Our research focuses on investigating ways of mining data from such platforms that can be used for modeling users and for semantically augmenting user profiles. This process can enhance adaptation and personalization in various adaptive Web-based systems. In this paper, we present the U-Sem people modeling service, a framework for the semantic enrichment and mining of people's profiles from usage data on the Social Web. We explain the architecture of our people modeling service and describe its application in an adult e-learning context as an example. Versions: Mar 21, 10:10, Mar 25, 09:37
The Decidability Frontier for Probabilistic Automata on Infinite Words
Venue: arXiv cs.LO 2011
Year: 2011

We consider probabilistic automata on infinite words with acceptance defined by safety, reachability, Büchi, coBüchi, and limit-average conditions. We consider quantitative and qualitative decision problems. We present extensions and adaptations of proofs for probabilistic finite automata and present a complete characterization of the decidability and undecidability frontier of the quantitative and qualitative decision problems for probabilistic automata on infinite words.
Doubly Cognitive Architecture Based Cognitive Wireless Sensor Network
Venue: arXiv cs.NI 2011
Year: 2011

Nowadays scarcity of spectrum availability is increasing highly. Adding cognition to the existing Wireless Sensor Network (WSN) infrastructure will help in this situation. As sensor nodes in WSN are limited with some constrains like power, efforts are required to increase the lifetime and other performance measures of the network. In this paper we propose the idea of Doubly Cognitive WSN. The basic idea is to progressively allocate the sensing resources only to the most promising areas of the spectrum. This work is based on Artificial Neural Network as well as on Support Vector Machine (SVM) concept. As the load of sensing resource is reduced significantly, this approach will save the energy of the nodes, and also reduce the sensing time dramatically. The proposed work can be enhanced by doing the pattern analysis thing after a sufficiently long time again and again to review the strategy of sensing. Thus Doubly Cognitive WSN will enable current WSN to overcome the spectrum scarcity as well as save the energy of the sensor nodes.