OpenRaiser/Intern-Atlas huggingface dataset:
Synthesizing Short-Circuiting Validation of Data Structure Invariants
Venue: arXiv cs.PL 2015
Year: 2015

This paper presents incremental verification-validation, a novel approach for checking rich data structure invariants expressed as separation logic assertions. Incremental verification-validation combines static verification of separation properties with efficient, short-circuiting dynamic validation of arbitrarily rich data constraints. A data structure invariant checker is an inductive predicate in separation logic with an executable interpretation; a short-circuiting checker is an invariant checker that stops checking whenever it detects at run time that an assertion for some sub-structure has been fully proven statically. At a high level, our approach does two things: it statically proves the separation properties of data structure invariants using a static shape analysis in a standard way but then leverages this proof in a novel manner to synthesize short-circuiting dynamic validation of the data properties. As a consequence, we enable dynamic validation to make up for imprecision in sound static analysis while simultaneously leveraging the static verification to make the remaining dynamic validation efficient. We show empirically that short-circuiting can yield asymptotic improvements in dynamic validation, with low overhead over no validation, even in cases where static verification is incomplete.
A Survey of Heterogeneous Information Network Analysis
Venue: arXiv cs.SI 2015
Year: 2015

Most real systems consist of a large number of interacting, multi-typed components, while most contemporary researches model them as homogeneous networks, without distinguishing different types of objects and links in the networks. Recently, more and more researchers begin to consider these interconnected, multi-typed data as heterogeneous information networks, and develop structural analysis approaches by leveraging the rich semantic meaning of structural types of objects and links in the networks. Compared to widely studied homogeneous network, the heterogeneous information network contains richer structure and semantic information, which provides plenty of opportunities as well as a lot of challenges for data mining. In this paper, we provide a survey of heterogeneous information network analysis. We will introduce basic concepts of heterogeneous information network analysis, examine its developments on different data mining tasks, discuss some advanced topics, and point out some future research directions.
Tales told by coloured tangles
Venue: arXiv cs.IT 2015
Year: 2015

