OpenRaiser/Intern-Atlas huggingface dataset:
An Uncertainty Principle for Discrete Signals
Venue: arXiv cs.IT 2013
Year: 2013

By use of window functions, time-frequency analysis tools like Short Time Fourier Transform overcome a shortcoming of the Fourier Transform and enable us to study the time- frequency characteristics of signals which exhibit transient os- cillatory behavior. Since the resulting representations depend on the choice of the window functions, it is important to know how they influence the analyses. One crucial question on a window function is how accurate it permits us to analyze the signals in the time and frequency domains. In the continuous domain (for functions defined on the real line), the limit on the accuracy is well-established by the Heisenberg's uncertainty principle when the time-frequency spread is measured in terms of the variance measures. However, for the finite discrete signals (where we consider the Discrete Fourier Transform), the uncertainty relation is not as well understood. Our work fills in some of the gap in the understanding and states uncertainty relation for a subclass of finite discrete signals. Interestingly, the result is a close parallel to that of the continuous domain: the time-frequency spread measure is, in some sense, natural generalization of the variance measure in the continuous domain, the lower bound for the uncertainty is close to that of the continuous domain, and the lower bound is achieved approximately by the 'discrete Gaussians'.
AliBI: An Alignment-Based Index for Genomic Datasets
Venue: arXiv cs.DS 2013
Year: 2013

With current hardware and software, a standard computer can now hold in RAM an index for approximate pattern matching on about half a dozen human genomes. Sequencing technologies have improved so quickly, however, that scientists will soon demand indexes for thousands of genomes. Whereas most researchers who have addressed this problem have proposed completely new kinds of indexes, we recently described a simple technique that scales standard indexes to work on more genomes. Our main idea was to filter the dataset with LZ77, build a standard index for the filtered file, and then create a hybrid of that standard index and an LZ77-based index. In this paper we describe how to our technique to use alignments instead of LZ77, in order to simplify and speed up both preprocessing and random access.
Rigid Body Localization Using Sensor Networks: Position and Orientation Estimation
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we propose a novel framework called rigid body localization for joint position and orientation estimation of a rigid body. We consider a setup in which a few sensors are mounted on a rigid body. The absolute position of the sensors on the rigid body, or the absolute position of the rigid body itself is not known. However, we know how the sensors are mounted on the rigid body, i.e., the sensor topology is known. Using range-only measurements between the sensors and a few anchors (nodes with known absolute positions), and without using any inertial measurements (e.g., accelerometers), we estimate the position and orientation of the rigid body. For this purpose, the absolute position of the sensors is expressed as an affine function of the Stiefel manifold. In other words, we represent the orientation as a rotation matrix, and absolute position as a translation vector. We propose a least-squares (LS), simplified unitarily constrained LS (SUC-LS), and optimal unitarily constrained least-squares (OUC-LS) estimator, where the latter is based on Newton's method. As a benchmark, we derive a unitarily constrained Cramér-Rao bound (UC-CRB). The known topology of the sensors can sometimes be perturbed during fabrication. To take these perturbations into account, a simplified unitarily constrained total-least-squares (SUC-TLS), and an optimal unitarily constrained total-least-squares (OUC-TLS) estimator are also proposed.
Veni Vidi Vici, A Three-Phase Scenario For Parameter Space Analysis in Image Analysis and Visualization
Venue: arXiv cs.CV 2013
Year: 2013

Automatic analysis of the enormous sets of images is a critical task in life sciences. This faces many challenges such as: algorithms are highly parameterized, significant human input is intertwined, and lacking a standard meta-visualization approach. This paper proposes an alternative iterative approach for optimizing input parameters, saving time by minimizing the user involvement, and allowing for understanding the workflow of algorithms and discovering new ones. The main focus is on developing an interactive visualization technique that enables users to analyze the relationships between sampled input parameters and corresponding output. This technique is implemented as a prototype called Veni Vidi Vici, or "I came, I saw, I conquered." This strategy is inspired by the mathematical formulas of numbering computable functions and is developed atop ImageJ, a scientific image processing program. A case study is presented to investigate the proposed framework. Finally, the paper explores some potential future issues in the application of the proposed approach in parameter space analysis in visualization.
Making Laplacians commute
Venue: arXiv cs.CV 2013
Year: 2013

In this paper, we construct multimodal spectral geometry by finding a pair of closest commuting operators (CCO) to a given pair of Laplacians. The CCOs are jointly diagonalizable and hence have the same eigenbasis. Our construction naturally extends classical data analysis tools based on spectral geometry, such as diffusion maps and spectral clustering. We provide several synthetic and real examples of applications in dimensionality reduction, shape analysis, and clustering, demonstrating that our method better captures the inherent structure of multi-modal data.
Compression for Quadratic Similarity Queries
Venue: arXiv cs.IT 2013
Year: 2013

