OpenRaiser/Intern-Atlas huggingface dataset:
Embedding AC Power Flow in the Complex Plane Part I: Modelling and Mathematical Foundation
Venue: arXiv cs.SY 2016
Year: 2016

Part I of this paper embeds the AC power flow problem with voltage control and exponential load model in the complex plane. Modeling the action of network controllers that regulate the magnitude of voltage phasors is a challenging task in the complex plane as it has to preserve the framework of holomorphicity for obtention of these complex variables with fixed magnitude. The paper presents two distinct approaches to modelling the voltage control of generator nodes. Exponential (or voltage-dependent) load models are crucial for accurate power flow studies under stressed conditions. This new framework for power flow studies exploits the theory of analytic continuation, especially the monodromy theorem for resolving issues that have plagued conventional numerical methods for decades. Here the focus is on the indispensable role of Pade approximants for analytic continuation of complex functions, expressed as power series, beyond the boundary of convergence of the series. The zero-pole distribution of these rational approximants serves as a proximity index to voltage collapse. Finally the mathematical underpinnings of this framework, namely the Stahl's theory and the rate of convergence of Pade approximants are explained.
In the mood: the dynamics of collective sentiments on Twitter
Venue: arXiv cs.SI 2016
Year: 2016

We study the relationship between the sentiment levels of Twitter users and the evolving network structure that the users created by @-mentioning each other. We use a large dataset of tweets to which we apply three sentiment scoring algorithms, including the open source SentiStrength program. Specifically we make three contributions. Firstly we find that people who have potentially the largest communication reach (according to a dynamic centrality measure) use sentiment differently than the average user: for example they use positive sentiment more often and negative sentiment less often. Secondly we find that when we follow structurally stable Twitter communities over a period of months, their sentiment levels are also stable, and sudden changes in community sentiment from one day to the next can in most cases be traced to external events affecting the community. Thirdly, based on our findings, we create and calibrate a simple agent-based model that is capable of reproducing measures of emotive response comparable to those obtained from our empirical dataset.
Multi-modal Fusion for Diabetes Mellitus and Impaired Glucose Regulation Detection
Venue: arXiv cs.CV 2016
Year: 2016

Effective and accurate diagnosis of Diabetes Mellitus (DM), as well as its early stage Impaired Glucose Regulation (IGR), has attracted much attention recently. Traditional Chinese Medicine (TCM) [3], [5] etc. has proved that tongue, face and sublingual diagnosis as a noninvasive method is a reasonable way for disease detection. However, most previous works only focus on a single modality (tongue, face or sublingual) for diagnosis, although different modalities may provide complementary information for the diagnosis of DM and IGR. In this paper, we propose a novel multi-modal classification method to discriminate between DM (or IGR) and healthy controls. Specially, the tongue, facial and sublingual images are first collected by using a non-invasive capture device. The color, texture and geometry features of these three types of images are then extracted, respectively. Finally, our so-called multi-modal similar and specific learning (MMSSL) approach is proposed to combine features of tongue, face and sublingual, which not only exploits the correlation but also extracts individual components among them. Experimental results on a dataset consisting of 192 Healthy, 198 DM and 114 IGR samples (all samples were obtained from Guangdong Provincial Hospital of Traditional Chinese Medicine) substantiate the effectiveness and superiority of our proposed method for the diagnosis of DM and IGR, compared to the case of using a single modality.
Backward-Forward Search for Manipulation Planning
Venue: arXiv cs.RO 2016
Year: 2016

In this paper we address planning problems in high-dimensional hybrid configuration spaces, with a particular focus on manipulation planning problems involving many objects. We present the hybrid backward-forward (HBF) planning algorithm that uses a backward identification of constraints to direct the sampling of the infinite action space in a forward search from the initial state towards a goal configuration. The resulting planner is probabilistically complete and can effectively construct long manipulation plans requiring both prehensile and nonprehensile actions in cluttered environments.
Ready for Rain? A View from SPEC Research on the Future of Cloud Metrics
Venue: arXiv cs.DC 2016
Year: 2016

In the past decade, cloud computing has emerged from a pursuit for a service-driven information and communication technology (ICT), into a signifcant fraction of the ICT market. Responding to the growth of the market, many alternative cloud services and their underlying systems are currently vying for the attention of cloud users and providers. Thus, benchmarking them is needed, to enable cloud users to make an informed choice, and to enable system DevOps to tune, design, and evaluate their systems. This requires focusing on old and new system properties, possibly leading to the re-design of classic benchmarking metrics, such as expressing performance as throughput and latency (response time), and the design of new, cloud-specififc metrics. Addressing this requirement, in this work we focus on four system properties: (i) elasticity of the cloud service, to accommodate large variations in the amount of service requested, (ii) performance isolation between the tenants of shared cloud systems, (iii) availability of cloud services and systems, and the (iv) operational risk of running a production system in a cloud environment.Focusing on key metrics, for each of these properties we review the state-of-the-art, then select or propose new metrics together with measurement approaches. We see the presented metrics as a foundation towards upcoming, industry-standard, cloud benchmarks. Keywords: Cloud Computing; Metrics; Measurement; Benchmarking; Elasticity; Isolation; Performance; Service Level Objective; Availability; Operational Risk.
Joint alignment of multiple protein-protein interaction networks via convex optimization
Venue: arXiv cs.DS 2016
Year: 2016

