OpenRaiser/Intern-Atlas huggingface dataset:
Wireless Powered Asynchronous Backscatter Networks with Sporadic Short Packets: Performance Analysis and Optimization
Venue: arXiv cs.IT 2018
Year: 2018

In the fifth generation era, the pervasive applications of Internet of Things and massive machine-type communications have initiated increasing research interests on the backscatter wireless powered communication (B-WPC) technique due to its ultra high energy efficiency and low cost. The ubiquitous B-WPC network is characterized by nodes with dynamic spatial positions and sporadic short packets, of which the performance has not been fully investigated. In this paper, we give a comprehensive analysis of a multi-antenna B-WPC network with sporadic short packets under a stochastic geometry framework. By exploiting a time-space Poisson point process model, the behavior of the network is well captured in a decentralized and asynchronous transmission way. We then analyze the energy and information outage performance in the energy harvest and backscatter modulation phases of the backscatter network, respectively. The optimal transmission slot length and division are obtained by maximizing the network-wide spatial throughput. Moreover, we find an interesting result that there exists the optimal tradeoff between the durations of the energy harvest and backscatter modulation phases for spatial throughput maximization. Numerical results are demonstrated to verify our analytical findings and show that this tradeoff region gets shrunk when the outage constraints become more stringent.
Join Query Optimization Techniques for Complex Event Processing Applications
Venue: arXiv cs.DB 2018
Year: 2018

Complex event processing (CEP) is a prominent technology used in many modern applications for monitoring and tracking events of interest in massive data streams. CEP engines inspect real-time information flows and attempt to detect combinations of occurrences matching predefined patterns. This is done by combining basic data items, also called primitive events, according to a pattern detection plan, in a manner similar to the execution of multi-join queries in traditional data management systems. Despite this similarity, little work has been done on utilizing existing join optimization methods to improve the performance of CEP-based systems. In this paper, we provide the first theoretical and experimental study of the relationship between these two research areas. We formally prove that the CEP Plan Generation problem is equivalent to the Join Query Plan Generation problem for a restricted class of patterns and can be reduced to it for a considerably wider range of classes. This result implies the NP-completeness of the CEP Plan Generation problem. We further show how join query optimization techniques developed over the last decades can be adapted and utilized to provide practically efficient solutions for complex event detection. Our experiments demonstrate the superiority of these techniques over existing strategies for CEP optimization in terms of throughput, latency, and memory consumption.
Studying Migrant Assimilation Through Facebook Interests
Venue: arXiv cs.SI 2018
Year: 2018

Migrants' assimilation is a major challenge for European societies, in part because of the sudden surge of refugees in recent years and in part because of long-term demographic trends. In this paper, we use Facebook's data for advertisers to study the levels of assimilation of Arabic-speaking migrants in Germany, as seen through the interests they express online. Our results indicate a gradient of assimilation along demographic lines, language spoken and country of origin. Given the difficulty to collect timely migration data, in particular for traits related to cultural assimilation, the methods that we develop and the results that we provide open new lines of research that computational social scientists are well-positioned to address.
Generalized Leapfrogging Samplesort: A Class of $O(n \log^2 n)$ Worst-Case Complexity and $O(n \log n)$ Average-Case Complexity Sorting Algorithms
Venue: arXiv cs.DS 2018
Year: 2018

The original Leapfrogging Samplesort operates on a sorted sample of size $s$ and an unsorted part of size $s+1$. We generalize this to a sorted sample of size $s$ and an unsorted part of size $(2^k-1)(s+1)$, where $k = O(1)$. We present a practical implementation of this class of algorithms and we show that the worst-case complexity is $O(n \log^2 n)$ and the average-case complexity is $O(n \log n)$. Keywords: Samplesort, Quicksort, Leapfrogging Samplesort, sorting, analysis of algorithms.
DeepSIC: Deep Semantic Image Compression
Venue: arXiv cs.CV 2018
Year: 2018

