OpenRaiser/Intern-Atlas huggingface dataset:
Revocable Hierarchical Identity-Based Encryption from Multilinear Maps
Venue: arXiv cs.CR 2016
Year: 2016

In identity-based encryption (IBE) systems, an efficient key delegation method to manage a large number of users and an efficient key revocation method to handle the dynamic credentials of users are needed. Revocable hierarchical IBE (RHIBE) can provide these two methods by organizing the identities of users as a hierarchy and broadcasting an update key for non-revoked users per each time period. To provide the key revocation functionality, previous RHIBE schemes use a tree-based revocation scheme. However, this approach has an inherent limitation such that the number of update key elements depends on the number of revoked users. In this paper, we propose two new RHIBE schemes in multilinear maps that use the public-key broadcast encryption scheme instead of using the tree-based revocation scheme to overcome the mentioned limitation. In our first RHIBE scheme, the number of private key elements and update key elements is reduced to $O(\ell)$ and $O(\ell)$ respectively where $\ell$ is the depth of a hierarchical identity. In our second RHIBE scheme, we can further reduce the number of private key elements from $O(\ell)$ to $O(1)$.
Process Discovery using Inductive Miner and Decomposition
Venue: arXiv cs.AI 2016
Year: 2016

This report presents a submission to the Process Discovery Contest. The contest is dedicated to the assessment of tools and techniques that discover business process models from event logs. The objective is to compare the efficiency of techniques to discover process models that provide a proper balance between "overfitting" and "underfitting". In the context of the Process Discovery Contest, process discovery is turned into a classification task with a training set and a test set; where a process model needs to decide whether traces are fitting or not. In this report, we first show how we use two discovery techniques, namely: Inductive Miner and Decomposition, to discover process models from the training set using ProM tool. Second, we show how we use replay results to 1) check the rediscoverability of models, and to 2) classify unseen traces (in test logs) as fitting or not. Then, we discuss the classification results of validation logs, the complexity of discovered models, and their impact on the selection of models for submission. The report ends with the pictures of the submitted process models.
Modeling Ambiguity, Subjectivity, and Diverging Viewpoints in Opinion Question Answering Systems
Venue: arXiv cs.IR 2016
Year: 2016

Product review websites provide an incredible lens into the wide variety of opinions and experiences of different people, and play a critical role in helping users discover products that match their personal needs and preferences. To help address questions that can't easily be answered by reading others' reviews, some review websites also allow users to pose questions to the community via a question-answering (QA) system. As one would expect, just as opinions diverge among different reviewers, answers to such questions may also be subjective, opinionated, and divergent. This means that answering such questions automatically is quite different from traditional QA tasks, where it is assumed that a single `correct' answer is available. While recent work introduced the idea of question-answering using product reviews, it did not account for two aspects that we consider in this paper: (1) Questions have multiple, often divergent, answers, and this full spectrum of answers should somehow be used to train the system; and (2) What makes a `good' answer depends on the asker and the answerer, and these factors should be incorporated in order for the system to be more personalized. Here we build a new QA dataset with 800 thousand questions---and over 3.1 million answers---and show that explicitly accounting for personalization and ambiguity leads both to quantitatively better answers, but also a more nuanced view of the range of supporting, but subjective, opinions.
Fast Bayesian Non-Negative Matrix Factorisation and Tri-Factorisation
Venue: arXiv cs.LG 2016
Year: 2016

We present a fast variational Bayesian algorithm for performing non-negative matrix factorisation and tri-factorisation. We show that our approach achieves faster convergence per iteration and timestep (wall-clock) than Gibbs sampling and non-probabilistic approaches, and do not require additional samples to estimate the posterior. We show that in particular for matrix tri-factorisation convergence is difficult, but our variational Bayesian approach offers a fast solution, allowing the tri-factorisation approach to be used more effectively.
The Reverse Cuthill-McKee Algorithm in Distributed-Memory
Venue: arXiv cs.DC 2016
Year: 2016

