OpenRaiser/Intern-Atlas huggingface dataset:
A Randomized Concurrent Algorithm for Disjoint Set Union
Venue: arXiv cs.DC 2016
Year: 2016

The disjoint set union problem is a basic problem in data structures with a wide variety of applications. We extend a known efficient sequential algorithm for this problem to obtain a simple and efficient concurrent wait-free algorithm running on an asynchronous parallel random access machine (APRAM). Crucial to our result is the use of randomization. Under a certain independence assumption, for a problem instance in which there are n elements, m operations, and p processes, our algorithm does Theta(m (alpha(n, m/(np)) + log(np/m + 1))) expected work, where the expectation is over the random choices made by the algorithm and alpha is a functional inverse of Ackermann's function. In addition, each operation takes O(log n) steps with high probability. Our algorithm is significantly simpler and more efficient than previous algorithms proposed by Anderson and Woll. Under our independence assumption, our algorithm achieves almost-linear speed-up for applications in which all or most of the processes can be kept busy.
Competitive Caching of Contents in 5G Edge Cloud Networks
Venue: arXiv cs.GT 2016
Year: 2016

The surge of mobile data traffic forces network operators to cope with capacity shortage. The deployment of small cells in 5G networks is meant to reduce latency, backhaul traffic and increase radio access capacity. In this context, mobile edge computing technology will be used to manage dedicated cache space in the radio access network. Thus, mobile network operators will be able to provision OTT content providers with new caching services to enhance the quality of experience of their customers on the move. In turn, the cache memory in the mobile edge network will become a shared resource. Hence, we study a competitive caching scheme where contents are stored at given price set by the mobile network operator. We first formulate a resource allocation problem for a tagged content provider seeking to minimize the expected missed cache rate. The optimal caching policy is derived accounting for popularity and availability of contents, the spatial distribution of small cells, and the caching strategies of competing content providers. It is showed to induce a specific order on contents to be cached based on their popularity and availability. Next, we study a game among content providers in the form of a generalized Kelly mechanism with bounded strategy sets and heterogeneous players. Existence and uniqueness of the Nash equilibrium are proved. Finally, extensive numerical results validate and characterize the performance of the model.
A Stochastic Geometry-based Demand Response Management Framework for Cellular Networks Powered by Smart Grid
Venue: arXiv cs.SY 2016
Year: 2016

In this paper, the production decisions across multiple energy suppliers in smart grid, powering cellular networks are investigated. The suppliers are characterized by different offered prices and pollutant emissions levels. The challenge is to decide the amount of energy provided by each supplier to each of the operators such that their profitability is maximized while respecting the maximum tolerated level of CO2 emissions. The cellular operators are characterized by their offered quality of service (QoS) to the subscribers and the number of users that determines their energy requirements. Stochastic geometry is used to determine the average power needed to achieve the target probability of coverage for each operator. The total average power requirements of all networks are fed to an optimization framework to find the optimal amount of energy to be provided from each supplier to the operators. The generalized $α$-fair utility function is used to avoid production bias among the suppliers based on profitability of generation. Results illustrate the production behavior of the energy suppliers versus QoS level, cost of energy, capacity of generation, and level of fairness.
Incremental View Maintenance for Deductive Graph Databases Using Generalized Discrimination Networks
Venue: arXiv cs.DB 2016
Year: 2016

Nowadays, graph databases are employed when relationships between entities are in the scope of database queries to avoid performance-critical join operations of relational databases. Graph queries are used to query and modify graphs stored in graph databases. Graph queries employ graph pattern matching that is NP-complete for subgraph isomorphism. Graph database views can be employed that keep ready answers in terms of precalculated graph pattern matches for often stated and complex graph queries to increase query performance. However, such graph database views must be kept consistent with the graphs stored in the graph database. In this paper, we describe how to use incremental graph pattern matching as technique for maintaining graph database views. We present an incremental maintenance algorithm for graph database views, which works for imperatively and declaratively specified graph queries. The evaluation shows that our maintenance algorithm scales when the number of nodes and edges stored in the graph database increases. Furthermore, our evaluation shows that our approach can outperform existing approaches for the incremental maintenance of graph query results.
Binary Subspace Coding for Query-by-Image Video Retrieval
Venue: arXiv cs.MM 2016
Year: 2016

