OpenRaiser/Intern-Atlas huggingface dataset:
Fast k-Nearest Neighbour Search via Dynamic Continuous Indexing
Venue: arXiv cs.DS 2017
Year: 2017

Existing methods for retrieving k-nearest neighbours suffer from the curse of dimensionality. We argue this is caused in part by inherent deficiencies of space partitioning, which is the underlying strategy used by most existing methods. We devise a new strategy that avoids partitioning the vector space and present a novel randomized algorithm that runs in time linear in dimensionality of the space and sub-linear in the intrinsic dimensionality and the size of the dataset and takes space constant in dimensionality of the space and linear in the size of the dataset. The proposed algorithm allows fine-grained control over accuracy and speed on a per-query basis, automatically adapts to variations in data density, supports dynamic updates to the dataset and is easy-to-implement. We show appealing theoretical properties and demonstrate empirically that the proposed algorithm outperforms locality-sensitivity hashing (LSH) in terms of approximation quality, speed and space efficiency.
Almost lossless analog signal separation and probabilistic uncertainty relations
Venue: arXiv cs.IT 2017
Year: 2017

We propose an information-theoretic framework for analog signal separation. Specifically, we consider the problem of recovering two analog signals, modeled as general random vectors, from the noiseless sum of linear measurements of the signals. Our framework is inspired by the groundbreaking work of Wu and Verdú (2010) on analog compression and encompasses, inter alia, inpainting, declipping, super-resolution, the recovery of signals corrupted by impulse noise, and the separation of (e.g., audio or video) signals into two distinct components. The main results we report are general achievability bounds for the compression rate, i.e., the number of measurements relative to the dimension of the ambient space the signals live in, under either measurability or Hölder continuity imposed on the separator. Furthermore, we find a matching converse for sources of mixed discrete-continuous distribution. For measurable separators our proofs are based on a new probabilistic uncertainty relation which shows that the intersection of generic subspaces with general sets of sufficiently small Minkowski dimension is empty. Hölder continuous separators are dealt with by introducing the concept of regularized probabilistic uncertainty relations. The probabilistic uncertainty relations we develop are inspired by embedding results in dynamical systems theory due to Sauer et al. (1991) and---conceptually---parallel classical Donoho-Stark and Elad-Bruckstein uncertainty principles at the heart of compressed sensing theory. Operationally, the new uncertainty relations take the theory of sparse signal separation beyond traditional sparsity---as measured in terms of the number of non-zero entries---to the more general notion of low description complexity as quantified by Minkowski dimension. Finally, our approach also allows to significantly strengthen key results in Wu and Verdú (2010).
Constacyclic codes of length $p^sn$ over $\mathbb{F}_{p^m}+u\mathbb{F}_{p^m}$
Venue: arXiv cs.IT 2017
Year: 2017

Let $\mathbb{F}_{p^m}$ be a finite field of cardinality $p^m$ and $R=\mathbb{F}_{p^m}[u]/\langle u^2\rangle=\mathbb{F}_{p^m}+u\mathbb{F}_{p^m}$ $(u^2=0)$, where $p$ is a prime and $m$ is a positive integer. For any $λ\in \mathbb{F}_{p^m}^{\times}$, an explicit representation for all distinct $λ$-constacyclic codes over $R$ of length $p^sn$ is given by a canonical form decomposition for each code, where $s$ and $n$ are positive integers satisfying ${\rm gcd}(p,n)=1$. For any such code, using its canonical form decomposition the representation for the dual code of the code is provided. Moreover, representations for all distinct negacyclic codes and their dual codes of length $p^sn$ over $R$ are obtained, and self-duality for these codes are determined. Finally, all distinct self-dual negacyclic codes over $\mathbb{F}_5+u\mathbb{F}_5$ of length $2\cdot 5^s\cdot 3^t$ are listed for any positive integer $t$.
Algebraic Construction of Tail-Biting Trellises for Linear Block Codes
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we present an algebraic construction of tail-biting trellises. The proposed method is based on the state space expressions, i.e., the state space is the image of the set of information sequences under the associated state matrix. Then combining with the homomorphism theorem, an algebraic trellis construction is obtained. We show that a tail-biting trellis constructed using the proposed method is isomorphic to the associated Koetter-Vardy (KV) trellis and tail-biting Bahl-Cocke-Jelinek-Raviv (BCJR) trellis. We also evaluate the complexity of the obtained tail-biting trellises. On the other hand, a matrix consisting of linearly independent rows of the characteristic matrix is regarded as a generalization of minimal-span generator matrices. Then we show that a KV trellis is constructed based on an extended minimal-span generator matrix. It is shown that this construction is a natural extension of the method proposed by McEliece (1996).
Data Protection: Combining Fragmentation, Encryption, and Dispersion, a final report
Venue: arXiv cs.CR 2017
Year: 2017

