OpenRaiser/Intern-Atlas huggingface dataset:
Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm
Venue: arXiv cs.DS 2017
Year: 2017

We describe a new cardinality estimation algorithm that is extremely space-efficient. It applies one of three novel estimators to the compressed state of the Flajolet-Martin-85 coupon collection process. In an apples-to-apples empirical comparison against compressed HyperLogLog sketches, the new algorithm simultaneously wins on all three dimensions of the time/space/accuracy tradeoff. Our prototype uses the zstd compression library, and produces sketches that are smaller than the entropy of HLL, so no possible implementation of compressed HLL can match its space efficiency. The paper's technical contributions include analyses and simulations of the three new estimators, accurate values for the entropies of FM85 and HLL, and a non-trivial method for estimating a double asymptotic limit via simulation.
Static Graph Challenge: Subgraph Isomorphism
Venue: arXiv cs.DC 2017
Year: 2017

The rise of graph analytic systems has created a need for ways to measure and compare the capabilities of these systems. Graph analytics present unique scalability difficulties. The machine learning, high performance computing, and visual analytics communities have wrestled with these difficulties for decades and developed methodologies for creating challenges to move these communities forward. The proposed Subgraph Isomorphism Graph Challenge draws upon prior challenges from machine learning, high performance computing, and visual analytics to create a graph challenge that is reflective of many real-world graph analytics processing systems. The Subgraph Isomorphism Graph Challenge is a holistic specification with multiple integrated kernels that can be run together or independently. Each kernel is well defined mathematically and can be implemented in any programming environment. Subgraph isomorphism is amenable to both vertex-centric implementations and array-based implementations (e.g., using the GraphBLAS.org standard). The computations are simple enough that performance predictions can be made based on simple computing hardware models. The surrounding kernels provide the context for each kernel that allows rigorous definition of both the input and the output for each kernel. Furthermore, since the proposed graph challenge is scalable in both problem size and hardware, it can be used to measure and quantitatively compare a wide range of present day and future systems. Serial implementations in C++, Python, Python with Pandas, Matlab, Octave, and Julia have been implemented and their single threaded performance have been measured. Specifications, data, and software are publicly available at GraphChallenge.org.
Multiparameter spectral analysis for aeroelastic instability problems
Venue: arXiv cs.SY 2017
Year: 2017

This paper presents a novel application of multiparameter spectral theory to the study of structural stability, with particular emphasis on aeroelastic flutter. Methods of multiparameter analysis allow the development of new solution algorithms for aeroelastic flutter problems; most significantly, a direct solver for polynomial problems of arbitrary order and size, something which has not before been achieved. Two major variants of this direct solver are presented, and their computational characteristics are compared. Both are effective for smaller problems arising in reduced-order modelling and preliminary design optimization. Extensions and improvements to this new conceptual framework and solution method are then discussed.
Machine Learning Inspired Energy-Efficient Hybrid Precoding for MmWave Massive MIMO Systems
Venue: arXiv cs.IT 2017
Year: 2017

Hybrid precoding is a promising technique for mmWave massive MIMO systems, as it can considerably reduce the number of required radio-frequency (RF) chains without obvious performance loss. However, most of the existing hybrid precoding schemes require a complicated phase shifter network, which still involves high energy consumption. In this paper, we propose an energy-efficient hybrid precoding architecture, where the analog part is realized by a small number of switches and inverters instead of a large number of high-resolution phase shifters. Our analysis proves that the performance gap between the proposed hybrid precoding architecture and the traditional one is small and keeps constant when the number of antennas goes to infinity. Then, inspired by the cross-entropy (CE) optimization developed in machine learning, we propose an adaptive CE (ACE)-based hybrid precoding scheme for this new architecture. It aims to adaptively update the probability distributions of the elements in hybrid precoder by minimizing the CE, which can generate a solution close to the optimal one with a sufficiently high probability. Simulation results verify that our scheme can achieve the near-optimal sum-rate performance and much higher energy efficiency than traditional schemes.
Application of a Convolutional Neural Network for image classification to the analysis of collisions in High Energy Physics
Venue: arXiv cs.CV 2017
Year: 2017

The application of deep learning techniques using convolutional neural networks to the classification of particle collisions in High Energy Physics is explored. An intuitive approach to transform physical variables, like momenta of particles and jets, into a single image that captures the relevant information, is proposed. The idea is tested using a well known deep learning framework on a simulation dataset, including leptonic ttbar events and the corresponding background at 7 TeV from the CMS experiment at LHC, available as Open Data. This initial test shows competitive results when compared to more classical approaches, like those using feedforward neural networks.
Scale-invariant unconstrained online learning
Venue: arXiv cs.LG 2017
Year: 2017

