OpenRaiser/Intern-Atlas huggingface dataset:
Spatial Context based Angular Information Preserving Projection for Hyperspectral Image Classification
Venue: arXiv cs.CV 2016
Year: 2016

Dimensionality reduction is a crucial preprocessing for hyperspectral data analysis - finding an appropriate subspace is often required for subsequent image classification. In recent work, we proposed supervised angular information based dimensionality reduction methods to find effective subspaces. Since unlabeled data are often more readily available compared to labeled data, we propose an unsupervised projection that finds a lower dimensional subspace where local angular information is preserved. To exploit spatial information from the hyperspectral images, we further extend our unsupervised projection to incorporate spatial contextual information around each pixel in the image. Additionally, we also propose a sparse representation based classifier which is optimized to exploit spatial information during classification - we hence assert that our proposed projection is particularly suitable for classifiers where local similarity and spatial context are both important. Experimental results with two real-world hyperspectral datasets demonstrate that our proposed methods provide a robust classification performance.
Multiuser Energy Diversity in Energy Harvesting Wireless Communications
Venue: arXiv cs.IT 2016
Year: 2016

Energy harvesting communication has raised great research interests due to its wide applications and feasibility of commercialization. In this paper, we investigate the multiuser energy diversity. Specifically, we reveal the throughput gain coming from the increase of total available energy harvested over time/space and from the combined dynamics of batteries. Considering both centralized and distributed access schemes, the scaling of the average throughput over the number of transmitters is studied, along with the scaling of corresponding available energy in the batteries.
Logic Programming with Graph Automorphism: Integrating naut with Prolog (Tool Description)
Venue: arXiv cs.DS 2016
Year: 2016

This paper presents the plnauty~library, a Prolog interface to the nauty graph-automorphism tool. Adding the capabilities of nauty to Prolog combines the strength of the "generate and prune" approach that is commonly used in logic programming and constraint solving, with the ability to reduce symmetries while reasoning over graph objects. Moreover, it enables the integration of nauty in existing tool-chains, such as SAT-solvers or finite domain constraints compilers which exist for Prolog. The implementation consists of two components: plnauty, an interface connecting \nauty's C library with Prolog, and plgtools, a Prolog framework integrating the software component of nauty, called gtools, with Prolog. The complete tool is available as a SWI-Prolog module. We provide a series of usage examples including two that apply to generate Ramsey graphs. This paper is under consideration for publication in TPLP.
Stochastic $k$-Center and $j$-Flat-Center Problems
Venue: arXiv cs.CG 2016
Year: 2016

Solving geometric optimization problems over uncertain data have become increasingly important in many applications and have attracted a lot of attentions in recent years. In this paper, we study two important geometric optimization problems, the $k$-center problem and the $j$-flat-center problem, over stochastic/uncertain data points in Euclidean spaces. For the stochastic $k$-center problem, we would like to find $k$ points in a fixed dimensional Euclidean space, such that the expected value of the $k$-center objective is minimized. For the stochastic $j$-flat-center problem, we seek a $j$-flat (i.e., a $j$-dimensional affine subspace) such that the expected value of the maximum distance from any point to the $j$-flat is minimized. We consider both problems under two popular stochastic geometric models, the existential uncertainty model, where the existence of each point may be uncertain, and the locational uncertainty model, where the location of each point may be uncertain. We provide the first PTAS (Polynomial Time Approximation Scheme) for both problems under the two models. Our results generalize the previous results for stochastic minimum enclosing ball and stochastic enclosing cylinder.
Grant-free Rateless Multiple Access: A Novel Massive Access Scheme for Internet of Things
Venue: arXiv cs.IT 2016
Year: 2016