The problem of performing similarity queries on compressed data is considered. We focus on the quadratic similarity measure, and study the fundamental tradeoff between compression rate, sequence length, and reliability of queries performed on compressed data. For a Gaussian source, we show that queries can be answered reliably if and only if the compression rate exceeds a given threshold - the identification rate - which we explicitly characterize. Moreover, when compression is performed at a rate greater than the identification rate, responses to queries on the compressed data can be made exponentially reliable. We give a complete characterization of this exponent, which is analogous to the error and excess-distortion exponents in channel and source coding, respectively. For a general source we prove that, as with classical compression, the Gaussian source requires the largest compression rate among sources with a given variance. Moreover, a robust scheme is described that attains this maximal rate for any source distribution.
Priority-aware Gray-box Placement of Virtual Machines in Cloud Platforms
Venue: arXiv cs.NI 2013
Year: 2013

Virtual machine (VM) placement is very important for cloud platforms. While techniques, such as live virtual machine migration, are very useful to balance the load in the data centers, they are expensive operations. In this position paper, we propose to minimize the chance of the load hot spots in the data center by applying the workload patterns of the VMs in the virtual machine placement algorithms - place VMs that require a lot of same type of resource across different physical servers. In this way, the resource competition of VMs on the same physical server is significantly mitigated. Meanwhile, we also consider the priorities of applications and VMs in our virtual machine placement algorithms.
Applied Similarity Problems Using Frechet Distance
Venue: arXiv cs.CG 2013
Year: 2013

In the first part of this thesis, we consider an instance of Frechet distance problem in which the speed of traversal along each segment of the curves is restricted to be within a specfied range. This setting is more realistic than the classical Frechet distance setting, specially in GIS applications. We also study this problem in the setting where the polygonal curves are inside a simple polygon. In the second part of this thesis, we present a data structure, called the free-space map, that enables us to solve several variants of the Frechet distance problem efficiently. Our data structure encapsulates all the information available in the free-space diagram, yet it is capable of answering more general type of queries efficiently. Given that the free-space map has the same size and construction time as the standard free-space diagram, it can be viewed as a powerful alternative to it. As part of the results in Part II of the thesis, we exploit the free-space map to improve the long-standing bound for computing the partial Frechet distance and obtain improved algorithms for computing the Frechet distance between two closed curves, and the so-called minimum/maximum walk problem. We also improve the map matching algorithm for the case when the map is a directed acyclic graph. As the last part of this thesis, given a point set S and a polygonal curve P in R^d, we study the problem of finding a polygonal curve Q through S, which has a minimum Frechet distance to P. Furthermore, if the problem requires that curve Q visits every point in S, we show it is NP-complete.
Supporting 64-bit global indices in Epetra and other Trilinos packages -- Techniques used and lessons learned
Venue: arXiv cs.MS 2013
Year: 2013

The Trilinos Project is an effort to facilitate the design, development, integration and ongoing support of mathematical software libraries within an object-oriented framework. It is intended for large-scale, complex multiphysics engineering and scientific applications. Epetra is one of its basic packages. It provides serial and parallel linear algebra capabilities. Before Trilinos version 11.0, released in 2012, Epetra used the C++ int data-type for storing global and local indices for degrees of freedom (DOFs). Since int is typically 32-bit, this limited the largest problem size to be smaller than approximately two billion DOFs. This was true even if a distributed memory machine could handle larger problems. We have added optional support for C++ long long data-type, which is at least 64-bit wide, for global indices. To save memory, maintain the speed of memory-bound operations, and reduce further changes to the code, the local indices are still 32-bit. We document the changes required to achieve this feature and how the new functionality can be used. We also report on the lessons learned in modifying a mature and popular package from various perspectives -- design goals, backward compatibility, engineering decisions, C++ language features, effects on existing users and other packages, and build integration.
Research Excellence Milestones of BRIC and N-11 Countries
Venue: arXiv cs.DL 2013
Year: 2013

While scientific performance is an important aspect of a stable and healthy economy, measures for it have yet to gain their place in economic country profiles. As useful indicators for this performance dimension, this paper introduces the concept of milestones for research excellence, as points of transition to higher-level contributions at the leading edge of science. The proposed milestones are based on two indicators associated with research excellence, the impact vitality profile and the production of review type publications, both applied to a country's publications in the top journals Nature and Science. The milestones are determined for two distinct groups of emerging market economies: the BRIC countries, which outperformed the relative growth expected at their identification in 2001, and the N-11 or Next Eleven countries, identified in 2005 as potential candidates for a BRIC-like evolution. Results show how these two groups at different economic levels can be clearly distinguished based on the research milestones, indicating a potential utility as parameters in an economic context.
Partition-based Field Normalization: An approach to highly specialized publication records
Venue: arXiv cs.DL 2013
Year: 2013

