OpenRaiser/Intern-Atlas huggingface dataset:
A Simple and Space Efficient Segment Tree Implementation
Venue: arXiv cs.DS 2018
Year: 2018

The segment tree is an extremely versatile data structure. In this paper, a new heap based implementation of segment trees is proposed. In such an implementation of segment tree, the structural information associated with the tree nodes can be removed completely. Some primary computational geometry problems such as stabbing counting queries, measure of union of intervals, and maximum clique size of Intervals are used to demonstrate the efficiency of the new heap based segment tree implementation. Each interval in a set $S=\{I_1 ,I_2 ,\cdots,I_n\}$ of $n$ intervals can be insert into or delete from the heap based segment tree in $O(\log n)$ time. All the primary computational geometry problems can be solved efficiently.
Convex Optimization Based Bit Allocation for Light Field Compression under Weighting and Consistency Constraints
Venue: arXiv cs.MM 2018
Year: 2018

Compared with conventional image and video, light field images introduce the weight channel, as well as the visual consistency of rendered view, information that has to be taken into account when compressing the pseudo-temporal-sequence (PTS) created from light field images. In this paper, we propose a novel frame level bit allocation framework for PTS coding. A joint model that measures weighted distortion and visual consistency, combined with an iterative encoding system, yields the optimal bit allocation for each frame by solving a convex optimization problem. Experimental results show that the proposed framework is effective in producing desired distortion distribution based on weights, and achieves up to 24.7% BD-rate reduction comparing to the default rate control algorithm.
Matching and MIS for Uniformly Sparse Graphs in the Low-Memory MPC Model
Venue: arXiv cs.DS 2018
Year: 2018

The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale parallel computation frameworks and has recently gained a lot of importance, especially in the context of classic graph problems. Unsatisfactorily, all current $\text{poly} (\log \log n)$-round MPC algorithms seem to get fundamentally stuck at the linear-memory barrier: their efficiency crucially relies on each machine having space at least linear in the number $n$ of nodes. As this might not only be prohibitively large, but also allows for easy if not trivial solutions for sparse graphs, we are interested in the low-memory MPC model, where the space per machine is restricted to be strongly sublinear, that is, $n^δ$ for any $0<δ<1$. We devise a degree reduction technique that reduces maximal matching and maximal independent set in graphs with arboricity $λ$ to the corresponding problems in graphs with maximum degree $\text{poly}(λ)$ in $O(\log^2 \log n)$ rounds. This gives rise to $O\left(\log^2\log n + T(\text{poly} λ)\right)$-round algorithms, where $T(Δ)$ is the $Δ$-dependency in the round complexity of maximal matching and maximal independent set in graphs with maximum degree $Δ$. A concurrent work by Ghaffari and Uitto shows that $T(Δ)=O(\sqrt{\log Δ})$. For graphs with arboricity $λ=\text{poly}(\log n)$, this almost exponentially improves over Luby's $O(\log n)$-round PRAM algorithm [STOC'85, JALG'86], and constitutes the first $\text{poly} (\log \log n)$-round maximal matching algorithm in the low-memory MPC model, thus breaking the linear-memory barrier. Previously, the only known subpolylogarithmic algorithm, due to Lattanzi et al. [SPAA'11], required strongly superlinear, that is, $n^{1+Ω(1)}$, memory per machine.
Eavesdropping Whilst You're Shopping: Balancing Personalisation and Privacy in Connected Retail Spaces
Venue: arXiv cs.CY 2018
Year: 2018

Physical retailers, who once led the way in tracking with loyalty cards and `reverse appends', now lag behind online competitors. Yet we might be seeing these tables turn, as many increasingly deploy technologies ranging from simple sensors to advanced emotion detection systems, even enabling them to tailor prices and shopping experiences on a per-customer basis. Here, we examine these in-store tracking technologies in the retail context, and evaluate them from both technical and regulatory standpoints. We first introduce the relevant technologies in context, before considering privacy impacts, the current remedies individuals might seek through technology and the law, and those remedies' limitations. To illustrate challenging tensions in this space we consider the feasibility of technical and legal approaches to both a) the recent `Go' store concept from Amazon which requires fine-grained, multi-modal tracking to function as a shop, and b) current challenges in opting in or out of increasingly pervasive passive Wi-Fi tracking. The `Go' store presents significant challenges with its legality in Europe significantly unclear and unilateral, technical measures to avoid biometric tracking likely ineffective. In the case of MAC addresses, we see a difficult-to-reconcile clash between privacy-as-confidentiality and privacy-as-control, and suggest a technical framework which might help balance the two. Significant challenges exist when seeking to balance personalisation with privacy, and researchers must work together, including across the boundaries of preferred privacy definitions, to come up with solutions that draw on both technology and the legal frameworks to provide effective and proportionate protection. Retailers, simultaneously, must ensure that their tracking is not just legal, but worthy of the trust of concerned data subjects.
Multi-time-horizon Solar Forecasting Using Recurrent Neural Network
Venue: arXiv cs.LG 2018
Year: 2018