Motivation: High-throughput experimental techniques have been producing more and more protein-protein interaction (PPI) data. PPI network alignment greatly benefits the understanding of evolutionary relationship among species, helps identify conserved sub-networks and provides extra information for functional annotations. Although a few methods have been developed for multiple PPI network alignment, the alignment quality is still far away from perfect and thus, new network alignment methods are needed. Result: In this paper, we present a novel method, denoted as ConvexAlign, for joint alignment of multiple PPI networks by convex optimization of a scoring function composed of sequence similarity, topological score and interaction conservation score. In contrast to existing methods that generate multiple alignments in a greedy or progressive manner, our convex method optimizes alignments globally and enforces consistency among all pairwise alignments, resulting in much better alignment quality. Tested on both synthetic and real data, our experimental results show that ConvexAlign outperforms several popular methods in producing functionally coherent alignments. ConvexAlign even has a larger advantage over the others in aligning real PPI networks. ConvexAlign also finds a few conserved complexes among 5 species which cannot be detected by the other methods.
Metrics for Community Analysis: A Survey
Venue: arXiv cs.SI 2016
Year: 2016

Detecting and analyzing dense groups or communities from social and information networks has attracted immense attention over last one decade due to its enormous applicability in different domains. Community detection is an ill-defined problem, as the nature of the communities is not known in advance. The problem has turned out to be even complicated due to the fact that communities emerge in the network in various forms - disjoint, overlapping, hierarchical etc. Various heuristics have been proposed depending upon the application in hand. All these heuristics have been materialized in the form of new metrics, which in most cases are used as optimization functions for detecting the community structure, or provide an indication of the goodness of detected communities during evaluation. There arises a need for an organized and detailed survey of the metrics proposed with respect to community detection and evaluation. In this survey, we present a comprehensive and structured overview of the start-of-the-art metrics used for the detection and the evaluation of community structure. We also conduct experiments on synthetic and real-world networks to present a comparative analysis of these metrics in measuring the goodness of the underlying community structure.
Lara: A Key-Value Algebra underlying Arrays and Relations
Venue: arXiv cs.DB 2016
Year: 2016

Data processing systems roughly group into families such as relational, array, graph, and key-value. Many data processing tasks exceed the capabilities of any one family, require data stored across families, or run faster when partitioned onto multiple families. Discovering ways to execute computation among multiple available systems, let alone discovering an optimal execution plan, is challenging given semantic differences between disparate families of systems. In this paper we introduce a new algebra, Lara, which underlies and unifies algebras representing the families above in order to facilitate translation between systems. We describe the operations and objects of Lara---union, join, and ext on associative tables---and show her properties and equivalences to other algebras. Multi-system optimization has a bright future, in which we proffer Lara for the role of universal connector.
Just-in-Time Static Type Checking for Dynamic Languages
Venue: arXiv cs.PL 2016
Year: 2016

Dynamic languages such as Ruby, Python, and JavaScript have many compelling benefits, but the lack of static types means subtle errors can remain latent in code for a long time. While many researchers have developed various systems to bring some of the benefits of static types to dynamic languages, prior approaches have trouble dealing with metaprogramming, which generates code as the program executes. In this paper, we propose Hummingbird, a new system that uses a novel technique, just-in-time static type checking, to type check Ruby code even in the presence of metaprogramming. In Hummingbird, method type signatures are gathered dynamically at run-time, as those methods are created. When a method is called, Hummingbird statically type checks the method body against current type signatures. Thus, Hummingbird provides thorough static checks on a per-method basis, while also allowing arbitrarily complex metaprogramming. For performance, Hummingbird memoizes the static type checking pass, invalidating cached checks only if necessary. We formalize Hummingbird using a core, Ruby-like language and prove it sound. To evaluate Hummingbird, we applied it to six apps, including three that use Ruby on Rails, a powerful framework that relies heavily on metaprogramming. We found that all apps typecheck successfully using Hummingbird, and that Hummingbird's performance overhead is reasonable. We applied Hummingbird to earlier versions of one Rails app and found several type errors that had been introduced and then fixed. Lastly, we demonstrate using Hummingbird in Rails development mode to typecheck an app as live updates are applied to it.
VConv-DAE: Deep Volumetric Shape Learning Without Object Labels
Venue: arXiv cs.CV 2016
Year: 2016

