OpenRaiser/Intern-Atlas huggingface dataset:
Toward Fast Reliable Communication at Rates Near Capacity with Gaussian Noise
Venue: arXiv cs.IT 2010
Year: 2010

For the additive Gaussian noise channel with average codeword power constraint, sparse superposition codes and adaptive successive decoding is developed. Codewords are linear combinations of subsets of vectors, with the message indexed by the choice of subset. A feasible decoding algorithm is presented. Communication is reliable with error probability exponentially small for all rates below the Shannon capacity.
Convergence-Optimal Quantizer Design of Distributed Contraction-based Iterative Algorithms with Quantized Message Passing
Venue: arXiv cs.DC 2010
Year: 2010

In this paper, we study the convergence behavior of distributed iterative algorithms with quantized message passing. We first introduce general iterative function evaluation algorithms for solving fixed point problems distributively. We then analyze the convergence of the distributed algorithms, e.g. Jacobi scheme and Gauss-Seidel scheme, under the quantized message passing. Based on the closed-form convergence performance derived, we propose two quantizer designs, namely the time invariant convergence-optimal quantizer (TICOQ) and the time varying convergence-optimal quantizer (TVCOQ), to minimize the effect of the quantization error on the convergence. We also study the tradeoff between the convergence error and message passing overhead for both TICOQ and TVCOQ. As an example, we apply the TICOQ and TVCOQ designs to the iterative waterfilling algorithm of MIMO interference game.
An Algorithm to List All the Fixed-Point Free Involutions on a Finite Set
Venue: arXiv cs.DS 2010
Year: 2010

An involution on a finite set is a bijection such as I(I(e))=e for all the element of the set. A fixed-point free involution on a finite set is an involution such as I(e)=e for none element of the set. In this article, the fixed-point free involutions are represented as partitions of the set and some properties linked to this representation are exhibited. Then an optimal algorithm to list all the fixed-point free involutions is presented. Its soundness relies on the representation of the fixed-point free involutions as partitions. Finally, an implementation of the algorithm is proposed, with an effective data representation.
Abelian Primitive Words
Venue: arXiv cs.FL 2010
Year: 2010

We investigate Abelian primitive words, which are words that are not Abelian powers. We show that unlike classical primitive words, the set of Abelian primitive words is not context-free. We can determine whether a word is Abelian primitive in linear time. Also different from classical primitive words, we find that a word may have more than one Abelian root. We also consider enumeration problems and the relation to the theory of codes.
Multi-Round Contention in Wireless LANs with Multipacket Reception
Venue: arXiv cs.NI 2010
Year: 2010

Multi-packet reception (MPR) has been recognized as a powerful capacity-enhancement technique for random-access wireless local area networks (WLANs). As is common with all random access protocols, the wireless channel is often under-utilized in MPR WLANs. In this paper, we propose a novel multi-round contention random-access protocol to address this problem. This work complements the existing random-access methods that are based on single-round contention. In the proposed scheme, stations are given multiple chances to contend for the channel until there are a sufficient number of ``winning" stations that can share the MPR channel for data packet transmission. The key issue here is the identification of the optimal time to stop the contention process and start data transmission. The solution corresponds to finding a desired tradeoff between channel utilization and contention overhead. In this paper, we conduct a rigorous analysis to characterize the optimal strategy using the theory of optimal stopping. An interesting result is that the optimal stopping strategy is a simple threshold-based rule, which stops the contention process as soon as the total number of winning stations exceeds a certain threshold. Compared with the conventional single-round contention protocol, the multi-round contention scheme significantly enhances channel utilization when the MPR capability of the channel is small to medium. Meanwhile, the scheme automatically falls back to single-round contention when the MPR capability is very large, in which case the throughput penalty due to random access is already small even with single-round contention.
Polar codes for the two-user multiple-access channel
Venue: arXiv cs.IT 2010
Year: 2010

Arikan's polar coding method is extended to two-user multiple-access channels. It is shown that if the two users of the channel use the Arikan construction, the resulting channels will polarize to one of five possible extremals, on each of which uncoded transmission is optimal. The sum rate achieved by this coding technique is the one that correponds to uniform input distributions. The encoding and decoding complexities and the error performance of these codes are as in the single-user case: $O(n\log n)$ for encoding and decoding, and $o(\exp(-n^{1/2-ε}))$ for block error probability, where $n$ is the block length.
Two-dimensional ranking of Wikipedia articles
Venue: arXiv cs.IR 2010
Year: 2010

