OpenRaiser/Intern-Atlas huggingface dataset:
Parallel Sorting System for Objects
Venue: arXiv cs.DC 2012
Year: 2012

Conventional sorting algorithms make use of such data structures as array, file and list which define access methods of the items to be sorted. Such traditional methods as exchange sort, divide and conquer sort, selection sort and insertion sort require supervisory control program. The supervisory control program has access to the items and is responsible for arranging them in the proper order. This paper presents a different sorting algorithm that does not require supervisory control program. The objects sort themselves and they are able to terminate when sorting is completed. The algorithm also employs parallel processing mechanisms to increase its efficiency and effectiveness. The paper makes a review of the traditional sorting methods, identifying their pros and cons and proposes a different design based on conceptual combination of these algorithms. Algorithms designed were implemented and tested in Java desktop application
An Indoor Tracking System Based on Bluetooth Technology
Venue: arXiv cs.NI 2012
Year: 2012

Implementations of tracking systems have become prevalent issues in modern technology due to its advantage of location detection of objects. Objects are usually tracked using trackers based on GPS, GSM, RFID and Bluetooth signal strength implementation. These mechanisms usually require line of sight operations, limited coverage and low level programming language for accessing Bluetooth signal strength. This paper presents an alternative technique for tracking the movement of indoor objects based on Bluetooth communication technology, principles of motion and least square statistical method. Algorithms are designed and implemented using Java
Design and Implementation A different Architectures of mixcolumn in FPGA
Venue: arXiv cs.CR 2012
Year: 2012

This paper details Implementation of the Encryption algorithm AES under VHDL language In FPGA by using different architecture of mixcolumn. We then review this research investigates the AES algorithm in FPGA and the Very High Speed Integrated Circuit Hardware Description language (VHDL). Altera Quartus II software is used for simulation and optimization of the synthesizable VHDL code. The set of transformations of both Encryptions and decryption are simulated using an iterative design approach in order to optimize the hardware consumption. Altera Cyclone III Family devices are utilized for hardware evaluation.
Outage-based ergodic link adaptation for fading channels with delayed CSIT
Venue: arXiv cs.IT 2012
Year: 2012

Link adaptation in which the transmission data rate is dynamically adjusted according to channel variation is often used to deal with time-varying nature of wireless channel. When channel state information at the transmitter (CSIT) is delayed by more than channel coherence time due to feedback delay, however, the effect of link adaptation can possibly be taken away if this delay is not taken into account. One way to deal with such delay is to predict current channel quality given available observation, but this would inevitably result in prediction error. In this paper, an algorithm with different view point is proposed. By using conditional cdf of current channel given observation, outage probability can be computed for each value of transmission rate $R$. By assuming that the transmission block error rate (BLER) is dominated by outage probability, the expected throughput can also be computed, and $R$ can be determined to maximize it. The proposed scheme is designed to be optimal if channel has ergodicity, and it is shown to considerably outperform conventional schemes in certain Rayleigh fading channel model.
Further Optimal Regret Bounds for Thompson Sampling
Venue: arXiv cs.LG 2012
Year: 2012

Thompson Sampling is one of the oldest heuristics for multi-armed bandit problems. It is a randomized algorithm based on Bayesian ideas, and has recently generated significant interest after several studies demonstrated it to have better empirical performance compared to the state of the art methods. In this paper, we provide a novel regret analysis for Thompson Sampling that simultaneously proves both the optimal problem-dependent bound of $(1+ε)\sum_i \frac{\ln T}{Δ_i}+O(\frac{N}{ε^2})$ and the first near-optimal problem-independent bound of $O(\sqrt{NT\ln T})$ on the expected regret of this algorithm. Our near-optimal problem-independent bound solves a COLT 2012 open problem of Chapelle and Li. The optimal problem-dependent regret bound for this problem was first proven recently by Kaufmann et al. [ALT 2012]. Our novel martingale-based analysis techniques are conceptually simple, easily extend to distributions other than the Beta distribution, and also extend to the more general contextual bandits setting [Manuscript, Agrawal and Goyal, 2012].
Implement Blind Interference Alignment over Homogeneous 3-user 2x1 Broadcast Channel
Venue: arXiv cs.IT 2012
Year: 2012

