OpenRaiser/Intern-Atlas huggingface dataset:
Studies and analysis of reference management software: a literature review
Venue: arXiv cs.DL 2015
Year: 2015

Reference management software is a well-known tool for scientific research work. Since the 1980s, it has been the subject of reviews and evaluations in library and information science literature. This paper presents a systematic review of published studies that evaluate reference management software with a comparative approach. The objective is to identify the types, models, and evaluation criteria that authors have adopted, in order to determine whether the methods used provide adequate methodological rigor and useful contributions to the field of study.
Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAP
Venue: arXiv cs.DS 2015
Year: 2015

In Part I, we study a special case of the unweighted Tree Augmentation Problem (TAP) via the Lasserre (Sum of Squares) system. In the special case, we forbid so-called stems; these are a particular type of subtree configuration. For stemless TAP, we prove that the integrality ratio of an SDP relaxation (the Lasserre tightening of an LP relaxation) is $\leq \frac{3}{2}+ε$, where $ε>0$ can be any small constant. We obtain this result by designing a polynomial-time algorithm for stemless TAP that achieves an approximation guarantee of ($\frac32+ε$) relative to the SDP relaxation. The algorithm is combinatorial and does not solve the SDP relaxation, but our analysis relies on the SDP relaxation. We generalize the combinatorial analysis of integral solutions from the previous literature to fractional solutions by identifying some properties of fractional solutions of the Lasserre system via the decomposition result of Karlin, Mathieu and Nguyen (IPCO 2011). Also, we present an example of stemless TAP such that the approximation guarantee of $\frac32$ is tight for the algorithm. In Part II of this paper, we extend the methods of Part I to prove the same results relative to the same SDP relaxation for TAP.
Aggregations over Generalized Hypertree Decompositions
Venue: arXiv cs.DB 2015
Year: 2015

We study a class of aggregate-join queries with multiple aggregation operators evaluated over annotated relations. We show that straightforward extensions of standard multiway join algorithms and generalized hypertree decompositions (GHDs) provide best-known runtime guarantees. In contrast, prior work uses bespoke algorithms and data structures and does not match these guarantees. Our extensions to the standard techniques are a pair of simple tests that (1) determine if two orderings of aggregation operators are equivalent and (2) determine if a GHD is compatible with a given ordering. These tests provide a means to find an optimal GHD that, when provided to standard join algorithms, will correctly answer a given aggregate-join query. The second class of our contributions is a pair of complete characterizations of (1) the set of orderings equivalent to a given ordering and (2) the set of GHDs compatible with some equivalent ordering. We show by example that previous approaches are incomplete. The key technical consequence of our characterizations is a decomposition of a compatible GHD into a set of (smaller) {\em unconstrained} GHDs, i.e. into a set of GHDs of sub-queries without aggregations. Since this decomposition is comprised of unconstrained GHDs, we are able to connect to the wide literature on GHDs for join query processing, thereby obtaining improved runtime bounds, MapReduce variants, and an efficient method to find approximately optimal GHDs.
X-TREPAN: a multi class regression and adapted extraction of comprehensible decision tree in artificial neural networks
Venue: arXiv cs.LG 2015
Year: 2015

In this work, the TREPAN algorithm is enhanced and extended for extracting decision trees from neural networks. We empirically evaluated the performance of the algorithm on a set of databases from real world events. This benchmark enhancement was achieved by adapting Single-test TREPAN and C4.5 decision tree induction algorithms to analyze the datasets. The models are then compared with X-TREPAN for comprehensibility and classification accuracy. Furthermore, we validate the experimentations by applying statistical methods. Finally, the modified algorithm is extended to work with multi-class regression problems and the ability to comprehend generalized feed forward networks is achieved.
Social Interaction in the Flickr Social Network
Venue: arXiv cs.SI 2015
Year: 2015