Rateless Multiple Access (RMA) is a novel non-orthogonal multiple access framework that is promising for massive access in Internet of Things (IoT) due to its high efficiency and low complexity. In the framework, after certain \emph{registration}, each active user respectively transmits to the access point (AP) randomly based on an assigned random access control function (RACf) until receiving an acknowledgement (ACK). In this work, by exploiting the intrinsic access pattern of each user, we propose a grant-free RMA scheme, which no longer needs the registration process as in the original RMA, thus greatly reduces the signalling overhead and system latency. Furthermore, we propose a low-complexity joint iterative detection and decoding algorithm in which the channel estimation, active user detection, and information decoding are done simultaneously. Finally, we propose a method based on density evolution (DE) to evaluate the system performance.
Bounds on the Reliability of a Typewriter Channel
Venue: arXiv cs.IT 2016
Year: 2016

We give new bounds on the reliability function of a typewriter channel with 5 inputs and crossover probability $1/2$. The lower bound is more of theoretical than practical importance; it improves very marginally the expurgated bound, providing a counterexample to a conjecture on its tightness by Shannon, Gallager and Berlekamp which does not need the construction of algebraic-geometric codes previously used by Katsman, Tsfasman and Vlăduţ. The upper bound is derived by using an adaptation of the linear programming bound and it is essentially useful as a low-rate anchor for the straight line bound.
Processing In-memory realization using Quantum Dot Cellular Automata
Venue: arXiv cs.ET 2016
Year: 2016

The present manuscript deals with the realization of Processing In-memory (PIM) computing architecture using Quantum Dot Cellular Automata (QCA) and Akers array. The PIM computing architecture becomes popular due to its effective framework for storage and computation of data in a single unit. Here, we illustrate two input NAND and NOR gate with the help of QCA based Akers Array as a case study. The QCA flip-flop is used as a primitive cell to design PIM architecture. The results suggested that both the gate have minimum power dissipation. The polarization results of proposed architecture suggested that the signals are in good control. The foot print of the primitive cell equals to 0.04 micron^2, which is smaller than conventional CMOS primitive cell. The combination of QCA and Akers array provides many additional benefits over the conventional architecture like reduction in the power consumption and feature size, furthermore, it also improves the computational speed.
Deep Active Contours
Venue: arXiv cs.CV 2016
Year: 2016

We propose a method for interactive boundary extraction which combines a deep, patch-based representation with an active contour framework. We train a class-specific convolutional neural network which predicts a vector pointing from the respective point on the evolving contour towards the closest point on the boundary of the object of interest. These predictions form a vector field which is then used for evolving the contour by the Sobolev active contour framework proposed by Sundaramoorthi et al. The resulting interactive segmentation method is very efficient in terms of required computational resources and can even be trained on comparatively small graphics cards. We evaluate the potential of the proposed method on both medical and non-medical challenge data sets, such as the STACOM data set and the PASCAL VOC 2012 data set.
Functional Augmented State Transfer (FAST) Architecture for Computationally Intensive Network Applications
Venue: arXiv cs.DC 2016
Year: 2016

We describe a novel architecture that combines the simplicity of RESTful architecture with the power of functional programming for delivering web-services. Although, RESTful architecture has been quite useful in simplifying the development of scalable systems, it is not suited for all types of network applications. Our architecture improves upon the RESTful architecture to provide scalable framework for computationally intensive network applications. The proposed architecture is ideal for applications that involve data management and data analysis/calculations on data. Data analytics and financial calculations are two areas where the architecture can be applied efficiently.
Joint Event Detection and Entity Resolution: a Virtuous Cycle
Venue: arXiv cs.CL 2016
Year: 2016

Clustering web documents has numerous applications, such as aggregating news articles into meaningful events, detecting trends and hot topics on the Web, preserving diversity in search results, etc. At the same time, the importance of named entities and, in particular, the ability to recognize them and to solve the associated co-reference resolution problem are widely recognized as key enabling factors when mining, aggregating and comparing content on the Web. Instead of considering these two problems separately, we propose in this paper a method that tackles jointly the problem of clustering news articles into events and cross-document co-reference resolution of named entities. The co-occurrence of named entities in the same clusters is used as an additional signal to decide whether two referents should be merged into one entity. These refined entities can in turn be used as enhanced features to re-cluster the documents and then be refined again, entering into a virtuous cycle that improves simultaneously the performances of both tasks. We implemented a prototype system and report results using the TDT5 collection of news articles, demonstrating the potential of our approach.
SALZA: Soft algorithmic complexity estimates for clustering and causality inference
Venue: arXiv cs.IT 2016
Year: 2016

