OpenRaiser/Intern-Atlas huggingface dataset:
GeoTextTagger: High-Precision Location Tagging of Textual Documents using a Natural Language Processing Approach
Venue: arXiv cs.AI 2016
Year: 2016

Location tagging, also known as geotagging or geolocation, is the process of assigning geographical coordinates to input data. In this paper we present an algorithm for location tagging of textual documents. Our approach makes use of previous work in natural language processing by using a state-of-the-art part-of-speech tagger and named entity recognizer to find blocks of text which may refer to locations. A knowledge base (OpenStreatMap) is then used to find a list of possible locations for each block. Finally, one location is chosen for each block by assigning distance-based scores to each location and repeatedly selecting the location and block with the best score. We tested our geolocation algorithm with Wikipedia articles about topics with a well-defined geographical location that are geotagged by the articles' authors, where classification approaches have achieved median errors as low as 11 km, with attainable accuracy limited by the class size. Our approach achieved a 10th percentile error of 490 metres and median error of 54 kilometres on the Wikipedia dataset we used. When considering the five location tags with the greatest scores, 50% of articles were assigned at least one tag within 8.5 kilometres of the article's author-assigned true location. We also tested our approach on Twitter messages that are tagged with the location from which the message was sent. Twitter texts are challenging because they are short and unstructured and often do not contain words referring to the location they were sent from, but we obtain potentially useful results. We explain how we use the Spark framework for data analytics to collect and process our test data. In general, classification-based approaches for location tagging may be reaching their upper accuracy limit, but our precision-focused approach has high accuracy for some texts and shows significant potential for improvement overall.
Edge Agreement of Second-order Multi-agent System with Dynamic Quantization via Directed Edge Laplacian
Venue: arXiv cs.IT 2016
Year: 2016

This work explores the edge agreement problem of second-order multi-agent system with dynamic quantization under directed communication. To begin with, by virtue of the directed edge laplacian, we derive a model reduction representation of the closed-loop multi-agent system depended on the spanning tree subgraph. Considering the limitations of the finite bandwidth channels, the quantization effects of second-order multi-agent system under directed graph are considered. Motivated by the observation that the static quantizer always lead to the practical stability rather than the asymptotic stability, the dynamic quantized communication strategy referring to the rooming in-rooming out scheme is employed. Based on the reduced model associated with the essential edge Laplacian, the asymptotic stability of second-order multi-agent system under dynamic quantized effects with only finite quantization level can be guaranteed. Finally, simulation results are provided to verify the theoretical analysis.
Flip Distance to a Non-crossing Perfect Matching
Venue: arXiv cs.DM 2016
Year: 2016

A perfect straight-line matching $M$ on a finite set $P$ of points in the plane is a set of segments such that each point in $P$ is an endpoint of exactly one segment. $M$ is non-crossing if no two segments in $M$ cross each other. Given a perfect straight-line matching $M$ with at least one crossing, we can remove this crossing by a flip operation. The flip operation removes two crossing segments on a point set $Q$ and adds two non-crossing segments to attain a new perfect matching $M'$. It is well known that after a finite number of flips, a non-crossing matching is attained and no further flip is possible. However, prior to this work, no non-trivial upper bound on the number of flips was known. If $g(n)$ (resp.~$k(n)$) is the maximum length of the longest (resp.~shortest) sequence of flips starting from any matching of size $n$, we show that $g(n) = O(n^3)$ and $g(n) = Ω(n^2)$ (resp.~$k(n) = O(n^2)$ and $k(n) = Ω(n)$).
Consistency of the Plug-In Estimator of the Entropy Rate for Ergodic Processes
Venue: arXiv cs.IT 2016
Year: 2016