Online social networking sites such as Facebook, Twitter and Flickr are among the most popular sites on the Web, providing platforms for sharing information and interacting with a large number of people. The different ways for users to interact, such as liking, retweeting and favoriting user-generated content, are among the defining and extremely popular features of these sites. While empirical studies have been done to learn about the network growth processes in these sites, few studies have focused on social interaction behaviour and the effect of social interaction on network growth. In this paper, we analyze large-scale data collected from the Flickr social network to learn about individual favoriting behaviour and examine the occurrence of link formation after a favorite is created. We do this using a systematic formulation of Flickr as a two-layer temporal multiplex network: the first layer describes the follow relationship between users and the second layer describes the social interaction between users in the form of favorite markings to photos uploaded by them. Our investigation reveals that (a) favoriting is well-described by preferential attachment, (b) over 50% of favorites are reciprocated within 10 days if at all they are reciprocated, (c) different kinds of favorites differ in how fast they are reciprocated, and (d) after a favorite is created, multiplex triangles are closed by the creation of follow links by the favoriter's followers to the favorite receiver.
Weighted Efficient Domination for $P_6$-Free Graphs in Polynomial Time
Venue: arXiv cs.DM 2015
Year: 2015

In a finite undirected graph $G=(V,E)$, a vertex $v \in V$ {\em dominates} itself and its neighbors in $G$. A vertex set $D \subseteq V$ is an {\em efficient dominating set} ({\em e.d.} for short) of $G$ if every $v \in V$ is dominated in $G$ by exactly one vertex of $D$. The {\em Efficient Domination} (ED) problem, which asks for the existence of an e.d. in $G$, is known to be NP-complete for $P_7$-free graphs but solvable in polynomial time for $P_5$-free graphs. The $P_6$-free case was the last open question for the complexity of ED on $F$-free graphs. Recently, Lokshtanov, Pilipczuk and van Leeuwen showed that weighted ED is solvable in polynomial time for $P_6$-free graphs, based on their sub-exponential algorithm for the Maximum Weight Independent Set problem for $P_6$-free graphs. Independently, at the same time, Mosca found a polynomial time algorithm for weighted ED on $P_6$-free graphs using a direct approach. In this paper, we describe the details of this approach which is simpler and much faster, namely its time bound is ${\cal O}(n^6 m)$.
Model Guided Sampling Optimization for Low-dimensional Problems
Venue: arXiv cs.NE 2015
Year: 2015

Optimization of very expensive black-box functions requires utilization of maximum information gathered by the process of optimization. Model Guided Sampling Optimization (MGSO) forms a more robust alternative to Jones' Gaussian-process-based EGO algorithm. Instead of EGO's maximizing expected improvement, the MGSO uses sampling the probability of improvement which is shown to be helpful against trapping in local minima. Further, the MGSO can reach close-to-optimum solutions faster than standard optimization algorithms on low dimensional or smooth problems.
Simultaneous Embeddings with Few Bends and Crossings
Venue: arXiv cs.CG 2015
Year: 2015

A simultaneous embedding with fixed edges (SEFE) of two planar graphs $R$ and $B$ is a pair of plane drawings of $R$ and $B$ that coincide when restricted to the common vertices and edges of $R$ and $B$. We show that whenever $R$ and $B$ admit a SEFE, they also admit a SEFE in which every edge is a polygonal curve with few bends and every pair of edges has few crossings. Specifically: (1) if $R$ and $B$ are trees then one bend per edge and four crossings per edge pair suffice (and one bend per edge is sometimes necessary), (2) if $R$ is a planar graph and $B$ is a tree then six bends per edge and eight crossings per edge pair suffice, and (3) if $R$ and $B$ are planar graphs then six bends per edge and sixteen crossings per edge pair suffice. Our results improve on a paper by Grilli et al. (GD'14), which proves that nine bends per edge suffice, and on a paper by Chan et al. (GD'14), which proves that twenty-four crossings per edge pair suffice.
OpenCL 2.0 for FPGAs using OCLAcc
Venue: arXiv cs.SE 2015
Year: 2015