A complete set of practical estimators for the conditional, simple and joint algorihmic complexities is presented, from which a semi-metric is derived. Also, new directed information estimators are proposed that are applied to causality inference on Directed Acyclic Graphs. The performances of these estimators are investigated and shown to compare well with respect to the state-of-the-art Normalized Compression Distance (NCD).
Progressive Analytics: A Computation Paradigm for Exploratory Data Analysis
Venue: arXiv cs.HC 2016
Year: 2016

Exploring data requires a fast feedback loop from the analyst to the system, with a latency below about 10 seconds because of human cognitive limitations. When data becomes large or analysis becomes complex, sequential computations can no longer be completed in a few seconds and data exploration is severely hampered. This article describes a novel computation paradigm called Progressive Computation for Data Analysis or more concisely Progressive Analytics, that brings at the programming language level a low-latency guarantee by performing computations in a progressive fashion. Moving this progressive computation at the language level relieves the programmer of exploratory data analysis systems from implementing the whole analytics pipeline in a progressive way from scratch, streamlining the implementation of scalable exploratory data analysis systems. This article describes the new paradigm through a prototype implementation called ProgressiVis, and explains the requirements it implies through examples.
Diurnal and Weekly Cycles in IPv6 Traffic
Venue: arXiv cs.NI 2016
Year: 2016

IPv6 activity is commonly reported as a fraction of network traffic per day. Within this traffic, however, are daily and weekly characteristics, driven by non-uniform IPv6 deployment across ISPs and regions. This paper discusses some of the more apparent patterns we observe today.
On the Sensitivity Conjecture for Disjunctive Normal Forms
Venue: arXiv cs.CC 2016
Year: 2016

The sensitivity conjecture of Nisan and Szegedy [CC '94] asks whether for any Boolean function $f$, the maximum sensitivity $s(f)$, is polynomially related to its block sensitivity $bs(f)$, and hence to other major complexity measures. Despite major advances in the analysis of Boolean functions over the last decade, the problem remains widely open. In this paper, we consider a restriction on the class of Boolean functions through a model of computation (DNF), and refer to the functions adhering to this restriction as admitting the Normalized Block property. We prove that for any function $f$ admitting the Normalized Block property, $bs(f) \leq 4s(f)^2$. We note that (almost) all the functions mentioned in literature that achieve a quadratic separation between sensitivity and block sensitivity admit the Normalized Block property. Recently, Gopalan et al. [ITCS '16] showed that every Boolean function $f$ is uniquely specified by its values on a Hamming ball of radius at most $2s(f)$. We extend this result and also construct examples of Boolean functions which provide the matching lower bounds.
Downlink MIMO HCNs with Residual Transceiver Hardware Impairments
Venue: arXiv cs.IT 2016
Year: 2016

A major limitation of heterogeneous cellular networks (HCNs) is the neglect of the additive residual transceiver hardware impairments (ARTHIs). The assumption of perfect hardware is quite strong and results in misleading conclusions. This paper models a general multiple-input multiple-output (MIMO) HCN with cell association by incorporating the RTHIs. We derive the coverage probability and shed light on the impact of the ARTHIs, when various transmission methods are applied. As the hardware quality decreases, the coverage probability worsens. Especially, this effect is more severe as the transmit power increases. Furthermore, we verify that in an HCN, it is better to employ at each base station as few transmit antennas as possible.
Low-Complexity Recursive Convolutional Precoding for OFDM-based Large-Scale Antenna System
Venue: arXiv cs.IT 2016
Year: 2016

