OpenRaiser/Intern-Atlas huggingface dataset:
Subgraph Similarity Search in Large Graphs
Venue: arXiv cs.SI 2015
Year: 2015

One of the major challenges in applications related to social networks, computational biology, collaboration networks etc., is to efficiently search for similar patterns in their underlying graphs. These graphs are typically noisy and contain thousands of vertices and millions of edges. In many cases, the graphs are unlabeled and the notion of similarity is also not well defined. We study the problem of searching an induced subgraph in a large target graph that is most similar to the given query graph. We assume that the query graph and target graph are undirected and unlabeled. We use graphlet kernels \cite{shervashidze2009efficient} to define graph similarity. Graphlet kernels are known to perform better than other kernels in different applications. Our algorithm maps topological neighborhood information of vertices in the query and target graphs to vectors. These local topological informations are then combined to find a target subgraph having highly similar global topology with the given query graph. We tested our algorithm on several real world networks such as facebook network, google plus network, youtube network, amazon network etc. Most of them contain thousands of vertices and million edges. Our algorithm is able to detect highly similar matches when queried in these networks. Our multi-threaded implementation takes about one second to find the match on a 32 core machine, excluding the time for one time preprocessing. Computationally expensive parts of our algorithm can be further scaled to standard parallel and distributed frameworks like map-reduce.
Single-Pole IIR Channel Power Prediction with Variable Delays
Venue: arXiv cs.IT 2015
Year: 2015

Exploiting outdated channel quality indicators is crucial in most adaptive wireless communication systems. This is often done through channel prediction based on previous received indicators. In this paper, we analyze the case where the feedback delay experienced by the quality indicators is not constant, but random. Focusing on a single-pole IIR predictor, we obtain analytical expressions for the MSE and the filter parameters, and study the throughput behavior through Monte Carlo simulations. Results show that prediction provides a performance advantage for average delays smaller than 30 ms for low terminal speeds.
A thermodynamical approach towards multi-criteria decision making (MCDM)
Venue: arXiv cs.AI 2015
Year: 2015

In multi-criteria decision making (MCDM) problems, ratings are assigned to the alternatives on different criteria by the expert group. In this paper, we propose a thermodynamically consistent model for MCDM using the analogies for thermodynamical indicators - energy, exergy and entropy. The most commonly used method for analysing MCDM problem is Technique for Order of Preference by Similarity to Ideal Solution (TOPSIS). The conventional TOPSIS method uses a measure similar to that of energy for the ranking of alternatives. We demonstrate that the ranking of the alternatives is more meaningful if we use exergy in place of energy. The use of exergy is superior due to the inclusion of a factor accounting for the quality of the ratings by the expert group. The unevenness in the ratings by the experts is measured by entropy. The procedure for the calculation of the thermodynamical indicators is explained in both crisp and fuzzy environment. Finally, two case studies are carried out to demonstrate effectiveness of the proposed model.
Link Regime and Power Savings of Decode-Forward Relaying in Fading Channels
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we re-examine the relay channel under the decode-forward (DF) strategy. Contrary to the established belief that block Markov coding is always the rate-optimal DF strategy, under certain channel conditions (a link regime), independent signaling between the source and relay achieves the same transmission rate without requiring coherent channel phase information. Further, this independent signaling regime allows the relay to conserve power. As such, we design a composite DF relaying strategy that achieves the same rate as block Markov DF but with less required relay power. The finding is attractive from the link adaptation perspective to adapt relay coding and relay power according to the link state. We examine this link adaptation in fading under both perfect channel state information (CSI) and practical CSI, in which nodes have perfect receive and long-term transmit CSI, and derive the corresponding relay power savings in both cases. We also derive the outage probability of the composite relaying scheme which adapts the signaling to the link regime. Through simulation, we expose a novel trade-off for relay placement showing that the relay conserves the most power when closer to the destination but achieves the most rate gain when closer to the source.
Tandem Queueing Systems Maximum Throughput Problem
Venue: arXiv cs.PF 2015
Year: 2015

In this paper we consider the problem of maximum throughput for tandem queueing system. We modeled this system as a Quasi-Birth-Death process. In order to do this we named level the number of customers waiting in the first buffer (including the customer in service) and we called phase the state of the remining servers. Using this model we studied the problem of maximum throughput of the system: the maximum arrival rate that a given system could support before becoming saturated, or unstable. We considered different particular cases of such systems, which were obtained by modifying the capacity of the intermediary buffers, the arrival rate and the service rates. The results of the simulations are presented in our paper and can be summed up in the following conclusions: 1. The analytic formula for the maximum throughput of the system tends to become rather complicated when the number of servers increase 2. The maximum throughput of the system converges as the number of servers increases 3. The homogeneous case reveals an interesting characteristic: if we reverse the order of the servers, maximum thruoughput of the system remains unchanged The QBD process used for the case of Poisson arrivals can be extended to model more general arrival processes.
Energy Consumption Forecasting for Smart Meters
Venue: arXiv cs.OH 2015
Year: 2015

