OpenRaiser/Intern-Atlas huggingface dataset:
Universal Compressed Text Indexing
Venue: arXiv cs.DS 2018
Year: 2018

The rise of repetitive datasets has lately generated a lot of interest in compressed self-indexes based on dictionary compression, a rich and heterogeneous family that exploits text repetitions in different ways. For each such compression scheme, several different indexing solutions have been proposed in the last two decades. To date, the fastest indexes for repetitive texts are based on the run-length compressed Burrows-Wheeler transform and on the Compact Directed Acyclic Word Graph. The most space-efficient indexes, on the other hand, are based on the Lempel-Ziv parsing and on grammar compression. Indexes for more universal schemes such as collage systems and macro schemes have not yet been proposed. Very recently, Kempa and Prezza [STOC 2018] showed that all dictionary compressors can be interpreted as approximation algorithms for the smallest string attractor, that is, a set of text positions capturing all distinct substrings. Starting from this observation, in this paper we develop the first universal compressed self-index, that is, the first indexing data structure based on string attractors, which can therefore be built on top of any dictionary-compressed text representation. Let $γ$ be the size of a string attractor for a text of length $n$. Our index takes $O(γ\log(n/γ))$ words of space and supports locating the $occ$ occurrences of any pattern of length $m$ in $O(m\log n + occ\log^εn)$ time, for any constant $ε>0$. This is, in particular, the first index for general macro schemes and collage systems. Our result shows that the relation between indexing and compression is much deeper than what was previously thought: the simple property standing at the core of all dictionary compressors is sufficient to support fast indexed queries.
Considerations Regarding the Flux Estimation in Induction Generator with Application at the Control of Unconventional Energetic Conversion Systems
Venue: arXiv cs.SY 2018
Year: 2018

The paper presents issues regarding the flux estimation of induction machines. The electrical machines variables estimation represents a major problem in the actual context of modern control approaches, especially of sensorless control strategies. There are considered several implementations of induction machine flux estimators by using the Matlab-Simulink environment and there are drawn the afferent conclusions.
Adaptive Fuzzy Controller for Synchronous Generator
Venue: arXiv cs.SY 2018
Year: 2018

This paper describes a PI fuzzy adaptive control structure. Based on classical PI fuzzy control structure (with integration on controller output) the authors have developed, implemented and validated an on-line self-tuning mechanism of regulator parameter. A study case for validation of proposed tuning mechanism is presented and analyzed with application to control of synchronous generator excitation system.
A General Path-Based Representation for Predicting Program Properties
Venue: arXiv cs.PL 2018
Year: 2018

Predicting program properties such as names or expression types has a wide range of applications. It can ease the task of programming and increase programmer productivity. A major challenge when learning from programs is $\textit{how to represent programs in a way that facilitates effective learning}$. We present a $\textit{general path-based representation}$ for learning from programs. Our representation is purely syntactic and extracted automatically. The main idea is to represent a program using paths in its abstract syntax tree (AST). This allows a learning model to leverage the structured nature of code rather than treating it as a flat sequence of tokens. We show that this representation is general and can: (i) cover different prediction tasks, (ii) drive different learning algorithms (for both generative and discriminative models), and (iii) work across different programming languages. We evaluate our approach on the tasks of predicting variable names, method names, and full types. We use our representation to drive both CRF-based and word2vec-based learning, for programs of four languages: JavaScript, Java, Python and C\#. Our evaluation shows that our approach obtains better results than task-specific handcrafted representations across different tasks and programming languages.
Why Comparing Single Performance Scores Does Not Allow to Draw Conclusions About Machine Learning Approaches
Venue: arXiv cs.LG 2018
Year: 2018

Developing state-of-the-art approaches for specific tasks is a major driving force in our research community. Depending on the prestige of the task, publishing it can come along with a lot of visibility. The question arises how reliable are our evaluation methodologies to compare approaches? One common methodology to identify the state-of-the-art is to partition data into a train, a development and a test set. Researchers can train and tune their approach on some part of the dataset and then select the model that worked best on the development set for a final evaluation on unseen test data. Test scores from different approaches are compared, and performance differences are tested for statistical significance. In this publication, we show that there is a high risk that a statistical significance in this type of evaluation is not due to a superior learning approach. Instead, there is a high risk that the difference is due to chance. For example for the CoNLL 2003 NER dataset we observed in up to 26% of the cases type I errors (false positives) with a threshold of p < 0.05, i.e., falsely concluding a statistically significant difference between two identical approaches. We prove that this evaluation setup is unsuitable to compare learning approaches. We formalize alternative evaluation setups based on score distributions.
Electrical energy prediction study case based on neural networks
Venue: arXiv cs.SY 2018
Year: 2018

