OpenRaiser/Intern-Atlas huggingface dataset:
Low Power Wideband Sensing for One-Bit Quantized Cognitive Radio Systems
Venue: arXiv cs.OH 2015
Year: 2015

We proposes an ultra low power wideband spectrum sensing architecture by utilizing a one-bit quantization at the cognitive radio (CR) receiver. The impact of this aggressive quantization is quantified and it is shown that the proposed method is robust to low signal-to-noise ratios (SNR). We derive closed-form expressions for both false alarm and detection probabilities. The sensing performance and the analytical results are assessed through comparisons with respective results from computer simulations. The results indicate that the proposed method provides significant saving in power, complexity, and sensing period on the account of an acceptable range of performance degradation.
Predicting Neighbor Distribution in Heterogeneous Information Networks
Venue: arXiv cs.SI 2015
Year: 2015

Recently, considerable attention has been devoted to the prediction problems arising from heterogeneous information networks. In this paper, we present a new prediction task, Neighbor Distribution Prediction (NDP), which aims at predicting the distribution of the labels on neighbors of a given node and is valuable for many different applications in heterogeneous information networks. The challenges of NDP mainly come from three aspects: the infinity of the state space of a neighbor distribution, the sparsity of available data, and how to fairly evaluate the predictions. To address these challenges, we first propose an Evolution Factor Model (EFM) for NDP, which utilizes two new structures proposed in this paper, i.e. Neighbor Distribution Vector (NDV) to represent the state of a given node's neighbors, and Neighbor Label Evolution Matrix (NLEM) to capture the dynamics of a neighbor distribution, respectively. We further propose a learning algorithm for Evolution Factor Model. To overcome the problem of data sparsity, the learning algorithm first clusters all the nodes and learns an NLEM for each cluster instead of for each node. For fairly evaluating the predicting results, we propose a new metric: Virtual Accuracy (VA), which takes into consideration both the absolute accuracy and the predictability of a node. Extensive experiments conducted on three real datasets from different domains validate the effectiveness of our proposed model EFM and metric VA.
Grid-based angle-constrained path planning
Venue: arXiv cs.AI 2015
Year: 2015

Square grids are commonly used in robotics and game development as spatial models and well known in AI community heuristic search algorithms (such as A*, JPS, Theta* etc.) are widely used for path planning on grids. A lot of research is concentrated on finding the shortest (in geometrical sense) paths while in many applications finding smooth paths (rather than the shortest ones but containing sharp turns) is preferable. In this paper we study the problem of generating smooth paths and concentrate on angle constrained path planning. We put angle-constrained path planning problem formally and present a new algorithm tailored to solve it - LIAN. We examine LIAN both theoretically and empirically. We show that it is sound and complete (under some restrictions). We also show that LIAN outperforms the analogues when solving numerous path planning tasks within urban outdoor navigation scenarios.
On the Hardness of Almost-Sure Termination
Venue: arXiv cs.LO 2015
Year: 2015

This paper considers the computational hardness of computing expected outcomes and deciding (universal) (positive) almost-sure termination of probabilistic programs. It is shown that computing lower and upper bounds of expected outcomes is $Σ_1^0$- and $Σ_2^0$-complete, respectively. Deciding (universal) almost-sure termination as well as deciding whether the expected outcome of a program equals a given rational value is shown to be $Π^0_2$-complete. Finally, it is shown that deciding (universal) positive almost-sure termination is $Σ_2^0$-complete ($Π_3^0$-complete).
Quasi-Cyclic Complementary Dual Code
Venue: arXiv cs.IT 2015
Year: 2015

LCD codes are linear codes that intersect with their dual trivially. Quasi cyclic codes that are LCD are characterized and studied by using their concatenated structure. Some asymptotic results are derived. Hermitian LCD codes are introduced to that end and their cyclic subclass is characterized. Constructions of QCCD codes from codes over larger alphabets are given.
Eye-Tracking Metrics for Task-Based Supervisory Control
Venue: arXiv cs.HC 2015
Year: 2015

