OpenRaiser/Intern-Atlas huggingface dataset:
A Comparative Study of Relaying Schemes with Decode-and-Forward over Nakagami-m Fading Channels
Venue: arXiv cs.IT 2011
Year: 2011

Utilizing relaying techniques to improve performance of wireless systems is a promising avenue. However, it is crucial to understand what type of relaying schemes should be used for achieving different performance objectives under realistic fading conditions. In this paper, we present a general framework for modelling and evaluating the performance of relaying schemes based on the decode-and-forward (DF) protocol over independent and not necessarily identically distributed (INID) Nakagami-m fading channels. In particular, we present closed-form expressions for the statistics of the instantaneous output signal-to-noise ratio of four significant relaying schemes with DF; two based on repetitive transmission and the other two based on relay selection (RS). These expressions are then used to obtain closed-form expressions for the outage probability and the average symbol error probability for several modulations of all considered relaying schemes over INID Nakagami-m fading. Importantly, it is shown that when the channel state information for RS is perfect, RS-based transmission schemes always outperform repetitive ones. Furthermore, when the direct link between the source and the destination nodes is sufficiently strong, relaying may not result in any gains and in this case it should be switched-off.
Counting Homomorphisms and Partition Functions
Venue: arXiv cs.CC 2011
Year: 2011

Homomorphisms between relational structures are not only fundamental mathematical objects, but are also of great importance in an applied computational context. Indeed, constraint satisfaction problems (CSPs), a wide class of algorithmic problems that occur in many different areas of computer science such as artificial intelligence or database theory, may be viewed as asking for homomorphisms between two relational structures [FedVar98]. In a logical setting, homomorphisms may be viewed as witnesses for positive primitive formulas in a relational language. As we shall see, homomorphisms, or more precisely the numbers of homomorphisms between two structures, are also related to a fundamental computational problem of statistical physics. In this article, we are concerned with the complexity of counting homomorphisms from a given structure A to a fixed structure B. Actually, we are mainly interested in a generalization of this problem to weighted homomorphisms (or partition functions). We almost exclusively focus on graphs. The first part of the article is a short survey of what is known about the problem. In the second part, we give a proof of a theorem due to Bulatov and the first author of this paper [BulGro05], which classifies the complexity of partition functions described by matrices with non-negative entries. The proof we give here is essentially the same as the original one, with a few shortcuts due to [Thu09], but it is phrased in a different, more graph theoretical language that may make it more accessible to most readers.
Low-rank Matrix Recovery from Errors and Erasures
Venue: arXiv cs.IT 2011
Year: 2011

This paper considers the recovery of a low-rank matrix from an observed version that simultaneously contains both (a) erasures: most entries are not observed, and (b) errors: values at a constant fraction of (unknown) locations are arbitrarily corrupted. We provide a new unified performance guarantee on when the natural convex relaxation of minimizing rank plus support succeeds in exact recovery. Our result allows for the simultaneous presence of random and deterministic components in both the error and erasure patterns. On the one hand, corollaries obtained by specializing this one single result in different ways recover (up to poly-log factors) all the existing works in matrix completion, and sparse and low-rank matrix recovery. On the other hand, our results also provide the first guarantees for (a) recovery when we observe a vanishing fraction of entries of a corrupted matrix, and (b) deterministic matrix completion.
On Non-Complete Sets and Restivo's Conjecture
Venue: arXiv cs.FL 2011
Year: 2011

A finite set S of words over the alphabet A is called non-complete if Fact(S*) is different from A*. A word w in A* - Fact(S*) is said to be uncompletable. We present a series of non-complete sets S_k whose minimal uncompletable words have length 5k^2 - 17k + 13, where k > 3 is the maximal length of words in S_k. This is an infinite series of counterexamples to Restivo's conjecture, which states that any non-complete set possesses an uncompletable word of length at most 2k^2.
Near concavity of the growth rate for coupled LDPC chains
Venue: arXiv cs.IT 2011
Year: 2011

