OpenRaiser/Intern-Atlas huggingface dataset:
Graph Quantization
Venue: arXiv cs.AI 2010
Year: 2010

Vector quantization(VQ) is a lossy data compression technique from signal processing, which is restricted to feature vectors and therefore inapplicable for combinatorial structures. This contribution presents a theoretical foundation of graph quantization (GQ) that extends VQ to the domain of attributed graphs. We present the necessary Lloyd-Max conditions for optimality of a graph quantizer and consistency results for optimal GQ design based on empirical distortion measures and stochastic optimization. These results statistically justify existing clustering algorithms in the domain of graphs. The proposed approach provides a template of how to link structural pattern recognition methods other than GQ to statistical pattern recognition.
Accelerating Competitive Learning Graph Quantization
Venue: arXiv cs.CV 2010
Year: 2010

Vector quantization(VQ) is a lossy data compression technique from signal processing for which simple competitive learning is one standard method to quantize patterns from the input space. Extending competitive learning VQ to the domain of graphs results in competitive learning for quantizing input graphs. In this contribution, we propose an accelerated version of competitive learning graph quantization (GQ) without trading computational time against solution quality. For this, we lift graphs locally to vectors in order to avoid unnecessary calculations of intractable graph distances. In doing so, the accelerated version of competitive learning GQ gradually turns locally into a competitive learning VQ with increasing number of iterations. Empirical results show a significant speedup by maintaining a comparable solution quality.
Effectively integrating information content and structural relationship to improve the GO-based similarity measure between proteins
Venue: arXiv cs.CE 2010
Year: 2010

The Gene Ontology (GO) provides a knowledge base to effectively describe proteins. However, measuring similarity between proteins based on GO remains a challenge. In this paper, we propose a new similarity measure, information coefficient similarity measure (SimIC), to effectively integrate both the information content (IC) of GO terms and the structural information of GO hierarchy to determine the similarity between proteins. Testing on yeast proteins, our results show that SimIC efficiently addresses the shallow annotation issue in GO, thus improves the correlations between GO similarities of yeast proteins and their expression similarities as well as between GO similarities of yeast proteins and their sequence similarities. Furthermore, we demonstrate that the proposed SimIC is superior in predicting yeast protein interactions. We predict 20484 yeast protein-protein interactions (PPIs) between 2462 proteins based on the high SimIC values of biological process (BP) and cellular component (CC). Examining the 214 MIPS complexes in our predicted PPIs shows that all members of 159 MIPS complexes can be found in our PPI predictions, which is more than those (120/214) found in PPIs predicted by relative specificity similarity (RSS). Integrating IC and structural information of GO hierarchy can improve the effectiveness of the semantic similarity measure of GO terms. The new SimIC can effectively correct the effect of shallow annotation, and then provide an effective way to measure similarity between proteins based on Gene Ontology.
The Capacity of Random Linear Coding Networks as Subspace Channels
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we consider noncoherent random linear coding networks (RLCNs) as a discrete memoryless channel (DMC) whose input and output alphabets consist of subspaces. This contrasts with previous channel models in the literature which assume matrices as the channel input and output. No particular assumptions are made on the network topology or the transfer matrix, except that the latter may be rank-deficient according to some rank deficiency probability distribution. We introduce a random vector basis selection procedure which renders the DMC symmetric. The capacity we derive can be seen as a lower bound on the capacity of noncoherent RLCNs, where subspace coding suffices to achieve this bound.
On Network-Error Correcting Convolutional Codes under the BSC Edge Error Model
Venue: arXiv cs.IT 2010
Year: 2010

Convolutional network-error correcting codes (CNECCs) are known to provide error correcting capability in acyclic instantaneous networks within the network coding paradigm under small field size conditions. In this work, we investigate the performance of CNECCs under the error model of the network where the edges are assumed to be statistically independent binary symmetric channels, each with the same probability of error $p_e$($0\leq p_e<0.5$). We obtain bounds on the performance of such CNECCs based on a modified generating function (the transfer function) of the CNECCs. For a given network, we derive a mathematical condition on how small $p_e$ should be so that only single edge network-errors need to be accounted for, thus reducing the complexity of evaluating the probability of error of any CNECC. Simulations indicate that convolutional codes are required to possess different properties to achieve good performance in low $p_e$ and high $p_e$ regimes. For the low $p_e$ regime, convolutional codes with good distance properties show good performance. For the high $p_e$ regime, convolutional codes that have a good \textit{slope} (the minimum normalized cycle weight) are seen to be good. We derive a lower bound on the slope of any rate $b/c$ convolutional code with a certain degree.
Joint Impact of Pathloss Shadowing and Fast Fading - An Outage Formula for Wireless Networks
Venue: arXiv cs.NI 2010
Year: 2010