Earth, water, air, food, shelter and energy are essential factors required for human being to survive on the planet. Among this energy plays a key role in our day to day living including giving lighting, cooling and heating of shelter, preparation of food. Due to this interdependency, energy, specifically electricity, production and distribution became a high tech industry. Unlike other industries, the key differentiator of electricity industry is the product itself. It can be produced but cannot be stored for future; production and consumption happen almost in near real-time. This particular peculiarity of the industry is the key driver for Machine Learning and Data Science based innovations in this industry. There is always a gap between the demand and supply in the electricity market across the globe. To fill the gap and improve the service efficiency through providing necessary supply to the market, commercial as well as federal electricity companies employ forecasting techniques to predict the future demand and try to meet the demand and provide curtailment guidelines to optimise the electricity consumption/demand. In this paper the authors examine the application of Machine Learning algorithms, specifically Boosted Decision Tree Regression, to the modelling and forecasting of energy consumption for smart meters. The data used for this exercise is obtained from DECC data website. Along with this data, the methodology has been tested in Smart Meter data obtained from EMA Singapore. This paper focuses on feature engineering for time series forecasting using regression algorithms and deriving a methodology to create personalised electricity plans offers for household users based on usage history.
Modeling Colors of Single Attribute Variations with Application to Food Appearance
Venue: arXiv cs.CV 2015
Year: 2015

This paper considers the intra-image color-space of an object or a scene when these are subject to a dominant single-source of variation. The source of variation can be intrinsic or extrinsic (i.e., imaging conditions) to the object. We observe that the quantized colors for such objects typically lie on a planar subspace of RGB, and in some cases linear or polynomial curves on this plane are effective in capturing these color variations. We also observe that the inter-image color sub-spaces are robust as long as drastic illumination change is not involved. We illustrate the use of this analysis for: discriminating between shading-change and reflectance-change for patches, and object detection, segmentation and recognition based on a single exemplar. We focus on images of food items to illustrate the effectiveness of the proposed approach.
Poseidon: A System Architecture for Efficient GPU-based Deep Learning on Multiple Machines
Venue: arXiv cs.LG 2015
Year: 2015

Deep learning (DL) has achieved notable successes in many machine learning tasks. A number of frameworks have been developed to expedite the process of designing and training deep neural networks (DNNs), such as Caffe, Torch and Theano. Currently they can harness multiple GPUs on a single machine, but are unable to use GPUs that are distributed across multiple machines; as even average-sized DNNs can take days to train on a single GPU with 100s of GBs to TBs of data, distributed GPUs present a prime opportunity for scaling up DL. However, the limited bandwidth available on commodity Ethernet networks presents a bottleneck to distributed GPU training, and prevents its trivial realization. To investigate how to adapt existing frameworks to efficiently support distributed GPUs, we propose Poseidon, a scalable system architecture for distributed inter-machine communication in existing DL frameworks. We integrate Poseidon with Caffe and evaluate its performance at training DNNs for object recognition. Poseidon features three key contributions that accelerate DNN training on clusters: (1) a three-level hybrid architecture that allows Poseidon to support both CPU-only and GPU-equipped clusters, (2) a distributed wait-free backpropagation (DWBP) algorithm to improve GPU utilization and to balance communication, and (3) a structure-aware communication protocol (SACP) to minimize communication overheads. We empirically show that Poseidon converges to same objectives as a single machine, and achieves state-of-art training speedup across multiple models and well-established datasets using a commodity GPU cluster of 8 nodes (e.g. 4.5x speedup on AlexNet, 4x on GoogLeNet, 4x on CIFAR-10). On the much larger ImageNet22K dataset, Poseidon with 8 nodes achieves better speedup and competitive accuracy to recent CPU-based distributed systems such as Adam and Le et al., which use 10s to 1000s of nodes.
Contributions to the compositional semantics of first-order predicate logic
Venue: arXiv cs.LO 2015
Year: 2015