The query-by-image video retrieval (QBIVR) task has been attracting considerable research attention recently. However, most existing methods represent a video by either aggregating or projecting all its frames into a single datum point, which may easily cause severe information loss. In this paper, we propose an efficient QBIVR framework to enable an effective and efficient video search with image query. We first define a similarity-preserving distance metric between an image and its orthogonal projection in the subspace of the video, which can be equivalently transformed to a Maximum Inner Product Search (MIPS) problem. Besides, to boost the efficiency of solving the MIPS problem, we propose two asymmetric hashing schemes, which bridge the domain gap of images and videos. The first approach, termed Inner-product Binary Coding (IBC), preserves the inner relationships of images and videos in a common Hamming space. To further improve the retrieval efficiency, we devise a Bilinear Binary Coding (BBC) approach, which employs compact bilinear projections instead of a single large projection matrix. Extensive experiments have been conducted on four real-world video datasets to verify the effectiveness of our proposed approaches as compared to the state-of-the-arts.
Managing Usability and Reliability Aspects in Cloud Computing
Venue: arXiv cs.SE 2016
Year: 2016

Cloud computing provides a great opportunity for scientists, as it enables large-scale experiments that cannot are too long to run on local desktop machines. Cloud-based computations can be highly parallel, long running and data-intensive, which is desirable for many kinds of scientific experiments. However, to unlock this power, we need a user-friendly interface and an easy-to-use methodology for conducting these experiments. For this reason, we introduce here a formal model of a cloud-based platform and the corresponding open-source implementation. The proposed solution allows to conduct experiments without having a deep technical understanding of cloud-computing, HPC, fault tolerance, or data management in order to leverage the benefits of cloud computing. In the current version, we have focused on biophysics and structural chemistry experiments, based on the analysis of big data from synchrotrons and atomic force microscopy. The domain experts noted the time savings for computing and data management, as well as user-friendly interface.
Model-based generation of natural language specifications
Venue: arXiv cs.SE 2016
Year: 2016

Application of formal models provides many benefits for the software and system development, however, the learning curve of formal languages could be a critical factor for an industrial project. Thus, a natural language specification that reflects all the aspects of the formal model might help to understand the model and be especially useful for the stakeholders who do not know the corresponding formal language. Moreover, an automated generation of the documentation from the model would replace manual updates of the documentation for the cases the model is modified. This paper presents an ongoing work on generating natural language specifications from formal models. Our goal is to generate documentation in English from the basic modelling artefacts, such as data types, state machines, and architectural components. To allow further formal analysis of the generated specification, we restrict English to its subset, Attempto Controlled English.
Fleet Size and Mix Split-Delivery Vehicle Routing
Venue: arXiv cs.AI 2016
Year: 2016

In the classic Vehicle Routing Problem (VRP) a fleet of of vehicles has to visit a set of customers while minimising the operations' costs. We study a rich variant of the VRP featuring split deliveries, an heterogeneous fleet, and vehicle-commodity incompatibility constraints. Our goal is twofold: define the cheapest routing and the most adequate fleet. To do so, we split the problem into two interdependent components: a fleet design component and a routing component. First, we define two Mixed Integer Programming (MIP) formulations for each component. Then we discuss several improvements in the form of valid cuts and symmetry breaking constraints. The main contribution of this paper is a comparison of the four resulting models for this Rich VRP. We highlight their strengths and weaknesses with extensive experiments. Finally, we explore a lightweight integration with Constraint Programming (CP). We use a fast CP model which gives good solutions and use the solution to warm-start our models.
Video Ladder Networks
Venue: arXiv cs.LG 2016
Year: 2016

We present the Video Ladder Network (VLN) for efficiently generating future video frames. VLN is a neural encoder-decoder model augmented at all layers by both recurrent and feedforward lateral connections. At each layer, these connections form a lateral recurrent residual block, where the feedforward connection represents a skip connection and the recurrent connection represents the residual. Thanks to the recurrent connections, the decoder can exploit temporal summaries generated from all layers of the encoder. This way, the top layer is relieved from the pressure of modeling lower-level spatial and temporal details. Furthermore, we extend the basic version of VLN to incorporate ResNet-style residual blocks in the encoder and decoder, which help improving the prediction results. VLN is trained in self-supervised regime on the Moving MNIST dataset, achieving competitive results while having very simple structure and providing fast inference.
Estimating Local Commuting Patterns From Geolocated Twitter Data
Venue: arXiv cs.CY 2016
Year: 2016