Field normalized citation rates are well-established indicators for research performance from the broadest aggregation levels such as countries, down to institutes and research teams. When applied to still more specialized publication sets at the level of individual scientists, also a more accurate delimitation is required of the reference domain that provides the expectations to which a performance is compared. This necessity for sharper accuracy challenges standard methodology based on predefined subject categories. This paper proposes a way to define a reference domain that is more strongly delimited than in standard methodology, by building it up out of cells of the partition created by the pre-defined subject categories and their intersections. This partition approach can be applied to different existing field normalization variants. The resulting reference domain lies between those generated by standard field normalization and journal normalization. Examples based on fictive and real publication records illustrate how the potential impact on results can exceed or be smaller than the effect of other currently debated normalization variants, depending on the case studied. The proposed Partition-based Field Normalization is expected to offer advantages in particular at the level of individual scientists and other very specific publication records, such as publication output from interdisciplinary research.
Performance Comparison of Reed Solomon Code and BCH Code over Rayleigh Fading Channel
Venue: arXiv cs.IT 2013
Year: 2013

Data transmission over a communication channel is prone to a number of factors that can render the data unreliable or inconsistent by introducing noise, crosstalk or various other disturbances. A mechanism has to be in place that detects these anomalies in the received data and corrects it to get the data back as it was meant to be sent by the sender. Over the years a number of error detection and correction methodologies have been devised to send and receive the data in a consistent and correct form. The best of these methodologies ensure that the data is received correctly by the receiver in minimum number of retransmissions. In this paper performance of Reed Solomon Code (RS) and BCH Code is compared over Rayleigh fading channel.
Optimal Random Matchings, Tours, and Spanning Trees in Hierarchically Separated Trees
Venue: arXiv cs.DM 2013
Year: 2013

We derive tight bounds on the expected weights of several combinatorial optimization problems for random point sets of size $n$ distributed among the leaves of a balanced hierarchically separated tree. We consider {\it monochromatic} and {\it bichromatic} versions of the minimum matching, minimum spanning tree, and traveling salesman problems. We also present tight concentration results for the monochromatic problems.
Performance study and simulation of an anycast protocol for wireless mobile ad hoc networks
Venue: arXiv cs.NI 2013
Year: 2013

This paper conducts a detailed simulation study of stateless anycast routing in a mobile wireless ad hoc network. The model covers all the fundamental aspects of such networks with a routing mechanism using a scheme of orientation-dependent inter-node communication links. The simulation system Winsim is used which explicitly represents parallelism of events and processes in the network. The purpose of these simulations is to investigate the effect of node s maximum speed, and different TTL over the network performance under two different scenarios. Simulation study investigates five practically important performance metrics of a wireless mobile ad hoc network and shows the dependence of this metrics on the transmission radius, link availability, and maximal possible node speed.
Towards a Better Understanding of Multi-User Cooperation: A Tradeoff between Transmission Reliability and Rate
Venue: arXiv cs.IT 2013
Year: 2013

This paper provides a review of recent advances in multi-user cooperative data transmission. The focus is on the inherent trade-off between achievable throughput and reliability of cooperative transmission. Research has shown that under a fixed transmit energy budget, increased cooperation doesn't necessarily lead to increased reliability. In fact, careful cooperation partner selection and power allocation is needed in order to fully exploit the benefits of cooperative transmission. Furthermore, depending on the multi-media content, different cooperation strategies may need to be considered.
Machine-Readable Privacy Certificates for Services
Venue: arXiv cs.CR 2013
Year: 2013

Privacy-aware processing of personal data on the web of services requires managing a number of issues arising both from the technical and the legal domain. Several approaches have been proposed to matching privacy requirements (on the clients side) and privacy guarantees (on the service provider side). Still, the assurance of effective data protection (when possible) relies on substantial human effort and exposes organizations to significant (non-)compliance risks. In this paper we put forward the idea that a privacy certification scheme producing and managing machine-readable artifacts in the form of privacy certificates can play an important role towards the solution of this problem. Digital privacy certificates represent the reasons why a privacy property holds for a service and describe the privacy measures supporting it. Also, privacy certificates can be used to automatically select services whose certificates match the client policies (privacy requirements). Our proposal relies on an evolution of the conceptual model developed in the Assert4Soa project and on a certificate format specifically tailored to represent privacy properties. To validate our approach, we present a worked-out instance showing how privacy property Retention-based unlinkability can be certified for a banking financial service.
Finite State Machine Synthesis for Evolutionary Hardware
Venue: arXiv cs.NE 2013
Year: 2013