This paper first studies the homogeneous 3-user 2x1 broadcast channel (BC) with no CSIT. We show a sufficient condition for it to achieve the optimal 3/2 degrees of freedom (DoF) by using Blind Interference Alignment (BIA). BIA refers to the interference alignment method without the need of CSIT. It further studies the 2x1 broadcast network in which there are K>=3 homogeneous single-antenna users, and their coherence time offsets are independently and uniformly distributed. We show that, if K>=11, the two-antenna transmitter can find, with more than 95% certainty, three users to form a BIA-feasible 3-user BC and achieve the optimal 3/2 DoF.
A framework for large-scale distributed AI search across disconnected heterogeneous infrastructures
Venue: arXiv cs.DC 2012
Year: 2012

We present a framework for a large-scale distributed eScience Artificial Intelligence search. Our approach is generic and can be used for many different problems. Unlike many other approaches, we do not require dedicated machines, homogeneous infrastructure or the ability to communicate between nodes. We give special consideration to the robustness of the framework, minimising the loss of effort even after total loss of infrastructure, and allowing easy verification of every step of the distribution process. In contrast to most eScience applications, the input data and specification of the problem is very small, being easily given in a paragraph of text. The unique challenges our framework tackles are related to the combinatorial explosion of the space that contains the possible solutions and the robustness of long-running computations. Not only is the time required to finish the computations unknown, but also the resource requirements may change during the course of the computation. We demonstrate the applicability of our framework by using it to solve a challenging and hitherto open problem in computational mathematics. The results demonstrate that our approach easily scales to computations of a size that would have been impossible to tackle in practice just a decade ago.
An FMM Based on Dual Tree Traversal for Many-core Architectures
Venue: arXiv cs.NA 2012
Year: 2012

The present work attempts to integrate the independent efforts in the fast N-body community to create the fastest N-body library for many-core and heterogenous architectures. Focus is placed on low accuracy optimizations, in response to the recent interest to use FMM as a preconditioner for sparse linear solvers. A direct comparison with other state-of-the-art fast N-body codes demonstrates that orders of magnitude increase in performance can be achieved by careful selection of the optimal algorithm and low-level optimization of the code. The current N-body solver uses a fast multipole method with an efficient strategy for finding the list of cell-cell interactions by a dual tree traversal. A task-based threading model is used to maximize thread-level parallelism and intra-node load-balancing. In order to extract the full potential of the SIMD units on the latest CPUs, the inner kernels are optimized using AVX instructions. Our code -- exaFMM -- is an order of magnitude faster than the current state-of-the-art FMM codes, which are themselves an order of magnitude faster than the average FMM code.
Eight-Fifth Approximation for TSP Paths
Venue: arXiv cs.DM 2012
Year: 2012