Tangle machines are a topologically inspired diagrammatic formalism to describe information flow in networks. This paper begins with an expository account of tangle machines motivated by the problem of describing `covariance intersection' fusion of Gaussian estimators in networks. It then gives two examples in which tangle machines tell stories of adiabatic quantum computations, and discusses learning tangle machines from data.
Eventually Consistent Register Revisited
Venue: arXiv cs.DC 2015
Year: 2015

In order to converge in the presence of concurrent updates, modern eventually consistent replication systems rely on causality information and operation semantics. It is relatively easy to use semantics of high-level operations on replicated data structures, such as sets, lists, etc. However, it is difficult to exploit semantics of operations on registers, which store opaque data. In existing register designs, concurrent writes are resolved either by the application, or by arbitrating them according to their timestamps. The former is complex and may require user intervention, whereas the latter causes arbitrary updates to be lost. In this work, we identify a register construction that generalizes existing ones by combining runtime causality ordering, to identify concurrent writes, with static data semantics, to resolve them. We propose a simple conflict resolution template based on an application-predefined order on the domain of values. It eliminates or reduces the number of conflicts that need to be resolved by the user or by an explicit application logic. We illustrate some variants of our approach with use cases, and how it generalizes existing designs.
Handcrafted Local Features are Convolutional Neural Networks
Venue: arXiv cs.CV 2015
Year: 2015

Image and video classification research has made great progress through the development of handcrafted local features and learning based features. These two architectures were proposed roughly at the same time and have flourished at overlapping stages of history. However, they are typically viewed as distinct approaches. In this paper, we emphasize their structural similarities and show how such a unified view helps us in designing features that balance efficiency and effectiveness. As an example, we study the problem of designing efficient video feature learning algorithms for action recognition. We approach this problem by first showing that local handcrafted features and Convolutional Neural Networks (CNNs) share the same convolution-pooling network structure. We then propose a two-stream Convolutional ISA (ConvISA) that adopts the convolution-pooling structure of the state-of-the-art handcrafted video feature with greater modeling capacities and a cost-effective training algorithm. Through custom designed network structures for pixels and optical flow, our method also reflects distinctive characteristics of these two data sources. Our experimental results on standard action recognition benchmarks show that by focusing on the structure of CNNs, rather than end-to-end training methods, we are able to design an efficient and powerful video feature learning algorithm.
Understanding learned CNN features through Filter Decoding with Substitution
Venue: arXiv cs.CV 2015
Year: 2015

In parallel with the success of CNNs to solve vision problems, there is a growing interest in developing methodologies to understand and visualize the internal representations of these networks. How the responses of a trained CNN encode the visual information is a fundamental question both for computer and human vision research. Image representations provided by the first convolutional layer as well as the resolution change provided by the max-polling operation are easy to understand, however, as soon as a second and further convolutional layers are added in the representation, any intuition is lost. A usual way to deal with this problem has been to define deconvolutional networks that somehow allow to explore the internal representations of the most important activations towards the image space, where deconvolution is assumed as a convolution with the transposed filter. However, this assumption is not the best approximation of an inverse convolution. In this paper we propose a new assumption based on filter substitution to reverse the encoding of a convolutional layer. This provides us with a new tool to directly visualize any CNN single neuron as a filter in the first layer, this is in terms of the image space.
Learning Expressionlets via Universal Manifold Model for Dynamic Facial Expression Recognition
Venue: arXiv cs.CV 2015
Year: 2015

Facial expression is temporally dynamic event which can be decomposed into a set of muscle motions occurring in different facial regions over various time intervals. For dynamic expression recognition, two key issues, temporal alignment and semantics-aware dynamic representation, must be taken into account. In this paper, we attempt to solve both problems via manifold modeling of videos based on a novel mid-level representation, i.e. \textbf{expressionlet}. Specifically, our method contains three key stages: 1) each expression video clip is characterized as a spatial-temporal manifold (STM) formed by dense low-level features; 2) a Universal Manifold Model (UMM) is learned over all low-level features and represented as a set of local modes to statistically unify all the STMs. 3) the local modes on each STM can be instantiated by fitting to UMM, and the corresponding expressionlet is constructed by modeling the variations in each local mode. With above strategy, expression videos are naturally aligned both spatially and temporally. To enhance the discriminative power, the expressionlet-based STM representation is further processed with discriminant embedding. Our method is evaluated on four public expression databases, CK+, MMI, Oulu-CASIA, and FERA. In all cases, our method outperforms the known state-of-the-art by a large margin.
Semi-supervised Collaborative Ranking with Push at Top
Venue: arXiv cs.LG 2015
Year: 2015

Existing collaborative ranking based recommender systems tend to perform best when there is enough observed ratings for each user and the observation is made completely at random. Under this setting recommender systems can properly suggest a list of recommendations according to the user interests. However, when the observed ratings are extremely sparse (e.g. in the case of cold-start users where no rating data is available), and are not sampled uniformly at random, existing ranking methods fail to effectively leverage side information to transduct the knowledge from existing ratings to unobserved ones. We propose a semi-supervised collaborative ranking model, dubbed \texttt{S$^2$COR}, to improve the quality of cold-start recommendation. \texttt{S$^2$COR} mitigates the sparsity issue by leveraging side information about both observed and missing ratings by collaboratively learning the ranking model. This enables it to deal with the case of missing data not at random, but to also effectively incorporate the available side information in transduction. We experimentally evaluated our proposed algorithm on a number of challenging real-world datasets and compared against state-of-the-art models for cold-start recommendation. We report significantly higher quality recommendations with our algorithm compared to the state-of-the-art.
Asymptotic Performance Analysis for 1-bit Bayesian Smoothing
Venue: arXiv cs.IT 2015
Year: 2015

Energy-efficient signal processing systems require estimation methods operating on data collected with low-complexity devices. Using analog-to-digital converters (ADC) with $1$-bit amplitude resolution has been identified as a possible option in order to obtain low power consumption. The $1$-bit performance loss, in comparison to an ideal receiver with $\infty$-bit ADC, is well-established and moderate for low SNR applications ($2/π$ or $-1.96$ dB). Recently it has been shown that for parameter estimation with state-space models the $1$-bit performance loss with Bayesian filtering can be significantly smaller ($\sqrt{2/π}$ or $-0.98$ dB). Here we extend the analysis to Bayesian smoothing where additional measurements are used to reconstruct the current state of the system parameter. Our results show that a $1$-bit receiver performing smoothing is able to outperform an ideal $\infty$-bit system carrying out filtering by the cost of an additional processing delay $Δ$.
Active exploration of sensor networks from a robotics perspective
Venue: arXiv cs.RO 2015
Year: 2015

Traditional algorithms for robots who need to integrate into a wireless network often focus on one specific task. In this work we want to develop simple, adaptive and reusable algorithms for real world applications for this scenario. Starting with the most basic task for mobile wireless network nodes, finding the position of another node, we introduce an algorithm able to solve this task. We then show how this algorithm can readily be employed to solve a large number of other related tasks like finding the optimal position to bridge two static network nodes. For this we first introduce a meta-algorithm inspired by autonomous robot learning strategies and the concept of internal models which yields a class of source seeking algorithms for mobile nodes. The effectiveness of this algorithm is demonstrated in real world experiments using a physical mobile robot and standard 802.11 wireless LAN in an office environment. We also discuss the differences to conventional algorithms and give the robotics perspective on this class of algorithms. Then we proceed to show how more complex tasks, which might be encountered by mobile nodes, can be encoded in the same framework and how the introduced algorithm can solve them. These tasks can be direct (cross layer) optimization tasks or can also encode more complex tasks like bridging two network nodes. We choose the bridging scenario as an example, implemented on a real physical robot, and show how the robot can solve it in a real world experiment.
SPIDER: Fault Resilient SDN Pipeline with Recovery Delay Guarantees
Venue: arXiv cs.NI 2015
Year: 2015

When dealing with node or link failures in Software Defined Networking (SDN), the network capability to establish an alternative path depends on controller reachability and on the round trip times (RTTs) between controller and involved switches. Moreover, current SDN data plane abstractions for failure detection (e.g. OpenFlow "Fast-failover") do not allow programmers to tweak switches' detection mechanism, thus leaving SDN operators still relying on proprietary management interfaces (when available) to achieve guaranteed detection and recovery delays. We propose SPIDER, an OpenFlow-like pipeline design that provides i) a detection mechanism based on switches' periodic link probing and ii) fast reroute of traffic flows even in case of distant failures, regardless of controller availability. SPIDER can be implemented using stateful data plane abstractions such as OpenState or Open vSwitch, and it offers guaranteed short (i.e. ms) failure detection and recovery delays, with a configurable trade off between overhead and failover responsiveness. We present here the SPIDER pipeline design, behavioral model, and analysis on flow tables' memory impact. We also implemented and experimentally validated SPIDER using OpenState (an OpenFlow 1.3 extension for stateful packet processing), showing numerical results on its performance in terms of recovery latency and packet losses.
Energy-Efficient Resource Allocation for Wireless Powered Communication Networks
Venue: arXiv cs.IT 2015
Year: 2015

This paper considers a wireless powered communication network (WPCN), where multiple users harvest energy from a dedicated power station and then communicate with an information receiving station. Our goal is to investigate the maximum achievable energy efficiency (EE) of the network via joint time allocation and power control while taking into account the initial battery energy of each user. We first study the EE maximization problem in the WPCN without any system throughput requirement. We show that the EE maximization problem for the WPCN can be cast into EE maximization problems for two simplified networks via exploiting its special structure. For each problem, we derive the optimal solution and provide the corresponding physical interpretation, despite the non-convexity of the problems. Subsequently, we study the EE maximization problem under a minimum system throughput constraint. Exploiting fractional programming theory, we transform the resulting non-convex problem into a standard convex optimization problem. This allows us to characterize the optimal solution structure of joint time allocation and power control and to derive an efficient iterative algorithm for obtaining the optimal solution. Simulation results verify our theoretical findings and demonstrate the effectiveness of the proposed joint time and power optimization.
Model-Driven Automatic Tiling with Cache Associativity Lattices
Venue: arXiv cs.PF 2015
Year: 2015

Traditional compiler optimization theory distinguishes three separate classes of cache miss -- Cold, Conflict and Capacity. Tiling for cache is typically guided by capacity miss counts. Models of cache function have not been effectively used to guide cache tiling optimizations due to model error and expense. Instead, heuristic or empirical approaches are used to select tilings. We argue that conflict misses, traditionally neglected or seen as a small constant effect, are the only fundamentally important cache miss category, that they form a solid basis by which caches can become modellable, and that models leaning on cache associatvity analysis can be used to generate cache performant tilings. We develop a mathematical framework that expresses potential and actual cache misses in associative caches using Associativity Lattices. We show these lattices to possess two theoretical advantages over rectangular tiles -- volume maximization and miss regularity. We also show that to generate such lattice tiles requires, unlike rectangular tiling, no explicit, expensive lattice point counting. We also describe an implementation of our lattice tiling approach, show that it can be used to give speedups of over 10x versus unoptimized code, and despite currently only tiling for one level of cache, can already be competitive with the aggressive compiler optimizations used in general purposes compares such as GCC and Intel's ICC. We also show that the tiling approach can lead to reasonable automatic parallelism when compared to existing auto-threading compilers.
Maximum lifetime broadcasting problem in sensor networks
Venue: arXiv cs.NI 2015
Year: 2015

We solve the maximum lifetime problem for the point-to-point and point-to-multipoint broadcast data transmission in one dimensional regular sensor network. Based on the analytical solution of the problem for one dimension we propose an algorithm solving the maximum lifetime broadcasting problem for point-to-point data transmission for any dimension.
A Block Regression Model for Short-Term Mobile Traffic Forecasting
Venue: arXiv cs.NI 2015
Year: 2015

Accurate mobile traffic forecast is important for efficient network planning and operations. However, existing traffic forecasting models have high complexity, making the forecasting process slow and costly. In this paper, we analyze some characteristics of mobile traffic such as periodicity, spatial similarity and short term relativity. Based on these characteristics, we propose a \emph{Block Regression} ({BR}) model for mobile traffic forecasting. This model employs seasonal differentiation so as to take into account of the temporally repetitive nature of mobile traffic. One of the key features of our {BR} model lies in its low complexity since it constructs a single model for all base stations. We evaluate the accuracy of {BR} model based on real traffic data and compare it with the existing models. Results show that our {BR} model offers equal accuracy to the existing models but has much less complexity.
Behavior Query Discovery in System-Generated Temporal Graphs
Venue: arXiv cs.SI 2015
Year: 2015

Computer system monitoring generates huge amounts of logs that record the interaction of system entities. How to query such data to better understand system behaviors and identify potential system risks and malicious behaviors becomes a challenging task for system administrators due to the dynamics and heterogeneity of the data. System monitoring data are essentially heterogeneous temporal graphs with nodes being system entities and edges being their interactions over time. Given the complexity of such graphs, it becomes time-consuming for system administrators to manually formulate useful queries in order to examine abnormal activities, attacks, and vulnerabilities in computer systems. In this work, we investigate how to query temporal graphs and treat query formulation as a discriminative temporal graph pattern mining problem. We introduce TGMiner to mine discriminative patterns from system logs, and these patterns can be taken as templates for building more complex queries. TGMiner leverages temporal information in graphs to prune graph patterns that share similar growth trend without compromising pattern quality. Experimental results on real system data show that TGMiner is 6-32 times faster than baseline methods. The discovered patterns were verified by system experts; they achieved high precision (97%) and recall (91%).
Min-O-Mee: A Proximity Based Network Application Leveraging The AllJoyn Framework
Venue: arXiv cs.NI 2015
Year: 2015

Close proximity of mobile devices can be utilized to create ad hoc and dynamic networks. These mobile Proximity Based Networks (PBNs) are Opportunistic Networks that enable devices to identify and communicate with each other without relying on any communication infrastructure. In addition, these networks are self organizing, highly dynamic and facilitate effective real-time communication. These characteristics render them very useful in a wide variety of complex scenarios such as vehicular communication, e-health, disaster networks, mobile social networks etc. In this work we employ the AllJoyn framework from Qualcomm which facilitates smooth discovery, attachment and data sharing between devices in close proximity. We develop \textit{Min-O-Mee}, a Minutes-of-Meeting app prototype in the Android platform, utilizing the AllJoyn framework. Min-O-Mee allows one of the participants to create a minutes-of-meeting document which can be shared with and edited by the other participants in the meeting. The app harnesses the spatial proximity of participants in a meeting and enables seamless data exchange between them. This characteristic allows Min-O-Mee to share not just minutes-of-meeting, but any data that needs to be exchanged among the participants, making it a versatile app. Further, we extend the basic AllJoyn framework to enable multi-hop communication among the devices in the PBN. We devise a novel routing mechanism that is suited to a proximity centric wireless network as it facilitates data routing and delivery over several hops to devices that are at the fringe of the PBN.
Principled Parallel Mean-Field Inference for Discrete Random Fields
Venue: arXiv cs.CV 2015
Year: 2015

Mean-field variational inference is one of the most popular approaches to inference in discrete random fields. Standard mean-field optimization is based on coordinate descent and in many situations can be impractical. Thus, in practice, various parallel techniques are used, which either rely on ad-hoc smoothing with heuristically set parameters, or put strong constraints on the type of models. In this paper, we propose a novel proximal gradient-based approach to optimizing the variational objective. It is naturally parallelizable and easy to implement. We prove its convergence, and then demonstrate that, in practice, it yields faster convergence and often finds better optima than more traditional mean-field optimization techniques. Moreover, our method is less sensitive to the choice of parameters.