In this paper, we analyse the joint impact of pathloss, shadowing and fast fading on wireless networks. Taking into account the pathloss and the shadowing, we first express the SINR distribution of a mobile located at a given distance from its serving base-station (BS). The moments of this distribution are easily computed, using the Fenton-Wilkinson method, and a fluid model that considers the cellular network as a continuum of BS. Then considering the joint impact of pathloss, shadowing and fast fading, we derive an easily computable outage probability formula, for a mobile located at any distance from its serving BS. We validate our approach by comparing all results to Monte Carlo simulations performed in a traditional hexagonal network. Indeed, we establish that the results given by the formula are close to the ones given by Monte Carlo simulations. The proposed framework is a powerful tool to study performances of cellular networks e.g. OFDMA systems (WiMAX, LTE).
The Condition of the Turking Class: Are Online Employers Fair and Honest?
Venue: arXiv cs.CY 2010
Year: 2010

Online labor markets give people in poor countries direct access to buyers in rich countries. Economic theory and empirical evidence strongly suggest that this kind of access improves human welfare. However, critics claim that abuses are endemic in these markets and that employers exploit unprotected, vulnerable workers. I investigate part of this claim using a randomized, paired survey in which I ask workers in an online labor market (Amazon Mechanical Turk) how they perceive online employers and employers in their host country in terms of honesty and fairness. I find that, on average, workers perceive the collection of online employers as slightly fairer and more honest than offline employers, though the effect is not significant. Views are more polarized in the online employer case, with more respondents having very positive views of the online collection of employers.
Multidimensional Data Structures and Techniques for Efficient Decision Making
Venue: arXiv cs.CG 2010
Year: 2010

In this paper we present several novel efficient techniques and multidimensional data structures which can improve the decision making process in many domains. We consider online range aggregation, range selection and range weighted median queries; for most of them, the presented data structures and techniques can provide answers in polylogarithmic time. The presented results have applications in many business and economic scenarios, some of which are described in detail in the paper.
A Reduced Offset Based Method for Fast Computation of the Prime Implicants Covering a Given Cube
Venue: arXiv cs.DS 2010
Year: 2010

In order to generate prime implicants for a given cube (minterm), most of minimization methods increase the dimension of this cube by removing one literal from it at a time. But there are two problems of exponential complexity. One of them is the selection of the order in which the literals are to be removed from the implicant at hand. The latter is the mechanism that checks whether a tentative literal removal is acceptable. The reduced Offset concept has been developed to avoid of these problems. This concept is based on positional-cube representation where each cube is represented by two n-bit strings. We show that each reduced Off-cube may be represented by a single n-bit string and propose a set of bitwise operations to be performed on such strings. The experiments on single-output benchmarks show that this approach can significantly speed up the minimization process, improve the quality of its results and reduce the amount of memory required for this aim.
An Exposition of a Result in "Conjugate Codes for Secure and Reliable Information Transmission"
Venue: arXiv cs.IT 2010
Year: 2010

An elementary proof of the attainability of random coding exponent with linear codes for additive channels is presented. The result and proof are from Hamada (Proc. ITW, Chendu, China, 2006), and the present material explains the proof in detail for those unfamiliar with elementary calculations on probabilities related to linear codes.
Genealogical Information Search by Using Parent Bidirectional Breadth Algorithm and Rule Based Relationship
Venue: arXiv cs.DS 2010
Year: 2010

Genealogical information is the best histories resources for culture study and cultural heritage. The genealogical research generally presents family information and depict tree diagram. This paper presents Parent Bidirectional Breadth Algorithm (PBBA) to find consanguine relationship between two persons. In addition, the paper utilizes rules based system in order to identify consanguine relationship. The study reveals that PBBA is fast to solve the genealogical information search problem and the Rule Based Relationship provides more benefits in blood relationship identification.
Cheating for Problem Solving: A Genetic Algorithm with Social Interactions
Venue: arXiv cs.NE 2010
Year: 2010