Task-based, rather than vehicle-based, control architectures have been shown to provide superior performance in certain human supervisory control missions. These results motivate the need for the development of robust, reliable usability metrics to aid in creating interfaces for use in this domain. To this end, we conduct a pilot usability study of a particular task-based supervisory control interface called the Research Environment for Supervisory Control of Heterogenous Unmanned Vehicles (RESCHU). In particular, we explore the use of eye-tracking metrics as an objective means of evaluating the RESCHU interface and providing guidance in improving usability. Our main goals for this study are to 1) better understand how eye-tracking can augment standard usability metrics, 2) formulate initial models of operator behavior, and 3) identify interesting areas of future research.
VCG Payments for Portfolio Allocations in Online Advertising
Venue: arXiv cs.GT 2015
Year: 2015

Some online advertising offers pay only when an ad elicits a response. Randomness and uncertainty about response rates make showing those ads a risky investment for online publishers. Like financial investors, publishers can use portfolio allocation over multiple advertising offers to pursue revenue while controlling risk. Allocations over multiple offers do not have a distinct winner and runner-up, so the usual second-price mechanism does not apply. This paper develops a pricing mechanism for portfolio allocations. The mechanism is efficient, truthful, and rewards offers that reduce risk.
Can Feedback Increase the Capacity of the Energy Harvesting Channel?
Venue: arXiv cs.IT 2015
Year: 2015

We investigate if feedback can increase the capacity of an energy harvesting communication channel where a transmitter powered by an exogenous energy arrival process and equipped with a finite battery communicates to a receiver over a memoryless channel. For a simple special case where the energy arrival process is deterministic and the channel is a BEC, we explicitly compute the feed-forward and feedback capacities and show that feedback can strictly increase the capacity of this channel. Building on this example, we also show that feedback can increase the capacity when the energy arrivals are i.i.d. known noncausally at the transmitter and the receiver.
Using Facebook for Image Steganography
Venue: arXiv cs.MM 2015
Year: 2015

Because Facebook is available on hundreds of millions of desktop and mobile computing platforms around the world and because it is available on many different kinds of platforms (from desktops and laptops running Windows, Unix, or OS X to hand held devices running iOS, Android, or Windows Phone), it would seem to be the perfect place to conduct steganography. On Facebook, information hidden in image files will be further obscured within the millions of pictures and other images posted and transmitted daily. Facebook is known to alter and compress uploaded images so they use minimum space and bandwidth when displayed on Facebook pages. The compression process generally disrupts attempts to use Facebook for image steganography. This paper explores a method to minimize the disruption so JPEG images can be used as steganography carriers on Facebook.
Frequency-domain analysis of nonlinear and linear integrators
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, frequency-domain analysis based on frequency sweep method is presented for a nonlinear double integrator and a new linear integrator. All the two types of integrators can estimate the onefold and double integrals of a signal synchronously. With respect to the linear double integrator, the nonlinear integrator has better estimation performance and stronger robustness. Importantly, the integrator parameters can be regulated from the frequency-domain analysis.
Selective Greedy Equivalence Search: Finding Optimal Bayesian Networks Using a Polynomial Number of Score Evaluations
Venue: arXiv cs.LG 2015
Year: 2015

