OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Top K Temporal Spatial Keyword Search
Venue: arXiv cs.DB 2018
Year: 2018

Massive amount of data that are geo-tagged and associated with text information are being generated at an unprecedented scale in many emerging applications such as location based services and social networks. Due to their importance, a large body of work has focused on efficiently computing various spatial keyword queries. In this paper,we study the top-$k$ temporal spatial keyword query which considers three important constraints during the search including time, spatial proximity and textual relevance. A novel index structure, namely SSG-tree, to efficiently insert/delete spatio-temporal web objects with high rates. Base on SSG-tree an efficient algorithm is developed to support top-k temporal spatial keyword query. We show via extensive experimentation with real spatial databases that our method has increased performance over alternate techniques
Partition-Balanced Families of Codes and Asymptotic Enumeration in Coding Theory
Venue: arXiv cs.IT 2018
Year: 2018

We introduce the class of partition-balanced families of codes, and show how to exploit their combinatorial invariants to obtain upper and lower bounds on the number of codes that have a prescribed property. In particular, we derive precise asymptotic estimates on the density functions of several classes of codes that are extremal with respect to minimum distance, covering radius, and maximality. The techniques developed in this paper apply to various distance functions, including the Hamming and the rank metric distances. Applications of our results show that, unlike the $\mathbb{F}_{q^m}$-linear MRD codes, the $\mathbb{F}_q$-linear MRD codes are not dense in the family of codes of the same dimension. More precisely, we show that the density of $\mathbb{F}_q$-linear MRD codes in $\mathbb{F}_q^{n \times m}$ in the set of all matrix codes of the same dimension is asymptotically at most $1/2$, both as $q \to +\infty$ and as $m \to +\infty$. We also prove that MDS and $\mathbb{F}_{q^m}$-linear MRD codes are dense in the family of maximal codes. Although there does not exist a direct analogue of the redundancy bound for the covering radius of $\mathbb{F}_q$-linear rank metric codes, we show that a similar bound is satisfied by a uniformly random matrix code with high probability. In particular, we prove that codes meeting this bound are dense. Finally, we compute the average weight distribution of linear codes in the rank metric, and other parameters that generalize the total weight of a linear code.
Polar Wavelets in Space
Venue: arXiv cs.NA 2018
Year: 2018

Recent work introduced a unified framework for steerable and directional wavelets in two and three dimensions that ensures many desirable properties, such as a multi-scale structure, fast transforms, and a flexible angular localization. We show that, for an appropriate choice for the radial window function, these wavelets also have closed form expressions for, among other things, the spatial representation, the filter taps for the fast transform, and the frame representation of the Laplace operator. The numerical practicality and benefits of our work are demonstrated using signal estimation from non-uniform, point-wise samples, as required for example in ray tracing, and for reconstructing a signal over a lower-dimensional sub-manifold, with applications for instance in medical imaging.
Cluster-based trajectory segmentation with local noise
Venue: arXiv cs.AI 2018
Year: 2018

We present a framework for the partitioning of a spatial trajectory in a sequence of segments based on spatial density and temporal criteria. The result is a set of temporally separated clusters interleaved by sub-sequences of unclustered points. A major novelty is the proposal of an outlier or noise model based on the distinction between intra-cluster (local noise) and inter-cluster noise (transition): the local noise models the temporary absence from a residence while the transition the definitive departure towards a next residence. We analyze in detail the properties of the model and present a comprehensive solution for the extraction of temporally ordered clusters. The effectiveness of the solution is evaluated first qualitatively and next quantitatively by contrasting the segmentation with ground truth. The ground truth consists of a set of trajectories of labeled points simulating animal movement. Moreover, we show that the approach can streamline the discovery of additional derived patterns, by presenting a novel technique for the analysis of periodic movement. From a methodological perspective, a valuable aspect of this research is that it combines the theoretical investigation with the application and external validation of the segmentation framework. This paves the way to an effective deployment of the solution in broad and challenging fields such as e-science.
Generalized Center Problems with Outliers
Venue: arXiv cs.DS 2018
Year: 2018

We study the $\mathcal{F}$-center problem with outliers: given a metric space $(X,d)$, a general down-closed family $\mathcal{F}$ of subsets of $X$, and a parameter $m$, we need to locate a subset $S\in \mathcal{F}$ of centers such that the maximum distance among the closest $m$ points in $X$ to $S$ is minimized. Our main result is a dichotomy theorem. Colloquially, we prove that there is an efficient $3$-approximation for the $\mathcal{F}$-center problem with outliers if and only if we can efficiently optimize a poly-bounded linear function over $\mathcal{F}$ subject to a partition constraint. One concrete upshot of our result is a polynomial time $3$-approximation for the knapsack center problem with outliers for which no (true) approximation algorithm was known.
Linear Quadratic Synchronization of Multi-Agent Systems: A Distributed Optimization Approach
Venue: arXiv cs.SY 2018
Year: 2018