The non-stationarity characteristic of the solar power renders traditional point forecasting methods to be less useful due to large prediction errors. This results in increased uncertainties in the grid operation, thereby negatively affecting the reliability and increased cost of operation. This research paper proposes a unified architecture for multi-time-horizon predictions for short and long-term solar forecasting using Recurrent Neural Networks (RNN). The paper describes an end-to-end pipeline to implement the architecture along with the methods to test and validate the performance of the prediction model. The results demonstrate that the proposed method based on the unified architecture is effective for multi-horizon solar forecasting and achieves a lower root-mean-squared prediction error compared to the previous best-performing methods which use one model for each time-horizon. The proposed method enables multi-horizon forecasts with real-time inputs, which have a high potential for practical applications in the evolving smart grid.
Tractable Querying and Learning in Hybrid Domains via Sum-Product Networks
Venue: arXiv cs.LG 2018
Year: 2018

Probabilistic representations, such as Bayesian and Markov networks, are fundamental to much of statistical machine learning. Thus, learning probabilistic representations directly from data is a deep challenge, the main computational bottleneck being inference that is intractable. Tractable learning is a powerful new paradigm that attempts to learn distributions that support efficient probabilistic querying. By leveraging local structure, representations such as sum-product networks (SPNs) can capture high tree-width models with many hidden layers, essentially a deep architecture, while still admitting a range of probabilistic queries to be computable in time polynomial in the network size. The leaf nodes in SPNs, from which more intricate mixtures are formed, are tractable univariate distributions, and so the literature has focused on Bernoulli and Gaussian random variables. This is clearly a restriction for handling mixed discrete-continuous data, especially if the continuous features are generated from non-parametric and non-Gaussian distribution families. In this work, we present a framework that systematically integrates SPN structure learning with weighted model integration, a recently introduced computational abstraction for performing inference in hybrid domains, by means of piecewise polynomial approximations of density functions of arbitrary shape. Our framework is instantiated by exploiting the notion of propositional abstractions, thus minimally interfering with the SPN structure learning module, and supports a powerful query interface for conditioning on interval constraints. Our empirical results show that our approach is effective, and allows a study of the trade off between the granularity of the learned model and its predictive power.
Modeling and Trade-off for Mobile Communication, Computing and Caching Networks
Venue: arXiv cs.IT 2018
Year: 2018

Computation task service delivery in a computing-enabled and caching-aided multi-user mobile edge computing (MEC) system is studied in this paper, where a MEC server can deliver the input or output datas of tasks to mobile devices over a wireless multicast channel. The computing-enabled and caching-aided mobile devices are able to store the input or output datas of some tasks, and also compute some tasks locally, reducing the wireless bandwidth consumption. The corresponding framework of this system is established, and under the latency constraint, we jointly optimize the caching and computing policy at mobile devices to minimize the required transmission bandwidth. The joint policy optimization problem is shown to be NP-hard, and based on equivalent transformation and exact penalization of the problem, a stationary point is obtained via concave convex procedure (CCCP). Moreover, in a symmetric scenario, gains offered by this approach are derived to analytically understand the influences of caching and computing resources at mobile devices, multicast transmission, the number of mobile devices, as well as the number of tasks on the transmission bandwidth. Our results indicate that exploiting the computing and caching resources at mobile devices can provide significant bandwidth savings.
WordNet-Based Information Retrieval Using Common Hypernyms and Combined Features
Venue: arXiv cs.CL 2018
Year: 2018

Text search based on lexical matching of keywords is not satisfactory due to polysemous and synonymous words. Semantic search that exploits word meanings, in general, improves search performance. In this paper, we survey WordNet-based information retrieval systems, which employ a word sense disambiguation method to process queries and documents. The problem is that in many cases a word has more than one possible direct sense, and picking only one of them may give a wrong sense for the word. Moreover, the previous systems use only word forms to represent word senses and their hypernyms. We propose a novel approach that uses the most specific common hypernym of the remaining undisambiguated multi-senses of a word, as well as combined WordNet features to represent word meanings. Experiments on a benchmark dataset show that, in terms of the MAP measure, our search engine is 17.7% better than the lexical search, and at least 9.4% better than all surveyed search systems using WordNet. Keywords Ontology, word sense disambiguation, semantic annotation, semantic search.
Visualizing test diversity to support test optimisation
Venue: arXiv cs.SE 2018
Year: 2018