The Library of Babel, described by Jorge Luis Borges, stores an enormous amount of information. The Library exists {\it ab aeterno}. Wikipedia, a free online encyclopaedia, becomes a modern analogue of such a Library. Information retrieval and ranking of Wikipedia articles become the challenge of modern society. While PageRank highlights very well known nodes with many ingoing links, CheiRank highlights very communicative nodes with many outgoing links. In this way the ranking becomes two-dimensional. Using CheiRank and PageRank we analyze the properties of two-dimensional ranking of all Wikipedia English articles and show that it gives their reliable classification with rich and nontrivial features. Detailed studies are done for countries, universities, personalities, physicists, chess players, Dow-Jones companies and other categories.
Stationary and Mobile Target Detection using Mobile Wireless Sensor Networks
Venue: arXiv cs.NI 2010
Year: 2010

In this work, we study the target detection and tracking problem in mobile sensor networks, where the performance metrics of interest are probability of detection and tracking coverage, when the target can be stationary or mobile and its duration is finite. We propose a physical coverage-based mobility model, where the mobile sensor nodes move such that the overlap between the covered areas by different mobile nodes is small. It is shown that for stationary target scenario the proposed mobility model can achieve a desired detection probability with a significantly lower number of mobile nodes especially when the detection requirements are highly stringent. Similarly, when the target is mobile the coverage-based mobility model produces a consistently higher detection probability compared to other models under investigation.
sTeX+ - a System for Flexible Formalization of Linked Data
Venue: arXiv cs.SE 2010
Year: 2010

We present the sTeX+ system, a user-driven advancement of sTeX - a semantic extension of LaTeX that allows for producing high-quality PDF documents for (proof)reading and printing, as well as semantic XML/OMDoc documents for the Web or further processing. Originally sTeX had been created as an invasive, semantic frontend for authoring XML documents. Here, we used sTeX in a Software Engineering case study as a formalization tool. In order to deal with modular pre-semantic vocabularies and relations, we upgraded it to sTeX+ in a participatory design process. We present a tool chain that starts with an sTeX+ editor and ultimately serves the generated documents as XHTML+RDFa Linked Data via an OMDoc-enabled, versioned XML database. In the final output, all structural annotations are preserved in order to enable semantic information retrieval services.
Can Realistic BitTorrent Experiments Be Performed on Clusters?
Venue: arXiv cs.NI 2010
Year: 2010

Network latency and packet loss are considered to be an important requirement for realistic evaluation of Peer-to-Peer protocols. Dedicated clusters, such as Grid'5000, do not provide the variety of network latency and packet loss rates that can be found in the Internet. However, compared to the experiments performed on testbeds such as PlanetLab, the experiments performed on dedicated clusters are reproducible, as the computational resources are not shared. In this paper, we perform experiments to study the impact of network latency and packet loss on the time required to download a file using BitTorrent. In our experiments, we observe a less than 15% increase on the time required to download a file when we increase the round-trip time between any two peers, from 0 ms to 400 ms, and the packet loss rate, from 0% to 5%. Our main conclusion is that the underlying network latency and packet loss have a marginal impact on the time required to download a file using BitTorrent. Hence, dedicated clusters such as Grid'5000 can be safely used to perform realistic and reproducible BitTorrent experiments.
Computational Analysis of .NET Remoting and Mobile agent in Distributed Environment
Venue: arXiv cs.NI 2010
Year: 2010

A mobile agent is a program that is not bound to the system on which it began execution, but rather travels amongst the hosts in the network with its code and current execution state (i.e. Distributed Environment).The implementation of distributed applications can be based on a multiplicity of technologies, e.g. plain sockets, Remote Procedure Call (RPC), Remote Method Invocation (RMI), Java Message Service (JMS), .NET Remoting, or Web Services. These technologies differ widely in complexity, interoperability, standardization, and ease of use. The Mobile Agent technology is emerging as an alternative to build a smart generation of highly distributed systems. In this work, we investigate the performance aspect of agent-based technologies for information retrieval. We present a comparative performance evaluation model of Mobile Agents versus .Net remoting by means of an analytical approach. A quantitative measurements are performed to compare .Net remoting and mobile agents using communication time, code size (agent code), Data size, number of node as performance parameters in this research work. The results depict that Mobile Agent paradigm offers a superior performance compared to .Net remoting paradigm, offers fast computational speed; procure lower invocation cost by making local invocations instead of remote invocations over the network, thereby reducing network bandwidth.
Engineering Semantic Web Applications by Using Object-Oriented Paradigm
Venue: arXiv cs.SE 2010
Year: 2010

