OpenRaiser/Intern-Atlas huggingface dataset:
Linear Cellular Automata as Discrete Models for Generating Cryptographic Sequences
Venue: arXiv cs.CR 2010
Year: 2010

In this paper, we develop a new cellular automata-based linear model for several nonlinear pseudorandom number generators with practical applications in symmetric cryptography. Such a model generates all the solutions of linear binary difference equations as well as many of these solutions are pseudo-random keystream sequences. In this way, a linear structure based on cellular automata may be used to generate not only difference equation solutions but also cryptographic sequences. The proposed model is very simple since it is based exclusively on successive concatenations of a basic linear automaton.
Self-Organized Authentication in Mobile Ad-hoc Networks
Venue: arXiv cs.CR 2010
Year: 2010

This work proposes a new distributed and self-organized authentication scheme for Mobile Ad-hoc NETworks (MANETs). Apart from describing all its components, special emphasis is placed on proving that the proposal fulfils most requirements derived from the special characteristics of MANETs, including limited physical protection of broadcast medium, frequent route changes caused by mobility, and lack of structured hierarchy. Interesting conclusions are obtained from an analysis of simulation experiments in different scenarios.
On the Separation of Lossy Source-Network Coding and Channel Coding in Wireline Networks
Venue: arXiv cs.IT 2010
Year: 2010

This paper proves the separation between source-network coding and channel coding in networks of noisy, discrete, memoryless channels. We show that the set of achievable distortion matrices in delivering a family of dependent sources across such a network equals the set of achievable distortion matrices for delivering the same sources across a distinct network which is built by replacing each channel by a noiseless, point-to-point bit-pipe of the corresponding capacity. Thus a code that applies source-network coding across links that are made almost lossless through the application of independent channel coding across each link asymptotically achieves the optimal performance across the network as a whole.
Dictionary Optimization for Block-Sparse Representations
Venue: arXiv cs.IT 2010
Year: 2010

Recent work has demonstrated that using a carefully designed dictionary instead of a predefined one, can improve the sparsity in jointly representing a class of signals. This has motivated the derivation of learning methods for designing a dictionary which leads to the sparsest representation for a given set of signals. In some applications, the signals of interest can have further structure, so that they can be well approximated by a union of a small number of subspaces (e.g., face recognition and motion segmentation). This implies the existence of a dictionary which enables block-sparse representations of the input signals once its atoms are properly sorted into blocks. In this paper, we propose an algorithm for learning a block-sparsifying dictionary of a given set of signals. We do not require prior knowledge on the association of signals into groups (subspaces). Instead, we develop a method that automatically detects the underlying block structure. This is achieved by iteratively alternating between updating the block structure of the dictionary and updating the dictionary atoms to better fit the data. Our experiments show that for block-sparse data the proposed algorithm significantly improves the dictionary recovery ability and lowers the representation error compared to dictionary learning methods that do not employ block structure.
Modélisation et extraction de données pour un entrepôt objet
Venue: arXiv cs.DB 2010
Year: 2010

This paper describes an object-oriented model for designing complex and time-variant data warehouse data. The main contribution is the warehouse class concept, which extends the class concept by temporal and archive filters as well as a mapping function. Filters allow the keeping of relevant data changes whereas the mapping function defines the warehouse class schema from a global data source schema. The approach take into account static properties as well as dynamic properties. The behaviour extraction is based on the use-matrix concept.
Analyse multigraduelle OLAP
Venue: arXiv cs.DB 2010
Year: 2010

Decisional systems are based on multidimensional databases improving OLAP analyses. The paper describes a new OLAP operator named "BLEND" to perform multigradual analyses. The operation transforms multidimensional structures during querying in order to analyse measures according to various granularity levels, which are reorganised into a single parameter. We study valid combinations of the operation in the context of strict hierarchies. First experimentations implement the operation in an R-OLAP framework showing the slight cost of this operation.
Contraintes pour modèle et langage multidimensionnels
Venue: arXiv cs.DB 2010
Year: 2010