A plug-in estimator of entropy is the entropy of the distribution where probabilities of symbols or blocks have been replaced with their relative frequencies in the sample. Consistency and asymptotic unbiasedness of the plug-in estimator can be easily demonstrated in the IID case. In this paper, we ask whether the plug-in estimator can be used for consistent estimation of the entropy rate $h$ of a stationary ergodic process. The answer is positive if, to estimate block entropy of order $k$, we use a sample longer than $2^{k(h+ε)}$, whereas it is negative if we use a sample shorter than $2^{k(h-ε)}$. In particular, if we do not know the entropy rate $h$, it is sufficient to use a sample of length $(|X|+ε)^{k}$ where $|X|$ is the alphabet size. The result is derived using $k$-block coding. As a by-product of our technique, we also show that the block entropy of a stationary process is bounded above by a nonlinear function of the average block entropy of its ergodic components. This inequality can be used for an alternative proof of the known fact that the entropy rate a stationary process equals the average entropy rate of its ergodic components.
Online Event Recognition from Moving Vessel Trajectories
Venue: arXiv cs.CV 2016
Year: 2016

We present a system for online monitoring of maritime activity over streaming positions from numerous vessels sailing at sea. It employs an online tracking module for detecting important changes in the evolving trajectory of each vessel across time, and thus can incrementally retain concise, yet reliable summaries of its recent movement. In addition, thanks to its complex event recognition module, this system can also offer instant notification to marine authorities regarding emergency situations, such as risk of collisions, suspicious moves in protected zones, or package picking at open sea. Not only did our extensive tests validate the performance, efficiency, and robustness of the system against scalable volumes of real-world and synthetically enlarged datasets, but its deployment against online feeds from vessels has also confirmed its capabilities for effective, real-time maritime surveillance.
The Past, Present, and Future of Transport-Layer Multipath
Venue: arXiv cs.NI 2016
Year: 2016

Multipathing in communication networks is gaining momentum due to its attractive features of increased reliability, throughput, fault tolerance, and load balancing capabilities. In particular, wireless environments and datacenters are envisioned to become largely dependent on the power of multipathing for seamless handovers, virtual machine (VM) migration and in general, pooling less proficient resources together for achieving overall high proficiency. The transport layer, with its knowledge about end-to-end path characteristics, is well placed to enhance performance through better utilization of multiple paths. Realizing the importance of transport-layer multipath, this paper investigates the modernization of traditional connection establishment, flow control, sequence number splitting, acknowledgement, and flow scheduling mechanisms for use with multiple paths. Since congestion control defines a fundamental feature of the transport layer, we study the working of multipath rate control and analyze its stability and convergence. We also discuss how various multipath congestion control algorithms differ in their window increase and decrease functions, their TCP-friendliness, and responsiveness. To the best of our knowledge, this is the first in-depth survey paper that has chronicled the evolution of the transport layer of the Internet from the traditional single-path TCP to the recent development of the modern multipath TCP (MPTCP) protocol. Along with describing the history of this evolution, we also highlight in this paper the remaining challenges and research issues.
Finite-Blocklength Bounds for Wiretap Channels
Venue: arXiv cs.IT 2016
Year: 2016

This paper investigates the maximal secrecy rate over a wiretap channel subject to reliability and secrecy constraints at a given blocklength. New achievability and converse bounds are derived, which are shown to be tighter than existing bounds. The bounds also lead to the tightest second-order coding rate for discrete memoryless and Gaussian wiretap channels.
Coalition-based Planning of Military Operations: Adversarial Reasoning Algorithms in an Integrated Decision Aid
Venue: arXiv cs.AI 2016
Year: 2016

Use of knowledge-based planning tools can help alleviate the challenges of planning a complex operation by a coalition of diverse parties in an adversarial environment. We explore these challenges and potential contributions of knowledge-based tools using as an example the CADET system, a knowledge-based tool capable of producing automatically (or with human guidance) battle plans with realistic degree of detail and complexity. In ongoing experiments, it compared favorably with human planners. Interleaved planning, scheduling, routing, attrition and consumption processes comprise the computational approach of this tool. From the coalition operations perspective, such tools offer an important aid in rapid synchronization of assets and actions of heterogeneous assets belonging to multiple organizations, potentially with distinct doctrine and rules of engagement. In this paper, we discuss the functionality of the tool, provide a brief overview of the technical approach and experimental results, and outline the potential value of such tools.
Future Trends and Challenges for Mobile and Convergent Networks
Venue: arXiv cs.NI 2016
Year: 2016