Hardening data protection using multiple methods rather than 'just' encryption is of paramount importance when considering continuous and powerful attacks in order to observe, steal, alter, or even destroy private and confidential information.Our purpose is to look at cost effective data protection by way of combining fragmentation, encryption, and dispersion over several physical machines. This involves deriving general schemes to protect data everywhere throughout a network of machines where they are being processed, transmitted, and stored during their entire life cycle. This is being enabled by a number of parallel and distributed architectures using various set of cores or machines ranging from General Purpose GPUs to multiple clouds. In this report, we first present a general and conceptual description of what should be a fragmentation, encryption, and dispersion system (FEDS) including a number of high level requirements such systems ought to meet. Then, we focus on two kind of fragmentation. First, a selective separation of information in two fragments a public one and a private one. We describe a family of processes and address not only the question of performance but also the questions of memory occupation, integrity or quality of the restitution of the information, and of course we conclude with an analysis of the level of security provided by our algorithms. Then, we analyze works first on general dispersion systems in a bit wise manner without data structure consideration; second on fragmentation of information considering data defined along an object oriented data structure or along a record structure to be stored in a relational database.
Joint Power Minimization Over Multi-Carrier Two-Way Relay Networks
Venue: arXiv cs.IT 2017
Year: 2017

The study considers a three-node, two-way relaying network (TWRN) over a multi-carrier system, aiming to minimize the total power consumption of all the transmit and receiver activities. By employing digital network coding (DNC) and physical-layer network coding (PNC), respectively, as well as a novel hybrid PNC/DNC switching scheme, the total transmission power of the considered multi-carrier TWRN system is firstly analyzed; and the derived analytical expressions are then used to formulate a set of nonconvex optimization problems. We will show how those nonconvex functions are convexified for better computational tracbility. It is observed in the numerical results that, the PNC scheme generally consumes less power than DNC but becomes worse in the very low SNR regime. The proposed hybrid PNC/DNC switching scheme that takes advantage of both, is shown to outperform in all SNR regimes.
Towards Evaluation of Cultural-scale Claims in Light of Topic Model Sampling Effects
Venue: arXiv cs.DL 2017
Year: 2017

Cultural-scale models of full text documents are prone to over-interpretation by researchers making unintentionally strong socio-linguistic claims (Pechenick et al., 2015) without recognizing that even large digital libraries are merely samples of all the books ever produced. In this study, we test the sensitivity of the topic models to the sampling process by taking random samples of books in the Hathi Trust Digital Library from different areas of the Library of Congress Classification Outline. For each classification area, we train several topic models over the entire class with different random seeds, generating a set of spanning models. Then, we train topic models on random samples of books from the classification area, generating a set of sample models. Finally, we perform a topic alignment between each pair of models by computing the Jensen-Shannon distance (JSD) between the word probability distributions for each topic. We take two measures on each model alignment: alignment distance and topic overlap. We find that sample models with a large sample size typically have an alignment distance that falls in the range of the alignment distance between spanning models. Unsurprisingly, as sample size increases, alignment distance decreases. We also find that the topic overlap increases as sample size increases. However, the decomposition of these measures by sample size differs by number of topics and by classification area. We speculate that these measures could be used to find classes which have a common "canon" discussed among all books in the area, as shown by high topic overlap and low alignment distance even in small sample sizes.
Influence Prediction for Continuous-Time Information Propagation on Networks
Venue: arXiv cs.SI 2017
Year: 2017