This paper defines a constraint-based model dedicated to multidimensional databases. The model we define represents data through a constellation of facts (subjects of analyse) associated to dimensions (axis of analyse), which are possibly shared. Each dimension is organised according to several hierarchies (views of analyse) integrating several levels of data granularity. In order to insure data consistency, we introduce 5 semantic constraints (exclusion, inclusion, partition, simultaneity, totality) which can be intra-dimension or inter-dimensions; the intra-dimension constraints allow the expression of constraints between hierarchies within a same dimension whereas the inter-dimensions constraints focus on hierarchies of distinct dimensions. We also study repercussions of these constraints on multidimensional manipulations and we provide extensions of the multidimensional operators.
Graph Sparsification by Edge-Connectivity and Random Spanning Trees
Venue: arXiv cs.DS 2010
Year: 2010

We present new approaches to constructing graph sparsifiers --- weighted subgraphs for which every cut has the same value as the original graph, up to a factor of $(1 \pm ε)$. Our first approach independently samples each edge $uv$ with probability inversely proportional to the edge-connectivity between $u$ and $v$. The fact that this approach produces a sparsifier resolves a question posed by Benczúr and Karger (2002). Concurrent work of Hariharan and Panigrahi also resolves this question. Our second approach constructs a sparsifier by forming the union of several uniformly random spanning trees. Both of our approaches produce sparsifiers with $O(n \log^2(n)/ε^2)$ edges. Our proofs are based on extensions of Karger's contraction algorithm, which may be of independent interest.
Recovery of sparsest signals via $\ell^q$-minimization
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, it is proved that every $s$-sparse vector ${\bf x}\in {\mathbb R}^n$ can be exactly recovered from the measurement vector ${\bf z}={\bf A} {\bf x}\in {\mathbb R}^m$ via some $\ell^q$-minimization with $0< q\le 1$, as soon as each $s$-sparse vector ${\bf x}\in {\mathbb R}^n$ is uniquely determined by the measurement ${\bf z}$.
Approximate Capacity of Gaussian Interference-Relay Networks with Weak Cross Links
Venue: arXiv cs.IT 2010
Year: 2010

In this paper we study a Gaussian relay-interference network, in which relay (helper) nodes are to facilitate competing information flows over a wireless network. We focus on a two-stage relay-interference network where there are weak cross-links, causing the networks to behave like a chain of Z Gaussian channels. For these Gaussian ZZ and ZS networks, we establish an approximate characterization of the rate region. The outer bounds to the capacity region are established using genie-aided techniques that yield bounds sharper than the traditional cut-set outer bounds. For the inner bound of the ZZ network, we propose a new interference management scheme, termed interference neutralization, which is implemented using structured lattice codes. This technique allows for over-the-air interference removal, without the transmitters having complete access the interfering signals. For both the ZZ and ZS networks, we establish a new network decomposition technique that (approximately) achieves the capacity region. We use insights gained from an exact characterization of the corresponding linear deterministic version of the problems, in order to establish the approximate characterization for Gaussian networks.
On Decidable Growth-Rate Properties of Imperative Programs
Venue: arXiv cs.LO 2010
Year: 2010

In 2008, Ben-Amram, Jones and Kristiansen showed that for a simple "core" programming language - an imperative language with bounded loops, and arithmetics limited to addition and multiplication - it was possible to decide precisely whether a program had certain growth-rate properties, namely polynomial (or linear) bounds on computed values, or on the running time. This work emphasized the role of the core language in mitigating the notorious undecidability of program properties, so that one deals with decidable problems. A natural and intriguing problem was whether more elements can be added to the core language, improving its utility, while keeping the growth-rate properties decidable. In particular, the method presented could not handle a command that resets a variable to zero. This paper shows how to handle resets. The analysis is given in a logical style (proof rules), and its complexity is shown to be PSPACE-complete (in contrast, without resets, the problem was PTIME). The analysis algorithm evolved from the previous solution in an interesting way: focus was shifted from proving a bound to disproving it, and the algorithm works top-down rather than bottom-up.
Weighted Soft Decision for Cooperative Sensing in Cognitive Radio Networks
Venue: arXiv cs.NI 2010
Year: 2010

