OpenRaiser/Intern-Atlas huggingface dataset:
Conflict and Computation on Wikipedia: a Finite-State Machine Analysis of Editor Interactions
Venue: arXiv cs.SI 2016
Year: 2016

What is the boundary between a vigorous argument and a breakdown of relations? What drives a group of individuals across it? Taking Wikipedia as a test case, we use a hidden Markov model to approximate the computational structure and social grammar of more than a decade of cooperation and conflict among its editors. Across a wide range of pages, we discover a bursty war/peace structure where the systems can become trapped, sometimes for months, in a computational subspace associated with significantly higher levels of conflict-tracking "revert" actions. Distinct patterns of behavior characterize the lower-conflict subspace, including tit-for-tat reversion. While a fraction of the transitions between these subspaces are associated with top-down actions taken by administrators, the effects are weak. Surprisingly, we find no statistical signal that transitions are associated with the appearance of particularly anti-social users, and only weak association with significant news events outside the system. These findings are consistent with transitions being driven by decentralized processes with no clear locus of control. Models of belief revision in the presence of a common resource for information-sharing predict the existence of two distinct phases: a disordered high-conflict phase, and a frozen phase with spontaneously-broken symmetry. The bistability we observe empirically may be a consequence of editor turn-over, which drives the system to a critical point between them.
Origami: A 803 GOp/s/W Convolutional Network Accelerator
Venue: arXiv cs.CV 2016
Year: 2016

An ever increasing number of computer vision and image/video processing challenges are being approached using deep convolutional neural networks, obtaining state-of-the-art results in object recognition and detection, semantic segmentation, action recognition, optical flow and superresolution. Hardware acceleration of these algorithms is essential to adopt these improvements in embedded and mobile computer vision systems. We present a new architecture, design and implementation as well as the first reported silicon measurements of such an accelerator, outperforming previous work in terms of power-, area- and I/O-efficiency. The manufactured device provides up to 196 GOp/s on 3.09 mm^2 of silicon in UMC 65nm technology and can achieve a power efficiency of 803 GOp/s/W. The massively reduced bandwidth requirements make it the first architecture scalable to TOp/s performance.
Strong reductions for extended formulations
Venue: arXiv cs.CC 2016
Year: 2016

We generalize the reduction mechanism for linear programming problems and semidefinite programming problems from [arXiv:1410.8816] in two ways 1) relaxing the requirement of affineness and 2) extending to fractional optimization problems. As applications we provide several new LP-hardness and SDP-hardness results, e.g., for the SparsestCut problem, the BalancedSeparator problem, the MaxCut problem and the Matching problem on 3-regular graphs. We also provide a new, very strong Lasserre integrality gap result for the IndependentSet problem, which is strictly greater than the best known LP approximation, showing that the Lasserre hierarchy does not always provide the tightest SDP relaxation.
Packet Transactions: High-level Programming for Line-Rate Switches
Venue: arXiv cs.NI 2016
Year: 2016

Many algorithms for congestion control, scheduling, network measurement, active queue management, security, and load balancing require custom processing of packets as they traverse the data plane of a network switch. To run at line rate, these data-plane algorithms must be in hardware. With today's switch hardware, algorithms cannot be changed, nor new algorithms installed, after a switch has been built. This paper shows how to program data-plane algorithms in a high-level language and compile those programs into low-level microcode that can run on emerging programmable line-rate switching chipsets. The key challenge is that these algorithms create and modify algorithmic state. The key idea to achieve line-rate programmability for stateful algorithms is the notion of a packet transaction : a sequential code block that is atomic and isolated from other such code blocks. We have developed this idea in Domino, a C-like imperative language to express data-plane algorithms. We show with many examples that Domino provides a convenient and natural way to express sophisticated data-plane algorithms, and show that these algorithms can be run at line rate with modest estimated die-area overhead.
A new methodology for comparing Google Scholar and Scopus
Venue: arXiv cs.DL 2016
Year: 2016

A new methodology is proposed for comparing Google Scholar (GS) with other citation indexes. It focuses on the coverage and citation impact of sources, indexing speed, and data quality, including the effect of duplicate citation counts. The method compares GS with Elsevier's Scopus, and is applied to a limited set of articles published in 12 journals from six subject fields, so that its findings cannot be generalized to all journals or fields. The study is exploratory, and hypothesis generating rather than hypothesis-testing. It confirms findings on source coverage and citation impact obtained in earlier studies. The ratio of GS over Scopus citation varies across subject fields between 1.0 and 4.0, while Open Access journals in the sample show higher ratios than their non-OA counterparts. The linear correlation between GS and Scopus citation counts at the article level is high: Pearson's R is in the range of 0.8-0.9. A median Scopus indexing delay of two months compared to GS is largely though not exclusively due to missing cited references in articles in press in Scopus. The effect of double citation counts in GS due to multiple citations with identical or substantially similar meta-data occurs in less than 2 per cent of cases. Pros and cons of article-based and what is termed as concept-based citation indexes are discussed.
A Planning based Framework for Essay Generation
Venue: arXiv cs.CL 2016
Year: 2016