With the advent of affordable depth sensors, 3D capture becomes more and more ubiquitous and already has made its way into commercial products. Yet, capturing the geometry or complete shapes of everyday objects using scanning devices (e.g. Kinect) still comes with several challenges that result in noise or even incomplete shapes. Recent success in deep learning has shown how to learn complex shape distributions in a data-driven way from large scale 3D CAD Model collections and to utilize them for 3D processing on volumetric representations and thereby circumventing problems of topology and tessellation. Prior work has shown encouraging results on problems ranging from shape completion to recognition. We provide an analysis of such approaches and discover that training as well as the resulting representation are strongly and unnecessarily tied to the notion of object labels. Thus, we propose a full convolutional volumetric auto encoder that learns volumetric representation from noisy data by estimating the voxel occupancy grids. The proposed method outperforms prior work on challenging tasks like denoising and shape completion. We also show that the obtained deep embedding gives competitive performance when used for classification and promising results for shape interpolation.
Tiered Forensic Methodology Model for Digital Field Triage by Non-Digital Evidence Specialists
Venue: arXiv cs.CR 2016
Year: 2016

Due to budgetary constraints and the high level of training required, digital forensic analysts are in short supply in police forces the world over. This inevitably leads to a prolonged time taken between an investigator sending the digital evidence for analysis and receiving the analytical report back. In an attempt to expedite this procedure, various process models have been created to place the forensic analyst in the field conducting a triage of the digital evidence. By conducting triage in the field, an investigator is able to act upon pertinent information quicker, while waiting on the full report. The work presented as part of this paper focuses on the training of front-line personnel in the field triage process, without the need of a forensic analyst attending the scene. The premise has been successfully implemented within regular/non-digital forensics, i.e., crime scene investigation. In that field, front-line members have been trained in specific tasks to supplement the trained specialists. The concept of front-line members conducting triage of digital evidence in the field is achieved through the development of a new process model providing guidance to these members. To prove the model's viability, an implementation of this new process model is presented and evaluated. The results outlined demonstrate how a tiered response involving digital evidence specialists and non-specialists can better deal with the increasing number of investigations involving digital evidence.
Area/latency optimized early output asynchronous full adders and relative-timed ripple carry adders
Venue: arXiv cs.AR 2016
Year: 2016

This article presents two area/latency optimized gate level asynchronous full adder designs which correspond to early output logic. The proposed full adders are constructed using the delay-insensitive dual-rail code and adhere to the four-phase return-to-zero handshaking. For an asynchronous ripple carry adder (RCA) constructed using the proposed early output full adders, the relative-timing assumption becomes necessary and the inherent advantages of the relative-timed RCA are: (1) computation with valid inputs, i.e., forward latency is data-dependent, and (2) computation with spacer inputs involves a bare minimum constant reverse latency of just one full adder delay, thus resulting in the optimal cycle time. With respect to different 32-bit RCA implementations, and in comparison with the optimized strong-indication, weak-indication, and early output full adder designs, one of the proposed early output full adders achieves respective reductions in latency by 67.8, 12.3 and 6.1 %, while the other proposed early output full adder achieves corresponding reductions in area by 32.6, 24.6 and 6.9 %, with practically no power penalty. Further, the proposed early output full adders based asynchronous RCAs enable minimum reductions in cycle time by 83.4, 15, and 8.8 % when considering carry-propagation over the entire RCA width of 32-bits, and maximum reductions in cycle time by 97.5, 27.4, and 22.4 % for the consideration of a typical carry chain length of 4 full adder stages, when compared to the least of the cycle time estimates of various strong-indication, weak-indication, and early output asynchronous RCAs of similar size. All the asynchronous full adders and RCAs were realized using standard cells in a semi-custom design fashion based on a 32/28 nm CMOS process technology.
Operational Semantics of Resolution and Productivity in Horn Clause Logic
Venue: arXiv cs.LO 2016
Year: 2016

This paper presents a study of operational and type-theoretic properties of different resolution strategies in Horn clause logic. We distinguish four different kinds of resolution: resolution by unification (SLD-resolution), resolution by term-matching, the recently introduced structural resolution, and partial (or lazy) resolution. We express them all uniformly as abstract reduction systems, which allows us to undertake a thorough comparative analysis of their properties. To match this small-step semantics, we propose to take Howard's System H as a type-theoretic semantic counterpart. Using System H, we interpret Horn formulas as types, and a derivation for a given formula as the proof term inhabiting the type given by the formula. We prove soundness of these abstract reduction systems relative to System H, and we show completeness of SLD-resolution and structural resolution relative to System H. We identify conditions under which structural resolution is operationally equivalent to SLD-resolution. We show correspondence between term-matching resolution for Horn clause programs without existential variables and term rewriting.
Logic for Unambiguous Context-Free Languages
Venue: arXiv cs.FL 2016
Year: 2016