The web information resources are growing explosively in number and volume. Now to retrieve relevant data from web has become very difficult and time-consuming. Semantic Web envisions that these web resources should be developed in machine-processable way in order to handle irrelevancy and manual processing problems. Whereas, the Semantic Web is an extension of current web, in which web resources are equipped with formal semantics about their interpretation through machines. These web resources are usually contained in web applications and systems, and their formal semantics are normally represented in the form of web-ontologies. In this research paper, an object-oriented design methodology (OODM) is upgraded for developing semantic web applications. OODM has been developed for designing of web applications for the current web. This methodology is good enough to develop web applications. It also provides a systematic approach for the web applications development but it is not helpful in generating machine-pocessable content of web applications in their development. Therefore, this methodology needs to be extended. In this paper, we propose that extension in OODM. This new extended version is referred to as the semantic web object-oriented design methodology (SW-OODM).
Understanding Semantic Web and Ontologies: Theory and Applications
Venue: arXiv cs.AI 2010
Year: 2010

Semantic Web is actually an extension of the current one in that it represents information more meaningfully for humans and computers alike. It enables the description of contents and services in machine-readable form, and enables annotating, discovering, publishing, advertising and composing services to be automated. It was developed based on Ontology, which is considered as the backbone of the Semantic Web. In other words, the current Web is transformed from being machine-readable to machine-understandable. In fact, Ontology is a key technique with which to annotate semantics and provide a common, comprehensible foundation for resources on the Semantic Web. Moreover, Ontology can provide a common vocabulary, a grammar for publishing data, and can supply a semantic description of data which can be used to preserve the Ontologies and keep them ready for inference. This paper provides basic concepts of web services and the Semantic Web, defines the structure and the main applications of ontology, and provides many relevant terms are explained in order to provide a basic understanding of ontologies.
SPOT: An R Package For Automatic and Interactive Tuning of Optimization Algorithms by Sequential Parameter Optimization
Venue: arXiv cs.NE 2010
Year: 2010

The sequential parameter optimization (SPOT) package for R is a toolbox for tuning and understanding simulation and optimization algorithms. Model-based investigations are common approaches in simulation and optimization. Sequential parameter optimization has been developed, because there is a strong need for sound statistical analysis of simulation and optimization algorithms. SPOT includes methods for tuning based on classical regression and analysis of variance techniques; tree-based models such as CART and random forest; Gaussian process models (Kriging), and combinations of different meta-modeling approaches. This article exemplifies how SPOT can be used for automatic and interactive tuning.
MINLIP for the Identification of Monotone Wiener Systems
Venue: arXiv cs.LG 2010
Year: 2010

This paper studies the MINLIP estimator for the identification of Wiener systems consisting of a sequence of a linear FIR dynamical model, and a monotonically increasing (or decreasing) static function. Given $T$ observations, this algorithm boils down to solving a convex quadratic program with $O(T)$ variables and inequality constraints, implementing an inference technique which is based entirely on model complexity control. The resulting estimates of the linear submodel are found to be almost consistent when no noise is present in the data, under a condition of smoothness of the true nonlinearity and local Persistency of Excitation (local PE) of the data. This result is novel as it does not rely on classical tools as a 'linearization' using a Taylor decomposition, nor exploits stochastic properties of the data. It is indicated how to extend the method to cope with noisy data, and empirical evidence contrasts performance of the estimator against other recently proposed techniques.
A Generic Storage API
Venue: arXiv cs.DB 2010
Year: 2010

We present a generic API suitable for provision of highly generic storage facilities that can be tailored to produce various individually customised storage infrastructures. The paper identifies a candidate set of minimal storage system building blocks, which are sufficiently simple to avoid encapsulating policy where it cannot be customised by applications, and composable to build highly flexible storage architectures. Four main generic components are defined: the store, the namer, the caster and the interpreter. It is hypothesised that these are sufficiently general that they could act as building blocks for any information storage and retrieval system. The essential characteristics of each are defined by an interface, which may be implemented by multiple implementing classes.
Detecting Danger: The Dendritic Cell Algorithm
Venue: arXiv cs.AI 2010
Year: 2010

The Dendritic Cell Algorithm (DCA) is inspired by the function of the dendritic cells of the human immune system. In nature, dendritic cells are the intrusion detection agents of the human body, policing the tissue and organs for potential invaders in the form of pathogens. In this research, and abstract model of DC behaviour is developed and subsequently used to form an algorithm, the DCA. The abstraction process was facilitated through close collaboration with laboratory- based immunologists, who performed bespoke experiments, the results of which are used as an integral part of this algorithm. The DCA is a population based algorithm, with each agent in the system represented as an 'artificial DC'. Each DC has the ability to combine multiple data streams and can add context to data suspected as anomalous. In this chapter the abstraction process and details of the resultant algorithm are given. The algorithm is applied to numerous intrusion detection problems in computer security including the detection of port scans and botnets, where it has produced impressive results with relatively low rates of false positives.
GroupLiNGAM: Linear non-Gaussian acyclic models for sets of variables
Venue: arXiv cs.AI 2010
Year: 2010