Diversity has been used as an effective criteria to optimise test suites for cost-effective testing. Particularly, diversity-based (alternatively referred to as similarity-based) techniques have the benefit of being generic and applicable across different Systems Under Test (SUT), and have been used to automatically select or prioritise large sets of test cases. However, it is a challenge to feedback diversity information to developers and testers since results are typically many-dimensional. Furthermore, the generality of diversity-based approaches makes it harder to choose when and where to apply them. In this paper we address these challenges by investigating: i) what are the trade-off in using different sources of diversity (e.g., diversity of test requirements or test scripts) to optimise large test suites, and ii) how visualisation of test diversity data can assist testers for test optimisation and improvement. We perform a case study on three industrial projects and present quantitative results on the fault detection capabilities and redundancy levels of different sets of test cases. Our key result is that test similarity maps, based on pair-wise diversity calculations, helped industrial practitioners identify issues with their test repositories and decide on actions to improve. We conclude that the visualisation of diversity information can assist testers in their maintenance and optimisation activities.
ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms
Venue: arXiv cs.IR 2018
Year: 2018

This paper describes ANN-Benchmarks, a tool for evaluating the performance of in-memory approximate nearest neighbor algorithms. It provides a standard interface for measuring the performance and quality achieved by nearest neighbor algorithms on different standard data sets. It supports several different ways of integrating $k$-NN algorithms, and its configuration system automatically tests a range of parameter settings for each algorithm. Algorithms are compared with respect to many different (approximate) quality measures, and adding more is easy and fast; the included plotting front-ends can visualise these as images, $\LaTeX$ plots, and websites with interactive plots. ANN-Benchmarks aims to provide a constantly updated overview of the current state of the art of $k$-NN algorithms. In the short term, this overview allows users to choose the correct $k$-NN algorithm and parameters for their similarity search task; in the longer term, algorithm designers will be able to use this overview to test and refine automatic parameter tuning. The paper gives an overview of the system, evaluates the results of the benchmark, and points out directions for future work. Interestingly, very different approaches to $k$-NN search yield comparable quality-performance trade-offs. The system is available at http://ann-benchmarks.com .
Joint Modeling and Optimization of Search and Recommendation
Venue: arXiv cs.IR 2018
Year: 2018

Despite the somewhat different techniques used in developing search engines and recommender systems, they both follow the same goal: helping people to get the information they need at the right time. Due to this common goal, search and recommendation models can potentially benefit from each other. The recent advances in neural network technologies make them effective and easily extendable for various tasks, including retrieval and recommendation. This raises the possibility of jointly modeling and optimizing search ranking and recommendation algorithms, with potential benefits to both. In this paper, we present theoretical and practical reasons to motivate joint modeling of search and recommendation as a research direction. We propose a general framework that simultaneously learns a retrieval model and a recommendation model by optimizing a joint loss function. Our preliminary results on a dataset of product data indicate that the proposed joint modeling substantially outperforms the retrieval and recommendation models trained independently. We list a number of future directions for this line of research that can potentially lead to development of state-of-the-art search and recommendation models.
Scene Learning: Deep Convolutional Networks For Wind Power Prediction by Embedding Turbines into Grid Space
Venue: arXiv cs.LG 2018
Year: 2018

Wind power prediction is of vital importance in wind power utilization. There have been a lot of researches based on the time series of the wind power or speed, but In fact, these time series cannot express the temporal and spatial changes of wind, which fundamentally hinders the advance of wind power prediction. In this paper, a new kind of feature that can describe the process of temporal and spatial variation is proposed, namely, Spatio-Temporal Features. We first map the data collected at each moment from the wind turbine to the plane to form the state map, namely, the scene, according to the relative positions. The scene time series over a period of time is a multi-channel image, i.e. the Spatio-Temporal Features. Based on the Spatio-Temporal Features, the deep convolutional network is applied to predict the wind power, achieving a far better accuracy than the existing methods. Compared with the starge-of-the-art method, the mean-square error (MSE) in our method is reduced by 49.83%, and the average time cost for training models can be shortened by a factor of more than 150.
Wireless Powered Communication Networks: TDD or FDD?
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we compare two common modes of duplexing in wireless powered communication networks (WPCN); namely TDD and FDD. So far, TDD has been the most widely used duplexing technique due to its simplicity. Yet, TDD does not allow the energy transmitter to function continuously, which means to deliver the same amount of energy as that in FDD, the transmitter has to have a higher maximum transmit power. On the other hand, when regulations for power spectral density limits are not restrictive, using FDD may lead to higher throughput than that of TDD by allocating less bandwidth to energy and therefore leaving more bandwidth for data. Hence, the best duplexing technique to choose for a specific problem needs careful examination and evaluation.
Computing Minimum Weight Cycles to Leverage Mispricings in Cryptocurrency Market Networks
Venue: arXiv cs.DM 2018
Year: 2018