Incorporating semantic information into the codecs during image compression can significantly reduce the repetitive computation of fundamental semantic analysis (such as object recognition) in client-side applications. The same practice also enable the compressed code to carry the image semantic information during storage and transmission. In this paper, we propose a concept called Deep Semantic Image Compression (DeepSIC) and put forward two novel architectures that aim to reconstruct the compressed image and generate corresponding semantic representations at the same time. The first architecture performs semantic analysis in the encoding process by reserving a portion of the bits from the compressed code to store the semantic representations. The second performs semantic analysis in the decoding step with the feature maps that are embedded in the compressed code. In both architectures, the feature maps are shared by the compression and the semantic analytics modules. To validate our approaches, we conduct experiments on the publicly available benchmarking datasets and achieve promising results. We also provide a thorough analysis of the advantages and disadvantages of the proposed technique.
Histogram of Oriented Depth Gradients for Action Recognition
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we report on experiments with the use of local measures for depth motion for visual action recognition from MPEG encoded RGBD video sequences. We show that such measures can be combined with local space-time video descriptors for appearance to provide a computationally efficient method for recognition of actions. Fisher vectors are used for encoding and concatenating a depth descriptor with existing RGB local descriptors. We then employ a linear SVM for recognizing manipulation actions using such vectors. We evaluate the effectiveness of such measures by comparison to the state-of-the-art using two recent datasets for action recognition in kitchen environments.
Mobility and Science operations On An Asteroid Using a Hopping Small Spacecraft on Stilts
Venue: arXiv cs.RO 2018
Year: 2018

There are thousands of asteroids in near-Earth space and millions in the Main Belt. They are diverse in physical properties and composition and are time capsules of the early solar system. This makes them strategic locations for planetary science, resource mining, planetary defense/security and as interplanetary depots and communication relays. Landing on a small asteroid and manipulating its surface materials remains a major unsolved challenge fraught with high risk. The asteroid surface may contain everything from hard boulders to soft regolith loosely held by cohesion and very low-gravity. Upcoming missions Hayabusa II and OSIRIS-REx will perform touch and go operations to mitigate the risks of landing on an asteroid. This limits the contact time and requires fuel expenditure for hovering. An important unknown is the problem of getting stuck or making a hard impact with the surface. The Spacecraft Penetrator for Increasing Knowledge of NEOs (SPIKE) mission concept will utilize a small-satellite bus that is propelled using a xenon-fueled ion engine and will contain an extendable, low-mass, high-strength boom with a tip containing force-moment sensors. SPIKE will enable contact with the asteroid surface, where it will perform detailed regolith analysis and seismology as well as penetrometry, while keeping the main spacecraft bus at a safe distance. Using one or more long stilts frees the spacecraft from having to hover above the asteroid and thus substantially reduces or eliminates fuel use when doing science operations. This enables much longer missions that include a series of hops to multiple locations on the small-body surface.
Using High-Speed WANs and Network Data Caches to Enable Remote and Distributed Visualization
Venue: arXiv cs.DC 2018
Year: 2018

Visapult is a prototype application and framework for remote visualization of large scientific datasets. We approach the technical challenges of tera-scale visualization with a unique architecture that employs high speed WANs and network data caches for data staging and transmission. This architecture allows for the use of available cache and compute resources at arbitrary locations on the network. High data throughput rates and network utilization are achieved by parallelizing I/O at each stage in the application, and by pipelining the visualization process. On the desktop, the graphics interactivity is effectively decoupled from the latency inherent in network applications. We present a detailed performance analysis of the application, and improvements resulting from field-test analysis conducted as part of the DOE Combustion Corridor project.
Atomic Cross-Chain Swaps
Venue: arXiv cs.DC 2018
Year: 2018

An atomic cross-chain swap is a distributed coordination task where multiple parties exchange assets across multiple blockchains, for example, trading bitcoin for ether. An atomic swap protocol guarantees (1) if all parties conform to the protocol, then all swaps take place, (2) if some coalition deviates from the protocol, then no conforming party ends up worse off, and (3) no coalition has an incentive to deviate from the protocol. A cross-chain swap is modeled as a directed graph ${\cal D}$, whose vertexes are parties and whose arcs are proposed asset transfers. For any pair $({\cal D},L)$, where ${\cal D} = (V,A)$ is a strongly-connected directed graph and $L \subset V$ a feedback vertex set for ${\cal D}$, we give an atomic cross-chain swap protocol for ${\cal D}$, using a form of hashed timelock contracts, where the vertexes in $L$ generate the hashlocked secrets. We show that no such protocol is possible if ${\cal D}$ is not strongly connected, or if ${\cal D}$ is strongly connected but $L$ is not a feedback vertex set. The protocol has time complexity $O(diam({\cal D}))$ and space complexity (bits stored on all blockchains) $O(|A|^2)$.
RGB image-based data analysis via discrete Morse theory and persistent homology
Venue: arXiv cs.CV 2018
Year: 2018

Understanding and comparing images for the purposes of data analysis is currently a very computationally demanding task. A group at Australian National University (ANU) recently developed open-source code that can detect fundamental topological features of a grayscale image in a computationally feasible manner. This is made possible by the fact that computers store grayscale images as cubical cellular complexes. These complexes can be studied using the techniques of discrete Morse theory. We expand the functionality of the ANU code by introducing methods and software for analyzing images encoded in red, green, and blue (RGB), because this image encoding is very popular for publicly available data. Our methods allow the extraction of key topological information from RGB images via informative persistence diagrams by introducing novel methods for transforming RGB-to-grayscale. This paradigm allows us to perform data analysis directly on RGB images representing water scarcity variability as well as crime variability. We introduce software enabling a a user to predict future image properties, towards the eventual aim of more rapid image-based data behavior prediction.
A Survey of Word Embeddings Evaluation Methods
Venue: arXiv cs.CL 2018
Year: 2018