Enhancing the current services or deploying new services operating in RF spectrum requires more licensed spectrum which may not be provided by the regulatory bodies because of spectrum scarcity. On the contrary, recent studies suggest that many portions of the licensed spectrum remains unused or underused for significant period of time raising the issue of spectrum access without license in an opportunistic manner. Among all the spectrum accessing techniques, sensing based methods are considered optimal for their simplicity and cost effectiveness. In this paper, we introduce a new cooperative spectrum sensing technique which considers the spatial variation of secondary (unlicensed) users and each user's contribution is weighted by a factor that depends on received power and path loss. Compared to existing techniques, the proposed one increases the sensing ability and spectrum utilization, and offers greater robustness to noise uncertainty. Moreover, this cooperative technique uses very simple energy detector as its building block thereby reduces the cost and operational complexity.
Key Generation in Wireless Sensor Networks Based on Frequency-selective Channels - Design, Implementation, and Analysis
Venue: arXiv cs.CR 2010
Year: 2010

Key management in wireless sensor networks faces several new challenges. The scale, resource limitations, and new threats such as node capture necessitate the use of an on-line key generation by the nodes themselves. However, the cost of such schemes is high since their secrecy is based on computational complexity. Recently, several research contributions justified that the wireless channel itself can be used to generate information-theoretic secure keys. By exchanging sampling messages during movement, a bit string can be derived that is only known to the involved entities. Yet, movement is not the only possibility to generate randomness. The channel response is also strongly dependent on the frequency of the transmitted signal. In our work, we introduce a protocol for key generation based on the frequency-selectivity of channel fading. The practical advantage of this approach is that we do not require node movement. Thus, the frequent case of a sensor network with static motes is supported. Furthermore, the error correction property of the protocol mitigates the effects of measurement errors and other temporal effects, giving rise to an agreement rate of over 97%. We show the applicability of our protocol by implementing it on MICAz motes, and evaluate its robustness and secrecy through experiments and analysis.
YAPA: A generic tool for computing intruder knowledge
Venue: arXiv cs.LO 2010
Year: 2010

Reasoning about the knowledge of an attacker is a necessary step in many formal analyses of security protocols. In the framework of the applied pi calculus, as in similar languages based on equational logics, knowledge is typically expressed by two relations: deducibility and static equivalence. Several decision procedures have been proposed for these relations under a variety of equational theories. However, each theory has its particular algorithm, and none has been implemented so far. We provide a generic procedure for deducibility and static equivalence that takes as input any convergent rewrite system. We show that our algorithm covers most of the existing decision procedures for convergent theories. We also provide an efficient implementation, and compare it briefly with the tools ProVerif and KiSs.
Modelling and Implementation of ITWS: An ultimate solution to ITS
Venue: arXiv cs.OH 2010
Year: 2010

Casualties due to traffic accidents are increasing day by day. Think of this message being displayed on your computer screen while you were driving "there's a possibility of collision with a car in the next few minutes if you go on driving with this speed and direction". Our research is intended towards developing collision avoidance architecture for the latest Intelligent Transport System. The exchange of safety messages among vehicles and with infrastructure devices poses major challenges. Specially, safety messages have to be adaptively distributed within a certain range of a basically unbounded system. These messages are to be well coordinated and processed via different algorithms. The purpose of the paper is to discuss the ITWS (intelligent transportation warning system), we have discussed the Assisted Global Positioning System(AGPS) system providing additional positioning information at variable conditions. We have also discussed study the Data fusion and kalaman filter in details. The performance of kalman filter and output are discussed. Hardware realization of this model is achieved through software defined radio (SDR).
A New Benchmark For Evaluation Of Graph-Theoretic Algorithms
Venue: arXiv cs.PF 2010
Year: 2010