Cryptocurrencies such as Bitcoin and Ethereum have recently gained a lot of popularity, not only as a digital form of currency but also as an investment vehicle. Online marketplaces and exchanges allow users across the world to convert between dozens of different cryptocurrencies and regular currencies such as euros or dollars. Due to the novelty of this concept, the volatility of these markets and the differences in maturity and usage of particular marketplaces, currency pairs may appear at multiple marketplaces but at different trading prices. This paper proposes a novel algorithmic approach to take advantage of these mispricings and capitalize upon the pricing differences that exist between exchanges and currency pairs. To do so, we model each combination of a currency and a market as one node in a graph. A directed link between two nodes indicates that a conversion between these two currency/market pairs is possible. The weight of the link relates to the exchange rate of executing this particular currency exchange. To leverage the mispricings, we seek for cycles in the graph such that upon multiplying the weights of the links in the cycle, a value greater than 1 is found and thus a profit can be made. Our goal is to do this efficiently, without exhaustively enumerating all possible cycles in the graph. Therefore, we convert our data and address the problem in terms of finding minimum weight triangles in graphs with integer weights, for which efficient algorithms can be utilized. We experiment with parameter settings (heuristics) related to the conversion of exchange rate data into integer weight values. We show that our approach improves upon a reasonable baseline algorithm in terms of computation time. Furthermore, using a real-world dataset, we demonstrate how the obtained minimal weight cycles indeed unveil a number of currency exchange cycles that result in a net profit.
A Collective Variational Autoencoder for Top-$N$ Recommendation with Side Information
Venue: arXiv cs.IR 2018
Year: 2018

Recommender systems have been studied extensively due to their practical use in many real-world scenarios. Despite this, generating effective recommendations with sparse user ratings remains a challenge. Side information associated with items has been widely utilized to address rating sparsity. Existing recommendation models that use side information are linear and, hence, have restricted expressiveness. Deep learning has been used to capture non-linearities by learning deep item representations from side information but as side information is high-dimensional existing deep models tend to have large input dimensionality, which dominates their overall size. This makes them difficult to train, especially with small numbers of inputs. Rather than learning item representations, which is problematic with high-dimensional side information, in this paper, we propose to learn feature representation through deep learning from side information. Learning feature representations, on the other hand, ensures a sufficient number of inputs to train a deep network. To achieve this, we propose to simultaneously recover user ratings and side information, by using a Variational Autoencoder (VAE). Specifically, user ratings and side information are encoded and decoded collectively through the same inference network and generation network. This is possible as both user ratings and side information are data associated with items. To account for the heterogeneity of user rating and side information, the final layer of the generation network follows different distributions depending on the type of information. The proposed model is easy to implement and efficient to optimize and is shown to outperform state-of-the-art top-$N$ recommendation methods that use side information.
Impact of Digital Time Delay on the Stable Grid Hosting Capacity of Large-scale Centralized Photovoltaic Plant
Venue: arXiv cs.SY 2018
Year: 2018

In view of the trend towards extensive application of digital controllers in the PV inverter of large-scale centralized photovoltaic (LSCPV) plant and the increasing number of grid-connected LSCPV plants, this paper investigates in detail the influence of the digital time delay of the inverter digital controller on the stable grid-hosting capacity of LSCPV plant. The studies are based on the Norton equivalent model of the grid-connected LSCPV system considering the digital time delay when modelling the digital control system of the PV inverter. Taking into account the actual situation in LSCPV plant, the stable grid-hosting capacity of LSCPV is discussed for the cases in which the PV inverters in the LSCPV plant have the same and different digital time delay values by using the root-locus method. Simulation results of the digitally controlled grid-connected LSCPV system model validates the theoretical analysis.
Future Scenarios and Challenges for Security and Privacy
Venue: arXiv cs.CY 2018
Year: 2018

Over the past half-century, technology has evolved beyond our wildest dreams. However, while the benefits of technological growth are undeniable, the nascent Internet did not anticipate the online threats we routinely encounter and the harms which can result. As our world becomes increasingly connected, it is critical we consider what implications current and future technologies have for security and privacy. We approach this challenge by surveying 30 predictions across industry, academia and international organisations to extract a number of common themes. Through this, we distill 10 emerging scenarios and reflect on the impact these might have on a range of stakeholders. Considering gaps in best practice and requirements for further research, we explore how security and privacy might evolve over the next decade. We find that existing guidelines both fail to consider the relationships between stakeholders and do not address the novel risks from wearable devices and insider threats. Our approach rigorously analyses emerging scenarios and suggests future improvements, of crucial importance as we look to pre-empt new technological threats.