Some traffic characteristics like real-time, location-based, and community-inspired, as well as the exponential increase on the data traffic in mobile networks, are challenging the academia and standardization communities to manage these networks in completely novel and intelligent ways, otherwise, current network infrastructures can not offer a connection service with an acceptable quality for both emergent traffic demand and application requisites. In this way, a very relevant research problem that needs to be addressed is how a heterogeneous wireless access infrastructure should be controlled to offer a network access with a proper level of quality for diverse flows ending at multi-mode devices in mobile scenarios. The current chapter reviews recent research and standardization work developed under the most used wireless access technologies and mobile access proposals. It comprehensively outlines the impact on the deployment of those technologies in future networking environments, not only on the network performance but also in how the most important requirements of several relevant players, such as, content providers, network operators, and users/terminals can be addressed. Finally, the chapter concludes referring the most notable aspects in how the environment of future networks are expected to evolve like technology convergence, service convergence, terminal convergence, market convergence, environmental awareness, energy-efficiency, self-organized and intelligent infrastructure, as well as the most important functional requisites to be addressed through that infrastructure such as flow mobility, data offloading, load balancing and vertical multihoming.
Achieving Large Multiplexing Gain in Distributed Antenna Systems via Cooperation with pCell Technology
Venue: arXiv cs.IT 2016
Year: 2016

In this paper we present pCellTM technology, the first commercial-grade wireless system that employs cooperation between distributed transceiver stations to create concurrent data links to multiple users in the same spectrum. First we analyze the per-user signal-to-interference-plus-noise ratio (SINR) employing a geometrical spatial channel model to define volumes in space of coherent signal around user antennas (or personal cells, i.e., pCells). Then we describe the system architecture consisting of a general-purpose-processor (GPP) based software-defined radio (SDR) wireless platform implementing a real-time LTE protocol stack to communicate with off-the-shelf LTE devices. Finally we present experimental results demonstrating up to 16 concurrent spatial channels for an aggregate average spectral efficiency of 59.3 bps/Hz in the downlink and 27.5 bps/Hz in the uplink, providing data rates of 200 Mbps downlink and 25 Mbps uplink in 5 MHz of TDD spectrum.
Precise Error Analysis of Regularized M-estimators in High-dimensions
Venue: arXiv cs.IT 2016
Year: 2016

A popular approach for estimating an unknown signal from noisy, linear measurements is via solving a so called \emph{regularized M-estimator}, which minimizes a weighted combination of a convex loss function and of a convex (typically, non-smooth) regularizer. We accurately predict the squared error performance of such estimators in the high-dimensional proportional regime. The random measurement matrix is assumed to have entries iid Gaussian, only minimal and rather mild regularity conditions are imposed on the loss function, the regularizer, and on the noise and signal distributions. We show that the error converges in probability to a nontrivial limit that is given as the solution to a minimax convex-concave optimization problem on four scalar optimization variables. We identify a new summary parameter, termed the Expected Moreau envelope to play a central role in the error characterization. The \emph{precise} nature of the results permits an accurate performance comparison between different instances of regularized M-estimators and allows to optimally tune the involved parameters (e.g. regularizer parameter, number of measurements). The key ingredient of our proof is the \emph{Convex Gaussian Min-max Theorem} (CGMT) which is a tight and strengthened version of a classical Gaussian comparison inequality that was proved by Gordon in 1988.
Parametric Bayesian Rejuvenation in Ambient Assisted Living through Software-based Thematic 5G Management
Venue: arXiv cs.CY 2016
Year: 2016