Word embeddings are real-valued word representations able to capture lexical semantics and trained on natural language corpora. Models proposing these representations have gained popularity in the recent years, but the issue of the most adequate evaluation method still remains open. This paper presents an extensive overview of the field of word embeddings evaluation, highlighting main problems and proposing a typology of approaches to evaluation, summarizing 16 intrinsic methods and 12 extrinsic methods. I describe both widely-used and experimental methods, systematize information about evaluation datasets and discuss some key challenges.
An Improved Tabu Search Heuristic for Static Dial-A-Ride Problem
Venue: arXiv cs.AI 2018
Year: 2018

Multi-vehicle routing has become increasingly important with the rapid development of autonomous vehicle technology. Dial-a-ride problem, a variant of vehicle routing problem (VRP), deals with the allocation of customer requests to vehicles, scheduling the pick-up and drop-off times and the sequence of serving those requests by ensuring high customer satisfaction with minimized travel cost. In this paper, we propose an improved tabu search (ITS) heuristic for static dial-a-ride problem (DARP) with the objective of obtaining high-quality solutions in short time. Two new techniques, initialization heuristic, and time window adjustment are proposed to achieve faster convergence to the global optimum. Various numerical experiments are conducted for the proposed solution methodology using DARP test instances from the literature and the convergence speed up is validated.
End-to-End Fine-Grained Action Segmentation and Recognition Using Conditional Random Field Models and Discriminative Sparse Coding
Venue: arXiv cs.CV 2018
Year: 2018

Fine-grained action segmentation and recognition is an important yet challenging task. Given a long, untrimmed sequence of kinematic data, the task is to classify the action at each time frame and segment the time series into the correct sequence of actions. In this paper, we propose a novel framework that combines a temporal Conditional Random Field (CRF) model with a powerful frame-level representation based on discriminative sparse coding. We introduce an end-to-end algorithm for jointly learning the weights of the CRF model, which include action classification and action transition costs, as well as an overcomplete dictionary of mid-level action primitives. This results in a CRF model that is driven by sparse coding features obtained using a discriminative dictionary that is shared among different actions and adapted to the task of structured output learning. We evaluate our method on three surgical tasks using kinematic data from the JIGSAWS dataset, as well as on a food preparation task using accelerometer data from the 50 Salads dataset. Our results show that the proposed method performs on par or better than state-of-the-art methods.
An Optimal Value Iteration Algorithm for Parity Games
Venue: arXiv cs.GT 2018
Year: 2018

The quest for a polynomial time algorithm for solving parity games gained momentum in 2017 when two different quasipolynomial time algorithms were constructed. In this paper, we further analyse the second algorithm due to Jurdziński and Lazić and called the succinct progress measure algorithm. It was presented as an improvement over a previous algorithm called the small progress measure algorithm, using a better data structure. The starting point of this paper is the observation that the underlying data structure for both progress measure algorithms are (subgraph-)universal trees. We show that in fact any universal tree gives rise to a value iteration algorithm à la succinct progress measure, and the complexity of the algorithm is proportional to the size of the chosen universal tree. We then show that both algorithms are instances of this generic algorithm for two constructions of universal trees, the first of exponential size (for small progress measure) and the second of quasipolynomial size (for succinct progress measure). The technical result of this paper is to show that the latter construction is asymptotically tight: universal trees have at least quasipolynomial size. This suggests that the succinct progress measure algorithm of Jurdziński and Lazić is in this framework optimal, and that the polynomial time algorithm for parity games is hiding someplace else.
Improving Multiple Object Tracking with Optical Flow and Edge Preprocessing
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we present a new method for detecting road users in an urban environment which leads to an improvement in multiple object tracking. Our method takes as an input a foreground image and improves the object detection and segmentation. This new image can be used as an input to trackers that use foreground blobs from background subtraction. The first step is to create foreground images for all the frames in an urban video. Then, starting from the original blobs of the foreground image, we merge the blobs that are close to one another and that have similar optical flow. The next step is extracting the edges of the different objects to detect multiple objects that might be very close (and be merged in the same blob) and to adjust the size of the original blobs. At the same time, we use the optical flow to detect occlusion of objects that are moving in opposite directions. Finally, we make a decision on which information we keep in order to construct a new foreground image with blobs that can be used for tracking. The system is validated on four videos of an urban traffic dataset. Our method improves the recall and precision metrics for the object detection task compared to the vanilla background subtraction method and improves the CLEAR MOT metrics in the tracking tasks for most videos.
Automatically Leveraging MapReduce Frameworks for Data-Intensive Applications
Venue: arXiv cs.DB 2018
Year: 2018