Ordering vertices of a graph is key to minimize fill-in and data structure size in sparse direct solvers, maximize locality in iterative solvers, and improve performance in graph algorithms. Except for naturally parallelizable ordering methods such as nested dissection, many important ordering methods have not been efficiently mapped to distributed-memory architectures. In this paper, we present the first-ever distributed-memory implementation of the reverse Cuthill-McKee (RCM) algorithm for reducing the profile of a sparse matrix. Our parallelization uses a two-dimensional sparse matrix decomposition. We achieve high performance by decomposing the problem into a small number of primitives and utilizing optimized implementations of these primitives. Our implementation shows strong scaling up to 1024 cores for smaller matrices and up to 4096 cores for larger matrices.
Incremental Nonparametric Weighted Feature Extraction for OnlineSubspace Pattern Classification
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, a new online method based on nonparametric weighted feature extraction (NWFE) is proposed. NWFE was introduced to enjoy optimum characteristics of linear discriminant analysis (LDA) and nonparametric discriminant analysis (NDA) while rectifying their drawbacks. It emphasizes the points near decision boundary by putting greater weights on them and deemphasizes other points. Incremental nonparametric weighted feature extraction (INWFE) is the online version of NWFE. INWFE has advantages of NWFE method such as extracting more than L-1 features in contrast to LDA. It is independent of the class distribution and performs well in complex distributed data. The effects of outliers are reduced due to the nature of its nonparametric scatter matrix. Furthermore, it is possible to add new samples asynchronously, i.e. whenever a new sample becomes available at any given time, it can be added to the algorithm. This is useful for many real world applications since all data cannot be available in advance. This method is implemented on Gaussian and non-Gaussian multidimensional data, a number of UCI datasets and Indian Pine dataset. Results are compared with NWFE in terms of classification accuracy and execution time. For nearest neighbour classifier it shows that this technique converges to NWFE at the end of learning process. In addition, the computational complexity is reduced in comparison with NWFE in terms of execution time.
Cost Efficiency for Economical Mobile Data Traffic Management from Users' Perspective
Venue: arXiv cs.NI 2016
Year: 2016

Explosive demand for wireless internet services has posed critical challenges for wireless network due to its limited capacity. To tackle this hurdle, wireless Internet service providers (WISPs) take the smart data pricing to manage data traffic loads. Meanwhile, from the users' perspective, it is also reasonable and desired to employ mobile data traffic management under the pricing policies of WISPs to improve the economic efficiency of data consumption. In this paper we introduce a concept of cost efficiency for user's mobile data management, defined as the ratio of user's mobile data consumption benefits and its expense. We propose an integrated cost-efficiency-based data traffic management scheme including long-term data demand planning, short-term data traffic pre-scheduling and real-time data traffic management. The real-time data traffic management algorithm is proposed to coordinate user's data consumption to tailor to the pre-scheduled data traffic profile. Numerical results demonstrate the effectiveness of cost efficiency framework in indicating and motivating mobile user's data consumption behavior. The proposed management scheme can effectively motivate the user to adjust its data consumption profile to obtain the optimal data consumption cost efficiency.
Parameterized Dataflow (Extended Abstract)
Venue: arXiv cs.PL 2016
Year: 2016

Dataflow networks have application in various forms of stream processing, for example for parallel processing of multimedia data. The description of dataflow graphs, including their firing behavior, is typically non-compositional and not amenable to separate compilation. This article considers a dataflow language with a type and effect system that captures the firing behavior of actors. This system allows definitions to abstract over actor firing rates, supporting the definition and safe composition of actor definitions where firing rates are not instantiated until a dataflow graph is launched.
Evaluating load balancing policies for performance and energy-efficiency
Venue: arXiv cs.PF 2016
Year: 2016

Nowadays, more and more increasingly hard computations are performed in challenging fields like weather forecasting, oil and gas exploration, and cryptanalysis. Many of such computations can be implemented using a computer cluster with a large number of servers. Incoming computation requests are then, via a so-called load balancing policy, distributed over the servers to ensure optimal performance. Additionally, being able to switch-off some servers during low period of workload, gives potential to reduced energy consumption. Therefore, load balancing forms, albeit indirectly, a trade-off between performance and energy consumption. In this paper, we introduce a syntax for load-balancing policies to dynamically select a server for each request based on relevant criteria, including the number of jobs queued in servers, power states of servers, and transition delays between power states of servers. To evaluate many policies, we implement two load balancers in: (i) iDSL, a language and tool-chain for evaluating service-oriented systems, and (ii) a simulation framework in AnyLogic. Both implementations are successfully validated by comparison of the results.
Static Analysis Using the Cloud
Venue: arXiv cs.DC 2016
Year: 2016

In this paper we describe our experience of using Microsoft Azure cloud computing platform for static analysis. We start by extending Static Driver Verifier to operate in the Microsoft Azure cloud with significant improvements in performance and scalability. We present our results of using SDV on single drivers and driver suites using various configurations of the cloud relative to a local machine. Finally, we describe the Static Module Verifier platform, a highly extensible and configurable platform for static analysis of generic modules, where we have integrated support for verification using a cloud services provider (Microsoft Azure in this case).
Configuring Cloud-Service Interfaces Using Flow Inheritance
Venue: arXiv cs.SE 2016
Year: 2016

