OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Data Storage with Minimum Storage Regenerating Codes - Exact and Functional Repair are Asymptotically Equally Efficient
Venue: arXiv cs.IT 2010
Year: 2010

We consider a set up where a file of size M is stored in n distributed storage nodes, using an (n,k) minimum storage regenerating (MSR) code, i.e., a maximum distance separable (MDS) code that also allows efficient exact-repair of any failed node. The problem of interest in this paper is to minimize the repair bandwidth B for exact regeneration of a single failed node, i.e., the minimum data to be downloaded by a new node to replace the failed node by its exact replica. Previous work has shown that a bandwidth of B=[M(n-1)]/[k(n-k)] is necessary and sufficient for functional (not exact) regeneration. It has also been shown that if k < = max(n/2, 3), then there is no extra cost of exact regeneration over functional regeneration. The practically relevant setting of low-redundancy, i.e., k/n>1/2 remains open for k>3 and it has been shown that there is an extra bandwidth cost for exact repair over functional repair in this case. In this work, we adopt into the distributed storage context an asymptotically optimal interference alignment scheme previously proposed by Cadambe and Jafar for large wireless interference networks. With this scheme we solve the problem of repair bandwidth minimization for (n,k) exact-MSR codes for all (n,k) values including the previously open case of k > \max(n/2,3). Our main result is that, for any (n,k), and sufficiently large file sizes, there is no extra cost of exact regeneration over functional regeneration in terms of the repair bandwidth per bit of regenerated data. More precisely, we show that in the limit as M approaches infinity, the ratio B/M = (n-1)/(k(n-k))$.
Segmented compressed sampling for analog-to-information conversion: Method and performance analysis
Venue: arXiv cs.IT 2010
Year: 2010

A new segmented compressed sampling method for analog-to-information conversion (AIC) is proposed. An analog signal measured by a number of parallel branches of mixers and integrators (BMIs), each characterized by a specific random sampling waveform, is first segmented in time into $M$ segments. Then the sub-samples collected on different segments and different BMIs are reused so that a larger number of samples than the number of BMIs is collected. This technique is shown to be equivalent to extending the measurement matrix, which consists of the BMI sampling waveforms, by adding new rows without actually increasing the number of BMIs. We prove that the extended measurement matrix satisfies the restricted isometry property with overwhelming probability if the original measurement matrix of BMI sampling waveforms satisfies it. We also show that the signal recovery performance can be improved significantly if our segmented AIC is used for sampling instead of the conventional AIC. Simulation results verify the effectiveness of the proposed segmented compressed sampling method and the validity of our theoretical studies.
Detecting DNS Tunnels Using Character Frequency Analysis
Venue: arXiv cs.CR 2010
Year: 2010

High-bandwidth covert channels pose significant risks to sensitive and proprietary information inside company networks. Domain Name System (DNS) tunnels provide a means to covertly infiltrate and exfiltrate large amounts of information passed network boundaries. This paper explores the possibility of detecting DNS tunnels by analyzing the unigram, bigram, and trigram character frequencies of domains in DNS queries and responses. It is empirically shown how domains follow Zipf's law in a similar pattern to natural languages, whereas tunneled traffic has more evenly distributed character frequencies. This approach allows tunnels to be detected across multiple domains, whereas previous methods typically concentrate on monitoring point to point systems. Anomalies are quickly discovered when tunneled traffic is compared to the character frequency fingerprint of legitimate domain traffic.
An approximate analytical (structural) superposition in terms of two, or more, "alfa"-circuits of the same topology: Pt. 2 - the "internal circuit mechanism"
Venue: arXiv cs.OH 2010
Year: 2010