Generating an article automatically with computer program is a challenging task in artificial intelligence and natural language processing. In this paper, we target at essay generation, which takes as input a topic word in mind and generates an organized article under the theme of the topic. We follow the idea of text planning \cite{Reiter1997} and develop an essay generation framework. The framework consists of three components, including topic understanding, sentence extraction and sentence reordering. For each component, we studied several statistical algorithms and empirically compared between them in terms of qualitative or quantitative analysis. Although we run experiments on Chinese corpus, the method is language independent and can be easily adapted to other language. We lay out the remaining challenges and suggest avenues for future research.
Design Principles for Scaling Multi-core OLTP Under High Contention
Venue: arXiv cs.DB 2016
Year: 2016

Although significant recent progress has been made in improving the multi-core scalability of high throughput transactional database systems, modern systems still fail to achieve scalable throughput for workloads involving frequent access to highly contended data. Most of this inability to achieve high throughput is explained by the fundamental constraints involved in guaranteeing ACID --- the addition of cores results in more concurrent transactions accessing the same contended data for which access must be serialized in order to guarantee isolation. Thus, linear scalability for contended workloads is impossible. However, there exist flaws in many modern architectures that exacerbate their poor scalability, and result in throughput that is much worse than fundamentally required by the workload. In this paper we identify two prevalent design principles that limit the multi-core scalability of many (but not all) transactional database systems on contended workloads: the multi-purpose nature of execution threads in these systems, and the lack of advanced planning of data access. We demonstrate the deleterious results of these design principles by implementing a prototype system, ORTHRUS, that is motivated by the principles of separation of database component functionality and advanced planning of transactions. We find that these two principles alone result in significantly improved scalability on high-contention workloads, and an order of magnitude increase in throughput for a non-trivial subset of these contended workloads.
Convergence and State Reconstruction of Time-varying Multi-agent Systems from Complete Observability Theory
Venue: arXiv cs.SY 2016
Year: 2016

We study continuous-time consensus dynamics for multi-agent systems with undirected switching interaction graphs. We establish a necessary and sufficient condition for exponential asymptotic consensus based on the classical theory of complete observability. The proof is remarkably simple compared to similar results in the literature and the conditions for consensus are mild. This observability-based method can also be applied to the case where negatively weighted edges are present. Additionally, as a by-product of the observability based arguments, we show that the nodes' initial value can be recovered from the signals on the edges up to a shift of the network average.
Analysis of Vessel Connectivities in Retinal Images by Cortically Inspired Spectral Clustering
Venue: arXiv cs.CV 2016
Year: 2016

Retinal images provide early signs of diabetic retinopathy, glaucoma, and hypertension. These signs can be investigated based on microaneurysms or smaller vessels. The diagnostic biomarkers are the change of vessel widths and angles especially at junctions, which are investigated using the vessel segmentation or tracking. Vessel paths may also be interrupted; crossings and bifurcations may be disconnected. This paper addresses a novel contextual method based on the geometry of the primary visual cortex (V1) to study these difficulties. We have analyzed the specific problems at junctions with a connectivity kernel obtained as the fundamental solution of the Fokker-Planck equation, which is usually used to represent the geometrical structure of multi-orientation cortical connectivity. Using the spectral clustering on a large local affinity matrix constructed by both the connectivity kernel and the feature of intensity, the vessels are identified successfully in a hierarchical topology each representing an individual perceptual unit.
What Happens to a Manifold Under a Bi-Lipschitz Map?
Venue: arXiv cs.IT 2016
Year: 2016

We study geometric and topological properties of the image of a smooth submanifold of $\mathbb{R}^{n}$ under a bi-Lipschitz map to $\mathbb{R}^{m}$. In particular, we characterize how the dimension, diameter, volume, and reach of the embedded manifold relate to the original. Our main result establishes a lower bound on the reach of the embedded manifold in the case where $m \le n$ and the bi-Lipschitz map is linear. We discuss implications of this work in signal processing and machine learning, where bi-Lipschitz maps on low-dimensional manifolds have been constructed using randomized linear operators.
A C++ library for Multimodal Deep Learning
Venue: arXiv cs.LG 2016
Year: 2016