Technologies for composition of loosely-coupled web services in a modular and flexible way are in high demand today. On the one hand, the services must be flexible enough to be reused in a variety of contexts. On the other hand, they must be specific enough so that their composition may be provably consistent. The existing technologies (WS-CDL, WSCI and session types) require a behavioural contract associated with each service, which is impossible to derive automatically. Furthermore, neither technology supports flow inheritance: a mechanism that automatically and transparently propagates data through service pipelines. This paper presents a novel mechanism for automatic interface configuration of such services. Instead of checking consistency of the behavioural contracts, our approach focuses solely on that of data formats in the presence of subtyping, polymorphism and flow inheritance. The paper presents a toolchain that automatically derives service interfaces from the code and performs interface configuration taking non-local constraints into account. Although the configuration mechanism is global, the services are compiled separately. As a result, the mechanism does not raise source security issues despite global service availability in adaptable form.
On the IP Traffic Matrix Problem in Hybrid SDN/OSPF Networks
Venue: arXiv cs.NI 2016
Year: 2016

IP networks with a hybrid control plane deploy a distributed routing protocol like OSPF and the centralized paradigm of SDN in parallel. The advantages and disadvantages of a hybrid control plane have already been extensively discussed in the literature. This paper examines to what extent hybrid SDN/OSPF can solve the IP traffic matrix and related monitoring problems, inherent to the IP layer. The problem persists in hybrid networks, as the required SDN byte counters for a complete traffic matrix may not be sufficiently implemented (or even not at all), or the deployed SDN nodes may be too few, or not adequately located in the network. For such cases, we propose to augment the SDN traffic statistics with SNMP-based measurements on IP backup links. We address implementation and network function virtualization aspects of the required hybrid monitoring infrastructure and discuss the timing issues of the measurements based on hands-on experiences in our lab. We furthermore provide a placement algorithm for SDN nodes and backup links that can guarantee a complete IP traffic matrix.
Approximate eigenvalue distribution of a cylindrically isotropic noise sample covariance matrix
Venue: arXiv cs.SY 2016
Year: 2016

The statistical behavior of the eigenvalues of the sample covariance matrix (SCM) plays a key role in determining the performance of adaptive beamformers (ABF) in presence of noise. This paper presents a method to compute the approximate eigenvalue density function (EDF) for the SCM of a \cin{} field when only a finite number of shapshots are available. The EDF of the ensemble covariance matrix (ECM) is modeled as an atomic density with many fewer atoms than the SCM size. The model results in substantial computational savings over more direct methods of computing the EDF. The approximate EDF obtained from this method agrees closely with histograms of eigenvalues obtained from simulation.
Content Selection in Data-to-Text Systems: A Survey
Venue: arXiv cs.CL 2016
Year: 2016

Data-to-text systems are powerful in generating reports from data automatically and thus they simplify the presentation of complex data. Rather than presenting data using visualisation techniques, data-to-text systems use natural (human) language, which is the most common way for human-human communication. In addition, data-to-text systems can adapt their output content to users' preferences, background or interests and therefore they can be pleasant for users to interact with. Content selection is an important part of every data-to-text system, because it is the module that determines which from the available information should be conveyed to the user. This survey initially introduces the field of data-to-text generation, describes the general data-to-text system architecture and then it reviews the state-of-the-art content selection methods. Finally, it provides recommendations for choosing an approach and discusses opportunities for future research.
On the Exact Amount of Missing Information that makes Finding Possible Winners Hard
Venue: arXiv cs.GT 2016
Year: 2016

We consider election scenarios with incomplete information, a situation that arises often in practice. There are several models of incomplete information and accordingly, different notions of outcomes of such elections. In one well-studied model of incompleteness, the votes are given by partial orders over the candidates. In this context we can frame the problem of finding a possible winner, which involves determining whether a given candidate wins in at least one completion of a given set of partial votes for a specific voting rule. The possible winner problem is well-known to be NP-complete in general, and it is in fact known to be NP-complete for several voting rules where the number of undetermined pairs in every vote is bounded only by some constant. In this paper, we address the question of determining precisely the smallest number of undetermined pairs for which the possible winner problem remains NP-complete. In particular, we find the exact values of $t$ for which the possible winner problem transitions to being NP-complete from being in P, where $t$ is the maximum number of undetermined pairs in every vote. We demonstrate tight results for a broad subclass of scoring rules which includes all the commonly used scoring rules (such as plurality, veto, Borda, $k$-approval, and so on), Copeland$^α$ for every $α\in[0,1]$, maximin, and Bucklin voting rules. A somewhat surprising aspect of our results is that for many of these rules, the possible winner problem turns out to be hard even if every vote has at most one undetermined pair of candidates.
Counterfactual Reasoning about Intent for Interactive Navigation in Dynamic Environments
Venue: arXiv cs.RO 2016
Year: 2016