We consider a variant of online convex optimization in which both the instances (input vectors) and the comparator (weight vector) are unconstrained. We exploit a natural scale invariance symmetry in our unconstrained setting: the predictions of the optimal comparator are invariant under any linear transformation of the instances. Our goal is to design online algorithms which also enjoy this property, i.e. are scale-invariant. We start with the case of coordinate-wise invariance, in which the individual coordinates (features) can be arbitrarily rescaled. We give an algorithm, which achieves essentially optimal regret bound in this setup, expressed by means of a coordinate-wise scale-invariant norm of the comparator. We then study general invariance with respect to arbitrary linear transformations. We first give a negative result, showing that no algorithm can achieve a meaningful bound in terms of scale-invariant norm of the comparator in the worst case. Next, we compliment this result with a positive one, providing an algorithm which "almost" achieves the desired bound, incurring only a logarithmic overhead in terms of the norm of the instances.
Single Reference Image based Scene Relighting via Material Guided Filtering
Venue: arXiv cs.CV 2017
Year: 2017

Image relighting is to change the illumination of an image to a target illumination effect without known the original scene geometry, material information and illumination condition. We propose a novel outdoor scene relighting method, which needs only a single reference image and is based on material constrained layer decomposition. Firstly, the material map is extracted from the input image. Then, the reference image is warped to the input image through patch match based image warping. Lastly, the input image is relit using material constrained layer decomposition. The experimental results reveal that our method can produce similar illumination effect as that of the reference image on the input image using only a single reference image.
More declarative tabling in Prolog using multi-prompt delimited control
Venue: arXiv cs.PL 2017
Year: 2017

Several Prolog implementations include a facility for tabling, an alternative resolution strategy which uses memoisation to avoid redundant duplication of computations. Until relatively recently, tabling has required either low-level support in the underlying Prolog engine, or extensive program transormation (de Guzman et al., 2008). An alternative approach is to augment Prolog with low level support for continuation capturing control operators, particularly delimited continuations, which have been investigated in the field of functional programming and found to be capable of supporting a wide variety of computational effects within an otherwise declarative language. This technical report describes an implementation of tabling in SWI Prolog based on delimited control operators for Prolog recently introduced by Schrijvers et al. (2013). In comparison with a previous implementation of tabling for SWI Prolog using delimited control (Desouter et al., 2015), this approach, based on the functional memoising parser combinators of Johnson (1995), stays closer to the declarative core of Prolog, requires less code, and is able to deliver solutions from systems of tabled predicates incrementally (as opposed to finding all solutions before delivering any to the rest of the program). A collection of benchmarks shows that a small number of carefully targeted optimisations yields performance within a factor of about 2 of the optimised version of Desouter et al.'s system currently included in SWI Prolog.
Massively-Parallel Feature Selection for Big Data
Venue: arXiv cs.LG 2017
Year: 2017

We present the Parallel, Forward-Backward with Pruning (PFBP) algorithm for feature selection (FS) in Big Data settings (high dimensionality and/or sample size). To tackle the challenges of Big Data FS PFBP partitions the data matrix both in terms of rows (samples, training examples) as well as columns (features). By employing the concepts of $p$-values of conditional independence tests and meta-analysis techniques PFBP manages to rely only on computations local to a partition while minimizing communication costs. Then, it employs powerful and safe (asymptotically sound) heuristics to make early, approximate decisions, such as Early Dropping of features from consideration in subsequent iterations, Early Stopping of consideration of features within the same iteration, or Early Return of the winner in each iteration. PFBP provides asymptotic guarantees of optimality for data distributions faithfully representable by a causal network (Bayesian network or maximal ancestral graph). Our empirical analysis confirms a super-linear speedup of the algorithm with increasing sample size, linear scalability with respect to the number of features and processing cores, while dominating other competitive algorithms in its class.
Towards Evaluating Size Reduction Techniques for Software Model Checking
Venue: arXiv cs.SE 2017
Year: 2017