The emergence of large stores of transactional data generated by increasing use of digital devices presents a huge opportunity for policymakers to improve their knowledge of the local environment and thus make more informed and better decisions. A research frontier is hence emerging which involves exploring the type of measures that can be drawn from data stores such as mobile phone logs, Internet searches and contributions to social media platforms, and the extent to which these measures are accurate reflections of the wider population. This paper contributes to this research frontier, by exploring the extent to which local commuting patterns can be estimated from data drawn from Twitter. It makes three contributions in particular. First, it shows that simple heuristics drawn from geolocated Twitter data offer a good proxy for local commuting patterns; one which outperforms the major existing method for estimating these patterns (the radiation model). Second, it investigates sources of error in the proxy measure, showing that the model performs better on short trips with higher volumes of commuters; it also looks at demographic biases but finds that, surprisingly, measurements are not significantly affected by the fact that the demographic makeup of Twitter users differs significantly from the population as a whole. Finally, it looks at potential ways of going beyond simple heuristics by incorporating temporal information into models.
PRIMA: Privacy-Preserving Identity and Access Management at Internet-Scale
Venue: arXiv cs.CR 2016
Year: 2016

The management of identities on the Internet has evolved from the traditional approach (where each service provider stores and manages identities) to a federated identity management system (where the identity management is delegated to a set of identity providers). On the one hand, federated identity ensures usability and provides economic benefits to service providers. On the other hand, it poses serious privacy threats to users as well as service providers. The current technology, which is prevalently deployed on the Internet, allows identity providers to track the user's behavior across a broad range of services. In this work, we propose PRIMA, a universal credential-based authentication system for supporting federated identity management in a privacy-preserving manner. Basically, PRIMA does not require any interaction between service providers and identity providers during the authentication process, thus preventing identity providers to profile users' behavior. Moreover, throughout the authentication process, PRIMA provides a mechanism for controlled disclosure of the users' private information. We have conducted comprehensive evaluations of the system to show the feasibility of our approach. Our performance analysis shows that an identity provider can process 1,426 to 3,332 requests per second when the key size is varied from 1024 to 2048-bit, respectively.
Explaining Radiological Emphysema Subtypes with Unsupervised Texture Prototypes: MESA COPD Study
Venue: arXiv cs.CV 2016
Year: 2016

Pulmonary emphysema is traditionally subcategorized into three subtypes, which have distinct radiological appearances on computed tomography (CT) and can help with the diagnosis of chronic obstructive pulmonary disease (COPD). Automated texture-based quantification of emphysema subtypes has been successfully implemented via supervised learning of these three emphysema subtypes. In this work, we demonstrate that unsupervised learning on a large heterogeneous database of CT scans can generate texture prototypes that are visually homogeneous and distinct, reproducible across subjects, and capable of predicting accurately the three standard radiological subtypes. These texture prototypes enable automated labeling of lung volumes, and open the way to new interpretations of lung CT scans with finer subtyping of emphysema.
Design and ARM-embedded implementation of a chaotic map-based multicast scheme for multiuser speech wireless communication
Venue: arXiv cs.CR 2016
Year: 2016

This paper proposes a chaotic map-based multicast scheme for multiuser speech wireless communication and implements it in an ARM platform. The scheme compresses the digital audio signal decoded by a sound card and then encrypts it with a three-level chaotic encryption scheme. First, the position of every bit of the compressed data is permuted randomly with a pseudo-random number sequence (PRNS) generated by a 6-D chaotic map. Then, the obtained data are further permuted in the level of byte with a PRNS generated by a 7-D chaotic map. Finally, it is operated with a multiround chaotic stream cipher. The whole system owns the following merits: the redundancy in the original audio file is reduced effectively and the corresponding unicity distance is increased; the balancing point between a high security level of the system and real-time conduction speed is achieved well. In the ARM implementation, the framework of communication of multicast-multiuser in a subnet and the Internet Group Manage Protocol is adopted to obtain the function of communication between one client and other ones. Comprehensive test results were provided to show the feasibility and security performance of the whole system.
Cross-Lingual Predicate Mapping Between Linked Data Ontologies
Venue: arXiv cs.AI 2016
Year: 2016

Ontologies in different natural languages often differ in quality in terms of richness of schema or richness of internal links. This difference is markedly visible when comparing a rich English language ontology with a non-English language counterpart. Discovering alignment between them is a useful endeavor as it serves as a starting point in bridging the disparity. In particular, our work is motivated by the absence of inter-language links for predicates in the localised versions of DBpedia. In this paper, we propose and demonstrate an ad-hoc system to find possible owl:equivalentProperty links between predicates in ontologies of different natural languages. We seek to achieve this mapping by using pre-existing inter-language links of the resources connected by the given predicate. Thus, our methodology stresses on semantic similarity rather than lexical. Moreover, through an evaluation, we show that our system is capable of outperforming a baseline system that is similar to the one used in recent OAEI campaigns.
Analysis and Evaluation of Real-time and Safety Characteristics of IEEE 802.11p protocol in VANET
Venue: arXiv cs.NI 2016
Year: 2016