Designing hardware is a time-consuming and complex process. Realization of both, embedded and high-performance applications can benefit from a design process on a higher level of abstraction. This helps to reduce development time and allows to iteratively test and optimize the hardware design during development, as common in software development. We present our tool, OCLAcc, which allows the generation of entire FPGA-based hardware accelerators from OpenCL and discuss the major novelties of OpenCL 2.0 and how they can be realized in hardware using OCLAcc.
In-Line-Test of Variability and Bit-Error-Rate of HfOx-Based Resistive Memory
Venue: arXiv cs.ET 2015
Year: 2015

Spatial and temporal variability of HfOx-based resistive random access memory (RRAM) are investigated for manufacturing and product designs. Manufacturing variability is characterized at different levels including lots, wafers, and chips. Bit-error-rate (BER) is proposed as a holistic parameter for the write cycle resistance statistics. Using the electrical in-line-test cycle data, a method is developed to derive BERs as functions of the design margin, to provide guidance for technology evaluation and product design. The proposed BER calculation can also be used in the off-line bench test and build-in-self-test (BIST) for adaptive error correction and for the other types of random access memories.
Fault Tolerant Control of Power Systems in presence of Sensor Failure
Venue: arXiv cs.SY 2015
Year: 2015

This paper addresses Fault Tolerant Control (FTC) of Large Power Systems (LPS) subject to sensor failure. Hiding the fault from the controller allows the nominal controller to remain in the loop. We assume specific faults that violate observability of a subsystem, and we cannot rely on these faulty subsystems when estimating states. We use a new method for reconfiguration control of these faults that lead to unobservability of subsystems. The method proposes augmenting a faulty subsystems with another subsystem(s) until a new subsystem is achieved that is observable. Next, finding the best subsystems among available candidates is considered and using structural analysis methods and grammian definition, a complete algorithm is proposed for FTC of LPS. The proposed approach is applied to the IEEE 14-bus test case and interactions are considered in nonlinear form. Simulation results show that the proposed approach works as intended.
Decidability of Equivalence of Aggregate Count-Distinct Queries
Venue: arXiv cs.DB 2015
Year: 2015

We address the problem of equivalence of count-distinct aggregate queries, prove that the problem is decidable, and can be decided in the third level of Polynomial hierarchy. We introduce the notion of core for conjunctive queries with comparisons as an extension of the classical notion for relational queries, and prove that the existence of isomorphism among cores of queries is a sufficient and necessary condition for equivalence of conjunctive queries with comparisons similar to the classical relational setting. However, it is not a necessary condition for equivalence of count-distinct queries. We introduce a relaxation of this condition based on a new notion, which is a potentially new query equivalent to the initial query, introduced to capture the behavior of count-distinct operator.
Dynamic Network Formation with Foresighted Agents
Venue: arXiv cs.GT 2015
Year: 2015

What networks can form and persist when agents are self-interested? Can such networks be efficient? A substantial theoretical literature predicts that the only networks that can form and persist must have very special shapes and that such networks cannot be efficient, but these predictions are in stark contrast to empirical findings. In this paper, we present a new model of network formation. In contrast to the existing literature, our model is dynamic (rather than static), we model agents as foresighted (rather than myopic) and we allow for the possibility that agents are heterogeneous (rather than homogeneous). We show that a very wide variety of networks can form and persist; in particular, efficient networks can form and persist if they provide every agent a strictly positive payoff. For the widely-studied connections model, we provide a full characterization of the set of efficient networks that can form and persist. Our predictions are consistent with empirical findings.
DiffSum - A Simple Post-Election Risk-Limiting Audit
Venue: arXiv cs.CY 2015
Year: 2015

This paper presents DiffSum, a simple post-election risk-limiting ballot-polling audit for two-candidate plurality elections. DiffSum sequentially draws ballots (without replacement) until the numbers $a$, $b$, of votes for candidates $A$, $B$ satisfies $a>b$ and $(a-b)^2 > c(a+b)$, where $A$ is the reported winner and $c$ is a suitably chosen constant. Bounds on the error rate (chance of approving an incorrect election outcome) are obtained via simulations. The method is compared with the Bravo method of Lindeman, Stark, and Yates.
Online Supervised Subspace Tracking
Venue: arXiv cs.LG 2015
Year: 2015