Convolutional Low-Density-Parity-Check (LDPC) ensembles have excellent performance. Their iterative threshold increases with their average degree, or with the size of the coupling window in randomized constructions. In the later case, as the window size grows, the Belief Propagation (BP) threshold attains the maximum-a-posteriori (MAP) threshold of the underlying ensemble. In this contribution we show that a similar phenomenon happens for the growth rate of coupled ensembles. Loosely speaking, we observe that as the coupling strength grows, the growth rate of the coupled ensemble comes close to the concave hull of the underlying ensemble's growth rate. For ensembles randomly coupled across a window the growth rate actually tends to the concave hull of the underlying one as the window size increases. Our observations are supported by the calculations of the combinatorial growth rate, and that of the growth rate derived from the replica method. The observed concavity is a general feature of coupled mean field graphical models and is already present at the level of coupled Curie-Weiss models. There, the canonical free energy of the coupled system tends to the concave hull of the underlying one. As we explain, the behavior of the growth rate of coupled ensembles is exactly analogous.
Program Optimization Based Pointer Analysis and Live Stack-Heap Analysis
Venue: arXiv cs.SE 2011
Year: 2011

In this paper, we present type systems for flow-sensitive pointer analysis, live stack-heap (variables) analysis, and program optimization. The type system for live stack-heap analysis is an enrichment of that for pointer analysis; the enrichment has the form of a second component being added to types of the latter system. Results of pointer analysis are proved useful via their use in the type system for live stack-heap analysis. The type system for program optimization is also an augmentation of that for live stack-heap analysis, but the augmentation takes the form of a transformation component being added to inference rules of the latter system. The form of program optimization being achieved is that of dead-code elimination. A form of program correction may result indirectly from eliminating faulty code (causing the program to abort) that is dead. Therefore program optimization can result in program correction. Our type systems have the advantage of being compositional and relatively-simply structured. The novelty of our work comes from the fact that our type system for program optimization associates the optimized version of a program with a justification (in the form of a type derivation) for the optimization. This justification is pretty much appreciated in many research areas like certified code (proof-carrying code) which is the motivation of this work
Algorithms for Computing Triangular Decompositions of Polynomial Systems
Venue: arXiv cs.SC 2011
Year: 2011