MDL, Multimodal Deep Learning Library, is a deep learning framework that supports multiple models, and this document explains its philosophy and functionality. MDL runs on Linux, Mac, and Unix platforms. It depends on OpenCV.
SR-Clustering: Semantic Regularized Clustering for Egocentric Photo Streams Segmentation
Venue: arXiv cs.AI 2016
Year: 2016

While wearable cameras are becoming increasingly popular, locating relevant information in large unstructured collections of egocentric images is still a tedious and time consuming processes. This paper addresses the problem of organizing egocentric photo streams acquired by a wearable camera into semantically meaningful segments. First, contextual and semantic information is extracted for each image by employing a Convolutional Neural Networks approach. Later, by integrating language processing, a vocabulary of concepts is defined in a semantic space. Finally, by exploiting the temporal coherence in photo streams, images which share contextual and semantic attributes are grouped together. The resulting temporal segmentation is particularly suited for further analysis, ranging from activity and event recognition to semantic indexing and summarization. Experiments over egocentric sets of nearly 17,000 images, show that the proposed approach outperforms state-of-the-art methods.
Incremental Method for Spectral Clustering of Increasing Orders
Venue: arXiv cs.SI 2016
Year: 2016

The smallest eigenvalues and the associated eigenvectors (i.e., eigenpairs) of a graph Laplacian matrix have been widely used for spectral clustering and community detection. However, in real-life applications the number of clusters or communities (say, $K$) is generally unknown a-priori. Consequently, the majority of the existing methods either choose $K$ heuristically or they repeat the clustering method with different choices of $K$ and accept the best clustering result. The first option, more often, yields suboptimal result, while the second option is computationally expensive. In this work, we propose an incremental method for constructing the eigenspectrum of the graph Laplacian matrix. This method leverages the eigenstructure of graph Laplacian matrix to obtain the $K$-th eigenpairs of the Laplacian matrix given a collection of all the $K-1$ smallest eigenpairs. Our proposed method adapts the Laplacian matrix such that the batch eigenvalue decomposition problem transforms into an efficient sequential leading eigenpair computation problem. As a practical application, we consider user-guided spectral clustering. Specifically, we demonstrate that users can utilize the proposed incremental method for effective eigenpair computation and determining the desired number of clusters based on multiple clustering metrics.
Community Detection in Complex Networks Using Density-based Clustering Algorithm
Venue: arXiv cs.SI 2016
Year: 2016

Like clustering analysis, community detection aims at assigning nodes in a network into different communities. Fdp is a recently proposed density-based clustering algorithm which does not need the number of clusters as prior input and the result is insensitive to its parameter. However, Fdp cannot be directly applied to community detection due to its inability to recognize the community centers in the network. To solve the problem, a new community detection method (named IsoFdp) is proposed in this paper. First, we use Isomap technique to map the network data into a low dimensional manifold which can reveal diverse pair-wised similarity. Then Fdp is applied to detect the communities in networks. An improved partition density function is proposed to select the proper number of communities automatically. We test our method on both synthetic and real-world networks, and the results demonstrate the effectiveness of our algorithm over the state-of-the-art methods.
A Mathematical Theory of Co-Design
Venue: arXiv cs.LO 2016
Year: 2016

One of the challenges of modern engineering, and robotics in particular, is designing complex systems, composed of many subsystems, rigorously and with optimality guarantees. This paper introduces a theory of co-design that describes "design problems", defined as tuples of "functionality space", "implementation space", and "resources space", together with a feasibility relation that relates the three spaces. Design problems can be interconnected together to create "co-design problems", which describe possibly recursive co-design constraints among subsystems. A co-design problem induces a family of optimization problems of the type "find the minimal resources needed to implement a given functionality"; the solution is an antichain (Pareto front) of resources. A special class of co-design problems are Monotone Co-Design Problems (MCDPs), for which functionality and resources are complete partial orders and the feasibility relation is monotone and Scott continuous. The induced optimization problems are multi-objective, nonconvex, nondifferentiable, noncontinuous, and not even defined on continuous spaces; yet, there exists a complete solution. The antichain of minimal resources can be characterized as a least fixed point, and it can be computed using Kleene's algorithm. The computation needed to solve a co-design problem can be bounded by a function of a graph property that quantifies the interdependence of the subproblems. These results make us much more optimistic about the problem of designing complex systems in a rigorous way.
Cost-Efficient Data Backup for Data Center Networks against ε-Time Early Warning Disaster
Venue: arXiv cs.NI 2016
Year: 2016

