OpenRaiser/Intern-Atlas huggingface dataset:
Error Concealment in Image Communication Using Edge Map Watermarking and Spatial Smoothing
Venue: arXiv cs.MM 2010
Year: 2010

We propose a novel error concealment algorithm to be used at the receiver side of a lossy image transmission system. Our algorithm involves hiding the edge map of the original image at the transmitter within itself using a robust watermarking scheme. At the receiver, wherever a lost block is detected, the extracted edge information is used as border constraint for the spatial smoothing employing the intact neighboring blocks in order to conceal errors. Simulation results show the superiority of our technique over existing methods even in case of high packet loss ratios in the communication network.
Constructions of Optical Queues With a Limited Number of Recirculations--Part II: Optimal Constructions
Venue: arXiv cs.IT 2010
Year: 2010

One of the main problems in all-optical packet-switched networks is the lack of optical buffers, and one feasible technology for the constructions of optical buffers is to use optical crossbar Switches and fiber Delay Lines (SDL). In this two-part paper, we consider SDL constructions of optical queues with a limited number of recirculations through the optical switches and the fiber delay lines. Such a problem arises from practical feasibility considerations. In Part I, we have proposed a class of greedy constructions for certain types of optical queues, including linear compressors, linear decompressors, and 2-to-1 FIFO multiplexers, and have shown that every optimal construction among our previous constructions of these types of optical queues under the constraint of a limited number of recirculations must be a greedy construction. In Part II, the present paper, we further show that there are at most two optimal constructions and give a simple algorithm to obtain the optimal construction(s). The main idea in Part II is to use \emph{pairwise comparison} to remove a sequence $\dbf_1^M\in \Gcal_{M,k}$ such that $B(\dbf_1^M;k)<B({\dbf'}_1^M;k)$ for some ${\dbf'}_1^M\in \Gcal_{M,k}$. To our surprise, the simple algorithm for obtaining the optimal construction(s) is related to the well-known \emph{Euclid's algorithm} for finding the greatest common divisor (gcd) of two integers. In particular, we show that if $\gcd(M,k)=1$, then there is only one optimal construction; if $\gcd(M,k)=2$, then there are two optimal constructions; and if $\gcd(M,k)\geq 3$, then there are at most two optimal constructions.
Space-efficient scheduling of stochastically generated tasks
Venue: arXiv cs.PF 2010
Year: 2010

We study the problem of scheduling tasks for execution by a processor when the tasks can stochastically generate new tasks. Tasks can be of different types, and each type has a fixed, known probability of generating other tasks. We present results on the random variable S^sigma modeling the maximal space needed by the processor to store the currently active tasks when acting under the scheduler sigma. We obtain tail bounds for the distribution of S^sigma for both offline and online schedulers, and investigate the expected value of S^sigma.
PROTECT: Proximity-based Trust-advisor using Encounters for Mobile Societies
Venue: arXiv cs.NI 2010
Year: 2010

Many interactions between network users rely on trust, which is becoming particularly important given the security breaches in the Internet today. These problems are further exacerbated by the dynamics in wireless mobile networks. In this paper we address the issue of trust advisory and establishment in mobile networks, with application to ad hoc networks, including DTNs. We utilize encounters in mobile societies in novel ways, noticing that mobility provides opportunities to build proximity, location and similarity based trust. Four new trust advisor filters are introduced - including encounter frequency, duration, behavior vectors and behavior matrices - and evaluated over an extensive set of real-world traces collected from a major university. Two sets of statistical analyses are performed; the first examines the underlying encounter relationships in mobile societies, and the second evaluates DTN routing in mobile peer-to-peer networks using trust and selfishness models. We find that for the analyzed trace, trust filters are stable in terms of growth with time (3 filters have close to 90% overlap of users over a period of 9 weeks) and the results produced by different filters are noticeably different. In our analysis for trust and selfishness model, our trust filters largely undo the effect of selfishness on the unreachability in a network. Thus improving the connectivity in a network with selfish nodes. We hope that our initial promising results open the door for further research on proximity-based trust.
New Visual Cryptography Algorithm For Colored Image
Venue: arXiv cs.CR 2010
Year: 2010

Visual Cryptography is a special encryption technique to hide information in images, which divide secret image into multiple layers. Each layer holds some information. The receiver aligns the layers and the secret information is revealed by human vision without any complex computation. The proposed algorithm is for color image, that presents a system which takes four pictures as an input and generates three images which correspond to three of the four input pictures. The decoding requires only selecting some subset of these 3 images, making transparencies of them, and stacking them on top of each other, so the forth picture is reconstructed by printing the three output images onto transparencies and stacking them together. The reconstructed image achieved in same size with original secret image.
Handling Overload Conditions In High Performance Trustworthy Information Retrieval Systems
Venue: arXiv cs.IR 2010
Year: 2010

Web search engines retrieve a vast amount of information for a given search query. But the user needs only trustworthy and high-quality information from this vast retrieved data. The response time of the search engine must be a minimum value in order to satisfy the user. An optimum level of response time should be maintained even when the system is overloaded. This paper proposes an optimal Load Shedding algorithm which is used to handle overload conditions in real-time data stream applications and is adapted to the Information Retrieval System of a web search engine. Experiment results show that the proposed algorithm enables a web search engine to provide trustworthy search results to the user within an optimum response time, even during overload conditions.
Preserving Privacy and Sharing the Data in Distributed Environment using Cryptographic Technique on Perturbed data
Venue: arXiv cs.CR 2010
Year: 2010

The main objective of data mining is to extract previously unknown patterns from large collection of data. With the rapid growth in hardware, software and networking technology there is outstanding growth in the amount data collection. Organizations collect huge volumes of data from heterogeneous databases which also contain sensitive and private information about and individual .The data mining extracts novel patterns from such data which can be used in various domains for decision making .The problem with data mining output is that it also reveals some information, which are considered to be private and personal. Easy access to such personal data poses a threat to individual privacy. There has been growing concern about the chance of misusing personal information behind the scene without the knowledge of actual data owner. Privacy is becoming an increasingly important issue in many data mining applications in distributed environment. Privacy preserving data mining technique gives new direction to solve this problem. PPDM gives valid data mining results without learning the underlying data values .The benefits of data mining can be enjoyed, without compromising the privacy of concerned individuals. The original data is modified or a process is used in such a way that private data and private knowledge remain private even after the mining process. In this paper we have proposed a framework that allows systemic transformation of original data using randomized data perturbation technique and the modified data is then submitted as result of client's query through cryptographic approach. Using this approach we can achieve confidentiality at client as well as data owner sites. This model gives valid data mining results for analysis purpose but the actual or true data is not revealed.
MIREX: MapReduce Information Retrieval Experiments
Venue: arXiv cs.IR 2010
Year: 2010

We propose to use MapReduce to quickly test new retrieval approaches on a cluster of machines by sequentially scanning all documents. We present a small case study in which we use a cluster of 15 low cost ma- chines to search a web crawl of 0.5 billion pages showing that sequential scanning is a viable approach to running large-scale information retrieval experiments with little effort. The code is available to other researchers at: http://mirex.sourceforge.net
Non-Systematic Codes for Physical Layer Security
Venue: arXiv cs.IT 2010
Year: 2010

This paper is a first study on the topic of achieving physical layer security by exploiting non-systematic channel codes. The chance of implementing transmission security at the physical layer is known since many years in information theory, but it is now gaining an increasing interest due to its many possible applications. It has been shown that channel coding techniques can be effectively exploited for designing physical layer security schemes, able to ensure that an unauthorized receiver, experiencing a channel different from that of the the authorized receiver, is not able to gather any information. Recently, it has been proposed to exploit puncturing techniques in order to reduce the security gap between the authorized and unauthorized channels. In this paper, we show that the same target can also be achieved by using non-systematic codes, able to scramble information bits within the transmitted codeword.
Revealing Method for the Intrusion Detection System
Venue: arXiv cs.NI 2010
Year: 2010

The goal of an Intrusion Detection is inadequate to detect errors and unusual activity on a network or on the hosts belonging to a local network by monitoring network activity. Algorithms for building detection models are broadly classified into two categories, Misuse Detection and Anomaly Detection. The proposed approach should be taken into account, as the security system violations caused by both incompliance with the security policy and attacks on the system resulting in the need to describe models. However, it is based on unified mathematical formalism which is provided for subsequent merger of the models. The above formalism in this paper presents a state machine describing the behavior of a system subject. The set of intrusion description models is used by the evaluation module and determines the likelihood of undesired actions the system is capable of detecting. The number of attacks which are not described by models determining the completeness of detection by the IDS linked to the ability of detecting security violations.
Conception and FPGA implementation of IEEE 802.11s mesh network MAC layer transmitter
Venue: arXiv cs.NI 2010
Year: 2010

This paper proposes, a hardware implementation of Wireless Mesh Networks (WMN) medium Access Controller (MAC) layer transmitter. In the literature a lot of works are focused on WMN routing protocol as well as performance analysis and software integration of WMN units, however few works deals with WMN hardware implementation. In this field our contribution is to conceive and to implements on FPGA a WMN MAC transmitter module. Our implementation, written in hardware description language (HDL) is based on the IEEE 802.11 s standard. The hardware implementation retains a good performance in speed.
Compressed Sensing: How sharp is the Restricted Isometry Property
Venue: arXiv cs.IT 2010
Year: 2010

Compressed Sensing (CS) seeks to recover an unknown vector with $N$ entries by making far fewer than $N$ measurements; it posits that the number of compressed sensing measurements should be comparable to the information content of the vector, not simply $N$. CS combines the important task of compression directly with the measurement task. Since its introduction in 2004 there have been hundreds of manuscripts on CS, a large fraction of which develop algorithms to recover a signal from its compressed measurements. Because of the paradoxical nature of CS -- exact reconstruction from seemingly undersampled measurements -- it is crucial for acceptance of an algorithm that rigorous analyses verify the degree of undersampling the algorithm permits. The Restricted Isometry Property (RIP) has become the dominant tool used for the analysis in such cases. We present here an asymmetric form of RIP which gives tighter bounds than the usual symmetric one. We give the best known bounds on the RIP constants for matrices from the Gaussian ensemble. Our derivations illustrate the way in which the combinatorial nature of CS is controlled. Our quantitative bounds on the RIP allow precise statements as to how aggressively a signal can be undersampled, the essential question for practitioners. We also document the extent to which RIP gives precise information about the true performance limits of CS, by comparing with approaches from high-dimensional geometry.
Deriving Good LDPC Convolutional Codes from LDPC Block Codes
Venue: arXiv cs.IT 2010
Year: 2010

Low-density parity-check (LDPC) convolutional codes are capable of achieving excellent performance with low encoding and decoding complexity. In this paper we discuss several graph-cover-based methods for deriving families of time-invariant and time-varying LDPC convolutional codes from LDPC block codes and show how earlier proposed LDPC convolutional code constructions can be presented within this framework. Some of the constructed convolutional codes significantly outperform the underlying LDPC block codes. We investigate some possible reasons for this "convolutional gain," and we also discuss the --- mostly moderate --- decoder cost increase that is incurred by going from LDPC block to LDPC convolutional codes.
Rate-distortion function via minimum mean square error estimation
Venue: arXiv cs.IT 2010
Year: 2010

We derive a simple general parametric representation of the rate-distortion function of a memoryless source, where both the rate and the distortion are given by integrals whose integrands include the minimum mean square error (MMSE) of the distortion $Δ=d(X,Y)$ based on the source symbol $X$, with respect to a certain joint distribution of these two random variables. At first glance, these relations may seem somewhat similar to the I-MMSE relations due to Guo, Shamai and Verdú, but they are, in fact, quite different. The new relations among rate, distortion, and MMSE are discussed from several aspects, and more importantly, it is demonstrated that they can sometimes be rather useful for obtaining non-trivial upper and lower bounds on the rate-distortion function, as well as for determining the exact asymptotic behavior for very low and for very large distortion. Analogous MMSE relations hold for channel capacity as well.
On Perfect Codes in the Johnson Graph
Venue: arXiv cs.IT 2010
Year: 2010

In this paper we consider the existence of nontrivial perfect codes in the Johnson graph J(n,w). We present combinatorial and number theory techniques to provide necessary conditions for existence of such codes and reduce the range of parameters in which 1-perfect and 2-perfect codes may exist.
Optimized puncturing distributions for irregular non-binary LDPC codes
Venue: arXiv cs.IT 2010
Year: 2010

In this paper we design non-uniform bit-wise puncturing distributions for irregular non-binary LDPC (NB-LDPC) codes. The puncturing distributions are optimized by minimizing the decoding threshold of the punctured LDPC code, the threshold being computed with a Monte-Carlo implementation of Density Evolution. First, we show that Density Evolution computed with Monte-Carlo simulations provides accurate (very close) and precise (small variance) estimates of NB-LDPC code ensemble thresholds. Based on the proposed method, we analyze several puncturing distributions for regular and semi-regular codes, obtained either by clustering punctured bits, or spreading them over the symbol-nodes of the Tanner graph. Finally, optimized puncturing distributions for non-binary LDPC codes with small maximum degree are presented, which exhibit a gap between 0.2 and 0.5 dB to the channel capacity, for punctured rates varying from 0.5 to 0.9.
Robustness maximization of parallel multichannel systems
Venue: arXiv cs.IT 2010
Year: 2010

Bit error rate (BER) minimization and SNR-gap maximization, two robustness optimization problems, are solved, under average power and bit-rate constraints, according to the waterfilling policy. Under peak-power constraint the solutions differ and this paper gives bit-loading solutions of both robustness optimization problems over independent parallel channels. The study is based on analytical approach with generalized Lagrangian relaxation tool and on greedy-type algorithm approach. Tight BER expressions are used for square and rectangular quadrature amplitude modulations. Integer bit solution of analytical continuous bit-rates is performed with a new generalized secant method. The asymptotic convergence of both robustness optimizations is proved for both analytical and algorithmic approaches. We also prove that, in conventional margin maximization problem, the equivalence between SNR-gap maximization and power minimization does not hold with peak-power limitation. Based on a defined dissimilarity measure, bit-loading solutions are compared over power line communication channel for multicarrier systems. Simulation results confirm the asymptotic convergence of both allocation policies. In non asymptotic regime the allocation policies can be interchanged depending on the robustness measure and the operating point of the communication system. The low computational effort of the suboptimal solution based on analytical approach leads to a good trade-off between performance and complexity.
Interference Mitigation through Limited Transmitter Cooperation
Venue: arXiv cs.IT 2010
Year: 2010

Interference limits performance in wireless networks, and cooperation among receivers or transmitters can help mitigate interference by forming distributed MIMO systems. Earlier work shows how limited receiver cooperation helps mitigate interference. The scenario with transmitter cooperation, however, is more difficult to tackle. In this paper we study the two-user Gaussian interference channel with conferencing transmitters to make progress towards this direction. We characterize the capacity region to within 6.5 bits/s/Hz, regardless of channel parameters. Based on the constant-to-optimality result, we show that there is an interesting reciprocity between the scenario with conferencing transmitters and the scenario with conferencing receivers, and their capacity regions are within a constant gap to each other. Hence in the interference-limited regime, the behavior of the benefit brought by transmitter cooperation is the same as that by receiver cooperation.
Employing fuzzy intervals and loop-based methodology for designing structural signature: an application to symbol recognition
Venue: arXiv cs.CV 2010
Year: 2010

Motivation of our work is to present a new methodology for symbol recognition. We support structural methods for representing visual associations in graphic documents. The proposed method employs a structural approach for symbol representation and a statistical classifier for recognition. We vectorize a graphic symbol, encode its topological and geometrical information by an ARG and compute a signature from this structural graph. To address the sensitivity of structural representations to deformations and degradations, we use data adapted fuzzy intervals while computing structural signature. The joint probability distribution of signatures is encoded by a Bayesian network. This network in fact serves as a mechanism for pruning irrelevant features and choosing a subset of interesting features from structural signatures, for underlying symbol set. Finally we deploy the Bayesian network in supervised learning scenario for recognizing query symbols. We have evaluated the robustness of our method against noise, on synthetically deformed and degraded images of pre-segmented 2D architectural and electronic symbols from GREC databases and have obtained encouraging recognition rates. A second set of experimentation was carried out for evaluating the performance of our method against context noise i.e. symbols cropped from complete documents. The results support the use of our signature by a symbol spotting system.
Some Results on the Functional Decomposition of Polynomials
Venue: arXiv cs.SC 2010
Year: 2010

If g and h are functions over some field, we can consider their composition f = g(h). The inverse problem is decomposition: given f, determine the ex- istence of such functions g and h. In this thesis we consider functional decom- positions of univariate and multivariate polynomials, and rational functions over a field F of characteristic p. In the polynomial case, "wild" behaviour occurs in both the mathematical and computational theory of the problem if p divides the degree of g. We consider the wild case in some depth, and deal with those polynomials whose decompositions are in some sense the "wildest": the additive polynomials. We determine the maximum number of decompositions and show some polynomial time algorithms for certain classes of polynomials with wild decompositions. For the rational function case we present a definition of the problem, a normalised version of the problem to which the general problem reduces, and an exponential time solution to the normal problem.
Optimal computation of symmetric Boolean functions in Tree networks
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we address the scenario where nodes with sensor data are connected in a tree network, and every node wants to compute a given symmetric Boolean function of the sensor data. We first consider the problem of computing a function of two nodes with integer measurements. We allow for block computation to enhance data fusion efficiency, and determine the minimum worst-case total number of bits to be exchanged to perform the desired computation. We establish lower bounds using fooling sets, and provide a novel scheme which attains the lower bounds, using information theoretic tools. For a class of functions called sum-threshold functions, this scheme is shown to be optimal. We then turn to tree networks and derive a lower bound for the number of bits exchanged on each link by viewing it as a two node problem. We show that the protocol of recursive innetwork aggregation achieves this lower bound in the case of sumthreshold functions. Thus we have provided a communication and in-network computation strategy that is optimal for each link. All the results can be extended to the case of non-binary alphabets. In the case of general graphs, we present a cut-set lower bound, and an achievable scheme based on aggregation along trees. For complete graphs, the complexity of this scheme is no more than twice that of the optimal scheme.
A Geometric View of Conjugate Priors
Venue: arXiv cs.LG 2010
Year: 2010

In Bayesian machine learning, conjugate priors are popular, mostly due to mathematical convenience. In this paper, we show that there are deeper reasons for choosing a conjugate prior. Specifically, we formulate the conjugate prior in the form of Bregman divergence and show that it is the inherent geometry of conjugate priors that makes them appropriate and intuitive. This geometric interpretation allows one to view the hyperparameters of conjugate priors as the {\it effective} sample points, thus providing additional intuition. We use this geometric understanding of conjugate priors to derive the hyperparameters and expression of the prior used to couple the generative and discriminative components of a hybrid model for semi-supervised learning.