Ameliorating elderly engagement is vital in rejuvenating independent living. However, recommended practices lack realization of personal traits despite socio -economic promise. The recent proliferation of IoT with the advent of smart-objects/things and personalized services pave the way for context-aware service management. Eventually, the major goal of this paper is to develop a context-aware model in predicting engagement of elderly care. Hence, key requirements are identified for elderly engagement, namely (a) discovery of contexts, which are relevant (b) scaling up (over time) of engagement. However, paramount challenges are imposed on this stipulation, such as, un-observability, independence and composite relationship of contexts. Therefore, a Topic-model based model is proposed to address scalability of contexts and its conjugal relationship with engagement. Eventually, systematic framework is demonstrated, which pinpoints key goals of context-aware services by participants' opinions, usage and feed-back.
Response-Time-Optimized Distributed Cloud Resource Allocation
Venue: arXiv cs.NI 2016
Year: 2016

A current trend in networking and cloud computing is to provide compute resources over widely dispersed places exemplified by initiatives like Network Function Virtualisation. This paves the way for a widespread service deployment and can improve service quality; a nearby server can reduce the user-perceived response times. But always using the nearest server is a bad decision if that server is already highly utilized. This paper investigates the optimal assignment of users to widespread resources -- a convex capacitated facility location problem with integrated queuing systems. We determine the response times depending on the number of used resources. This enables service providers to balance between resource costs and the corresponding service quality. We also present a linear problem reformulation showing small optimality gaps and faster solving times; this speed-up enables a swift reaction to demand changes. Finally, we compare solutions by either considering or ignoring queuing systems and discuss the response time reduction by using the more complex model. Our investigations are backed by large-scale numerical evaluations.
Solving Dense Image Matching in Real-Time using Discrete-Continuous Optimization
Venue: arXiv cs.CV 2016
Year: 2016

Dense image matching is a fundamental low-level problem in Computer Vision, which has received tremendous attention from both discrete and continuous optimization communities. The goal of this paper is to combine the advantages of discrete and continuous optimization in a coherent framework. We devise a model based on energy minimization, to be optimized by both discrete and continuous algorithms in a consistent way. In the discrete setting, we propose a novel optimization algorithm that can be massively parallelized. In the continuous setting we tackle the problem of non-convex regularizers by a formulation based on differences of convex functions. The resulting hybrid discrete-continuous algorithm can be efficiently accelerated by modern GPUs and we demonstrate its real-time performance for the applications of dense stereo matching and optical flow.
Sub-Quadratic Decoding of Gabidulin Codes
Venue: arXiv cs.IT 2016
Year: 2016

This paper shows how to decode errors and erasures with Gabidulin codes in sub-quadratic time in the code length, improving previous algorithms which had at least quadratic complexity. The complexity reduction is achieved by accelerating operations on linearized polynomials. In particular, we present fast algorithms for division, multi-point evaluation and interpolation of linearized polynomials and show how to efficiently compute minimal subspace polynomials.
Role-based Label Propagation Algorithm for Community Detection
Venue: arXiv cs.SI 2016
Year: 2016

Community structure of networks provides comprehensive insight into their organizational structure and functional behavior. LPA is one of the most commonly adopted community detection algorithms with nearly linear time complexity. But it suffers from poor stability and occurrence of monster community due to the introduced randomize. We note that different community-oriented node roles impact the label propagation in different ways. In this paper, we propose a role-based label propagation algorithm (roLPA), in which the heuristics with regard to community-oriented node role were used. We have evaluated the proposed algorithm on both real and artificial networks. The result shows that roLPA is comparable to the state-of-the-art community detection algorithms.
Prediction-based Online Trajectory Compression
Venue: arXiv cs.DB 2016
Year: 2016