Many modern robotics applications require robots to function autonomously in dynamic environments including other decision making agents, such as people or other robots. This calls for fast and scalable interactive motion planning. This requires models that take into consideration the other agent's intended actions in one's own planning. We present a real-time motion planning framework that brings together a few key components including intention inference by reasoning counterfactually about potential motion of the other agents as they work towards different goals. By using a light-weight motion model, we achieve efficient iterative planning for fluid motion when avoiding pedestrians, in parallel with goal inference for longer range movement prediction. This inference framework is coupled with a novel distributed visual tracking method that provides reliable and robust models for the current belief-state of the monitored environment. This combined approach represents a computationally efficient alternative to previously studied policy learning methods that often require significant offline training or calibration and do not yet scale to densely populated environments. We validate this framework with experiments involving multi-robot and human-robot navigation. We further validate the tracker component separately on much larger scale unconstrained pedestrian data sets.
Estimating the concentration of gold nanoparticles incorporated on Natural Rubber membranes using Multi-Level Starlet Optimal Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

This study consolidates Multi-Level Starlet Segmentation (MLSS) and Multi-Level Starlet Optimal Segmentation (MLSOS), techniques for photomicrograph segmentation that use starlet wavelet detail levels to separate areas of interest in an input image. Several segmentation levels can be obtained using Multi-Level Starlet Segmentation; after that, Matthews correlation coefficient (MCC) is used to choose an optimal segmentation level, giving rise to Multi-Level Starlet Optimal Segmentation. In this paper, MLSOS is employed to estimate the concentration of gold nanoparticles with diameter around 47 nm, reducted on natural rubber membranes. These samples were used on the construction of SERS/SERRS substrates and in the study of natural rubber membranes with incorporated gold nanoparticles influence on Leishmania braziliensis physiology. Precision, recall and accuracy are used to evaluate the segmentation performance, and MLSOS presents accuracy greater than 88% for this application.
Cryptanalysis of a Classical chaos-based cryptosystem with some quantum cryptography features
Venue: arXiv cs.CR 2016
Year: 2016

The application of synchronization theory to build up new cryptosystems has been a hot topic during the last two decades. In this paper we analyze a recent proposal in this field. We pinpoint the main limitations of the software implementation of chaos-based systems designed on the grounds of synchronization theory. In addition, we show that the cryptosystem under evaluation possesses serious security problems that imply a clear reduction of the key space.
Gradual Typing in an Open World
Venue: arXiv cs.PL 2016
Year: 2016

Gradual typing combines static and dynamic typing in the same language, offering the benefits of both to programmers. Static typing provides error detection and strong guarantees while dynamic typing enables rapid prototyping and flexible programming idioms. For programmers to fully take advantage of a gradual type system, however, they must be able to trust their type annotations, and so runtime checks must be performed at the boundaries of static and dynamic code to ensure that static types are respected. Higher order and mutable values cannot be completely checked at these boundaries, and so additional checks must be performed at their use sites. Traditionally, this has been achieved by installing wrappers or proxies on such values that moderate the flow of data between static and dynamic, but these can cause problems if the language supports comparison of object identity or has a foreign function interface. Reticulated Python is a gradually typed variant of Python implemented via a source-to-source translator for Python 3. It implements a proxy-free alternative design named transient casts. This paper presents a formal semantics for transient casts and shows that not only are they sound, but they work in an open-world setting in which the Reticulated translator has only been applied to some of the program; the rest is untranslated Python. We formalize this open world soundness property and use Coq to prove that it holds for Anthill Python, a calculus that models Reticulated Python.
Low-Delay Distributed Source Coding for Time-Varying Sources with Unknown Statistics
Venue: arXiv cs.IT 2016
Year: 2016

We consider a system in which two nodes take correlated measurements of a random source with time-varying and unknown statistics. The observations of the source at the first node are to be losslessly replicated with a given probability of outage at the second node, which receives data from the first node over a constant-rate errorless channel. We develop a system and associated strategies for joint distributed source coding (encoding and decoding) and transmission control in order to achieve low end-to-end delay. Slepian-Wolf coding in its traditional form cannot be applied in our scenario, since the encoder requires the joint statistics of the observations and the associated decoding delay is very high. We analytically evaluate the performance of our strategies and show that the delay achieved by them are order optimal, as the conditional entropy of the source approaches to the channel rate. We also evaluate the performance of our algorithms based on real-world experiments using two cameras recording videos of a scene at different angles. Having realized our schemes, we demonstrated that, even with a very low-complexity quantizer, a compression ratio of approximately 50% is achievable for lossless replication at the decoder, at an average delay of a few seconds.