Formal verification techniques are widely used for detecting design flaws in software systems. Formal verification can be done by transforming an already implemented source code to a formal model and attempting to prove certain properties of the model (e.g. that no erroneous state can occur during execution). Unfortunately, transformations from source code to a formal model often yield large and complex models, making the verification process inefficient and costly. In order to reduce the size of the resulting model, optimization transformations can be used. Such optimizations include common algorithms known from compiler design and different program slicing techniques. Our paper describes a framework for transforming C programs to a formal model, enhanced by various optimizations for size reduction. We evaluate and compare several optimization algorithms regarding their effect on the size of the model and the efficiency of the verification. Results show that different optimizations are more suitable for certain models, justifying the need for a framework that includes several algorithms.
From Concurrent Programs to Simulating Sequential Programs: Correctness of a Transformation
Venue: arXiv cs.PL 2017
Year: 2017

Frama-C is a software analysis framework that provides a common infrastructure and a common behavioral specification language to plugins that implement various static and dynamic analyses of C programs. Most plugins do not support concurrency. We have proposed Conc2Seq, a Frama-C plugin based on program transformation, capable to leverage the existing huge code base of plugins and to handle concurrent C programs. In this paper we formalize and sketch the proof of correctness of the program transformation principle behind Conc2Seq, and present an effort towards the full mechanization of both the formalization and proofs with the proof assistant Coq.
A Story of Parametric Trace Slicing, Garbage and Static Analysis
Venue: arXiv cs.SE 2017
Year: 2017

This paper presents a proposal (story) of how statically detecting unreachable objects (in Java) could be used to improve a particular runtime verification approach (for Java), namely parametric trace slicing. Monitoring algorithms for parametric trace slicing depend on garbage collection to (i) cleanup data-structures storing monitored objects, ensuring they do not become unmanageably large, and (ii) anticipate the violation of (non-safety) properties that cannot be satisfied as a monitored object can no longer appear later in the trace. The proposal is that both usages can be improved by making the unreachability of monitored objects explicit in the parametric property and statically introducing additional instrumentation points generating related events. The ideas presented in this paper are still exploratory and the intention is to integrate the described techniques into the MarQ monitoring tool for quantified event automata.
Fragmented Monitoring
Venue: arXiv cs.SE 2017
Year: 2017

Field data is an invaluable source of information for testers and developers because it witnesses how software systems operate in real environments, capturing scenarios and configurations relevant to end-users. Unfortunately, collecting traces might be resource-consuming and can significantly affect the user experience, for instance causing annoying slowdowns. Existing monitoring techniques can control the overhead introduced in the applications by reducing the amount of collected data, for instance by collecting each event only with a given probability. However, collecting fewer events limits the amount of information extracted from the field and may fail in providing a comprehensive picture of the behavior of a program. In this paper we present fragmented monitoring, a monitoring technique that addresses the issue of collecting information from the field without annoying users. The key idea of fragmented monitoring is to reduce the overhead by recording partial traces (fragments) instead of full traces, while annotating the beginning and the end of each fragment with state information. These annotations are exploited offline to derive traces that might be likely observed in the field and that could not be collected directly due to the overhead that would be introduced in a program.
Area Protection in Adversarial Path-Finding Scenarios with Multiple Mobile Agents on Graphs: a theoretical and experimental study of target-allocation strategies for defense coordination
Venue: arXiv cs.AI 2017
Year: 2017

We address a problem of area protection in graph-based scenarios with multiple agents. The problem consists of two adversarial teams of agents that move in an undirected graph shared by both teams. Agents are placed in vertices of the graph; at most one agent can occupy a vertex; and they can move into adjacent vertices in a conflict free way. Teams have asymmetric goals: the aim of one team - attackers - is to invade into given area while the aim of the opponent team - defenders - is to protect the area from being entered by attackers by occupying selected vertices. We study strategies for allocating vertices to be occupied by the team of defenders to block attacking agents. We show that the decision version of the problem of area protection is PSPACE-hard under the assumption that agents can allocate their target vertices multiple times. Further we develop various on-line vertex-allocation strategies for the defender team in a simplified variant of the problem with single stage vertex allocation and evaluated their performance in multiple benchmarks. The success of a strategy is heavily dependent on the type of the instance, and so one of the contributions of this work is that we identify suitable vertex-allocation strategies for diverse instance types. In particular, we introduce a simulation-based method that identifies and tries to capture bottlenecks in the graph, that are frequently used by the attackers. Our experimental evaluation suggests that this method often allows a successful defense even in instances where the attackers significantly outnumber the defenders.
Family Shopping Recommendation System Using User Profile and Behavior Data
Venue: arXiv cs.IR 2017
Year: 2017