Large-scale antenna (LSA) has gained a lot of attention recently since it can significantly improve the performance of wireless systems. Similar to multiple-input multiple-output (MIMO) orthogonal frequency division multiplexing (OFDM) or MIMO-OFDM, LSA can be also combined with OFDM to deal with frequency selectivity in wireless channels. However, such combination suffers from substantially increased complexity proportional to the number of antennas in LSA systems. For the conventional implementation of LSA-OFDM, the number of inverse fast Fourier transforms (IFFTs) increases with the antenna number since each antenna requires an IFFT for OFDM modulation. Furthermore, zero-forcing (ZF) precoding is required in LSA systems to support more users, and the required matrix inversion leads to a huge computational burden. In this paper, we propose a low-complexity recursive convolutional precoding to address the issues above. The traditional ZF precoding can be implemented through the recursive convolutional precoding in the time domain so that only one IFFT is required for each user and the matrix inversion can be also avoided. Simulation results show that the proposed approach can achieve the same performance as that of ZF but with much lower complexity.
Grounded Fixpoints and Active Integrity Constraints
Venue: arXiv cs.DB 2016
Year: 2016

The formalism of active integrity constraints was introduced as a way to specify particular classes of integrity constraints over relational databases together with preferences on how to repair existing inconsistencies. The rule-based syntax of such integrity constraints also provides algorithms for finding such repairs that achieve the best asymptotic complexity. However, the different semantics that have been proposed for these integrity constraints all exhibit some counter-intuitive examples. In this work, we look at active integrity constraints using ideas from algebraic fixpoint theory. We show how database repairs can be modeled as fixpoints of particular operators on databases, and study how the notion of grounded fixpoint induces a corresponding notion of grounded database repair that captures several natural intuitions, and in particular avoids the problems of previous alternative semantics. In order to study grounded repairs in their full generality, we need to generalize the notion of grounded fixpoint to non-deterministic operators. We propose such a definition and illustrate its plausibility in the database context.
A Novel Information Theoretic Framework for Finding Semantic Similarity in WordNet
Venue: arXiv cs.IR 2016
Year: 2016

Information content (IC) based measures for finding semantic similarity is gaining preferences day by day. Semantics of concepts can be highly characterized by information theory. The conventional way for calculating IC is based on the probability of appearance of concepts in corpora. Due to data sparseness and corpora dependency issues of those conventional approaches, a new corpora independent intrinsic IC calculation measure has evolved. In this paper, we mainly focus on such intrinsic IC model and several topological aspects of the underlying ontology. Accuracy of intrinsic IC calculation and semantic similarity measure rely on these aspects deeply. Based on these analysis we propose an information theoretic framework which comprises an intrinsic IC calculator and a semantic similarity model. Our approach is compared with state of the art semantic similarity measures based on corpora dependent IC calculation as well as intrinsic IC based methods using several benchmark data set. We also compare our model with the related Edge based, Feature based and Distributional approaches. Experimental results show that our intrinsic IC model gives high correlation value when applied to different semantic similarity models. Our proposed semantic similarity model also achieves significant results when embedded with some state of the art IC models including ours.
Distance Sensitive Bloom Filters Without False Negatives
Venue: arXiv cs.DS 2016
Year: 2016