We propose a new graph-theoretic benchmark in this paper. The benchmark is developed to address shortcomings of an existing widely-used graph benchmark. We thoroughly studied a large number of traditional and contemporary graph algorithms reported in the literature to have clear understanding of their algorithmic and run-time characteristics. Based on this study, we designed a suite of kernels, each of which represents a specific class of graph algorithms. The kernels are designed to capture the typical run-time behavior of target algorithms accurately, while limiting computational and spatial overhead to ensure its computation finishes in reasonable time. We expect that the developed benchmark will serve as a much needed tool for evaluating different architectures and programming models to run graph algorithms.
An affine-intuitionistic system of types and effects: confluence and termination
Venue: arXiv cs.LO 2010
Year: 2010

We present an affine-intuitionistic system of types and effects which can be regarded as an extension of Barber-Plotkin Dual Intuitionistic Linear Logic to multi-threaded programs with effects. In the system, dynamically generated values such as references or channels are abstracted into a finite set of regions. We introduce a discipline of region usage that entails the confluence (and hence determinacy) of the typable programs. Further, we show that a discipline of region stratification guarantees termination.
On Capacity Scaling of Underwater Networks: An Information-Theoretic Perspective
Venue: arXiv cs.IT 2010
Year: 2010

Capacity scaling laws are analyzed in an underwater acoustic network with $n$ regularly located nodes on a square. A narrow-band model is assumed where the carrier frequency is allowed to scale as a function of $n$. In the network, we characterize an attenuation parameter that depends on the frequency scaling as well as the transmission distance. A cut-set upper bound on the throughput scaling is then derived in extended networks. Our result indicates that the upper bound is inversely proportional to the attenuation parameter, thus resulting in a highly power-limited network. Interestingly, it is seen that unlike the case of wireless radio networks, our upper bound is intrinsically related to the attenuation parameter but not the spreading factor. Furthermore, we describe an achievable scheme based on the simple nearest neighbor multi-hop (MH) transmission. It is shown under extended networks that the MH scheme is order-optimal as the attenuation parameter scales exponentially with $\sqrt{n}$ (or faster). Finally, these scaling results are extended to a random network realization.
A two-step fusion process for multi-criteria decision applied to natural hazards in mountains
Venue: arXiv cs.AI 2010
Year: 2010

Mountain river torrents and snow avalanches generate human and material damages with dramatic consequences. Knowledge about natural phenomenona is often lacking and expertise is required for decision and risk management purposes using multi-disciplinary quantitative or qualitative approaches. Expertise is considered as a decision process based on imperfect information coming from more or less reliable and conflicting sources. A methodology mixing the Analytic Hierarchy Process (AHP), a multi-criteria aid-decision method, and information fusion using Belief Function Theory is described. Fuzzy Sets and Possibilities theories allow to transform quantitative and qualitative criteria into a common frame of discernment for decision in Dempster-Shafer Theory (DST ) and Dezert-Smarandache Theory (DSmT) contexts. Main issues consist in basic belief assignments elicitation, conflict identification and management, fusion rule choices, results validation but also in specific needs to make a difference between importance and reliability and uncertainty in the fusion process.
Extension of Wirtinger Calculus in RKH Spaces and the Complex Kernel LMS
Venue: arXiv cs.LG 2010
Year: 2010