With the arrival of the big data era, recommendation system has been a hot technology for enterprises to streamline their sales. Recommendation algorithms for individual users have been extensively studied over the past decade. Most existing recommendation systems also focus on individual user recommendations, however in many daily activities, items are recommended to the groups not one person. As an effective means to solve the problem of group recommendation problem,we extend the single user recommendation to group recommendation. Specifically we propose a novel approach for family-based shopping recommendation system. We use the dataset from the real shopping mall consisting of shopping records table, client-profile table and family relationship table. Our algorithm integrates user behavior similarity and user profile similarity to build the user based collaborative filtering model. We evaluate our approach on a real-world shopping mall dataset.
Secure Channel for Molecular Communications
Venue: arXiv cs.IT 2017
Year: 2017

Molecular communication in nanonetworks is an emerging communication paradigm that uses molecules as information carriers. Achieving a secure information exchange is one of the practical challenges that need to be considered to address the potential of molecular communications in nanonetworks. In this article, we have introduced secure channel into molecular communications to prevent eavesdropping. First, we propose a Diffie Hellman algorithm-based method by which communicating nanomachines can exchange a secret key through molecular signaling. Then, we use this secret key to perform ciphering. Also, we present both the algorithm for secret key exchange and the secured molecular communication system. The proposed secured system is found effective in terms of energy consumption.
A Multi-traffic Inter-cell Interference Coordination Scheme in Dense Cellular Networks
Venue: arXiv cs.NI 2017
Year: 2017

This paper proposes a novel semi-distributed and practical ICIC scheme based on the Almost Blank SubFrame (ABSF) approach specified by 3GPP. We define two mathematical programming problems for the cases of guaranteed and best-effort traffic, and use game theory to study the properties of the derived ICIC distributed schemes, which are compared in detail against unaffordable centralized schemes. Based on the analysis of the proposed models, we define Distributed Multi-traffic Scheduling (DMS), a unified distributed framework for adaptive interference-aware scheduling of base stations in future cellular networks which accounts for both guaranteed and best-effort traffic. DMS follows a two-tier approach, consisting of local ABSF schedulers, which perform the resource distribution between guaranteed and best effort traffic, and a lightweight local supervisor, which coordinates ABSF local decisions. As a result of such a two-tier design, DMS requires very light signaling to drive the local schedulers to globally efficient operating points. As shown by means of numerical results, DMS allows to (i) maximize radio resources reuse, (ii) provide requested quality for guaranteed traffic, (iii) minimize the time dedicated to guaranteed traffic to leave room for best-effort traffic, and (iv) maximize resource utilization efficiency for best-effort traffic.
An LSTM-Based Dynamic Customer Model for Fashion Recommendation
Venue: arXiv cs.IR 2017
Year: 2017

Online fashion sales present a challenging use case for personalized recommendation: Stores offer a huge variety of items in multiple sizes. Small stocks, high return rates, seasonality, and changing trends cause continuous turnover of articles for sale on all time scales. Customers tend to shop rarely, but often buy multiple items at once. We report on backtest experiments with sales data of 100k frequent shoppers at Zalando, Europe's leading online fashion platform. To model changing customer and store environments, our recommendation method employs a pair of neural networks: To overcome the cold start problem, a feedforward network generates article embeddings in "fashion space," which serve as input to a recurrent neural network that predicts a style vector in this space for each client, based on their past purchase sequence. We compare our results with a static collaborative filtering approach, and a popularity ranking baseline.
Self-supporting Topology Optimization for Additive Manufacturing
Venue: arXiv cs.CE 2017
Year: 2017

The paper presents a topology optimization approach that designs an optimal structure, called a self-supporting structure, which is ready to be fabricated via additive manufacturing without the usage of additional support structures. Such supports in general have to be created during the fabricating process so that the primary object can be manufactured layer by layer without collapse, which is very time-consuming and waste of material. The proposed approach resolves this problem by formulating the self-supporting requirements as a novel explicit quadratic continuous constraint in the topology optimization problem, or specifically, requiring the number of unsupported elements (in terms of the sum of squares of their densities) to be zero. Benefiting form such novel formulations, computing sensitivity of the self-supporting constraint with respect to the design density is straightforward, which otherwise would require lots of research efforts in general topology optimization studies. The derived sensitivity for each element is only linearly dependent on its sole density, which, different from previous layer-based sensitivities, consequently allows for a parallel implementation and possible higher convergence rate. In addition, a discrete convolution operator is also designed to detect the unsupported elements as involved in each step of optimization iteration, and improves the detection process 100 times as compared with simply enumerating these elements. The approach works for cases of general overhang angle, or general domain, and produces an optimized structures, and their associated optimal compliance, very close to that of the reference structure obtained without considering the self-supporting constraint, as demonstrated by extensive 2D and 3D benchmark examples.