This paper presents some considerations regarding the prediction of the electrical energy consumption. It is well known that the central element of a microeconomic analysis is represented by the economical agents actions, actions that follow their own interest such as: the consumer maximization of his satisfaction, the producer maximization of his profit. The study case is focused on the prediction of the sold energy in Banat region. The goal of this study case is to optimize the electrical energy quantity purchased from the producer by the energy distributor in Banat region. The prediction is based on neural networks. There are used feed-forward and Elman type neural networks. In order to enhance the prediction accuracy there have been used both linear and nonlinear preprocessing units. The aspects considered in this paper can be extrapolated in any general case of prediction based application, not only in the already stated case of electrical energy.
Crossing the Architectural Barrier: Evaluating Representative Regions of Parallel HPC Applications
Venue: arXiv cs.PF 2018
Year: 2018

Exascale computing will get mankind closer to solving important social, scientific and engineering problems. Due to high prototyping costs, High Performance Computing (HPC) system architects make use of simulation models for design space exploration and hardware-software co-design. However, as HPC systems reach exascale proportions, the cost of simulation increases, since simulators themselves are largely single-threaded. Tools for selecting representative parts of parallel applications to reduce running costs are widespread, e.g., BarrierPoint achieves this by analysing, in simulation, abstract characteristics such as basic blocks and reuse distances. However, architectures new to HPC have a limited set of tools available. In this work, we provide an independent cross-architectural evaluation on real hardware - across Intel and ARM - of the BarrierPoint methodology, when applied to parallel HPC proxy applications. We present both cases: when the methodology can be applied and when it cannot. In the former case, results show that we can predict the performance of full application execution by running shorter representative sections. In the latter case, we dive into the underlying issues and suggest improvements. We demonstrate a total simulation time reduction of up to 178x, whilst keeping the error below 2.3% for both cycles and instructions.
Evaluation of angular dispersion for various propagation environments in emerging 5G systems
Venue: arXiv cs.IT 2018
Year: 2018

Angular dispersion is the effect of a multi-path propagation observed in received signals. An assessment of this phenomenon is particularly important from the viewpoint of emerging fifth generation (5G) communication systems. In these systems, using the beam-forming and massive multiple-input multiple-output antenna arrays are planned. This phenomenon also has a negative impact on direction finding and older generation communication systems used in an urban environment. In this paper, we present the angular dispersion evaluation for various propagation environments based on simulation studies. This analysis is carried out for different environment types defined in the 3GPP standard model for a selected frequency. In this case, the angular spread is determinated based on the power angular spectrum. This parameter is the basis for the influence evaluation of the propagation environment on the received signal angular dispersion.
Visual-Inertial Teach and Repeat for Aerial Inspection
Venue: arXiv cs.RO 2018
Year: 2018

Industrial facilities often require periodic visual inspections of key installations. Examining these points of interest is time consuming, potentially hazardous or require special equipment to reach. MAVs are ideal platforms to automate this expensive and tedious task. In this work we present a novel system that enables a human operator to teach a visual inspection task to an autonomous aerial vehicle by simply demonstrating the task using a handheld device. To enable robust operation in confined, GPS-denied environments, the system employs the Google Tango visual-inertial mapping framework as the only source of pose estimates. In a first step the operator records the desired inspection path and defines the inspection points. The mapping framework then computes a feature-based localization map, which is shared with the robot. After take-off, the robot estimates its pose based on this map and plans a smooth trajectory through the way points defined by the operator. Furthermore, the system is able to track the poses of other robots or the operator, localized in the same map, and follow them in real-time while keeping a safe distance.
BAGAN: Data Augmentation with Balancing GAN
Venue: arXiv cs.CV 2018
Year: 2018

Image classification datasets are often imbalanced, characteristic that negatively affects the accuracy of deep-learning classifiers. In this work we propose balancing GAN (BAGAN) as an augmentation tool to restore balance in imbalanced datasets. This is challenging because the few minority-class images may not be enough to train a GAN. We overcome this issue by including during the adversarial training all available images of majority and minority classes. The generative model learns useful features from majority classes and uses these to generate images for minority classes. We apply class conditioning in the latent space to drive the generation process towards a target class. The generator in the GAN is initialized with the encoder module of an autoencoder that enables us to learn an accurate class-conditioning in the latent space. We compare the proposed methodology with state-of-the-art GANs and demonstrate that BAGAN generates images of superior quality when trained with an imbalanced dataset.
Noise-based logic gates by operations on the reference system
Venue: arXiv cs.ET 2018
Year: 2018