Recent spatio-temporal data applications, such as car-shar\-ing and smart cities, impose new challenges regarding the scalability and timeliness of data processing systems. Trajectory compression is a promising approach for scaling up spatio-temporal databases. However, existing techniques fail to address the online setting, in which a compressed version of a trajectory stream has to be maintained over time. In this paper, we introduce ONTRAC, a new framework for map-matched online trajectory compression. ONTRAC learns prediction models for suppressing updates to a trajectory database using training data. Two prediction schemes are proposed, one for road segments via a Markov model and another for travel-times by combining Quadratic Programming and Expectation Maximization. Experiments show that ONTRAC outperforms the state-of-the-art offline technique even when long update delays (4 mininutes) are allowed and achieves up to 21 times higher compression ratio for travel-times. Moreover, our approach increases database scalability by up to one order of magnitude.
Usability Evaluation of Dwell-free Eye Typing Techniques
Venue: arXiv cs.HC 2016
Year: 2016

Dwelling is an essential task to be performed to select keys from an on-screen keyboard present in the eye typing interface. This selection task can be performed by fixing eye gaze on a key for a prolonged time. Spending sufficient amount of time on each key effectively decreases the overall eye typing rate. To address the problem, researchers proposed mechanisms, which diminish the dwell time. We conducted a within-subject usability evaluation of four dwell-free eye typing techniques. The results of first-time usability study, longitudinal study and subjective evaluation conducted with 15 participants confirm the superiority of controlled eye movement based advanced eye typing method (Adv-EyeK) than the other three techniques.
Finite Blocklength Achievable Rates for Energy Harvesting AWGN Channels with Infinite Buffer
Venue: arXiv cs.IT 2016
Year: 2016

We consider an additive White Gaussian channel where the transmitter is powered by an energy harvesting source. For such a system, we provide a lower bound on the maximal code book at finite code lengths that improves upon previously known bounds.
Minimal Header Overhead for Random Linear Network Coding
Venue: arXiv cs.IT 2016
Year: 2016

The energy used to transmit a single bit of data between the devices in wireless networks is equal to the energy for performing hundreds of instructions in those devices. Thus the reduction of the data necessary to transmit, while keeping the same functionality of the employed algorithms is a formidable and challenging scientific task. We describe an algorithm called Small Set of Allowed Coefficients (SSAC) that produces the shortest header overhead in random linear network coding schemes compared with all other approaches reported in the literature. The header overhead length is 2 to 7 times shorter than the length achieved by related compression techniques. For example, SSAC algorithm compresses the length of the header overhead in a generation of 128 packets to 24 bits, while the closest best result achieved by an algorithm based on error correcting codes has a header overhead length of 84 bits in $GF(16)$ and 224 bits in $GF(256)$. We show that the header length in SSAC does not depend on the size of the finite field where the operations are performed, i.e., it just depends on the number of combined packets $m$.
Quegel: A General-Purpose Query-Centric Framework for Querying Big Graphs
Venue: arXiv cs.DC 2016
Year: 2016

Pioneered by Google's Pregel, many distributed systems have been developed for large-scale graph analytics. These systems expose the user-friendly "think like a vertex" programming interface to users, and exhibit good horizontal scalability. However, these systems are designed for tasks where the majority of graph vertices participate in computation, but are not suitable for processing light-workload graph queries where only a small fraction of vertices need to be accessed. The programming paradigm adopted by these systems can seriously under-utilize the resources in a cluster for graph query processing. In this work, we develop a new open-source system, called Quegel, for querying big graphs, which treats queries as first-class citizens in the design of its computing model. Users only need to specify the Pregel-like algorithm for a generic query, and Quegel processes light-workload graph queries on demand using a novel superstep-sharing execution model to effectively utilize the cluster resources. Quegel further provides a convenient interface for constructing graph indexes, which significantly improve query performance but are not supported by existing graph-parallel systems. Our experiments verified that Quegel is highly efficient in answering various types of graph queries and is up to orders of magnitude faster than existing systems.