We consider the problem of predicting the time evolution of influence, the expected number of activated nodes, given a set of initially active nodes on a propagation network. To address the significant computational challenges of this problem on large-scale heterogeneous networks, we establish a system of differential equations governing the dynamics of probability mass functions on the state graph where the nodes each lumps a number of activation states of the network, which can be considered as an analogue to the Fokker-Planck equation in continuous space. We provides several methods to estimate the system parameters which depend on the identities of the initially active nodes, network topology, and activation rates etc. The influence is then estimated by the solution of such a system of differential equations. This approach gives rise to a class of novel and scalable algorithms that work effectively for large-scale and dense networks. Numerical results are provided to show the very promising performance in terms of prediction accuracy and computational efficiency of this approach.
DNA-GA: A New Approach of Network Performance Analysis
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we propose a new approach of network performance analysis, which is based on our previous works on the deterministic network analysis using the Gaussian approximation (DNA-GA). First, we extend our previous works to a signal-to-interference ratio (SIR) analysis, which makes our DNA-GA analysis a formal microscopic analysis tool. Second, we show two approaches for upgrading the DNA-GA analysis to a macroscopic analysis tool. Finally, we perform a comparison between the proposed DNA-GA analysis and the existing macroscopic analysis based on stochastic geometry. Our results show that the DNA-GA analysis possesses a few special features: (i) shadow fading is naturally considered in the DNAGA analysis; (ii) the DNA-GA analysis can handle non-uniform user distributions and any type of multi-path fading; (iii) the shape and/or the size of cell coverage areas in the DNA-GA analysis can be made arbitrary for the treatment of hotspot network scenarios. Thus, DNA-GA analysis is very useful for the network performance analysis of the 5th generation (5G) systems with general cell deployment and user distribution, both on a microscopic level and on a macroscopic level.
Algorithmic aspects of branched coverings
Venue: arXiv cs.CC 2017
Year: 2017

This is the announcement, and the long summary, of a series of articles on the algorithmic study of Thurston maps. We describe branched coverings of the sphere in terms of group-theoretical objects called bisets, and develop a theory of decompositions of bisets. We introduce a canonical "Levy" decomposition of an arbitrary Thurston map into homeomorphisms, metrically-expanding maps and maps doubly covered by torus endomorphisms. The homeomorphisms decompose themselves into finite-order and pseudo-Anosov maps, and the expanding maps decompose themselves into rational maps. As an outcome, we prove that it is decidable when two Thurston maps are equivalent. We also show that the decompositions above are computable, both in theory and in practice.
Shapely monads and analytic functors
Venue: arXiv cs.LO 2017
Year: 2017

In this paper, we give precise mathematical form to the idea of a structure whose data and axioms are faithfully represented by a graphical calculus; some prominent examples are operads, polycategories, properads, and PROPs. Building on the established presentation of such structures as algebras for monads on presheaf categories, we describe a characteristic property of the associated monads---the shapeliness of the title---which says that "any two operations of the same shape agree". An important part of this work is the study of analytic functors between presheaf categories, which are a common generalisation of Joyal's analytic endofunctors on sets and of the parametric right adjoint functors on presheaf categories introduced by Diers and studied by Carboni--Johnstone, Leinster and Weber. Our shapely monads will be found among the analytic endofunctors, and may be characterised as the submonads of a universal analytic monad with "exactly one operation of each shape". In fact, shapeliness also gives a way to define the data and axioms of a structure directly from its graphical calculus, by generating a free shapely monad on the basic operations of the calculus. In this paper we do this for some of the examples listed above; in future work, we intend to do so for graphical calculi such as Milner's bigraphs, Lafont's interaction nets, or Girard's multiplicative proof nets, thereby obtaining canonical notions of denotational model.
Content-based Dynaic Routing in Structured Overlays Networks
Venue: arXiv cs.DC 2017
Year: 2017