Henkin, Monk and Tarski gave a compositional semantics for first-order predicate logic. We extend this work by including function symbols in the language and by giving the denotation of the atomic formula as a composition of the denotations of its predicate symbol and of its tuple of arguments. In addition we give the denotation of a term as a composition of the denotations of its function symbol and of its tuple of arguments.
Secure Degrees of Freedom of the Gaussian Diamond-Wiretap Channel
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider the Gaussian diamond-wiretap channel that consists of an orthogonal broadcast channel from a source to two relays and a Gaussian fast-fading multiple access-wiretap channel from the two relays to a legitimate destination and an eavesdropper. For the multiple access part, we consider both the case with full channel state information (CSI) and the case with no eavesdropper's CSI, at the relays and the legitimate destination. For both the cases, we establish the exact secure degrees of freedom and generalize the results for multiple relays. For the converse part, we introduce a new technique of capturing the trade-off between the message rate and the amount of individual randomness injected at each relay. In the achievability part, we show (i) how to strike a balance between sending message symbols and common noise symbols from the source to the relays in the broadcast component and (ii) how to combine artificial noise-beamforming and noise-alignment techniques at the relays in the multiple access component. In the case with full CSI, we propose a scheme where the relays simultaneously beamform common noise signals in the null space of the legitimate destination's channel, and align them with the message signals at the eavesdropper. In the case with no eavesdropper's CSI, we present a scheme that efficiently utilizes the broadcast links by incorporating computation between the message and common noise symbols at the source. Finally, most of our achievability and converse techniques can also be adapted to the Gaussian (non-fading) channel model.
Tracking Angles of Departure and Arrival in a Mobile Millimeter Wave Channel
Venue: arXiv cs.IT 2015
Year: 2015

Millimeter wave provides a very promising approach for meeting the ever-growing traffic demand in next generation wireless networks. To utilize this band, it is crucial to obtain the channel state information in order to perform beamforming and combining to compensate for severe path loss. In contrast to lower frequencies, a typical millimeter wave channel consists of a few dominant paths. Thus it is generally sufficient to estimate the path gains, angles of departure (AoDs), and angles of arrival (AoAs) of those paths. Proposed in this paper is a dual timescale model to characterize abrupt channel changes (e.g., blockage) and slow variations of AoDs and AoAs. This work focuses on tracking the slow variations and detecting abrupt changes. A Kalman filter based tracking algorithm and an abrupt change detection method are proposed. The tracking algorithm is compared with the adaptive algorithm due to Alkhateeb, Ayach, Leus and Heath (2014) in the case with single radio frequency chain. Simulation results show that to achieve the same tracking performance, the proposed algorithm requires much lower signal-to-noise-ratio (SNR) and much fewer pilots than the other algorithm. Moreover, the change detection method can always detect abrupt changes with moderate number of pilots and SNR.
SourcererCC: Scaling Code Clone Detection to Big Code
Venue: arXiv cs.SE 2015
Year: 2015

Despite a decade of active research, there is a marked lack in clone detectors that scale to very large repositories of source code, in particular for detecting near-miss clones where significant editing activities may take place in the cloned code. We present SourcererCC, a token-based clone detector that targets three clone types, and exploits an index to achieve scalability to large inter-project repositories using a standard workstation. SourcererCC uses an optimized inverted-index to quickly query the potential clones of a given code block. Filtering heuristics based on token ordering are used to significantly reduce the size of the index, the number of code-block comparisons needed to detect the clones, as well as the number of required token-comparisons needed to judge a potential clone. We evaluate the scalability, execution time, recall and precision of SourcererCC, and compare it to four publicly available and state-of-the-art tools. To measure recall, we use two recent benchmarks, (1) a large benchmark of real clones, BigCloneBench, and (2) a Mutation/Injection-based framework of thousands of fine-grained artificial clones. We find SourcererCC has both high recall and precision, and is able to scale to a large inter-project repository (250MLOC) using a standard workstation.
Machine Ruling
Venue: arXiv cs.CY 2015
Year: 2015

Emerging technologies, such as big data, Internet of things, cloud computing, mobile Internet, and robotics, breed and expedite new applications and fields. In the mean while, the long-term prosperity and happiness of human race demands advanced technologies. In this paper, the aforementioned emerging technologies are applied to management and governance for the long-term prosperity and happiness of human race. The term "machine ruling" is coined, introduced, and justified. Moreover, the framework and architecture of machine ruling are proposed. Enabling technologies and challenges are discussed.
Path computation in multi-layer multi-domain networks: A language theoretic approach
Venue: arXiv cs.DS 2015
Year: 2015

Multi-layer networks are networks in which several protocols may coexist at different layers. The Pseudo-Wire architecture provides encapsulation and de-capsulation functions of protocols over Packet-Switched Networks. In a multi-domain context, computing a path to support end-to-end services requires the consideration of encapsulation and decapsulation capabilities. It appears that graph models are not expressive enough to tackle this problem. In this paper, we propose a new model of heterogeneous networks using Automata Theory. A network is modeled as a Push-Down Automaton (PDA) which is able to capture the encapsulation and decapsulation capabilities, the PDA stack corresponding to the stack of encapsulated protocols. We provide polynomial algorithms that compute the shortest path either in hops or in the number of encapsulations and decapsulations along the inter-domain path, the latter reducing manual configurations and possible loops in the path.
Spatial Phase-Sweep: Increasing temporal resolution of transient imaging using a light source array
Venue: arXiv cs.CV 2015
Year: 2015