We propose a variation of the standard genetic algorithm that incorporates social interaction between the individuals in the population. Our goal is to understand the evolutionary role of social systems and its possible application as a non-genetic new step in evolutionary algorithms. In biological populations, ie animals, even human beings and microorganisms, social interactions often affect the fitness of individuals. It is conceivable that the perturbation of the fitness via social interactions is an evolutionary strategy to avoid trapping into local optimum, thus avoiding a fast convergence of the population. We model the social interactions according to Game Theory. The population is, therefore, composed by cooperator and defector individuals whose interactions produce payoffs according to well known game models (prisoner's dilemma, chicken game, and others). Our results on Knapsack problems show, for some game models, a significant performance improvement as compared to a standard genetic algorithm.
Méthode du point proximal: principe et applications aux algorithmes itératifs
Venue: arXiv cs.IT 2010
Year: 2010

This paper recalls the proximal point method. We study two iterative algorithms: the Blahut-Arimoto algorithm for computing the capacity of arbitrary discrete memoryless channels, as an example of an iterative algorithm working with probability density estimates and the iterative decoding of the Bit Interleaved Coded Modulation (BICM-ID). For these iterative algorithms, we apply the proximal point method which allows new interpretations with improved convergence rate.
A Key Distribution Scheme for Sensor Networks Using Structured Graphs
Venue: arXiv cs.CR 2010
Year: 2010

This paper presents a new key predistribution scheme for sensor networks based on structured graphs. Structured graphs are advantageous in that they can be optimized to minimize the parameter of interest. The proposed approach achieves a balance between the number of keys per node, path lengths, network diameter and the complexity of routing algorithm.
Avoiding Interruptions - QoE Trade-offs in Block-coded Streaming Media Applications
Venue: arXiv cs.MM 2010
Year: 2010

We take an analytical approach to study Quality of user Experience (QoE) for video streaming applications. First, we show that random linear network coding applied to blocks of video frames can significantly simplify the packet requests at the network layer and save resources by avoiding duplicate packet reception. Network coding allows us to model the receiver's buffer as a queue with Poisson arrivals and deterministic departures. We consider the probability of interruption in video playback as well as the number of initially buffered packets (initial waiting time) as the QoE metrics. We characterize the optimal trade-off between these metrics by providing upper and lower bounds on the minimum initial buffer size, required to achieve certain level of interruption probability for different regimes of the system parameters. Our bounds are asymptotically tight as the file size goes to infinity.
The Capacity of a Class of Linear Deterministic Networks
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we investigate optimal coding strategies for a class of linear deterministic relay networks. The network under study is a relay network, with one source, one destination, and two relay nodes. Additionally, there is a disturbing source of signals that causes interference with the information signals received by the relay nodes. Our model captures the effect of the interference of message signals and disturbing signals on a single relay network, or the interference of signals from multiple relay networks with each other in the linear deterministic framework. For several ranges of the network parameters we find upper bounds on the maximum achievable source--destination rate in the presense of the disturbing node and in each case we find an optimal coding scheme that achieves the upper bound.
Biological Inspiration for Artificial Immune Systems
Venue: arXiv cs.AI 2010
Year: 2010

Artificial immune systems (AISs) to date have generally been inspired by naive biological metaphors. This has limited the effectiveness of these systems. In this position paper two ways in which AISs could be made more biologically realistic are discussed. We propose that AISs should draw their inspiration from organisms which possess only innate immune systems, and that AISs should employ systemic models of the immune system to structure their overall design. An outline of plant and invertebrate immune systems is presented, and a number of contemporary research that more biologically-realistic AISs could have is also discussed.
On the Efficiency of Fast RSA Variants in Modern Mobile Phones
Venue: arXiv cs.CR 2010
Year: 2010

Modern mobile phones are increasingly being used for more services that require modern security mechanisms such as the public key cryptosystem RSA. It is, however, well known that public key cryptography demands considerable computing resources and that RSA encryption is much faster than RSA decryption. It is consequently an interesting question if RSA as a whole can be executed efficiently on modern mobile phones. In this paper, we explore the efficiency on modern mobile phones of variants of the RSA cryptosystem, covering CRT, MultiPrime RSA, MultiPower RSA, Rebalanced RSA and R Prime RSA by comparing the encryption and decryption time using a simple Java implementation and a typical RSA setup.
Application of a Fuzzy Programming Technique to Production Planning in the Textile Industry
Venue: arXiv cs.AI 2010
Year: 2010

Many engineering optimization problems can be considered as linear programming problems where all or some of the parameters involved are linguistic in nature. These can only be quantified using fuzzy sets. The aim of this paper is to solve a fuzzy linear programming problem in which the parameters involved are fuzzy quantities with logistic membership functions. To explore the applicability of the method a numerical example is considered to determine the monthly production planning quotas and profit of a home textile group.
An Efficient Approach Toward the Asymptotic Analysis of Node-Based Recovery Algorithms in Compressed Sensing
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we propose a general framework for the asymptotic analysis of node-based verification-based algorithms. In our analysis we tend the signal length $n$ to infinity. We also let the number of non-zero elements of the signal $k$ scale linearly with $n$. Using the proposed framework, we study the asymptotic behavior of the recovery algorithms over random sparse matrices (graphs) in the context of compressive sensing. Our analysis shows that there exists a success threshold on the density ratio $k/n$, before which the recovery algorithms are successful, and beyond which they fail. This threshold is a function of both the graph and the recovery algorithm. We also demonstrate that there is a good agreement between the asymptotic behavior of recovery algorithms and finite length simulations for moderately large values of $n$.
Tranceiver Design using Linear Precoding in a Multiuser MIMO System with Limited Feedback
Venue: arXiv cs.IT 2010
Year: 2010

We investigate quantization and feedback of channel state information in a multiuser (MU) multiple input multiple output (MIMO) system. Each user may receive multiple data streams. Our design minimizes the sum mean squared error (SMSE) while accounting for the imperfections in channel state information (CSI) at the transmitter. This paper makes three contributions: first, we provide an end-to-end SMSE transceiver design that incorporates receiver combining, feedback policy and transmit precoder design with channel uncertainty. This enables the proposed transceiver to outperform the previously derived limited feedback MU linear transceivers. Second, we remove dimensionality constraints on the MIMO system, for the scenario with multiple data streams per user, using a combination of maximum expected signal combining (MESC) and minimum MSE receiver. This makes the feedback of each user independent of the others and the resulting feedback overhead scales linearly with the number of data streams instead of the number of receiving antennas. Finally, we analyze SMSE of the proposed algorithm at high signal-to-noise ratio (SNR) and large number of transmit antennas. As an aside, we show analytically why the bit error rate, in the high SNR regime, increases if quantization error is ignored.
Information Theoretic Bounds for Low-Rank Matrix Completion
Venue: arXiv cs.IT 2010
Year: 2010

This paper studies the low-rank matrix completion problem from an information theoretic perspective. The completion problem is rephrased as a communication problem of an (uncoded) low-rank matrix source over an erasure channel. The paper then uses achievability and converse arguments to present order-wise optimal bounds for the completion problem.
Outage Efficient Strategies for Network MIMO with Partial CSIT
Venue: arXiv cs.IT 2010
Year: 2010

We consider a multi-cell MIMO downlink (network MIMO) where $B$ base-stations (BS) with $M$ antennas connected to a central station (CS) serve $K$ single-antenna user terminals (UT). Although many works have shown the potential benefits of network MIMO, the conclusion critically depends on the underlying assumptions such as channel state information at transmitters (CSIT) and backhaul links. In this paper, by focusing on the impact of partial CSIT, we propose an outage-efficient strategy. Namely, with side information of all UT's messages and local CSIT, each BS applies zero-forcing (ZF) beamforming in a distributed manner. For a small number of UTs ($K\leq M$), the ZF beamforming creates $K$ parallel MISO channels. Based on the statistical knowledge of these parallel channels, the CS performs a robust power allocation that simultaneously minimizes the outage probability of all UTs and achieves a diversity gain of $B(M-K+1)$ per UT. With a large number of UTs ($K \geq M$), we propose a so-called distributed diversity scheduling (DDS) scheme to select a subset of $\Ks$ UTs with limited backhaul communication. It is proved that DDS achieves a diversity gain of $B\frac{K}{\Ks}(M-\Ks+1)$, which scales optimally with the number of cooperative BSs $B$ as well as UTs. Numerical results confirm that even under realistic assumptions such as partial CSIT and limited backhaul communications, network MIMO can offer high data rates with a sufficient reliability to individual UTs.
Linear Finite-Field Deterministic Networks With Many Sources and One Destination
Venue: arXiv cs.IT 2010
Year: 2010

We find the capacity region of linear finite-field deterministic networks with many sources and one destination. Nodes in the network are subject to interference and broadcast constraints, specified by the linear finite-field deterministic model. Each node can inject its own information as well as relay other nodes' information. We show that the capacity region coincides with the cut-set region. Also, for a specific case of correlated sources we provide necessary and sufficient conditions for the sources transmissibility. Given the "deterministic model" approximation for the corresponding Gaussian network model, our results may be relevant to wireless sensor networks where the sensing nodes multiplex the relayed data from the other nodes with their own data, and where the goal is to decode all data at a single "collector" node.
On Achievable Rates for Non-Linear Deterministic Interference Channels
Venue: arXiv cs.IT 2010
Year: 2010

This paper extends the literature on interference alignment to more general classes of deterministic channels which incorporate non-linear input-output relationships. It is found that the concept of alignment extends naturally to these deterministic interference channels, and in many cases, the achieved degrees of freedom (DoF) can be shown to be optimal.