We introduce Selective Greedy Equivalence Search (SGES), a restricted version of Greedy Equivalence Search (GES). SGES retains the asymptotic correctness of GES but, unlike GES, has polynomial performance guarantees. In particular, we show that when data are sampled independently from a distribution that is perfect with respect to a DAG ${\cal G}$ defined over the observable variables then, in the limit of large data, SGES will identify ${\cal G}$'s equivalence class after a number of score evaluations that is (1) polynomial in the number of nodes and (2) exponential in various complexity measures including maximum-number-of-parents, maximum-clique-size, and a new measure called {\em v-width} that is at least as small as---and potentially much smaller than---the other two. More generally, we show that for any hereditary and equivalence-invariant property $Π$ known to hold in ${\cal G}$, we retain the large-sample optimality guarantees of GES even if we ignore any GES deletion operator during the backward phase that results in a state for which $Π$ does not hold in the common-descendants subgraph.
Queueing Game For Spectrum Access in Cognitive Radio Networks
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, we investigate the problem of spectrum access decision-making for the Secondary Users (SUs) in the cognitive radio networks. When the Primary Users (PUs) are absent on certain frequency bandwidth, SUs can formulate a queue and wait for the Base Station (BS) to serve. The queue of the SUs will be dismissed if the PU is emerging in the system. Leveraging the queueing game approaches, the decision-making process of the SUs that whether to queue or not is studied. Both individual equilibrium and social optimization strategies are derived analytically. Moreover, the optimal pricing strategy of the service provider is investigated as well. Our proposed algorithms and corresponding analysis are validated through simulation studies.
A Multi-layered Acoustic Tokenizing Deep Neural Network (MAT-DNN) for Unsupervised Discovery of Linguistic Units and Generation of High Quality Features
Venue: arXiv cs.CL 2015
Year: 2015

This paper summarizes the work done by the authors for the Zero Resource Speech Challenge organized in the technical program of Interspeech 2015. The goal of the challenge is to discover linguistic units directly from unlabeled speech data. The Multi-layered Acoustic Tokenizer (MAT) proposed in this work automatically discovers multiple sets of acoustic tokens from the given corpus. Each acoustic token set is specified by a set of hyperparameters that describe the model configuration. These sets of acoustic tokens carry different characteristics of the given corpus and the language behind thus can be mutually reinforced. The multiple sets of token labels are then used as the targets of a Multi-target DNN (MDNN) trained on low-level acoustic features. Bottleneck features extracted from the MDNN are used as feedback for the MAT and the MDNN itself. We call this iterative system the Multi-layered Acoustic Tokenizing Deep Neural Network (MAT-DNN) which generates high quality features for track 1 of the challenge and acoustic tokens for track 2 of the challenge.
Automated Synthesis of Distributed Controllers
Venue: arXiv cs.FL 2015
Year: 2015

Synthesis is a particularly challenging problem for concurrent programs. At the same time it is a very promising approach, since concurrent programs are difficult to get right, or to analyze with traditional verification techniques. This paper gives an introduction to distributed synthesis in the setting of Mazurkiewicz traces, and its applications to decentralized runtime monitoring. 1 Context Modern computing systems are increasingly distributed and heterogeneous. Software needs to be able to exploit these advances, providing means for applications to be more performant. Traditional concurrent programming paradigms, as in Java, are based on threads, shared-memory, and locking mechanisms that guard access to common data. More recent paradigms like the reactive programming model of Erlang [4] and Scala [35,36] replace shared memory by asynchronous message passing, where sending a message is non-blocking. In all these concurrent frameworks, writing reliable software is a serious challenge. Programmers tend to think about code mostly in a sequential way, and it is hard to grasp all possible schedulings of events in a concurrent execution. For similar reasons, verification and analysis of concurrent programs is a difficult task. Testing, which is still the main method for error detection in software, has low coverage for concurrent programs. The reason is that bugs in such programs are difficult to reproduce: they may happen under very specific thread schedules and the likelihood of taking such corner-case schedules is very low. Automated verification, such as model-checking and other traditional exploration techniques, can handle very limited instances of concurrent programs, mostly because of the very large number of possible states and of possible interleavings of executions. Formal analysis of programs requires as a prerequisite a clean mathematical model for programs. Verification of sequential programs starts usually with an abstraction step -- reducing the value domains of variables to finite domains, viewing conditional branching as non-determinism, etc. Another major simplification consists in disallowing recursion. This leads to a very robust computational model, namely finite-state automata and regular languages. Regular languages of words (and trees) are particularly well understood notions. The deep connections between logic and automata revealed by the foundational work of Büchi, Rabin, and others, are the main ingredients in automata-based verification .
Empirical comparison of network sampling techniques
Venue: arXiv cs.SI 2015
Year: 2015