The distributed optimal synchronization problem with linear quadratic cost is solved in this paper for multi-agent systems with an undirected communication topology. For the first time, the optimal synchronization problem is formulated as a distributed optimization problem with a linear quadratic cost functional that integrates quadratic synchronization errors and quadratic input signals subject to agent dynamics and synchronization constraints. By introducing auxiliary synchronization state variables and combining the distributed synchronization method with the alternating direction method of multiplier (ADMM), a new distributed control protocol is designed for solving the distributed optimization problem. With this construction, the optimal synchronization control problem is separated into several independent subproblems: a synchronization optimization, an input minimization and a dual optimization. These subproblems are then solved by distributed numerical algorithms based on the Lyapunov method and dynamic programming. Numerical examples for both homogeneous and heterogeneous multi-agent systems are given to demonstrate the effectiveness of the proposed method.
Nonovershooting Cooperative Output Regulation for Linear Multi-Agent Systems
Venue: arXiv cs.SY 2018
Year: 2018

We consider the problem of cooperative output regulation for linear multi-agent systems. A distributed dynamic output feedback design method is presented that solves the cooperative output regulation problem and also ensures that all agents track the desired reference signal without overshoot in their transient response.
Efficient active learning of sparse halfspaces
Venue: arXiv cs.LG 2018
Year: 2018

We study the problem of efficient PAC active learning of homogeneous linear classifiers (halfspaces) in $\mathbb{R}^d$, where the goal is to learn a halfspace with low error using as few label queries as possible. Under the extra assumption that there is a $t$-sparse halfspace that performs well on the data ($t \ll d$), we would like our active learning algorithm to be {\em attribute efficient}, i.e. to have label requirements sublinear in $d$. In this paper, we provide a computationally efficient algorithm that achieves this goal. Under certain distributional assumptions on the data, our algorithm achieves a label complexity of $O(t \cdot \mathrm{polylog}(d, \frac 1 ε))$. In contrast, existing algorithms in this setting are either computationally inefficient, or subject to label requirements polynomial in $d$ or $\frac 1 ε$.
Competitive Video Retrieval with vitrivr at the Video Browser Showdown 2018 - Final Notes
Venue: arXiv cs.MM 2018
Year: 2018

This paper presents an after-the-fact summary of the participation of the vitrivr system to the 2018 Video Browser Showdown. A particular focus is on additions made since the original publication and the systems performance during the competition.
Trends in Russian research output indexed in Scopus and Web of Science
Venue: arXiv cs.DL 2018
Year: 2018

Trends are analysed in the annual number of documents published by Russian institutions and indexed in Scopus and Web of Science, giving special attention to the time period starting in the year 2013 in which the Project 5-100 was launched by the Russian Government. Numbers are broken down by document type, publication language, type of source, research discipline, country and source. It is concluded that Russian publication counts strongly depend upon the database used, and upon changes in database coverage, and that one should be cautious when using indicators derived from WoS, and especially from Scopus, as tools in the measurement of research performance and international orientation of the Russian science system.
Uniformization Problems for Synchronizations of Automatic Relations on Words
Venue: arXiv cs.FL 2018
Year: 2018

A uniformization of a binary relation is a function that is contained in the relation and has the same domain as the relation. The synthesis problem asks for effective uniformization for classes of relations and functions that can be implemented in a specific way. We consider the synthesis problem for automatic relations over finite words (also called regular or synchronized rational relations) by functions implemented by specific classes of sequential transducers. It is known that the problem "Given an automatic relation, does it have a uniformization by a subsequential transducer?" is decidable in the two variants where the uniformization can either be implemented by an arbitrary subsequential transducer or it has to be implemented by a synchronous transducer. We introduce a new variant of this problem in which the allowed input/output behavior of the subsequential transducer is specified by a set of synchronizations and prove decidability for a specific class of synchronizations.
Dictionary Learning and Sparse Coding on Statistical Manifolds
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we propose a novel information theoretic framework for dictionary learning (DL) and sparse coding (SC) on a statistical manifold (the manifold of probability distributions). Unlike the traditional DL and SC framework, our new formulation does not explicitly incorporate any sparsity inducing norm in the cost function being optimized but yet yields sparse codes. Our algorithm approximates the data points on the statistical manifold (which are probability distributions) by the weighted Kullback-Leibeler center/mean (KL-center) of the dictionary atoms. The KL-center is defined as the minimizer of the maximum KL-divergence between itself and members of the set whose center is being sought. Further, we prove that the weighted KL-center is a sparse combination of the dictionary atoms. This result also holds for the case when the KL-divergence is replaced by the well known Hellinger distance. From an applications perspective, we present an extension of the aforementioned framework to the manifold of symmetric positive definite matrices (which can be identified with the manifold of zero mean gaussian distributions), $\mathcal{P}_n$. We present experiments involving a variety of dictionary-based reconstruction and classification problems in Computer Vision. Performance of the proposed algorithm is demonstrated by comparing it to several state-of-the-art methods in terms of reconstruction and classification accuracy as well as sparsity of the chosen representation.
An Operating System Level Data Migration Scheme in Hybrid DRAM-NVM Memory Architecture
Venue: arXiv cs.OS 2018
Year: 2018