We give in this paper a logical characterization for unambiguous Context Free Languages, in the vein of descriptive complexity. A fragment of the logic characterizing context free languages given by Lautemann, Schwentick and Thérien [18] based on implicit definability is used for this aim. We obtain a new connection between two undecidable problems, a logical one and a language theoretical one.
On Reducing the Number of Visual Words in the Bag-of-Features Representation
Venue: arXiv cs.CV 2016
Year: 2016

A new class of applications based on visual search engines are emerging, especially on smart-phones that have evolved into powerful tools for processing images and videos. The state-of-the-art algorithms for large visual content recognition and content based similarity search today use the "Bag of Features" (BoF) or "Bag of Words" (BoW) approach. The idea, borrowed from text retrieval, enables the use of inverted files. A very well known issue with this approach is that the query images, as well as the stored data, are described with thousands of words. This poses obvious efficiency problems when using inverted files to perform efficient image matching. In this paper, we propose and compare various techniques to reduce the number of words describing an image to improve efficiency and we study the effects of this reduction on effectiveness in landmark recognition and retrieval scenarios. We show that very relevant improvement in performance are achievable still preserving the advantages of the BoF base approach.
Predicting Privacy Attitudes Using Phone Metadata
Venue: arXiv cs.CY 2016
Year: 2016

With the increasing usage of smartphones, there is a corresponding increase in the phone metadata generated by individuals using these devices. Managing the privacy of personal information on these devices can be a complex task. Recent research has suggested the use of social and behavioral data for automatically recommending privacy settings. This paper is the first effort to connect users' phone use metadata with their privacy attitudes. Based on a 10-week long field study involving phone metadata collection via an app, and a survey on privacy attitudes, we report that an analysis of cell phone metadata may reveal vital clues to a person's privacy attitudes. Specifically, a predictive model based on phone usage metadata significantly outperforms a comparable personality features-based model in predicting individual privacy attitudes. The results motivate a newer direction of automatically inferring a user's privacy attitudes by looking at their phone usage characteristics.
Consistently Estimating Markov Chains with Noisy Aggregate Data
Venue: arXiv cs.LG 2016
Year: 2016

We address the problem of estimating the parameters of a time-homogeneous Markov chain given only noisy, aggregate data. This arises when a population of individuals behave independently according to a Markov chain, but individual sample paths cannot be observed due to limitations of the observation process or the need to protect privacy. Instead, only population-level counts of the number of individuals in each state at each time step are available. When these counts are exact, a conditional least squares (CLS) estimator is known to be consistent and asymptotically normal. We initiate the study of method of moments estimators for this problem to handle the more realistic case when observations are additionally corrupted by noise. We show that CLS can be interpreted as a simple "plug-in" method of moments estimator. However, when observations are noisy, it is not consistent because it fails to account for additional variance introduced by the noise. We develop a new, simpler method of moments estimator that bypasses this problem and is consistent under noisy observations.
SLING: A Near-Optimal Index Structure for SimRank
Venue: arXiv cs.DB 2016
Year: 2016

SimRank is a similarity measure for graph nodes that has numerous applications in practice. Scalable SimRank computation has been the subject of extensive research for more than a decade, and yet, none of the existing solutions can efficiently derive SimRank scores on large graphs with provable accuracy guarantees. In particular, the state-of-the-art solution requires up to a few seconds to compute a SimRank score in million-node graphs, and does not offer any worst-case assurance in terms of the query error. This paper presents SLING, an efficient index structure for SimRank computation. SLING guarantees that each SimRank score returned has at most $\varepsilon$ additive error, and it answers any single-pair and single-source SimRank queries in $O(1/\varepsilon)$ and $O(n/\varepsilon)$ time, respectively. These time complexities are near-optimal, and are significantly better than the asymptotic bounds of the most recent approach. Furthermore, SLING requires only $O(n/\varepsilon)$ space (which is also near-optimal in an asymptotic sense) and $O(m/\varepsilon + n\log \frac{n}δ/\varepsilon^2)$ pre-computation time, where $δ$ is the failure probability of the preprocessing algorithm. We experimentally evaluate SLING with a variety of real-world graphs with up to several millions of nodes. Our results demonstrate that SLING is up to $10000$ times (resp. $110$ times) faster than competing methods for single-pair (resp. single-source) SimRank queries, at the cost of higher space overheads.