In the past few years, the storage and analysis of large-scale and fast evolving networks present a great challenge. Therefore, a number of different techniques have been proposed for sampling large networks. In general, network exploration techniques approximate the original networks more accurately than random node and link selection. Yet, link selection with additional subgraph induction step outperforms most other techniques. In this paper, we apply subgraph induction also to random walk and forest-fire sampling. We analyze different real-world networks and the changes of their properties introduced by sampling. We compare several sampling techniques based on the match between the original networks and their sampled variants. The results reveal that the techniques with subgraph induction underestimate the degree and clustering distribution, while overestimate average degree and density of the original networks. Techniques without subgraph induction step exhibit exactly the opposite behavior. Hence, the performance of the sampling techniques from random selection category compared to network exploration sampling does not differ significantly, while clear differences exist between the techniques with subgraph induction step and the ones without it.
Limitations of PLL simulation: hidden oscillations in MatLab and SPICE
Venue: arXiv cs.OH 2015
Year: 2015

Nonlinear analysis of the phase-locked loop (PLL) based circuits is a challenging task, thus in modern engineering literature simplified mathematical models and simulation are widely used for their study. In this work the limitations of numerical approach is discussed and it is shown that, e.g. hidden oscillations may not be found by simulation. Corresponding examples in SPICE and MatLab, which may lead to wrong conclusions concerning the operability of PLL-based circuits, are presented.
EMMA: A Resource Oriented Framework for Service Choreography over Wireless Sensor and Actor Networks
Venue: arXiv cs.NI 2015
Year: 2015

Current Internet of Things (IoT) development requires service distribution over Wireless Sensor and Actor Networks (WSAN) to deal with the drastic increasing of network management complexity. Because of the specific constraints of WSAN, centralized approaches are strongly limited. Multi-hop communication used by WSAN introduces transmission latency, packet errors, router congestion and security issues. As it uses local services, a decentralized service model avoid long path communications between nodes and applications. But the main issue is then to have such local services installed on the desired nodes. Environment Monitoring and Management Agent (EMMA) system proposes a set of software to deploy and to execute such services over Wireless Sensor and Actor Networks (WSAN) through a middleware based on Resource Oriented Architecture (ROA). Its Internet integration and the local management of data heterogeneity are facilitated through the use of current standard protocols such as IPv6 LoW Power Wireless Area Networks (6LoWPAN) and Constrained Application Protocol (CoAP). This contribution presents EMMA middleware, methodology and tools used to determine efficient service mapping and its deployment.
Exploiting Correlation among Data Items for Cache Replacement in Ad-hoc Networks
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, we have proposed a novel technique for cache replacement in Ad-hoc Network based on the mining of Association Rules
Catching the head, tail, and everything in between: a streaming algorithm for the degree distribution
Venue: arXiv cs.DS 2015
Year: 2015

The degree distribution is one of the most fundamental graph properties of interest for real-world graphs. It has been widely observed in numerous domains that graphs typically have a tailed or scale-free degree distribution. While the average degree is usually quite small, the variance is quite high and there are vertices with degrees at all scales. We focus on the problem of approximating the degree distribution of a large streaming graph, with small storage. We design an algorithm headtail, whose main novelty is a new estimator of infrequent degrees using truncated geometric random variables. We give a mathematical analysis of headtail and show that it has excellent behavior in practice. We can process streams will millions of edges with storage less than 1% and get extremely accurate approximations for all scales in the degree distribution. We also introduce a new notion of Relative Hausdorff distance between tailed histograms. Existing notions of distances between distributions are not suitable, since they ignore infrequent degrees in the tail. The Relative Hausdorff distance measures deviations at all scales, and is a more suitable distance for comparing degree distributions. By tracking this new measure, we are able to give strong empirical evidence of the convergence of headtail.
Snake-in-the-Box Codes for Rank Modulation under Kendall's $τ$-Metric
Venue: arXiv cs.IT 2015
Year: 2015