With the emergence of Non-Volatile Memories (NVMs) and their shortcomings such as limited endurance and high power consumption in write requests, several studies have suggested hybrid memory architecture employing both Dynamic Random Access Memory (DRAM) and NVM in a memory system. By conducting a comprehensive experiments, we have observed that such studies lack to consider very important aspects of hybrid memories including the effect of: a) data migrations on performance, b) data migrations on power, and c) the granularity of data migration. This paper presents an efficient data migration scheme at the Operating System level in a hybrid DRAMNVM memory architecture. In the proposed scheme, two Least Recently Used (LRU) queues, one for DRAM section and one for NVM section, are used for the sake of data migration. With careful characterization of the workloads obtained from PARSEC benchmark suite, the proposed scheme prevents unnecessary migrations and only allows migrations which benefits the system in terms of power and performance. The experimental results show that the proposed scheme can reduce the power consumption up to 79% compared to DRAM-only memory and up to 48% compared to the state-of-the art techniques.
Storage Scheduling with Stochastic Uncertainties: Feasibility and Cost of Imbalances
Venue: arXiv cs.SY 2018
Year: 2018

Dispatchability of renewable energy sources and inflexible loads can be achieved using a volatility-compensating energy storage. However, as the future power outputs of the inflexible devices are uncertain, the computation of a dispatch schedule for such aggregated systems is non-trivial. In the present paper, we propose a novel scheduling method that enforces the feasibility of the dispatch schedule with a pre-determined probability based on a description of the operation of the system as a two-stage decision process. Thereby, a crucial point is the use of probabilistic forecasts, in terms of cumulative density function, of the inflexible energy consumption/production profile. Then, for the sake of comparison, we introduce a second scheduling method based on state-of-the-art scenario optimization, where, unlike the proposed method, the focus is on the minimization of the expected final cost. We draw upon simulations based on real consumption and production data to compare the methods and illustrate our findings.
Capturing points with a rotating polygon (and a 3D extension)
Venue: arXiv cs.CG 2018
Year: 2018

We study the problem of rotating a simple polygon to contain the maximum number of elements from a given point set in the plane. We consider variations of this problem where the rotation center is a given point or lies on a line segment, a line, or a polygonal chain. We also solve an extension to 3D where we rotate a polyhedron around a given point to contain the maximum number of elements from a set of points in the space.
A Radiative Transfer Framework for Spatially-Correlated Materials
Venue: arXiv cs.GR 2018
Year: 2018

We introduce a non-exponential radiative framework that takes into account the local spatial correlation of scattering particles in a medium. Most previous works in graphics have ignored this, assuming uncorrelated media with a uniform, random local distribution of particles. However, positive and negative correlation lead to slower- and faster-than-exponential attenuation respectively, which cannot be predicted by the Beer-Lambert law. As our results show, this has a major effect on extinction, and thus appearance. From recent advances in neutron transport, we first introduce our Extended Generalized Boltzmann Equation, and develop a general framework for light transport in correlated media. We lift the limitations of the original formulation, including an analysis of the boundary conditions, and present a model suitable for computer graphics, based on optical properties of the media and statistical distributions of scatterers. In addition, we present an analytic expression for transmittance in the case of positive correlation, and show how to incorporate it efficiently into a Monte Carlo renderer. We show results with a wide range of both positive and negative correlation, and demonstrate the differences compared to classic light transport.
Holarchic Structures for Decentralized Deep Learning - A Performance Analysis
Venue: arXiv cs.LG 2018
Year: 2018