Finding the structure of a graphical model has been received much attention in many fields. Recently, it is reported that the non-Gaussianity of data enables us to identify the structure of a directed acyclic graph without any prior knowledge on the structure. In this paper, we propose a novel non-Gaussianity based algorithm for more general type of models; chain graphs. The algorithm finds an ordering of the disjoint subsets of variables by iteratively evaluating the independence between the variable subset and the residuals when the remaining variables are regressed on those. However, its computational cost grows exponentially according to the number of variables. Therefore, we further discuss an efficient approximate approach for applying the algorithm to large sized graphs. We illustrate the algorithm with artificial and real-world datasets.
Power Allocation Strategies across N Orthogonal Channels at Both Source and Relay
Venue: arXiv cs.IT 2010
Year: 2010

We consider a wireless relay network with one source, one relay and one destination, where communications between nodes are preformed via N orthogonal channels. This, for example, is the case when orthogonal frequency division multiplexing is employed for data communications. Since the power available at the source and relay is limited, we study optimal power allocation strategies at the source and relay in order to maximize the overall source-destination capacity under individual power constraints at the source and/or the relay. Depending on the availability of the channel state information at the source and rely, optimal power allocation strategies are performed at both the source and relay or only at the relay. Considering different setups for the problem, various optimization problems are formulated and solved. Some properties of the optimal solution are also proved.
Mining Top-K Frequent Itemsets Through Progressive Sampling
Venue: arXiv cs.DS 2010
Year: 2010

We study the use of sampling for efficiently mining the top-K frequent itemsets of cardinality at most w. To this purpose, we define an approximation to the top-K frequent itemsets to be a family of itemsets which includes (resp., excludes) all very frequent (resp., very infrequent) itemsets, together with an estimate of these itemsets' frequencies with a bounded error. Our first result is an upper bound on the sample size which guarantees that the top-K frequent itemsets mined from a random sample of that size approximate the actual top-K frequent itemsets, with probability larger than a specified value. We show that the upper bound is asymptotically tight when w is constant. Our main algorithmic contribution is a progressive sampling approach, combined with suitable stopping conditions, which on appropriate inputs is able to extract approximate top-K frequent itemsets from samples whose sizes are smaller than the general upper bound. In order to test the stopping conditions, this approach maintains the frequency of all itemsets encountered, which is practical only for small w. However, we show how this problem can be mitigated by using a variation of Bloom filters. A number of experiments conducted on both synthetic and real bench- mark datasets show that using samples substantially smaller than the original dataset (i.e., of size defined by the upper bound or reached through the progressive sampling approach) enable to approximate the actual top-K frequent itemsets with accuracy much higher than what analytically proved.
Data Stream Clustering: Challenges and Issues
Venue: arXiv cs.DB 2010
Year: 2010

Very large databases are required to store massive amounts of data that are continuously inserted and queried. Analyzing huge data sets and extracting valuable pattern in many applications are interesting for researchers. We can identify two main groups of techniques for huge data bases mining. One group refers to streaming data and applies mining techniques whereas second group attempts to solve this problem directly with efficient algorithms. Recently many researchers have focused on data stream as an efficient strategy against huge data base mining instead of mining on entire data base. The main problem in data stream mining means evolving data is more difficult to detect in this techniques therefore unsupervised methods should be applied. However, clustering techniques can lead us to discover hidden information. In this survey, we try to clarify: first, the different problem definitions related to data stream clustering in general; second, the specific difficulties encountered in this field of research; third, the varying assumptions, heuristics, and intuitions forming the basis of different approaches; and how several prominent solutions tackle different problems. Index Terms- Data Stream, Clustering, K-Means, Concept drift
Static and Dynamic Quality Assurance by Aspect Oriented Techniques
Venue: arXiv cs.SE 2010
Year: 2010

The overall goal of the described research project was to create applicable quality assurance patterns for Java software systems using the aspect-oriented programming language extension AspectJ 5. We tried to develop aspects to check static quality criteria as a variable mutator convention and architectural layering rules. We successfully developed aspects for automating the following dynamic quality criteria: Parameterized Exception Chaining, Comfortable Declaration of Parameterized Exceptions, Not-Null Checking of Reference Variables.
Domain Representable Spaces Defined by Strictly Positive Induction
Venue: arXiv cs.LO 2010
Year: 2010

Recursive domain equations have natural solutions. In particular there are domains defined by strictly positive induction. The class of countably based domains gives a computability theory for possibly non-countably based topological spaces. A $ qcb_{0} $ space is a topological space characterized by its strong representability over domains. In this paper, we study strictly positive inductive definitions for $ qcb_{0} $ spaces by means of domain representations, i.e. we show that there exists a canonical fixed point of every strictly positive operation on $qcb_{0} $ spaces.