Transient imaging or light-in-flight techniques capture the propagation of an ultra-short pulse of light through a scene, which in effect captures the optical impulse response of the scene. Recently, it has been shown that we can capture transient images using commercially available Time-of-Flight (ToF) systems such as Photonic Mixer Devices (PMD). In this paper, we propose `spatial phase-sweep', a technique that exploits the speed of light to increase the temporal resolution beyond the 100 picosecond limit imposed by current electronics. Spatial phase-sweep uses a linear array of light sources with spatial separation of about 3 mm between them, thereby resulting in a time shift of about 10 picoseconds, which translates into 100 Gfps of transient imaging in theory. We demonstrate a prototype and transient imaging results using spatial phase-sweep.
The 2015 Sheffield System for Transcription of Multi-Genre Broadcast Media
Venue: arXiv cs.CL 2015
Year: 2015

We describe the University of Sheffield system for participation in the 2015 Multi-Genre Broadcast (MGB) challenge task of transcribing multi-genre broadcast shows. Transcription was one of four tasks proposed in the MGB challenge, with the aim of advancing the state of the art of automatic speech recognition, speaker diarisation and automatic alignment of subtitles for broadcast media. Four topics are investigated in this work: Data selection techniques for training with unreliable data, automatic speech segmentation of broadcast media shows, acoustic modelling and adaptation in highly variable environments, and language modelling of multi-genre shows. The final system operates in multiple passes, using an initial unadapted decoding stage to refine segmentation, followed by three adapted passes: a hybrid DNN pass with input features normalised by speaker-based cepstral normalisation, another hybrid stage with input features normalised by speaker feature-MLLR transformations, and finally a bottleneck-based tandem stage with noise and speaker factorisation. The combination of these three system outputs provides a final error rate of 27.5% on the official development set, consisting of 47 multi-genre shows.
$K$ Users Caching Two Files: An Improved Achievable Rate
Venue: arXiv cs.IT 2015
Year: 2015

Caching is an approach to smoothen the variability of traffic over time. Recently it has been proved that the local memories at the users can be exploited for reducing the peak traffic in a much more efficient way than previously believed. In this work we improve upon the existing results and introduce a novel caching strategy that takes advantage of simultaneous coded placement and coded delivery in order to decrease the worst case achievable rate with $2$ files and $K$ users. We will show that for any cache size $\frac{1}{K}<M<1$ our scheme outperforms the state of the art.
Multivariate Time Series Classification Using Dynamic Time Warping Template Selection for Human Activity Recognition
Venue: arXiv cs.AI 2015
Year: 2015

Accurate and computationally efficient means for classifying human activities have been the subject of extensive research efforts. Most current research focuses on extracting complex features to achieve high classification accuracy. We propose a template selection approach based on Dynamic Time Warping, such that complex feature extraction and domain knowledge is avoided. We demonstrate the predictive capability of the algorithm on both simulated and real smartphone data.
Research on Scalability of Operating Systems on Multicore Processors
Venue: arXiv cs.OS 2015
Year: 2015

Large number of cores and hardware resource sharing are two characteristics on multicore processors, which bring new challenges for the design of operating systems. How to locate and analyze the speedup restrictive factors in operating systems, how to simulate and avoid the phenomenon that speedup decreases with the number of cores because of lock contention (i.e., lock thrashing) and how to avoid the contention of shared resources such as the last level cache are key challenges for the operating system scalability research on multicore systems.
Transformed Residual Quantization for Approximate Nearest Neighbor Search
Venue: arXiv cs.CV 2015
Year: 2015

The success of product quantization (PQ) for fast nearest neighbor search depends on the exponentially reduced complexities of both storage and computation with respect to the codebook size. Recent efforts have been focused on employing sophisticated optimization strategies, or seeking more effective models. Residual quantization (RQ) is such an alternative that holds the same property as PQ in terms of the aforementioned complexities. In addition to being a direct replacement of PQ, hybrids of PQ and RQ can yield more gains for approximate nearest neighbor search. This motivated us to propose a novel approach to optimizing RQ and the related hybrid models. With an observation of the general randomness increase in a residual space, we propose a new strategy that jointly learns a local transformation per residual cluster with an ultimate goal to reduce overall quantization errors. We have shown that our approach can achieve significantly better accuracy on nearest neighbor search than both the original and the optimized PQ on several very large scale benchmarks.