Structure plays a key role in learning performance. In centralized computational systems, hyperparameter optimization and regularization techniques such as dropout are computational means to enhance learning performance by adjusting the deep hierarchical structure. However, in decentralized deep learning by the Internet of Things, the structure is an actual network of autonomous interconnected devices such as smart phones that interact via complex network protocols. Self-adaptation of the learning structure is a challenge. Uncertainties such as network latency, node and link failures or even bottlenecks by limited processing capacity and energy availability can signif- icantly downgrade learning performance. Network self-organization and self-management is complex, while it requires additional computational and network resources that hinder the feasibility of decentralized deep learning. In contrast, this paper introduces a self-adaptive learning approach based on holarchic learning structures for exploring, mitigating and boosting learning performance in distributed environments with uncertainties. A large-scale performance analysis with 864000 experiments fed with synthetic and real-world data from smart grid and smart city pilot projects confirm the cost-effectiveness of holarchic structures for decentralized deep learning.
Synaptic Cleft Segmentation in Non-Isotropic Volume Electron Microscopy of the Complete Drosophila Brain
Venue: arXiv cs.CV 2018
Year: 2018

Neural circuit reconstruction at single synapse resolution is increasingly recognized as crucially important to decipher the function of biological nervous systems. Volume electron microscopy in serial transmission or scanning mode has been demonstrated to provide the necessary resolution to segment or trace all neurites and to annotate all synaptic connections. Automatic annotation of synaptic connections has been done successfully in near isotropic electron microscopy of vertebrate model organisms. Results on non-isotropic data in insect models, however, are not yet on par with human annotation. We designed a new 3D-U-Net architecture to optimally represent isotropic fields of view in non-isotropic data. We used regression on a signed distance transform of manually annotated synaptic clefts of the CREMI challenge dataset to train this model and observed significant improvement over the state of the art. We developed open source software for optimized parallel prediction on very large volumetric datasets and applied our model to predict synaptic clefts in a 50 tera-voxels dataset of the complete Drosophila brain. Our model generalizes well to areas far away from where training data was available.
Mobility-Aware Analysis of 5G and B5G Cellular Networks: A Tutorial
Venue: arXiv cs.NI 2018
Year: 2018

Providing network connectivity to mobile users is a key requirement for cellular wireless networks. User mobility impacts network performance as well as user perceived service quality. For efficient network dimensioning and optimization, it is therefore required to characterize the mobility-aware network performance metrics such as the handoff rate, handoff probability, sojourn time, direction switch rate, and users' throughput or coverage. This characterization is particularly challenging for heterogeneous, dense/ultra-dense, and random cellular networks such as the emerging 5G and beyond 5G (B5G) networks. In this article, we provide a tutorial on mobility-aware performance analysis of both the spatially random and non-random, single-tier and multi-tier cellular networks. We first provide a summary of the different mobility models which include purely random models, spatially correlated, and temporally correlated models. The differences among various mobility models, their statistical properties, and their pros and cons are presented. We then describe two main analytical approaches for mobility-aware performance analysis of both random and non-random cellular networks. For the first approach, we describe a general methodology and present several case studies for different cellular network tessellations such as square lattice, hexagon lattice, single-tier and multi-tier models in which base-stations (BSs) follow a homogeneous Poisson Point Process (PPP). For the second approach, we also outline the general methodology. In addition, we discuss some limitations/imperfections of the existing techniques and provide corrections to these imperfections. Finally, we point out specific 5G application scenarios where the impact of mobility would be significant and outline the challenges associated with mobility-aware analysis of those scenarios.
FlashAbacus: A Self-Governing Flash-Based Accelerator for Low-Power Systems
Venue: arXiv cs.AR 2018
Year: 2018

Energy efficiency and computing flexibility are some of the primary design constraints of heterogeneous computing. In this paper, we present FlashAbacus, a data-processing accelerator that self-governs heterogeneous kernel executions and data storage accesses by integrating many flash modules in lightweight multiprocessors. The proposed accelerator can simultaneously process data from different applications with diverse types of operational functions, and it allows multiple kernels to directly access flash without the assistance of a host-level file system or an I/O runtime library. We prototype FlashAbacus on a multicore-based PCIe platform that connects to FPGA-based flash controllers with a 20 nm node process. The evaluation results show that FlashAbacus can improve the bandwidth of data processing by 127%, while reducing energy consumption by 78.4%, as compared to a conventional method of heterogeneous computing. \blfootnote{This paper is accepted by and will be published at 2018 EuroSys. This document is presented to ensure timely dissemination of scholarly and technical work.
Polarization Weight Family Methods for Polar Code Construction
Venue: arXiv cs.IT 2018
Year: 2018

Polar codes are the first proven capacity-achieving codes. Recently, they are adopted as the channel coding scheme for 5G due to their superior performance.A polar code for encoding length-K information bits in length-N codeword could be specified by the polar code construction method. Most construction methods define a polar code related to channel parameter set, e.g. designed signal-to-noise ratio. Polarization weight (PW) is a channel-independent approximation method, which estimates the subchannel reliability as a function of its index. In this paper, we generalize the PW method by including higher-order bases or extended bases. The proposed methods have robust performance while preserving the computational and mathematical simplicity as PW.