We propose a new, low-complexity solution to realize multi-input-bit gates acting on exponentially large superpositions in noise-based logic processors. Two examples are shown, the NOT gate and the CNOT gate. The operations can be executed and repeated with polynomial time and hardware complexity. The lack of a solution of this problem had been one of the major issues prohibiting the efficient realization of Shor's algorithm by Instantaneous Noise-Based Logic, which runs on a classical Turing computer with a true random number generator. With the method described in this paper, we are one step closer to this goal.
Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays
Venue: arXiv cs.DS 2018
Year: 2018

Many succinct data structures on the word RAM require precomputed tables to start operating. Usually, the tables can be constructed in sublinear time. In this time, most of a data structure is not initialized, i.e., there is plenty of unused space allocated for the data structure. We present a general framework to store temporarily extra buffers between the real data so that the data can be processed immediately, stored first in the buffers, and then moved into the real data structure after finishing the tables. As an application, we apply our framework to Dodis, Patrascu, and Thorup's data structure (STOC 2010) that emulates c-ary memory and to Farzan and Munro's succinct encoding of arbitrary graphs (TCS 2013). We also use our framework to present an in-place dynamical initializable array.
Secure and Reliable Biometric Access Control for Resource-Constrained Systems and IoT
Venue: arXiv cs.CR 2018
Year: 2018

With the emergence of the Internet-of-Things (IoT), there is a growing need for access control and data protection on low-power, pervasive devices. Biometric-based authentication is promising for IoT due to its convenient nature and lower susceptibility to attacks. However, the costs associated with biometric processing and template protection are nontrivial for smart cards, key fobs, and so forth. In this paper, we discuss the security, cost, and utility of biometric systems and develop two major frameworks for improving them. First, we introduce a new framework for implementing biometric systems based on physical unclonable functions (PUFs) and hardware obfuscation that, unlike traditional software approaches, does not require nonvolatile storage of a biometric template/key. Aside from reducing the risk of compromising the biometric, the nature of obfuscation also provides protection against access control circumvention via malware and fault injection. The PUF provides non-invertibility and non-linkability. Second, a major requirement of the proposed PUF/obfuscation approach is that a reliable (robust) key be generated from the users input biometric. We propose a noiseaware biometric quantization framework capable of generating unique, reliable keys with reduced enrollment time and denoising costs. Finally, we conduct several case studies. In the first, the proposed noise-aware approach is compared to our previous approach for multiple biometric modalities, including popular ones (fingerprint and iris) and emerging cardiovascular ones (ECG and PPG). The results show that ECG provides the best tradeoff between reliability, key length, entropy, and cost. In the second and third case studies, we demonstrate how reliability, denoising costs, and enrollment times can be simultaneously improved by modeling subject intra-variations for ECG.
Structural Properties of Optimal Transmission Policies for Delay-Sensitive Energy Harvesting Wireless Sensors
Venue: arXiv cs.NI 2018
Year: 2018

We consider an energy harvesting sensor transmitting latency-sensitive data over a fading channel. We aim to find the optimal transmission scheduling policy that minimizes the packet queuing delay given the available harvested energy. We formulate the problem as a Markov decision process (MDP) over a state-space spanned by the transmitter's buffer, battery, and channel states, and analyze the structural properties of the resulting optimal value function, which quantifies the long-run performance of the optimal scheduling policy. We show that the optimal value function (i) is non-decreasing and has increasing differences in the queue backlog; (ii) is non-increasing and has increasing differences in the battery state; and (iii) is submodular in the buffer and battery states. Our numerical results confirm these properties and demonstrate that the optimal scheduling policy outperforms a so-called greedy policy in terms of sensor outages, buffer overflows, energy efficiency, and queuing delay.
Rate-distortion functions of non-stationary Markoff chains and their block-independent approximations
Venue: arXiv cs.IT 2018
Year: 2018

It is proved that the limit of the normalized rate-distortion functions of block independent approximations of an irreducible, aperiodic Markoff chain is independent of the initial distribution of the Markoff chain and thus, is also equal to the rate-distortion function of the Markoff chain.
JSweep: A Patch-centric Data-driven Approach for Parallel Sweeps on Large-scale Meshes
Venue: arXiv cs.DC 2018
Year: 2018

In mesh-based numerical simulations, sweep is an important computation pattern. During sweeping a mesh, computations on cells are strictly ordered by data dependencies in given directions. Due to such a serial order, parallelizing sweep is challenging, especially for unstructured and deforming structured meshes. Meanwhile, recent high-fidelity multi-physics simulations of particle transport, including nuclear reactor and inertial confinement fusion, require {\em sweeps} on large scale meshes with billions of cells and hundreds of directions. In this paper, we present JSweep, a parallel data-driven computational framework integrated in the JAxMIN infrastructure. The essential of JSweep is a general patch-centric data-driven abstraction, coupled with a high performance runtime system leveraging hybrid parallelism of MPI+threads and achieving dynamic communication on contemporary multi-core clusters. Built on JSweep, we implement a representative data-driven algorithm, Sn transport, featuring optimizations of vertex clustering, multi-level priority strategy and patch-angle parallelism. Experimental evaluation with two real-world applications on structured and unstructured meshes respectively, demonstrates that JSweep can scale to tens of thousands of processor cores with reasonable parallel efficiency.
Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems
Venue: arXiv cs.DB 2018
Year: 2018