This is the second part, after [1], of the research devoted to analysis of 1-ports composed of similar conductors ("f-circuits") described by the characteristic i = f(v) of a polynomial type. This analysis is performed by means of the power-law "alfa"-circuits" introduced in [2], for which f(v) ~ v^"alfa". The f-circuits are constructed from the "alfa"-circuits of the same topology, with the proper "alfa", so that the given topology is kept, and 'f' is an additive function of the connection. Explaining the situation described in detail in [1], we note and analyze a simple "circuit mechanism" that causes the difference between the input current of the f-circuit and the sum of the input currents of the f-circuits before the composition to be relatively small. The case of two degrees, f(v) = Dmv^m + Dnv^n, m unequal n, is treated in the main proofs. Some simulations are presented, and some boundaries for the error of the superposition are found. The cases of f(.) being a polynomial of the third or fourth degrees are finally briefly considered.
Understanding periodicity and regularity of nodal encounters in mobile networks: A spectral analysis
Venue: arXiv cs.NI 2010
Year: 2010

Study on human mobility is gaining increasing attention from the research community with its multiple applications to use in mobile networks, particularly for the purpose of message delivery in the Delay Tolerant Networks. To better understand the potential of mobile nodes as message relays, our study investigates the encounter pattern of mobile devices. Specifically, we examine the extensive network traces that reflect mobility of communication devices. We analyze the periodicity in encounter pattern by using power spectral analysis. Strong periodicity was observed among rarely encountering mobile nodes while the periodicity was weaker among frequently encountering nodes. Further, we present a method to search regularly encountering pairs and discuss the findings. To our knowledge, we are the first to analyze the periodicity of encounter pattern with large network traces, which is a critical basis for designing an efficient delivery scheme using mobile nodes.
Plagiarism Detection Using Graph-Based Representation
Venue: arXiv cs.OH 2010
Year: 2010

Plagiarism of material from the Internet is a widespread and growing problem. Several methods used to detect the plagiarism and similarity between the source document and suspected documents such as fingerprint based on character or n-gram. In this paper, we discussed a new method to detect the plagiarism based on graph representation; however, Preprocessing for each document is required such as breaking down the document into its constituent sentences. Segmentation of each sentence into separated terms and stop word removal. We build the graph by grouping each sentence terms in one node, the resulted nodes are connected to each other based on order of sentence within the document, all nodes in graph are also connected to top level node "Topic Signature". Topic signature node is formed by extracting the concepts of each sentence terms and grouping them in such node. The main advantage of the proposed method is the topic signature which is main entry for the graph is used as quick guide to the relevant nodes. which should be considered for the comparison between source documents and suspected one. We believe the proposed method can achieve a good performance in terms of effectiveness and efficiency.
Improving Supply Chain Coordination by Linking Dynamic Procurement Decision to Multi-Agent System
Venue: arXiv cs.MA 2010
Year: 2010

The Internet has changed the way business is conducted in many ways. For example, in the field of procurement, the possibility to directly interact with a trading partner has given rise to new mechanisms in the supply chain management. One such interactive dynamic procurement, which lets both buyer and seller software agents bid by potential buyer agents instead of static procurement by vendors. Dynamic procurement decision could provide the buying and selling channel to buyer, to avoid occurring condition that seller could not deliver on the contract promise. Using NYOP(Name Your Own Price) to be the core of dynamic procurement negotiation algorithm sets up multi-agent dynamic supply chain system, to present the DSINs(Dynamic Supply Chain Information Networks) by JADE, and to present the dynamic supply chain logistic simulation by eM-Plant. Finally, evaluating supply chain performance with supply chain performance metrics (such as bullwhip, fill rate), to be the reference of enterprise making deciding in the future.
An Efficient Watermarking Algorithm to Improve Payload and Robustness without Affecting Image Perceptual Quality
Venue: arXiv cs.CV 2010
Year: 2010

Capacity, Robustness, & Perceptual quality of watermark data are very important issues to be considered. A lot of research is going on to increase these parameters for watermarking of the digital images, as there is always a tradeoff among them. . In this paper an efficient watermarking algorithm to improve payload and robustness without affecting perceptual quality of image data based on DWT is discussed. The aim of the paper is to employ the nested watermarks in wavelet domain which increases the capacity and ultimately the robustness against attacks and selection of different scaling factor values for LL & HH bands and during embedding not to create the visible artifacts in the original image and therefore the original and watermarked image is similar.
Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus
Venue: arXiv cs.DM 2010
Year: 2010