MapReduce is a popular programming paradigm for developing large-scale, data-intensive computation. Many frameworks that implement this paradigm have recently been developed. To leverage these frameworks, however, developers must become familiar with their APIs and rewrite existing code. Casper is a new tool that automatically translates sequential Java programs into the MapReduce paradigm. Casper identifies potential code fragments to rewrite and translates them in two steps: (1) Casper uses program synthesis to search for a program summary (i.e., a functional specification) of each code fragment. The summary is expressed using a high-level intermediate language resembling the MapReduce paradigm and verified to be semantically equivalent to the original using a theorem prover. (2) Casper generates executable code from the summary, using either the Hadoop, Spark, or Flink API. We evaluated Casper by automatically converting real-world, sequential Java benchmarks to MapReduce. The resulting benchmarks perform up to 48.2x faster compared to the original.
Personalized Survival Prediction with Contextual Explanation Networks
Venue: arXiv cs.LG 2018
Year: 2018

Accurate and transparent prediction of cancer survival times on the level of individual patients can inform and improve patient care and treatment practices. In this paper, we design a model that concurrently learns to accurately predict patient-specific survival distributions and to explain its predictions in terms of patient attributes such as clinical tests or assessments. Our model is flexible and based on a recurrent network, can handle various modalities of data including temporal measurements, and yet constructs and uses simple explanations in the form of patient- and time-specific linear regression. For analysis, we use two publicly available datasets and show that our networks outperform a number of baselines in prediction while providing a way to inspect the reasons behind each prediction.
Enabling Low-power Duplex Visible Light Communication
Venue: arXiv cs.NI 2018
Year: 2018

The new generation of LED-based illuminating infrastructures has enabled a "dual-paradigm" where LEDs are used for both illumination and communication purposes. The ubiquity of lighting makes visible light communication (VLC) well suited for communication with mobile devices and sensor nodes in indoor environment. Existing research on VLC has primarily been focused on advancing the performance of one-way communication. In this paper, we present Retro-VLC, a low-power duplex VLC system that enables a mobile device to perform bi-directional communication with the illuminating LEDs over the same light carrier. The design features a retro-reflector fabric that backscatters light, an LCD shutter that modulates information bits on the backscattered light carrier, and several low-power optimization techniques. We have prototyped the Reader system and made a few battery-free tag devices. Experimental results show that the tag can achieve a 10kbps downlink speed and 0.5kbps uplink speed over a distance of 2.4m. We also outline several potential applications of the proposed Retro-VLC system.
Multiple Accounts Detection on Facebook Using Semi-Supervised Learning on Graphs
Venue: arXiv cs.SI 2018
Year: 2018

In social networks, a single user may create multiple accounts to spread his / her opinions and to influence others, by actively comment on different news pages. It would be beneficial to both social networks and their communities, to demote such abnormal activities, and the first step is to detect those accounts. However, the detection is challenging, because these accounts may have very realistic names and reasonable activity patterns. In this paper, we investigate three different approaches, and propose using graph embedding together with semi-supervised learning, to predict whether a pair of accounts are created by the same user. We carry out extensive experimental analyses to understand how changes in the input data and algorithmic parameters / optimization affect the prediction performance. We also discover that local information have higher importance than the global ones for such prediction, and point out the threshold leading to the best results. We test the proposed approach with 6700 Facebook pages from the Middle East, and achieve the averaged accuracy at 0.996 and AUC (area under curve) at 0.952 for users with the same name; with the U.S. 2016 election dataset, we obtain the best AUC at 0.877 for users with different names.
A State-of-the-Art of Semantic Change Computation
Venue: arXiv cs.CL 2018
Year: 2018

This paper reviews the state-of-the-art of semantic change computation, one emerging research field in computational linguistics, proposing a framework that summarizes the literature by identifying and expounding five essential components in the field: diachronic corpus, diachronic word sense characterization, change modelling, evaluation data and data visualization. Despite the potential of the field, the review shows that current studies are mainly focused on testifying hypotheses proposed in theoretical linguistics and that several core issues remain to be solved: the need for diachronic corpora of languages other than English, the need for comprehensive evaluation data for evaluation, the comparison and construction of approaches to diachronic word sense characterization and change modelling, and further exploration of data visualization techniques for hypothesis justification.