A Bloom filter is a widely used data-structure for representing a set $S$ and answering queries of the form "Is $x$ in $S$?". By allowing some false positive answers (saying "yes" when the answer is in fact `no') Bloom filters use space significantly below what is required for storing $S$. In the distance sensitive setting we work with a set $S$ of (Hamming) vectors and seek a data structure that offers a similar trade-off, but answers queries of the form "Is $x$ close to an element of $S$?" (in Hamming distance). Previous work on distance sensitive Bloom filters have accepted false positive and false negative answers. Absence of false negatives is of critical importance in many applications of Bloom filters, so it is natural to ask if this can be also achieved in the distance sensitive setting. Our main contributions are upper and lower bounds (that are tight in several cases) for space usage in the distance sensitive setting where false negatives are not allowed.
Multi-point Codes over Kummer Extensions
Venue: arXiv cs.IT 2016
Year: 2016

This paper is concerned with the construction of algebraic geometric codes defined from Kummer extensions. It plays a significant role in the study of such codes to describe bases for the Riemann-Roch spaces associated with totally ramified places. Along this line, we give an explicit characterization of Weierstrass semigroups and pure gaps. Additionally, we determine the floor of a certain type of divisor introduced by Maharaj, Matthews and Pirsic. Finally, we apply these results to find multi-point codes with good parameters. As one of the examples, a presented code with parameters $ [254,228,\geqslant 16] $ over $ \mathbb{F}_{64} $ yields a new record.
An Approximation Algorithm for the Art Gallery Problem
Venue: arXiv cs.CG 2016
Year: 2016

Given a simple polygon $\mathcal{P}$ on $n$ vertices, two points $x,y$ in $\mathcal{P}$ are said to be visible to each other if the line segment between $x$ and $y$ is contained in $\mathcal{P}$. The Point Guard Art Gallery problem asks for a minimum set $S$ such that every point in $\mathcal{P}$ is visible from a point in $S$. The set $S$ is referred to as guards. Assuming integer coordinates and a specific general position assumption, we present the first $O(\log \text{OPT})$-approximation algorithm for the point guard problem for simple polygons. This algorithm combines ideas of a paper of Efrat and Har-Peled [Inf. Process. Lett. 2006] and Deshpande et. al. [WADS 2007]. We also point out a mistake in the latter.
Decentralized Opportunistic Access for D2D Underlaid Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

We propose a decentralized access control scheme for interference management in D2D (device-to-device) underlaid cellular networks. Our method combines SIR-aware link activation with cellular exclusion regions in a case where D2D links opportunistically access the licensed cellular spectrum. Analytical expressions and tight approximations for the coverage probabilities of cellular and D2D links are derived. We characterize the impact of the guard zone radius and the SIR threshold on the D2D area spectral efficiency and cellular coverage. A tractable approach was proposed in order to find the SIR threshold and guard zone radius, which maximize the area spectral efficiency of the D2D communication while ensuring sufficient coverage probability for cellular uplink users. Simulations validate the accuracy of our analytical results and show the performance gain of our proposed scheme compared to existing state-of-the-art solutions.
Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees
Venue: arXiv cs.CG 2016
Year: 2016

We consider the problem of augmenting an n-vertex graph embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present exact algorithms for the cases when (i) the input graph is a path, running in O(n \log^3 n) time, and (ii) the input graph is a tree, running in O(n^2 \log n) time. We also present an algorithm that computes a (1+\eps)-approximation in O(n + 1/\eps^3) time, for paths in R^d, where d is a constant.
Set-Consensus Collections are Decidable
Venue: arXiv cs.DC 2016
Year: 2016

A natural way to measure the power of a distributed-computing model is to characterize the set of tasks that can be solved in it. %the model. In general, however, the question of whether a given task can be solved in a given model is undecidable, even if we only consider the wait-free shared-memory model. In this paper, we address this question for restricted classes of models and tasks. We show that the question of whether a collection $C$ of \emph{$(\ell,j)$-set consensus} objects, for various $\ell$ (the number of processes that can invoke the object) and $j$ (the number of distinct outputs the object returns), can be used by $n$ processes to solve wait-free $k$-set consensus is decidable. Moreover, we provide a simple $O(n^2)$ decision algorithm, based on a dynamic programming solution to the Knapsack optimization problem. We then present an \emph{adaptive} wait-free set-consensus algorithm that, for each set of participating processes, achieves the best level of agreement that is possible to achieve using $C$. Overall, this gives us a complete characterization of a read-write model defined by a collection of set-consensus objects through its \emph{set-consensus power}.