We prove the approximation ratio 8/5 for the metric $\{s,t\}$-path-TSP problem, and more generally for shortest connected $T$-joins. The algorithm that achieves this ratio is the simple "Best of Many" version of Christofides' algorithm (1976), suggested by An, Kleinberg and Shmoys (2012), which consists in determining the best Christofides $\{s,t\}$-tour out of those constructed from a family $\Fscr_{>0}$ of trees having a convex combination dominated by an optimal solution $x^*$ of the fractional relaxation. They give the approximation guarantee $\frac{\sqrt{5}+1}{2}$ for such an $\{s,t\}$-tour, which is the first improvement after the 5/3 guarantee of Hoogeveen's Christofides type algorithm (1991). Cheriyan, Friggstad and Gao (2012) extended this result to a 13/8-approximation of shortest connected $T$-joins, for $|T|\ge 4$. The ratio 8/5 is proved by simplifying and improving the approach of An, Kleinberg and Shmoys that consists in completing $x^*/2$ in order to dominate the cost of "parity correction" for spanning trees. We partition the edge-set of each spanning tree in $\Fscr_{>0}$ into an $\{s,t\}$-path (or more generally, into a $T$-join) and its complement, which induces a decomposition of $x^*$. This decomposition can be refined and then efficiently used to complete $x^*/2$ without using linear programming or particular properties of $T$, but by adding to each cut deficient for $x^*/2$ an individually tailored explicitly given vector, inherent in $x^*$. A simple example shows that the Best of Many Christofides algorithm may not find a shorter $\{s,t\}$-tour than 3/2 times the incidentally common optima of the problem and of its fractional relaxation.
logcf: An Efficient Tool for Real Root Isolation
Venue: arXiv cs.SC 2012
Year: 2012

This paper revisits an algorithm for isolating real roots of univariate polynomials based on continued fractions. It follows the work of Vincent, Uspen- sky, Collins and Akritas, Johnson and Krandick. We use some tricks, especially a new algorithm for computing an upper bound of positive roots. In this way, the algorithm of isolating real roots is improved. The complexity of our method for computing an upper bound of positive roots is O(n log(u+1)) where u is the optimal upper bound satisfying Theorem 3 and n is the degree of the polynomial. Our method has been implemented as a software package logcf using C++ language. For many benchmarks logcf is two or three times faster than the function RootIntervals of Mathematica. And it is much faster than another continued fractions based software CF, which seems to be one of the fastest available open software for exact real root isolation. For those benchmarks which have only real roots, logcf is much faster than Sleeve and eigensolve which are based on numerical computation.
Age-sensitive bibliographic coupling with an application in the history of science
Venue: arXiv cs.DL 2012
Year: 2012

In science mapping, bibliographic coupling (BC) has been a standard tool for discovering the cognitive structure of research areas, such as constituent subareas, directions, schools of thought, or paradigms. Modelled as a set of documents, research areas are often sorted into document clusters via BC representing a thematic unit each. In this paper we propose an alternative method called age-sensitive bibliographic coupling: the aim is to enable the standard method to produce historically valid thematic units, that is, to yield document clusters that represent the historical development of the thematic structure of the subject as well. As such, the method is expected to be especially beneficial for investigations on science dynamics and the history of science. We apply the method within a bibliometric study in the modern history of bioscience, addressing the development of a complex, interdisciplinary discourse called the Species Problem.
Improved in-place associative integer sorting
Venue: arXiv cs.DS 2012
Year: 2012

A novel integer sorting technique was proposed replacing bucket sort, distribution counting sort and address calculation sort family of algorithms which requires only constant amount of additional memory. The technique was inspired from one of the ordinal theories of "serial order in behavior" and explained by the analogy with the three main stages in the formation and retrieval of memory in cognitive neuroscience namely (i) practicing, (ii) storing and (iii) retrieval. In this study, the technique is improved both theoretically and practically and an algorithm is obtained which is faster than the former making it more competitive. With the improved version, n integers S[0...n-1] each in the range [0, n-1] are sorted exactly in O(n) time while the complexity of the former technique was the recursion T(n) = T(n/2) + O(n) yielding T(n) = O(n).
Incomplete Information in RDF
Venue: arXiv cs.DB 2012
Year: 2012

We extend RDF with the ability to represent property values that exist, but are unknown or partially known, using constraints. Following ideas from the incomplete information literature, we develop a semantics for this extension of RDF, called RDFi, and study SPARQL query evaluation in this framework.
Textual Features for Programming by Example
Venue: arXiv cs.AI 2012
Year: 2012