The need for safety in transportation systems has increased the popularity and applicability of Vehicular Ad-Hoc Networks (VANETs) in recent years. On-time reception and processing of alarms caused by possible accidents as well as the preventive actions have important roles in reducing human and financial losses in road accidents. In such cases, the performance of safety applications should be evaluated and guaranteed to show whether or not they can ensure the safety of humans and cars. In this paper, we analyze the behavior of Vehicular Ad-Hoc Networks by checking the real-time properties of the IEEE 802.11p protocol using a Colored Petri Net model. To analyze the performance of related standards, simulations are conducted using CPNTools. Standards from European Telecommunications Standards Institute (ETSI), and Vehicle Safety Communications (VSC) are evaluated in this research. We will show that such standards may not completely fulfill the safety requirements in particular situations.
Segmental Convolutional Neural Networks for Detection of Cardiac Abnormality With Noisy Heart Sound Recordings
Venue: arXiv cs.SD 2016
Year: 2016

Heart diseases constitute a global health burden, and the problem is exacerbated by the error-prone nature of listening to and interpreting heart sounds. This motivates the development of automated classification to screen for abnormal heart sounds. Existing machine learning-based systems achieve accurate classification of heart sound recordings but rely on expert features that have not been thoroughly evaluated on noisy recordings. Here we propose a segmental convolutional neural network architecture that achieves automatic feature learning from noisy heart sound recordings. Our experiments show that our best model, trained on noisy recording segments acquired with an existing hidden semi-markov model-based approach, attains a classification accuracy of 87.5% on the 2016 PhysioNet/CinC Challenge dataset, compared to the 84.6% accuracy of the state-of-the-art statistical classifier trained and evaluated on the same dataset. Our results indicate the potential of using neural network-based methods to increase the accuracy of automated classification of heart sound recordings for improved screening of heart diseases.
Play With Me? Understanding and Measuring the Social Aspect of Casual Gaming
Venue: arXiv cs.HC 2016
Year: 2016

Social gaming is today a pervasive phenomenon. Driven by the advent of social networks and the digitization of game distribution. In this paper the impact of digitization and so-cial networks such as Facebook on digital games is de-scribed and evaluated. This impact follows several vectors, including the introduction of new game formats and extend-ing the traditional audiences for games, which in turn has increased industrial revenue. The industry is in turn shaped by new business model such as Free-to-Play, digital distri-bution and the use of viral social features. These changes do not only appear irreversible, but more importantly, play a part in shaping the future of digital game design, notably for mobile devices. The paper presents new knowledge from controlled live experiments from a casual social game across Facebook and mobile platforms, finding positive re-turns by adding social gameplay features. This suggests that not only social network games, but also casual mobile games can benefit from deeper social gameplay mechanics. Given the impact of social features on gameplay, Game An-alytics will need to evolve to be able to handle requirements that arise from the introduction of social features, e.g. how to measure engagement against social features and shaping organic and viral spreading of a game.
Automatic Detection of ADHD and ASD from Expressive Behaviour in RGBD Data
Venue: arXiv cs.CV 2016
Year: 2016

Attention Deficit Hyperactivity Disorder (ADHD) and Autism Spectrum Disorder (ASD) are neurodevelopmental conditions which impact on a significant number of children and adults. Currently, the diagnosis of such disorders is done by experts who employ standard questionnaires and look for certain behavioural markers through manual observation. Such methods for their diagnosis are not only subjective, difficult to repeat, and costly but also extremely time consuming. In this work, we present a novel methodology to aid diagnostic predictions about the presence/absence of ADHD and ASD by automatic visual analysis of a person's behaviour. To do so, we conduct the questionnaires in a computer-mediated way while recording participants with modern RGBD (Colour+Depth) sensors. In contrast to previous automatic approaches which have focussed only detecting certain behavioural markers, our approach provides a fully automatic end-to-end system for directly predicting ADHD and ASD in adults. Using state of the art facial expression analysis based on Dynamic Deep Learning and 3D analysis of behaviour, we attain classification rates of 96% for Controls vs Condition (ADHD/ASD) group and 94% for Comorbid (ADHD+ASD) vs ASD only group. We show that our system is a potentially useful time saving contribution to the diagnostic field of ADHD and ASD.