In this paper, we show that for an $n$-vertex graph $G$ of genus $g$, the edge expansion of $G$ can be determined in time $n^{O(g^2)}$. We show that the same is true for various other similar measures of edge connectivity.
Rank Awareness in Joint Sparse Recovery
Venue: arXiv cs.IT 2010
Year: 2010

In this paper we revisit the sparse multiple measurement vector (MMV) problem where the aim is to recover a set of jointly sparse multichannel vectors from incomplete measurements. This problem has received increasing interest as an extension of the single channel sparse recovery problem which lies at the heart of the emerging field of compressed sensing. However the sparse approximation problem has origins which include links to the field of array signal processing where we find the inspiration for a new family of MMV algorithms based on the MUSIC algorithm. We highlight the role of the rank of the coefficient matrix X in determining the difficulty of the recovery problem. We derive the necessary and sufficient conditions for the uniqueness of the sparse MMV solution, which indicates that the larger the rank of X the less sparse X needs to be to ensure uniqueness. We also show that the larger the rank of X the less the computational effort required to solve the MMV problem through a combinatorial search. In the second part of the paper we consider practical suboptimal algorithms for solving the sparse MMV problem. We examine the rank awareness of popular algorithms such as SOMP and mixed norm minimization techniques and show them to be rank blind in terms of worst case analysis. We then consider a family of greedy algorithms that are rank aware. The simplest such algorithm is a discrete version of MUSIC and is guaranteed to recover the sparse vectors in the full rank MMV case under mild conditions. We extend this idea to develop a rank aware pursuit algorithm that naturally reduces to Order Recursive Matching Pursuit (ORMP) in the single measurement case and also provides guaranteed recovery in the full rank multi-measurement case. Numerical simulations demonstrate that the rank aware algorithms are significantly better than existing algorithms in dealing with multiple measurements.
Multiplication of sparse Laurent polynomials and Poisson series on modern hardware architectures
Venue: arXiv cs.SC 2010
Year: 2010

In this paper we present two algorithms for the multiplication of sparse Laurent polynomials and Poisson series (the latter being algebraic structures commonly arising in Celestial Mechanics from the application of perturbation theories). Both algorithms first employ the Kronecker substitution technique to reduce multivariate multiplication to univariate multiplication, and then use the schoolbook method to perform the univariate multiplication. The first algorithm, suitable for moderately-sparse multiplication, uses the exponents of the monomials resulting from the univariate multiplication as trivial hash values in a one dimensional lookup array of coefficients. The second algorithm, suitable for highly-sparse multiplication, uses a cache-optimised hash table which stores the coefficient-exponent pairs resulting from the multiplication using the exponents as keys. Both algorithms have been implemented with attention to modern computer hardware architectures. Particular care has been devoted to the efficient exploitation of contemporary memory hierarchies through cache-blocking techniques and cache-friendly term ordering. The first algorithm has been parallelised for shared-memory multicore architectures, whereas the second algorithm is in the process of being parallelised. We present benchmarks comparing our algorithms to the routines of other computer algebra systems, both in sequential and parallel mode.
Highway Mobility and Vehicular Ad-Hoc Networks in NS-3
Venue: arXiv cs.NI 2010
Year: 2010

The study of vehicular ad-hoc networks (VANETs) requires efficient and accurate simulation tools. As the mobility of vehicles and driver behavior can be affected by network messages, these tools must include a vehicle mobility model integrated with a quality network simulator. We present the first implementation of a well-known vehicle mobility model to ns-3, the next generation of the popular ns-2 networking simulator. Vehicle mobility and network communication are integrated through events. User-created event handlers can send network messages or alter vehicle mobility each time a network message is received and each time vehicle mobility is updated by the model. To aid in creating simulations, we have implemented a straight highway model that manages vehicle mobility, while allowing for various user customizations. We show that the results of our implementation of the mobility model matches that of the model's author and provide an example of using our implementation in ns-3.
Measuring Data and VoIP Traffic in WiMAX Networks
Venue: arXiv cs.NI 2010
Year: 2010