We present a framework for supervised subspace tracking, when there are two time series $x_t$ and $y_t$, one being the high-dimensional predictors and the other being the response variables and the subspace tracking needs to take into consideration of both sequences. It extends the classic online subspace tracking work which can be viewed as tracking of $x_t$ only. Our online sufficient dimensionality reduction (OSDR) is a meta-algorithm that can be applied to various cases including linear regression, logistic regression, multiple linear regression, multinomial logistic regression, support vector machine, the random dot product model and the multi-scale union-of-subspace model. OSDR reduces data-dimensionality on-the-fly with low-computational complexity and it can also handle missing data and dynamic data. OSDR uses an alternating minimization scheme and updates the subspace via gradient descent on the Grassmannian manifold. The subspace update can be performed efficiently utilizing the fact that the Grassmannian gradient with respect to the subspace in many settings is rank-one (or low-rank in certain cases). The optimization problem for OSDR is non-convex and hard to analyze in general; we provide convergence analysis of OSDR in a simple linear regression setting. The good performance of OSDR compared with the conventional unsupervised subspace tracking are demonstrated via numerical examples on simulated and real data.
Preprint Virtual Reality Assistant Technology for Learning Primary Geography
Venue: arXiv cs.HC 2015
Year: 2015

This is the preprint version of our paper on ICWL2015. A virtual reality based enhanced technology for learning primary geography is proposed, which synthesizes several latest information technologies including virtual reality(VR), 3D geographical information system(GIS), 3D visualization and multimodal human-computer-interaction (HCI). The main functions of the proposed system are introduced, i.e. Buffer analysis, Overlay analysis, Space convex hull calculation, Space convex decomposition, 3D topology analysis and 3D space intersection detection. The multimodal technologies are employed in the system to enhance the immersive perception of the users.
Trusted routing vs. VPN for secured data transfer over IP-networks/Internet
Venue: arXiv cs.NI 2015
Year: 2015

Though objectives of trusted routing and virtual private networks (VPN) data transfer methods are to guarantee data transfer securely to from senders to receivers over public networks like Internet yet there are paramount differences between the two methods. This paper analyses their differences.
Information Sets of Multiplicity Codes
Venue: arXiv cs.IT 2015
Year: 2015

We here provide a method for systematic encoding of the Multiplicity codes introduced by Kopparty, Saraf and Yekhanin in 2011. The construction is built on an idea of Kop-party. We properly define information sets for these codes and give detailed proofs of the validity of Kopparty's construction, that use generating functions. We also give a complexity estimate of the associated encoding algorithm.
Iterative hypothesis testing for multi-object tracking in presence of features with variable reliability
Venue: arXiv cs.CV 2015
Year: 2015

This paper assumes prior detections of multiple targets at each time instant, and uses a graph-based approach to connect those detections across time, based on their position and appearance estimates. In contrast to most earlier works in the field, our framework has been designed to exploit the appearance features, even when they are only sporadically available, or affected by a non-stationary noise, along the sequence of detections. This is done by implementing an iterative hypothesis testing strategy to progressively aggregate the detections into short trajectories, named tracklets. Specifically, each iteration considers a node, named key-node, and investigates how to link this key-node with other nodes in its neighborhood, under the assumption that the target appearance is defined by the key-node appearance estimate. This is done through shortest path computation in a temporal neighborhood of the key-node. The approach is conservative in that it only aggregates the shortest paths that are sufficiently better compared to alternative paths. It is also multi-scale in that the size of the investigated neighborhood is increased proportionally to the number of detections already aggregated into the key-node. The multi-scale nature of the process and the progressive relaxation of its conservativeness makes it both computationally efficient and effective. Experimental validations are performed extensively on a toy example, a 15 minutes long multi-view basketball dataset, and other monocular pedestrian datasets.
Receiving Pseudorandom PSK
Venue: arXiv cs.IT 2015
Year: 2015