Worst-case optimal join algorithms are the class of join algorithms whose runtime match the worst-case output size of a given join query. While the first provably worst-case optimal join algorithm was discovered relatively recently, the techniques and results surrounding these algorithms grow out of decades of research from a wide range of areas, intimately connecting graph theory, algorithms, information theory, constraint satisfaction, database theory, and geometric inequalities. These ideas are not just paperware: in addition to academic project implementations, two variations of such algorithms are the work-horse join algorithms of commercial database and data analytics engines. This paper aims to be a brief introduction to the design and analysis of worst-case optimal join algorithms. We discuss the key techniques for proving runtime and output size bounds. We particularly focus on the fascinating connection between join algorithms and information theoretic inequalities, and the idea of how one can turn a proof into an algorithm. Finally, we conclude with a representative list of fundamental open problems in this area.
Extreme Scale FMM-Accelerated Boundary Integral Equation Solver for Wave Scattering
Venue: arXiv cs.PF 2018
Year: 2018

Algorithmic and architecture-oriented optimizations are essential for achieving performance worthy of anticipated energy-austere exascale systems. In this paper, we present an extreme scale FMM-accelerated boundary integral equation solver for wave scattering, which uses FMM as a matrix-vector multiplication inside the GMRES iterative method. Our FMM Helmholtz kernels treat nontrivial singular and near-field integration points. We implement highly optimized kernels for both shared and distributed memory, targeting emerging Intel extreme performance HPC architectures. We extract the potential thread- and data-level parallelism of the key Helmholtz kernels of FMM. Our application code is well optimized to exploit the AVX-512 SIMD units of Intel Skylake and Knights Landing architectures. We provide different performance models for tuning the task-based tree traversal implementation of FMM, and develop optimal architecture-specific and algorithm aware partitioning, load balancing, and communication reducing mechanisms to scale up to 6,144 compute nodes of a Cray XC40 with 196,608 hardware cores. With shared memory optimizations, we achieve roughly 77% of peak single precision floating point performance of a 56-core Skylake processor, and on average 60% of peak single precision floating point performance of a 72-core KNL. These numbers represent nearly 5.4x and 10x speedup on Skylake and KNL, respectively, compared to the baseline scalar code. With distributed memory optimizations, on the other hand, we report near-optimal efficiency in the weak scalability study with respect to both the logarithmic communication complexity as well as the theoretical scaling complexity of FMM. In addition, we exhibit up to 85% efficiency in strong scaling. We compute in excess of 2 billion DoF on the full-scale of the Cray XC40 supercomputer.
An Efficient Method to Transform SAT problems to Binary Integer Linear Programming Problem
Venue: arXiv cs.CC 2018
Year: 2018

In computational complexity theory, a decision problem is NP-complete when it is both in NP and NP-hard. Although a solution to a NP-complete can be verified quickly, there is no known algorithm to solve it in polynomial time. There exists a method to reduce a SAT (Satifiability) problem to Subset Sum Problem (SSP) in the literature, however, it can only be applied to small or medium size problems. Our study is to find an efficient method to transform a SAT problem to a mixed integer linear programming problem in larger size. Observing the feature of variable-clauses constraints in SAT, we apply linear inequality model (LIM) to the problem and propose a method called LIMSAT. The new method can work efficiently for very large size problem with thousands of variables and clauses in SAT tested using up-to-date benchmarks.
Reinforcement Learning for Fair Dynamic Pricing
Venue: arXiv cs.LG 2018
Year: 2018

Unfair pricing policies have been shown to be one of the most negative perceptions customers can have concerning pricing, and may result in long-term losses for a company. Despite the fact that dynamic pricing models help companies maximize revenue, fairness and equality should be taken into account in order to avoid unfair price differences between groups of customers. This paper shows how to solve dynamic pricing by using Reinforcement Learning (RL) techniques so that prices are maximized while keeping a balance between revenue and fairness. We demonstrate that RL provides two main features to support fairness in dynamic pricing: on the one hand, RL is able to learn from recent experience, adapting the pricing policy to complex market environments; on the other hand, it provides a trade-off between short and long-term objectives, hence integrating fairness into the model's core. Considering these two features, we propose the application of RL for revenue optimization, with the additional integration of fairness as part of the learning procedure by using Jain's index as a metric. Results in a simulated environment show a significant improvement in fairness while at the same time maintaining optimisation of revenue.