Acyclic overlays used for broker-based publish/subscribe systems provide unique paths for content-based routing from a publisher to interested subscribers. Cyclic overlays may provide multiple paths, however, the subscription broadcast process generates one content-based routing path per subscription. This poses serious challenges in offering dynamic routing of notifications when congestion is detected because instantaneous updates in routing tables are required to generate alternative routing paths. This paper introduces the first subscription-based publish/subscribe system, OctopiS, which offers inter-cluster dynamic routing when congestion in the output queues is detected. OctopiS is based on a formally defined Structured Cyclic Overlay Topology (SCOT). SCOT is divided into homogeneous clusters where each cluster has equal number of brokers and connects to other clusters through multiple inter-cluster overlay links. These links are used to provide parallel routing paths between publishers and subscribers connected to brokers in different clusters. While aiming at deployment at data center networks, OctopiS generates subscription-trees of shortest lengths used by Static Notification Routing (SNR) algorithm. Dynamic Notification Routing (DNR) algorithm uses a bit-vector mechanism to exploit the structuredness of a clustered SCOT to offer inter-cluster dynamic routing without making updates in routing tables and minimizing load on overwhelmed brokers and congested links. Experiments on a cluster testbed with real world data show that OctopiS is scalable and reduces the number of inter-broker messages in subscription delivery by 89%, subscription delay by 77%, end-to-end notification delay in static and dynamic routing by 47% and 58% respectively, and the lengths of output queues of brokers in dynamic routing paths by 59%.
Graphs of Edge-Intersecting and Non-Splitting One Bend Paths in a Grid
Venue: arXiv cs.DM 2017
Year: 2017

The families EPT (resp. EPG) Edge Intersection Graphs of Paths in a tree (resp. in a grid) are well studied graph classes. Recently we introduced the graph classes Edge-Intersecting and Non-Splitting Paths in a Tree ENPT, and in a Grid (ENPG). It was shown that ENPG contains an infinite hierarchy of subclasses that are obtained by restricting the number of bends in the paths. Motivated by this result, in this work we focus on one bend {ENPG} graphs. We show that one bend ENPG graphs are properly included in two bend ENPG graphs. We also show that trees and cycles are one bend ENPG graphs, and characterize the split graphs and co-bipartite graphs that are one bend ENPG. We prove that the recognition problem of one bend ENPG split graphs is NP-complete even in a very restricted subfamily of split graphs. Last we provide a linear time recognition algorithm for one bend ENPG co-bipartite graphs.
Feature Selection for Classification under Anonymity Constraint
Venue: arXiv cs.LG 2017
Year: 2017

Over the last decade, proliferation of various online platforms and their increasing adoption by billions of users have heightened the privacy risk of a user enormously. In fact, security researchers have shown that sparse microdata containing information about online activities of a user although anonymous, can still be used to disclose the identity of the user by cross-referencing the data with other data sources. To preserve the privacy of a user, in existing works several methods (k-anonymity, l-diversity, differential privacy) are proposed that ensure a dataset which is meant to share or publish bears small identity disclosure risk. However, the majority of these methods modify the data in isolation, without considering their utility in subsequent knowledge discovery tasks, which makes these datasets less informative. In this work, we consider labeled data that are generally used for classification, and propose two methods for feature selection considering two goals: first, on the reduced feature set the data has small disclosure risk, and second, the utility of the data is preserved for performing a classification task. Experimental results on various real-world datasets show that the method is effective and useful in practice.
Implementing a Bayes Filter in a Neural Circuit: The Case of Unknown Stimulus Dynamics
Venue: arXiv cs.LG 2017
Year: 2017