Pseudorandom PSK [1] enables parallel communication on the same carrier frequency and at the same time. We propose different signal processing methods to receive data modulated with pseudorandom PSK. This includes correlation with the carrier frequency which can be applied to signals in the kHz to MHz range and signal processing in the intermediate frequency where the correlation with the carrier frequency is performed analogous in the RF front end. We analyze the computation complexity for signal processing with the parameters of symbol length $T$ and number of repetitions of each symbol $K$ with pseudorandom PSK and show that the number of operations for each sampling point is $Θ\left(K\right)$.
In-Network View Synthesis for Interactive Multiview Video Systems
Venue: arXiv cs.MM 2015
Year: 2015

To enable Interactive multiview video systems with a minimum view-switching delay, multiple camera views are sent to the users, which are used as reference images to synthesize additional virtual views via depth-image-based rendering. In practice, bandwidth constraints may however restrict the number of reference views sent to clients per time unit, which may in turn limit the quality of the synthesized viewpoints. We argue that the reference view selection should ideally be performed close to the users, and we study the problem of in-network reference view synthesis such that the navigation quality is maximized at the clients. We consider a distributed cloud network architecture where data stored in a main cloud is delivered to end users with the help of cloudlets, i.e., resource-rich proxies close to the users. In order to satisfy last-hop bandwidth constraints from the cloudlet to the users, a cloudlet re-samples viewpoints of the 3D scene into a discrete set of views (combination of received camera views and virtual views synthesized) to be used as reference for the synthesis of additional virtual views at the client. This in-network synthesis leads to better viewpoint sampling given a bandwidth constraint compared to simple selection of camera views, but it may however carry a distortion penalty in the cloudlet-synthesized reference views. We therefore cast a new reference view selection problem where the best subset of views is defined as the one minimizing the distortion over a view navigation window defined by the user under some transmission bandwidth constraints. We show that the view selection problem is NP-hard, and propose an effective polynomial time algorithm using dynamic programming to solve the optimization problem. Simulation results finally confirm the performance gain offered by virtual view synthesis in the network.
Implication of Unobservable State-and-topology Cyber-physical Attacks
Venue: arXiv cs.SY 2015
Year: 2015

This paper studies the physical consequences of a class of unobservable state-and-topology cyber-physical attacks in which both state and topology data for a sub-network of the network are changed by an attacker to mask a physical attack. The problem is formulated as a two-stage optimization problem which aims to cause overload in a line of the network with limited attack resources. It is shown that unobservable state-and-topology cyber-physical attacks as studied in this paper can make the system operation more vulnerable to line outages and failures.
Stability analysis of sampled-data switched systems with quantization
Venue: arXiv cs.SY 2015
Year: 2015

We propose a stability analysis method for sampled-data switched linear systems with finite-level static quantizers. In the closed-loop system, information on the active mode of the plant is transmitted to the controller only at each sampling time. This limitation of switching information leads to a mode mismatch between the plant and the controller, and the system may become unstable. A mode mismatch also makes it difficult to find an attractor set to which the state trajectory converges. A switching condition for stability is characterized by the total time when the modes of the plant and the controller are different. Under the condition, we derive an ultimate bound on the state trajectories by using a common Lyapunov function computed from a randomized algorithm. The switching condition can be reduced to a dwell-time condition.
Turing's Imitation Game has been Improved
Venue: arXiv cs.AI 2015
Year: 2015

Using the recently introduced universal computing model, called orchestrated machine, that represents computations in a dissipative environment, we consider a new kind of interpretation of Turing's Imitation Game. In addition we raise the question whether the intelligence may show fractal properties. Then we sketch a vision of what robotic cars are going to do in the future. Finally we give the specification of an artificial life game based on the concept of orchestrated machines. The purpose of this paper is to start the search for possible relationships between these different topics.