Due to its large coverage area, low cost of deployment and high speed data rates, WiMAX is a promising technology for providing wireless last-mile connectivity. Physical and MAC layer of this technology refer to the IEEE 802.16e standard, which defines 5 different data delivery service classes that can be used in order to satisfy Quality of Service (QoS) requirements of different applications, such as VoIP, videoconference, FTP, Web, etc. The main aim of the paper is to examine a case of QoS deployment over a cellular WiMAX network. In particular, the paper compares the performance obtained using two different QoS configurations differing from the delivery service class used to transport VoIP traffic, i.e. UGS or ertPS. Results indicate that for delay-sensitive traffic that fluctuates beyond its nominal rate, having the possibility to give back some of its reserved bandwidth, ertPS has the advantage to permit the transmission of BE traffic.
Investigation on QoS of Campus-wide WiFi Networks
Venue: arXiv cs.NI 2010
Year: 2010

WiFi is widely implemented in campus wide including administrative, teaching and student's accommodation. Wireless communications are associated with interconnect devices which includes cellular networks, infrared, bluetooth and WiFi enabled devices. It involves mobility and freedom of assessing information anytime and anywhere. A study on WiFi networks in a campus environment is presented in this paper. The aim of the research was to investigate the connectivity problems to WiFi networks. The study includes WiFi performance analysis as well as network auditing. Channel overlapping and saturation condition were some of the problems encountered. Different types of software were used for analyzing the results.
Modelling and Design of a Microstrip Band-Pass Filter Using Space Mapping Techniques
Venue: arXiv cs.OH 2010
Year: 2010

Determination of design parameters based on electromagnetic simulations of microwave circuits is an iterative and often time-consuming procedure. Space mapping is a powerful technique to optimize such complex models by efficiently substituting accurate but expensive electromagnetic models, fine models, with fast and approximate models, coarse models. In this paper, we apply two space mapping, an explicit space mapping as well as an implicit and response residual space mapping, techniques to a case study application, a microstrip band-pass filter. First, we model the case study application and optimize its design parameters, using explicit space mapping modelling approach. Then, we use implicit and response residual space mapping approach to optimize the filter's design parameters. Finally, the performance of each design methods is evaluated. It is shown that the use of above-mentioned techniques leads to achieving satisfactory design solutions with a minimum number of computationally expensive fine model evaluations.
Chunky and Equal-Spaced Polynomial Multiplication
Venue: arXiv cs.SC 2010
Year: 2010

Finding the product of two polynomials is an essential and basic problem in computer algebra. While most previous results have focused on the worst-case complexity, we instead employ the technique of adaptive analysis to give an improvement in many "easy" cases. We present two adaptive measures and methods for polynomial multiplication, and also show how to effectively combine them to gain both advantages. One useful feature of these algorithms is that they essentially provide a gradient between existing "sparse" and "dense" methods. We prove that these approaches provide significant improvements in many cases but in the worst case are still comparable to the fastest existing algorithms.
Relating L-Resilience and Wait-Freedom via Hitting Sets
Venue: arXiv cs.DC 2010
Year: 2010