In order to interact intelligently with objects in the world, animals must first transform neural population responses into estimates of the dynamic, unknown stimuli which caused them. The Bayesian solution to this problem is known as a Bayes filter, which applies Bayes' rule to combine population responses with the predictions of an internal model. In this paper we present a method for learning to approximate a Bayes filter when the stimulus dynamics are unknown. To do this we use the inferential properties of probabilistic population codes to compute Bayes' rule, and train a neural network to compute approximate predictions by the method of maximum likelihood. In particular, we perform stochastic gradient descent on the negative log-likelihood with a novel approximation of the gradient. We demonstrate our methods on a finite-state, a linear, and a nonlinear filtering problem, and show how the hidden layer of the neural network develops tuning curves which are consistent with findings in experimental neuroscience.
Prediction-Based Task Assignment in Spatial Crowdsourcing (Technical Report)
Venue: arXiv cs.DB 2017
Year: 2017

Spatial crowdsourcing refers to a system that periodically assigns a number of location-based workers with spatial tasks nearby (e.g., taking photos or videos at some spatial locations). Previous works on the spatial crowdsourcing usually designed task assignment strategies that maximize some assignment scores, which are however only based on available workers/tasks in the system at the time point of assigning workers/tasks. These strategies may achieve local optimality, due to the neglect of future workers/tasks that may join the system. In contrast, in this paper, we aim to achieve "globally" optimal task assignments, by considering not only those present, but also future (via predictions), workers/tasks. Specifically, we formalize an important problem, namely prediction-based spatial crowdsourcing (PB-SC), which expects to obtain a "globally" optimal strategy for worker-and-task assignments, over both present and predicted task/worker locations, such that the total assignment quality score is maximized under the constraint of the traveling budget. In this paper, we design an effective grid-based prediction method to estimate spatial distributions of workers/tasks in the future, and then utilize the predicted ones in our procedure of task assignments. We prove that the PB-SC problem is NP-hard, and thus intractable. Therefore, we propose efficient approximate algorithms to tackle the PB-SC problem, including greedy and divide-and-conquer (D&C) approaches, which can efficiently assign workers to spatial tasks with high quality scores and low budget consumptions, by considering both current and future task/worker distributions. Through extensive experiments, we demonstrate the efficiency and effectiveness of our PB-SC processing approaches on real/synthetic data.
Performance Analysis of an Unreliable $M/G/1$ Retrial Queue with Two-way Communication
Venue: arXiv cs.NI 2017
Year: 2017

Efficient use of call center operators through technological innovations more often come at the expense of added operation management issues. In this paper, the stationary characteristics of an $M/G/1$ retrial queue is investigated where the single server, subject to active failures, primarily attends incoming calls and directs outgoing calls only when idle. The incoming calls arriving at the server follow a Poisson arrival process, while outgoing calls are made in an exponentially distributed time. On finding the server unavailable (either busy or temporarily broken down), incoming calls intrinsically join the virtual orbit from which they re-attempt for service at exponentially distributed time intervals. The system stability condition along with probability generating functions for the joint queue length distribution of the number of calls in the orbit and the state of the server are derived and evaluated numerically in the context of mean system size, server availability, failure frequency and orbit waiting time.
General Cut-Generating Procedures for the Stable Set Polytope
Venue: arXiv cs.DM 2017
Year: 2017

We propose general separation procedures for generating cuts for the stable set polytope, inspired by a procedure by Rossi and Smriglio and applying a lifting method by Xavier and Campêlo. In contrast to existing cut-generating procedures, ours generate both rank and non-rank valid inequalities, hence they are of a more general nature than existing methods. This is accomplished by iteratively solving a lifting problem, which consists of a maximum weighted stable set problem on a smaller graph. Computational experience on DIMACS benchmark instances shows that the proposed approach may be a useful tool for generating cuts for the stable set polytope.