For a Gray code in the scheme of rank modulation for flash memories, the codewords are permutations and two consecutive codewords are obtained using a push-to-the-top operation. We consider snake-in-the-box codes under Kendall's $τ$-metric, which is a Gray code capable of detecting one Kendall's $τ$-error. We answer two open problems posed by Horovitz and Etzion. Firstly, we prove the validity of a construction given by them, resulting in a snake of size $M_{2n+1}=\frac{(2n+1)!}{2}-2n+1$. Secondly, we come up with a different construction aiming at a longer snake of size $M_{2n+1}=\frac{(2n+1)!}{2}-2n+3$. The construction is applied successfully to $S_7$.
Fast Geometric Fit Algorithm for Sphere Using Exact Solution
Venue: arXiv cs.CV 2015
Year: 2015

Sphere fitting is a common problem in almost all science and engineering disciplines. Most of methods available are iterative in behavior. This involves fitting of the parameters in a least square sense or in a geometric sense. Here we extend the methods of Thomas Chan and Landau who fitted the 2D data using circle. This work closely resemble their work in redefining the error estimate and solving the sphere fitting problem exactly. The solutions for center and radius of the sphere can be found exactly and the equations can be hard coded for high performance. We have also shown some comparison with other popular methods and how this method behaves.
A study on central soft sets: Definitions and basic operations
Venue: arXiv cs.LO 2015
Year: 2015

In this paper, a new kind of soft sets related with some common decision making problems in real life called central soft sets is introduced. Properties of some basic operations on central soft sets are shown. It is investigated that some classic operations between soft sets can be obtained by central soft sets with selecting different central sets. We initiate the concepts of an evaluation system for a parameters set and its optional solutions. An algorithm is presented to solve such decision making problems.
A Decision-Aided Parallel SC-List Decoder for Polar Codes
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we propose a decision-aided scheme for parallel SC-List decoding of polar codes. At the parallel SC-List decoder, each survival path is extended based on multiple information bits, therefore the number of split paths becomes very large and the sorting to find the top L paths becomes very complex. We propose a decision-aided scheme to reduce the number of split paths and thus reduce the sorting complexity.
Clustering by transitive propagation
Venue: arXiv cs.LG 2015
Year: 2015

We present a global optimization algorithm for clustering data given the ratio of likelihoods that each pair of data points is in the same cluster or in different clusters. To define a clustering solution in terms of pairwise relationships, a necessary and sufficient condition is that belonging to the same cluster satisfies transitivity. We define a global objective function based on pairwise likelihood ratios and a transitivity constraint over all triples, assigning an equal prior probability to all clustering solutions. We maximize the objective function by implementing max-sum message passing on the corresponding factor graph to arrive at an O(N^3) algorithm. Lastly, we demonstrate an application inspired by mutational sequencing for decoding random binary words transmitted through a noisy channel.
TRISHUL: A Single-pass Optimal Two-level Inclusive Data Cache Hierarchy Selection Process for Real-time MPSoCs
Venue: arXiv cs.AR 2015
Year: 2015

Hitherto discovered approaches analyze the execution time of a real time application on all the possible cache hierarchy setups to find the application specific optimal two level inclusive data cache hierarchy to reduce cost, space and energy consumption while satisfying the time deadline in real time Multiprocessor Systems on Chip. These brute force like approaches can take years to complete. Alternatively, memory access trace driven crude estimation methods can find a cache hierarchy quickly by compromising the accuracy of results. In this article, for the first time, we propose a fast and accurate trace driven approach to find the optimal real time application specific two level inclusive data cache hierarchy. Our proposed approach TRISHUL predicts the optimal cache hierarchy performance first and then utilizes that information to find the optimal cache hierarchy quickly. TRISHUL can suggest a cache hierarchy, which has up to 128 times smaller size, up to 7 times faster compared to the suggestion of the state of the art crude trace driven two level inclusive cache hierarchy selection approach for the application traces analyzed.