We propose new algorithms for computing triangular decompositions of polynomial systems incrementally. With respect to previous works, our improvements are based on a {\em weakened} notion of a polynomial GCD modulo a regular chain, which permits to greatly simplify and optimize the sub-algorithms. Extracting common work from similar expensive computations is also a key feature of our algorithms. In our experimental results the implementation of our new algorithms, realized with the {\RegularChains} library in {\Maple}, outperforms solvers with similar specifications by several orders of magnitude on sufficiently difficult problems.
A Note on: `Algorithms for Connected Set Cover Problem and Fault-Tolerant Connected Set Cover Problem'
Venue: arXiv cs.DS 2011
Year: 2011

A flaw in the greedy approximation algorithm proposed by Zhang et al. for minimum connected set cover problem is corrected, and a stronger result on the approximation ratio of the modified greedy algorithm is established. The results are now consistent with the existing results on connected dominating set problem which is a special case of the minimum connected set cover problem.
A distributed Approach for Access and Visibility Task with a Manikin and a Robot in a Virtual Reality Environment
Venue: arXiv cs.RO 2011
Year: 2011

This paper presents a new method, based on a multi-agent system and on a digital mock-up technology, to assess an efficient path planner for a manikin or a robot for access and visibility task taking into account ergonomic constraints or joint and mechanical limits. In order to solve this problem, the human operator is integrated in the process optimization to contribute to a global perception of the environment. This operator cooperates, in real-time, with several automatic local elementary agents. The result of this work validates solutions through the digital mock-up; it can be applied to simulate maintenability and mountability tasks.
SLDs for Visualizing Multicolor Elevation Contour Lines in Geo-Spatial Web Applications
Venue: arXiv cs.MM 2011
Year: 2011

This paper addresses the need for geospatial consumers (either humans or machines) to visualize multicolored elevation contour poly lines with respect their different contour intervals and control the visual portrayal of the data with which they work. The current OpenGIS Web Map Service (WMS) specification supports the ability for an information provider to specify very basic styling options by advertising a preset collection of visual portrayals for each available data set. However, while a WMS currently can provide the user with a choice of style options, the WMS can only tell the user the name of each style. It cannot tell the user what portrayal will look like on the map. More importantly, the user has no way of defining their own styling rules. The ability for a human or machine client to define these rules requires a styling language that the client and server can both understand. Defining this language, called the StyledLayerDescriptor (SLD), is the main focus of this paper, and it can be used to portray the output of Web Map Servers, Web Feature Servers and Web Coverage Servers.
The Role of Social Networks in Online Shopping: Information Passing, Price of Trust, and Consumer Choice
Venue: arXiv cs.SI 2011
Year: 2011

While social interactions are critical to understanding consumer behavior, the relationship between social and commerce networks has not been explored on a large scale. We analyze Taobao, a Chinese consumer marketplace that is the world's largest e-commerce website. What sets Taobao apart from its competitors is its integrated instant messaging tool, which buyers can use to ask sellers about products or ask other buyers for advice. In our study, we focus on how an individual's commercial transactions are embedded in their social graphs. By studying triads and the directed closure process, we quantify the presence of information passing and gain insights into when different types of links form in the network. Using seller ratings and review information, we then quantify a price of trust. How much will a consumer pay for transaction with a trusted seller? We conclude by modeling this consumer choice problem: if a buyer wishes to purchase a particular product, how does (s)he decide which store to purchase it from? By analyzing the performance of various feature sets in an information retrieval setting, we demonstrate how the social graph factors into understanding consumer behavior.
Multiple Unicast Capacity of 2-Source 2-Sink Networks
Venue: arXiv cs.IT 2011
Year: 2011

We study the sum capacity of multiple unicasts in wired and wireless multihop networks. With 2 source nodes and 2 sink nodes, there are a total of 4 independent unicast sessions (messages), one from each source to each sink node (this setting is also known as an X network). For wired networks with arbitrary connectivity, the sum capacity is achieved simply by routing. For wireless networks, we explore the degrees of freedom (DoF) of multihop X networks with a layered structure, allowing arbitrary number of hops, and arbitrary connectivity within each hop. For the case when there are no more than two relay nodes in each layer, the DoF can only take values 1, 4/3, 3/2 or 2, based on the connectivity of the network, for almost all values of channel coefficients. When there are arbitrary number of relays in each layer, the DoF can also take the value 5/3 . Achievability schemes incorporate linear forwarding, interference alignment and aligned interference neutralization principles. Information theoretic converse arguments specialized for the connectivity of the network are constructed based on the intuition from linear dimension counting arguments.
Network attack detection at flow level
Venue: arXiv cs.CR 2011
Year: 2011

In this paper, we propose a new method for detecting unauthorized network intrusions, based on a traffic flow model and Cisco NetFlow protocol application. The method developed allows us not only to detect the most common types of network attack (DDoS and port scanning), but also to make a list of trespassers' IP-addresses. Therefore, this method can be applied in intrusion detection systems, and in those systems which lock these IP-addresses.
Fixed Parameter Tractable Algorithm for Firefighting Problem
Venue: arXiv cs.DS 2011
Year: 2011

The firefighter problem is defined as below. A fire initially breaks out at a vertex r on a graph G. In each step, a firefighter chooses to protect one vertex, which is not yet burnt. And the fire spreads out to its unprotected neighboring vertices afterwards. The objective of the problem is to choose a sequence of vertices to protect, in order to save maximum number of vertices from the fire. In this paper, we will introduce a parameter k into the firefighter problem and give several FPT algorithms using a random separation technique of Cai, Chan and Chan. We will prove firefighter problem is FPT on general graph if we take total number of vertices burnt to be a parameter. If we parameterize the number of protected vertices, we discover several FPT algorithms of the firefighter problem on degree bounded graph and unicyclic graph. Furthermore, we also study the firefighter problem on weighted and valued graph, and the problem with multiple fire sources on degree-bounded graph.
Analysis of Block OMP using Block RIP
Venue: arXiv cs.IT 2011
Year: 2011

Orthogonal matching pursuit (OMP) is a canonical greedy algorithm for sparse signal reconstruction. When the signal of interest is block sparse, i.e., it has nonzero coefficients occurring in clusters, the block version of OMP algorithm (i.e., Block OMP) outperforms the conventional OMP. In this paper, we demonstrate that a new notion of block restricted isometry property (Block RIP), which is less stringent than standard restricted isometry property (RIP), can be used for a very straightforward analysis of Block OMP. It is demonstrated that Block OMP can exactly recover any block K-sparse signal in no more than K steps if the Block RIP of order K+1 with a sufficiently small isometry constant is satisfied. Using this result it can be proved that Block OMP can yield better reconstruction properties than the conventional OMP when the signal is block sparse.
A Statistical Nonparametric Approach of Face Recognition: Combination of Eigenface & Modified k-Means Clustering
Venue: arXiv cs.CV 2011
Year: 2011

Facial expressions convey non-verbal cues, which play an important role in interpersonal relations. Automatic recognition of human face based on facial expression can be an important component of natural human-machine interface. It may also be used in behavioural science. Although human can recognize the face practically without any effort, but reliable face recognition by machine is a challenge. This paper presents a new approach for recognizing the face of a person considering the expressions of the same human face at different instances of time. This methodology is developed combining Eigenface method for feature extraction and modified k-Means clustering for identification of the human face. This method endowed the face recognition without using the conventional distance measure classifiers. Simulation results show that proposed face recognition using perception of k-Means clustering is useful for face images with different facial expressions.
Latent table discovery by semantic relationship extraction between unrelated sets of entity sets of structured data sources
Venue: arXiv cs.DB 2011
Year: 2011

Querying is one of the basic functionality expected from a database system. Query efficiency is adversely affected by increase in the number of participating tables. Also, querying based on syntax largely limits the gamut of queries a database system can process. Syntactic queries rely on the database table structure, which is a cause of concern for large organisations due to incompatibility between heterogeneous systems that store data distributed across geographic locations. Solution to these problems is answered to some extent by moving towards semantic technology by making data and the database meaningful. In doing so, relationship between sets of entity sets will not be limited only to syntactic constraints but would also permit semantic connections nonetheless such relationships may be tacit, intangible and invisible. The goal of this work is to extract such hidden relationships between unrelated sets of entity sets and store them in a tangible form. A few sample cases are provided to vindicate that the proposed work improves querying significantly.
Multi-Hop Routing and Scheduling in Wireless Networks in the SINR model
Venue: arXiv cs.DS 2011
Year: 2011

We present an algorithm for multi-hop routing and scheduling of requests in wireless networks in the \sinr\ model. The goal of our algorithm is to maximize the throughput or maximize the minimum ratio between the flow and the demand. Our algorithm partitions the links into buckets. Every bucket consists of a set of links that have nearly equivalent reception powers. We denote the number of nonempty buckets by $\sigdiv$. Our algorithm obtains an approximation ratio of $O(\sigdiv \cdot \log n)$, where $n$ denotes the number of nodes. For the case of linear powers $\sigdiv =1$, hence the approximation ratio of the algorithm is $O(\log n)$. This is the first practical approximation algorithm for linear powers with an approximation ratio that depends only on $n$ (and not on the max-to-min distance ratio). If the transmission power of each link is part of the input (and arbitrary), then $\sigdiv = O(\logΓ+ \log Δ)$, where $Γ$ denotes the ratio of the max-to-min power, and $Δ$ denotes the ratio of the max-to-min distance. Hence, the approximation ratio is $O(\log n \cdot (\logΓ+ \log Δ))$. Finally, we consider the case that the algorithm needs to assign powers to each link in a range $[\pmin,\pmax]$. An extension of the algorithm to this case achieves an approximation ratio of $O[(\log n + \log \log Γ) \cdot (\logΓ+ \log Δ)]$.
A Basic Unified Context for Evaluating the Beam Forming and MIMO Options in a Wireless Link
Venue: arXiv cs.IT 2011
Year: 2011

For one isolated wireless link we take a unified look at simple beamforming (BF) as contrasted with MIMO to see how both emerge and under which conditions advantage goes to one or the other. Communication is from a high base array to a user in clutter. The channel propagation model is derived from fundamentals. The base knows the power angular spectrum, but not the channel instantiation. Eigenstates of the field spatial autocorrelation are the preferred apodizations (APODs) which are drivers of the natural modes for exciting lectric fields. Preference for MIMO or BF depends on APOD spectra which are surveyed pointing to various asymptotic effects, including the maximum BF gain. Performance is studied under varying eigenmode power settings at 10% outage. We focus on (1,4) driving the strongest mode for BF and (4,4) driving the 4 strongest for MIMO. Results are obtained under representative parameter settings, e.g. an angular spread of 8 deg, 2 GHz carrier, 0 dB SNR and an array aperture of 1.68m (4 field decorrelation lengths) with antenna elements spaced as close as lambda/2. We find MIMO excelling for array apertures much larger than the decorrelation length; BF does almost as well for smaller apertures.
Fuzzy Rules and Evidence Theory for Satellite Image Analysis
Venue: arXiv cs.CV 2011
Year: 2011

Design of a fuzzy rule based classifier is proposed. The performance of the classifier for multispectral satellite image classification is improved using Dempster- Shafer theory of evidence that exploits information of the neighboring pixels. The classifiers are tested rigorously with two known images and their performance are found to be better than the results available in the literature. We also demonstrate the improvement of performance while using D-S theory along with fuzzy rule based classifiers over the basic fuzzy rule based classifiers for all the test cases.
Two Dimensional Random Patterns
Venue: arXiv cs.CR 2011
Year: 2011

A new approach to the generation of random sequences and two dimensional random patterns is proposed in this paper in which random sequences are generated by making use of either Delaunay triangulation or Voronoi diagrams drawn from random points taken in a two dimensional plane. Both the random sequences and two dimensional random patterns generated in this manner are shown to be more random when compared to pseudo-random sequences and patterns.
"Improved FCM algorithm for Clustering on Web Usage Mining"
Venue: arXiv cs.IR 2011
Year: 2011

In this paper we present clustering method is very sensitive to the initial center values, requirements on the data set too high, and cannot handle noisy data the proposal method is using information entropy to initialize the cluster centers and introduce weighting parameters to adjust the location of cluster centers and noise problems.The navigation datasets which are sequential in nature, Clustering web data is finding the groups which share common interests and behavior by analyzing the data collected in the web servers, this improves clustering on web data efficiently using improved fuzzy c-means(FCM) clustering. Web usage mining is the application of data mining techniques to web log data repositories. It is used in finding the user access patterns from web access log. Web data Clusters are formed using on MSNBC web navigation dataset.
Optimal Channel Training in Uplink Network MIMO Systems
Venue: arXiv cs.IT 2011
Year: 2011

We consider a multi-cell frequency-selective fading uplink channel (network MIMO) from K single-antenna user terminals (UTs) to B cooperative base stations (BSs) with M antennas each. The BSs, assumed to be oblivious of the applied codebooks, forward compressed versions of their observations to a central station (CS) via capacity limited backhaul links. The CS jointly decodes the messages from all UTs. Since the BSs and the CS are assumed to have no prior channel state information (CSI), the channel needs to be estimated during its coherence time. Based on a lower bound of the ergodic mutual information, we determine the optimal fraction of the coherence time used for channel training, taking different path losses between the UTs and the BSs into account. We then study how the optimal training length is impacted by the backhaul capacity. Although our analytical results are based on a large system limit, we show by simulations that they provide very accurate approximations for even small system dimensions.