Data backup in data center networks (DCNs) is critical to minimize the data loss under disaster. This paper considers the cost-efficient data backup for DCNs against a disaster with $\varepsilon$ early warning time. Given geo-distributed DCNs and such a $\varepsilon$-time early warning disaster, we investigate the issue of how to back up the data in DCN nodes under risk to other safe DCN nodes within the $\varepsilon$ early warning time constraint, which is significant because it is an emergency data protection scheme against a predictable disaster and also help DCN operators to build a complete backup scheme, i.e., regular backup and emergency backup. Specifically, an Integer Linear Program (ILP)-based theoretical framework is proposed to identify the optimal selections of backup DCN nodes and data transmission paths, such that the overall data backup cost is minimized. Extensive numerical results are also provided to illustrate the proposed framework for DCN data backup.
A Novel Reduced Model for Electrical Networks with Constant Power Loads
Venue: arXiv cs.SY 2016
Year: 2016

We consider a network-preserved model of power networks with proper algebraic constraints resulting from constant power loads. Both for the linear and the nonlinear differential algebraic model of the network, we derive explicit reduced models which are fully expressed in terms of ordinary differential equations. For deriving these reduced models, we introduce the "projected incidence" matrix which yields a novel decomposition of the reduced Laplacian matrix. With the help of this new matrix, we provide a complementary approach to Kron reduction which is able to cope with constant power loads and nonlinear power flow equations.
Survivability in Time-varying Networks
Venue: arXiv cs.NI 2016
Year: 2016

Time-varying graphs are a useful model for networks with dynamic connectivity such as vehicular networks, yet, despite their great modeling power, many important features of time-varying graphs are still poorly understood. In this paper, we study the survivability properties of time-varying networks against unpredictable interruptions. We first show that the traditional definition of survivability is not effective in time-varying networks, and propose a new survivability framework. To evaluate the survivability of time-varying networks under the new framework, we propose two metrics that are analogous to MaxFlow and MinCut in static networks. We show that some fundamental survivability-related results such as Menger's Theorem only conditionally hold in time-varying networks. Then we analyze the complexity of computing the proposed metrics and develop several approximation algorithms. Finally, we conduct trace-driven simulations to demonstrate the application of our survivability framework to the robust design of a real-world bus communication network.
Evaluating Hive and Spark SQL with BigBench
Venue: arXiv cs.DB 2016
Year: 2016

The objective of this work was to utilize BigBench [1] as a Big Data benchmark and evaluate and compare two processing engines: MapReduce [2] and Spark [3]. MapReduce is the established engine for processing data on Hadoop. Spark is a popular alternative engine that promises faster processing times than the established MapReduce engine. BigBench was chosen for this comparison because it is the first end-to-end analytics Big Data benchmark and it is currently under public review as TPCx-BB [4]. One of our goals was to evaluate the benchmark by performing various scalability tests and validate that it is able to stress test the processing engines. First, we analyzed the steps necessary to execute the available MapReduce implementation of BigBench [1] on Spark. Then, all the 30 BigBench queries were executed on MapReduce/Hive with different scale factors in order to see how the performance changes with the increase of the data size. Next, the group of HiveQL queries were executed on Spark SQL and compared with their respective Hive runtimes. This report gives a detailed overview on how to setup an experimental Hadoop cluster and execute BigBench on both Hive and Spark SQL. It provides the absolute times for all experiments preformed for different scale factors as well as query results which can be used to validate correct benchmark execution. Additionally, multiple issues and workarounds were encountered and solved during our work. An evaluation of the resource utilization (CPU, memory, disk and network usage) of a subset of representative BigBench queries is presented to illustrate the behavior of the different query groups on both processing engines. Last but not least it is important to mention that larger parts of this report are taken from the master thesis of Max-Georg Beer, entitled "Evaluation of BigBench on Apache Spark Compared to MapReduce" [5].
Exploiting Local Structures with the Kronecker Layer in Convolutional Networks
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we propose and study a technique to reduce the number of parameters and computation time in convolutional neural networks. We use Kronecker product to exploit the local structures within convolution and fully-connected layers, by replacing the large weight matrices by combinations of multiple Kronecker products of smaller matrices. Just as the Kronecker product is a generalization of the outer product from vectors to matrices, our method is a generalization of the low rank approximation method for convolution neural networks. We also introduce combinations of different shapes of Kronecker product to increase modeling capacity. Experiments on SVHN, scene text recognition and ImageNet dataset demonstrate that we can achieve $3.3 \times$ speedup or $3.6 \times$ parameter reduction with less than 1\% drop in accuracy, showing the effectiveness and efficiency of our method. Moreover, the computation efficiency of Kronecker layer makes using larger feature map possible, which in turn enables us to outperform the previous state-of-the-art on both SVHN(digit recognition) and CASIA-HWDB (handwritten Chinese character recognition) datasets.