The condition of t-resilience stipulates that an n-process program is only obliged to make progress when at least n-t processes are correct. Put another way, the live sets, the collection of process sets such that progress is required if all the processes in one of these sets are correct, are all sets with at least n-t processes. We show that the ability of arbitrary collection of live sets L to solve distributed tasks is tightly related to the minimum hitting set of L, a minimum cardinality subset of processes that has a non-empty intersection with every live set. Thus, finding the computing power of L is NP-complete. For the special case of colorless tasks that allow participating processes to adopt input or output values of each other, we use a simple simulation to show that a task can be solved L-resiliently if and only if it can be solved (h-1)-resiliently, where h is the size of the minimum hitting set of L. For general tasks, we characterize L-resilient solvability of tasks with respect to a limited notion of weak solvability: in every execution where all processes in some set in L are correct, outputs must be produced for every process in some (possibly different) participating set in L. Given a task T, we construct another task T_L such that T is solvable weakly L-resiliently if and only if T_L is solvable weakly wait-free.
Minimum energy required to copy one bit of information
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we calculate energy required to copy one bit of useful information in the presence of thermal noise. For this purpose, we consider a quantum system capable of storing one bit of classical information, which is initially in a mixed state corresponding to temperature T. We calculate how many of these systems must be used to store useful information and control bits protecting the content against transmission errors. Finally, we analyze how adding these extra bits changes the total energy consumed during the copying.
A Design of Paraunitary Polyphase Matrices of Rational Filter Banks Based on (P,Q) Shift-Invariant Systems
Venue: arXiv cs.IT 2010
Year: 2010

In this paper we present a method to design paraunitary polyphase matrices of critically sampled rational filter banks. The method is based on (P,Q) shift-invariant systems, and so any kind of rational splitting of the frequency spectrum can be achieved using this method. Ideal (P,Q) shift-invariant system with smallest P and Q that map of a band of input spectrum to the output spectrum are obtained. A new set of filters is obtained that characterize a (P,Q) shift-invariant system. Ideal frequency spectrum of these filters are obtained using ideal $(P,Q)$ shift-invariant systems. Actual paraunitary polyphase matrices are then obtained by minimizing the stopband energies of these filters against the parameters of the paraunitary polyphase matrices.
VAGO method for the solution of elliptic second-order boundary value problems
Venue: arXiv cs.NA 2010
Year: 2010

Mathematical physics problems are often formulated using differential oprators of vector analysis - invariant operators of first order, namely, divergence, gradient and rotor operators. In approximate solution of such problems it is natural to employ similar operator formulations for grid problems, too. The VAGO (Vector Analysis Grid Operators) method is based on such a methodology. In this paper the vector analysis difference operators are constructed using the Delaunay triangulation and the Voronoi diagrams. Further the VAGO method is used to solve approximately boundary value problems for the general elliptic equation of second order. In the convection-diffusion-reaction equation the diffusion coefficient is a symmetric tensor of second order.
Ontology-based inference for causal explanation
Venue: arXiv cs.AI 2010
Year: 2010

We define an inference system to capture explanations based on causal statements, using an ontology in the form of an IS-A hierarchy. We first introduce a simple logical language which makes it possible to express that a fact causes another fact and that a fact explains another fact. We present a set of formal inference patterns from causal statements to explanation statements. We introduce an elementary ontology which gives greater expressiveness to the system while staying close to propositional reasoning. We provide an inference system that captures the patterns discussed, firstly in a purely propositional framework, then in a datalog (limited predicate) framework.
Optimum Design of a 4x4 Planar Butler Matrix Array for WLAN Application
Venue: arXiv cs.NI 2010
Year: 2010

In recent years, high-speed wireless communication is in vogue. In wireless communication systems, multipath fading, delay and interference occurres by reflection or diffraction. In a high-speed wireless communication, it becomes a necessary to separate desired signal from delay or interference signal. Thus to overcome these problems Smart antenna systems have been developed. Basically there are two types of smart antenna systems, one is Switched beam system and another Adaptive array system.This paper presents the optimum design of a 4x4 plannar Butler matrix array as a key component of a switched beam smart antenna system, operating at 5.2 GHz for WLAN with a dielectric substrate, FR4 of er =4.9 and h=1.6mm. Conception details, simulation results and measurements are also given for the components (microstrip antenna, hybrid couplers, cross-coupler, phase shifter) used to implement the matrix. In this dissertation, mathematical calculations for all the components using MATLAB is done and then every individual component is designed using the commercial software SONNET. Then these entire components have been combined on a single substrate and simulated using SONNET.