In Programming by Example, a system attempts to infer a program from input and output examples, generally by searching for a composition of certain base functions. Performing a naive brute force search is infeasible for even mildly involved tasks. We note that the examples themselves often present clues as to which functions to compose, and how to rank the resulting programs. In text processing, which is our domain of interest, clues arise from simple textual features: for example, if parts of the input and output strings are permutations of one another, this suggests that sorting may be useful. We describe a system that learns the reliability of such clues, allowing for faster search and a principled ranking over programs. Experiments on a prototype of this system show that this learning scheme facilitates efficient inference on a range of text processing tasks.
Performance Analysis of MIMO Radar Waveform using Accelerated Particle Swarm Optimization Algorithm
Venue: arXiv cs.OH 2012
Year: 2012

The Accelerated Particle Swarm Optimization Algorithm is promoted to numerically design orthogonal Discrete Frequency Waveforms and Modified Discrete Frequency Waveforms (DFCWs) with good correlation properties for MIMO radar. We employ Accelerated Particle Swarm Optimization algorithm (ACC_PSO), Particles of a swarm communicate good positions, velocity and accelerations to each other as well as dynamically adjust their own position, velocity and acceleration derived from the best of all particles. The simulation results show that the proposed algorithm is effective for the design of DFCWs signal used in MIMO radar.
Game Theoretic Formation of a Centrality Based Network
Venue: arXiv cs.GT 2012
Year: 2012

We model the formation of networks as a game where players aspire to maximize their own centrality by increasing the number of other players to which they are path-wise connected, while simultaneously incurring a cost for each added adjacent edge. We simulate the interactions between players using an algorithm that factors in rational strategic behavior based on a common objective function. The resulting networks exhibit pairwise stability, from which we derive necessary stable conditions for specific graph topologies. We then expand the model to simulate non-trivial games with large numbers of players. We show that using conditions necessary for the stability of star topologies we can induce the formation of hub players that positively impact the total welfare of the network.
Network Massive MIMO for Cell-Boundary Users: From a Precoding Normalization Perspective
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we propose network massive multiple- input multiple-output (MIMO) systems, where three radio units (RUs) connected via one digital unit (DU) support multiple user equipments (UEs) at a cell-boundary through the same radio resource, i.e., the same frequency/time band. For precoding designs, zero-forcing (ZF) and matched filter (MF) with vector or matrix normalization are considered. We also derive the formulae of the lower and upper bounds of the achievable sum rate for each precoding. Based on our analytical results, we observe that vector normalization is better for ZF while matrix normalization is better for MF. Given antenna configurations, we also derive the optimal switching point as a function of the number of active users in a network. Numerical simulations confirm our analytical
A Cramer-Rao Bound for Semi-Blind Channel Estimation in Redundant Block Transmission Systems
Venue: arXiv cs.IT 2012
Year: 2012

A Cramer-Rao bound (CRB) for semi-blind channel estimators in redundant block transmission systems is derived. The derived CRB is valid for any system adopting a full-rank linear redundant precoder, including the popular cyclic-prefixed orthogonal frequency-division multiplexing system. Simple forms of CRBs for multiple complex parameters, either unconstrained or constrained by a holomorphic function, are also derived, which facilitate the CRB derivation of the problem of interest. The derived CRB is a lower bound on the variance of any unbiased semi-blind channel estimator, and can serve as a tractable performance metric for system design.
Minimum Communication Cost for Joint Distributed Source Coding and Dispersive Information Routing
Venue: arXiv cs.IT 2012
Year: 2012