This article considers application of genetic algorithms for finite machine synthesis. The resulting genetic finite state machines synthesis algorithm allows for creation of machines with less number of states and within shorter time. This makes it possible to use hardware-oriented genetic finite machines synthesis algorithm in autonomous systems on reconfigurable platforms.
AMCTD: Adaptive Mobility of Courier nodes in Threshold-optimized DBR Protocol for Underwater Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

In dense underwater sensor networks (UWSN), the major confronts are high error probability, incessant variation in topology of sensor nodes, and much energy consumption for data transmission. However, there are some remarkable applications of UWSN such as management of seabed and oil reservoirs, exploration of deep sea situation and prevention of aqueous disasters. In order to accomplish these applications, ignorance of the limitations of acoustic communications such as high delay and low bandwidth is not feasible. In this paper, we propose Adaptive mobility of Courier nodes in Threshold-optimized Depth-based routing (AMCTD), exploring the proficient amendments in depth threshold and implementing the optimal weight function to achieve longer network lifetime. We segregate our scheme in 3 major phases of weight updating, depth threshold variation and adaptive mobility of courier nodes. During data forwarding, we provide the framework for alterations in threshold to cope with the sparse condition of network. We ultimately perform detailed simulations to scrutinize the performance of our proposed scheme and its comparison with other two notable routing protocols in term of network lifetime and other essential parameters. The simulations results verify that our scheme performs better than the other techniques and near to optimal in the field of UWSN.
THE-FAME: THreshold based Energy-efficient FAtigue MEasurment for Wireless Body Area Sensor Networks using Multiple Sinks
Venue: arXiv cs.NI 2013
Year: 2013

Wireless Body Area Sensor Network (WBASN) is a technology employed mainly for patient health monitoring. New research is being done to take the technology to the next level i.e. player's fatigue monitoring in sports. Muscle fatigue is the main cause of player's performance degradation. This type of fatigue can be measured by sensing the accumulation of lactic acid in muscles. Excess of lactic acid makes muscles feel lethargic. Keeping this in mind we propose a protocol \underline{TH}reshold based \underline{E}nergy-efficient \underline{FA}tigue \underline{ME}asurement (THE-FAME) for soccer players using WBASN. In THE-FAME protocol, a composite parameter has been used that consists of a threshold parameter for lactic acid accumulation and a parameter for measuring distance covered by a particular player. When any parameters's value in this composite parameter shows an increase beyond threshold, the players is declared to be in a fatigue state. The size of battery and sensor should be very small for the sake of players' best performance. These sensor nodes, implanted inside player's body, are made energy efficient by using multiple sinks instead of a single sink. Matlab simulation results show the effectiveness of THE-FAME.
The Power of Mediation in an Extended El Farol Game
Venue: arXiv cs.GT 2013
Year: 2013

A mediator implements a correlated equilibrium when it proposes a strategy to each player confidentially such that the mediator's proposal is the best interest for every player to follow. In this paper, we present a mediator that implements the best correlated equilibrium for an extended El Farol game with symmetric players. The extended El Farol game we consider incorporates both negative and positive network effects. We study the degree to which this type of mediator can decrease the overall social cost. In particular, we give an exact characterization of Mediation Value (MV) and Enforcement Value (EV) for this game. MV is the ratio of the minimum social cost over all Nash equilibria to the minimum social cost over all mediators, and EV is the ratio of the minimum social cost over all mediators to the optimal social cost. This sort of exact characterization is uncommon for games with both kinds of network effects. An interesting outcome of our results is that both the MV and EV values can be unbounded for our game.
Fast Polar Decoders: Algorithm and Implementation
Venue: arXiv cs.AR 2013
Year: 2013

Polar codes provably achieve the symmetric capacity of a memoryless channel while having an explicit construction. This work aims to increase the throughput of polar decoder hardware by an order of magnitude relative to the state of the art successive-cancellation decoder. We present an algorithm, architecture, and FPGA implementation of a gigabit-per-second polar decoder.
Diffusion Least Mean P-Power Algorithms for Distributed Estimation in Alpha-Stable Noise Environments
Venue: arXiv cs.IT 2013
Year: 2013

We propose a diffusion least mean p-power (LMP) algorithm for distributed estimation in alpha stable noise environments, which is one of the widely used models that appears in various environments. Compared with the diffusion least mean squares (LMS) algorithm, better performance is obtained for the diffusion LMP methods when the noise is with alpha-stable distribution.