Over the last decade, kernel methods for nonlinear processing have successfully been used in the machine learning community. However, so far, the emphasis has been on batch techniques. It is only recently, that online adaptive techniques have been considered in the context of signal processing tasks. To the best of our knowledge, no kernel-based strategy has been developed, so far, that is able to deal with complex valued signals. In this paper, we take advantage of a technique called complexification of real RKHSs to attack this problem. In order to derive gradients and subgradients of operators that need to be defined on the associated complex RKHSs, we employ the powerful tool ofWirtinger's Calculus, which has recently attracted much attention in the signal processing community. Writinger's calculus simplifies computations and offers an elegant tool for treating complex signals. To this end, in this paper, the notion of Writinger's calculus is extended, for the first time, to include complex RKHSs and use it to derive the Complex Kernel Least-Mean-Square (CKLMS) algorithm. Experiments verify that the CKLMS can be used to derive nonlinear stable algorithms, which offer significant performance improvements over the traditional complex LMS orWidely Linear complex LMS (WL-LMS) algorithms, when dealing with nonlinearities.
Attribute Weighting with Adaptive NBTree for Reducing False Positives in Intrusion Detection
Venue: arXiv cs.CR 2010
Year: 2010

In this paper, we introduce new learning algorithms for reducing false positives in intrusion detection. It is based on decision tree-based attribute weighting with adaptive naïve Bayesian tree, which not only reduce the false positives (FP) at acceptable level, but also scale up the detection rates (DR) for different types of network intrusions. Due to the tremendous growth of network-based services, intrusion detection has emerged as an important technique for network security. Recently data mining algorithms are applied on network-based traffic data and host-based program behaviors to detect intrusions or misuse patterns, but there exist some issues in current intrusion detection algorithms such as unbalanced detection rates, large numbers of false positives, and redundant attributes that will lead to the complexity of detection model and degradation of detection accuracy. The purpose of this study is to identify important input attributes for building an intrusion detection system (IDS) that is computationally efficient and effective. Experimental results performed using the KDD99 benchmark network intrusion detection dataset indicate that the proposed approach can significantly reduce the number and percentage of false positives and scale up the balance detection rates for different types of network intrusions.
An Efficient Vein Pattern-based Recognition System
Venue: arXiv cs.CV 2010
Year: 2010

This paper presents an efficient human recognition system based on vein pattern from the palma dorsa. A new absorption based technique has been proposed to collect good quality images with the help of a low cost camera and light source. The system automatically detects the region of interest from the image and does the necessary preprocessing to extract features. A Euclidean Distance based matching technique has been used for making the decision. It has been tested on a data set of 1750 image samples collected from 341 individuals. The accuracy of the verification system is found to be 99.26% with false rejection rate (FRR) of 0.03%.
Performance Oriented Query Processing In GEO Based Location Search Engines
Venue: arXiv cs.IR 2010
Year: 2010

Geographic location search engines allow users to constrain and order search results in an intuitive manner by focusing a query on a particular geographic region. Geographic search technology, also called location search, has recently received significant interest from major search engine companies. Academic research in this area has focused primarily on techniques for extracting geographic knowledge from the web. In this paper, we study the problem of efficient query processing in scalable geographic search engines. Query processing is a major bottleneck in standard web search engines, and the main reason for the thousands of machines used by the major engines. Geographic search engine query processing is different in that it requires a combination of text and spatial data processing techniques. We propose several algorithms for efficient query processing in geographic search engines, integrate them into an existing web search query processor, and evaluate them on large sets of real data and query traces.
A Survey of Mobile WiMAX IEEE 802.16m Standard
Venue: arXiv cs.NI 2010
Year: 2010

IEEE 802.16m amends the IEEE 802.16 Wireless MAN-OFDMA specification to provide an advanced air interface for operation in licenced bands. It will meet the cellular layer requirements of IMT-Advanced next generation mobile networks. It will be designed to provide significantly improved performance compared to other high rate broadband cellular network systems. For the next generation mobile networks, it is important to consider increasing peak, sustained data reates, corresponding spectral efficiencies, system capacity and cell coverage as well as decreasing latency and providing QoS while carefully considering overall system complexity. In this paper we provide an overview of the state-of-the-art mobile WiMAX technology and its development. We focus our discussion on Physical Layer, MAC Layer, Schedular,QoS provisioning and mobile WiMAX specification.