This paper considers the problem of minimum cost communication of correlated sources over a network with multiple sinks, which consists of distributed source coding followed by routing. We introduce a new routing paradigm called dispersive information routing, wherein the intermediate nodes are allowed to `split' a packet and forward subsets of the received bits on each of the forward paths. This paradigm opens up a rich class of research problems which focus on the interplay between encoding and routing in a network. Unlike conventional routing methods such as in [1], dispersive information routing ensures that each sink receives just the information needed to reconstruct the sources it is required to reproduce. We demonstrate using simple examples that our approach offers better asymptotic performance than conventional routing techniques. This paradigm leads to a new information theoretic setup, which has not been studied earlier. We propose a new coding scheme, using principles from multiple descriptions encoding [2] and Han and Kobayashi decoding [3]. We show that this coding scheme achieves the complete rate region for certain special cases of the general setup and thereby achieves the minimum communication cost under this routing paradigm.
A performance Analysis of the Game of Life based on parallel algorithm
Venue: arXiv cs.DC 2012
Year: 2012

In this article, Conway's Game of Life using OpenMP parallel processing to simulate several different parallel methods, experimental performance results and compare to find the optimal solution of the parallelization of the Game of Life. Finally pointed out the importance of the design of parallel algorithms in solving the parallel problem.
Head Frontal-View Identification Using Extended LLE
Venue: arXiv cs.CV 2012
Year: 2012

Automatic head frontal-view identification is challenging due to appearance variations caused by pose changes, especially without any training samples. In this paper, we present an unsupervised algorithm for identifying frontal view among multiple facial images under various yaw poses (derived from the same person). Our approach is based on Locally Linear Embedding (LLE), with the assumption that with yaw pose being the only variable, the facial images should lie in a smooth and low dimensional manifold. We horizontally flip the facial images and present two K-nearest neighbor protocols for the original images and the flipped images, respectively. In the proposed extended LLE, for any facial image (original or flipped one), we search (1) the Ko nearest neighbors among the original facial images and (2) the Kf nearest neighbors among the flipped facial images to construct the same neighborhood graph. The extended LLE eliminates the differences (because of background, face position and scale in the whole image and some asymmetry of left-right face) between the original facial image and the flipped facial image at the same yaw pose so that the flipped facial images can be used effectively. Our approach does not need any training samples as prior information. The experimental results show that the frontal view of head can be identified reliably around the lowest point of the pose manifold for multiple facial images, especially the cropped facial images (little background and centered face).
A Metric for the Activeness of a Distributed Object Oriented Component Library
Venue: arXiv cs.SE 2012
Year: 2012

This paper makes an attempt to analyze the Activeness of a Distributed Object Oriented Component Library and develops a software metric called Distributed Component Activeness Quotient which is defined as the degree of readiness of a DOOCL. The advantages of the DCAQ include a possible comparison between various DOOCLs leading to selection of the best DOOCL for use during the development task, and providing a measure for gauging the usefulness of the DOOCL as indicated by the value of the DCAQ. The disadvantage of the DCAQ is that it may have some error because of its subjective and random nature. The Stability of a DOOCL is another characteristic which is indicated by the DCAQ. The greater the value of the DCAQ, greater will be the stability of the corresponding DOOCL.
Minimum weight spanning trees of weighted scale free networks
Venue: arXiv cs.DS 2012
Year: 2012

In this lecture we will consider the minimum weight spanning tree (MST) problem, i.e., one of the simplest and most vital combinatorial optimization problems. We will discuss a particular greedy algorithm that allows to compute a MST for undirected weighted graphs, namely Kruskal's algorithm, and we will study the structure of MSTs obtained for weighted scale free random graphs. This is meant to clarify whether the structure of MSTs is sensitive to correlations between edge weights and topology of the underlying scale free graphs.
Classification Of Heterogeneous Operating System
Venue: arXiv cs.OS 2012
Year: 2012

Operating system is a bridge between system and user. An operating system (OS) is a software program that manages the hardware and software resources of a computer. The OS performs basic tasks, such as controlling and allocating memory, prioritizing the processing of instructions, controlling input and output devices, facilitating networking, and managing files. It is difficult to present a complete as well as deep account of operating systems developed till date. So, this paper tries to overview only a subset of the available operating systems and its different categories. OS are being developed by a large number of academic and commercial organizations for the last several decades. This paper, therefore, concentrates on the different categories of OS with special emphasis to those that had deep impact on the evolution process. The aim of this paper is to provide a brief timely commentary on the different categories important operating systems available today.