OpenRaiser/Intern-Atlas huggingface dataset:
JADE, TraSMAPI and SUMO: A tool-chain for simulating traffic light control
Venue: arXiv cs.MA 2016
Year: 2016

Increased stress, fuel consumption, air pollution, accidents and delays are some of the consequences of traffic congestion usually incurring in tremendous economic impacts, which society aims to remedy in order to leverage a sustainable development. Recently, unconventional means for modeling and controlling such complex traffic systems relying on multi-agent systems have arisen. This paper contributes to the understanding of such complex and highly dynamic systems by proposing an open-source tool-chain to implement multi-agent-based solutions in traffic and transportation. The proposed approach relies on two very popular tools in both domains, with focus on traffic light control. This tool-chain consists in combining JADE (Java Agent DEvelopment Framework), for the implementation of multi-agent systems, with SUMO (Simulation of Urban MObility), for the microscopic simulation of traffic interactions. TraSMAPI (Traffic Simulation Manager Application Programming Interface) is used to combine JADE and SUMO allowing communication between them. A demonstration of the concept is presented to illustrate the main features of this tool-chain, using Q-Learning as the reinforcement learning method for each traffic light agent in a simulated network. Results demonstrate the feasibility of the proposed framework as a practical means to experiment with different agent-based designs of intelligent transportation solutions.
Factorizing the factorization - a spectral-element solver for elliptic equations with linear operation count
Venue: arXiv cs.NA 2016
Year: 2016

High-order methods gain more and more attention in computational fluid dynamics. However, the potential advantage of these methods depends critically on the availability of efficient elliptic solvers. With spectral-element methods, static condensation is a common approach to reduce the number of degree of freedoms and to improve the condition of the algebraic equations. The resulting system is block-structured and the face-based operator well suited for matrix-matrix multiplications. However, a straight-forward implementation scales super-linearly with the number of unknowns and, therefore, prohibits the application to high polynomial degrees. This paper proposes a novel factorization technique, which yields a linear operation count of just 13N multiplications, where N is the total number of unknowns. In comparison to previous work it saves a factor larger than 3 and clearly outpaces unfactored variants for all polynomial degrees. Using the new technique as a building block for a preconditioned conjugate gradient method resulted in a runtime scaling linearly with N for polynomial degrees $2 \leq p \leq 32$ . Moreover the solver proved remarkably robust for aspect ratios up to 128.
Reversible Logic Circuit Complexity Analysis via Functional Decomposition
Venue: arXiv cs.ET 2016
Year: 2016

Reversible computation is gaining increasing relevance in the context of several post-CMOS technologies, the most prominent of those being Quantum computing. One of the key theoretical problem pertaining to reversible logic synthesis is the upper bound of the gate count. Compared to the known bounds, the results obtained by optimal synthesis methods are significantly less. In this paper, we connect this problem with the multiplicative complexity analysis of classical Boolean functions. We explore the possibility of relaxing the ancilla and if that approach makes the upper bound tighter. Our results are negative. The ancilla-free synthesis methods by using transformations and by starting from an Exclusive Sum-of-Product (ESOP) formulation remain, theoretically, the synthesis methods for achieving least gate count for the cases where the number of variables $n$ is $< 8$ and otherwise, respectively.
Extracting Keyword for Disambiguating Name Based on the Overlap Principle
Venue: arXiv cs.IR 2016
Year: 2016

Name disambiguation has become one of the main themes in the Semantic Web agenda. The semantic web is an extension of the current Web in which information is not only given well-defined meaning, but also has many purposes that contain the ambiguous naturally or a lot of thing came with the overlap, mainly deals with the persons name. Therefore, we develop an approach to extract keywords from web snippet with utilizing the overlap principle, a concept to understand things with ambiguous, whereby features of person are generated for dealing with the variety of web, the web is steadily gaining ground in the semantic research.
Source and Physical-Layer Network Coding for Correlated Two-Way Relaying
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we study a half-duplex two-way relay channel (TWRC) with correlated sources exchanging bidirectional information. In the case, when both sources have the knowledge of correlation statistics, a source compression with physical-layer network coding (SCPNC) scheme is proposed to perform the distributed compression at each source node. When only the relay has the knowledge of correlation statistics, we propose a relay compression with physical-layer network coding (RCPNC) scheme to compress the bidirectional messages at the relay. The closed-form block error rate (BLER) expressions of both schemes are derived and verified through simulations. It is shown that the proposed schemes achieve considerable improvements in both error performance and throughput compared with the conventional non-compression scheme in correlated two-way relay networks (CTWRNs).
Unsupervised Deep Hashing for Large-scale Visual Search
Venue: arXiv cs.CV 2016
Year: 2016

Learning based hashing plays a pivotal role in large-scale visual search. However, most existing hashing algorithms tend to learn shallow models that do not seek representative binary codes. In this paper, we propose a novel hashing approach based on unsupervised deep learning to hierarchically transform features into hash codes. Within the heterogeneous deep hashing framework, the autoencoder layers with specific constraints are considered to model the nonlinear mapping between features and binary codes. Then, a Restricted Boltzmann Machine (RBM) layer with constraints is utilized to reduce the dimension in the hamming space. Extensive experiments on the problem of visual search demonstrate the competitiveness of our proposed approach compared to state-of-the-art.
Technical Report: Representing SES Cases Using Ontology
Venue: arXiv cs.DL 2016
Year: 2016

Socio-ecological System (SES) research studies the interaction between environment, users, and governance of environment resources. Data produced during the research cycle can be both long-tail (e.g. heterogeneous) and longitudinal data. For example, the IFRI (International Forestry Resources and Institutions) data set contains studies carried out over a period of 20 years. Given the complexity of a SES system, case studies that are accumulated over time and from different sites (e.g. site visit cases) are highly valuable in the understanding of new SES system behavior for instance. We, as a group of informatics researchers collaborating with personnel from the Workshop in Political Theory and Policy Analysis at Indiana University, are developing informatics approaches to facilitating SES scholars' research. Here we focus on presenting our work on representing SES cases using ontology. An ontology for the SES field can help organize concepts in the field, describe resources such as data and publications using a shared vocabulary, and also facilitate data use and query for researchers. We develop a core SES ontology, which contains core concepts and resources in the field and can be used to describe actual concept and resource instances, and also a tool for contributing instances by drawing graphs, called Cmap2SES.
The Capacity of Online (Causal) $q$-ary Error-Erasure Channels
Venue: arXiv cs.IT 2016
Year: 2016

In the $q$-ary online (or "causal") channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword $\mathbf{x} =(x_1,\ldots,x_n) \in \{0,1,\ldots,q-1\}^n$ symbol by symbol via a channel limited to at most $pn$ errors and/or $p^{*} n$ erasures. The channel is "online" in the sense that at the $i$th step of communication the channel decides whether to corrupt the $i$th symbol or not based on its view so far, i.e., its decision depends only on the transmitted symbols $(x_1,\ldots,x_i)$. This is in contrast to the classical adversarial channel in which the corruption is chosen by a channel that has a full knowledge on the sent codeword $\mathbf{x}$. In this work we study the capacity of $q$-ary online channels for a combined corruption model, in which the channel may impose at most $pn$ {\em errors} and at most $p^{*} n$ {\em erasures} on the transmitted codeword. The online channel (in both the error and erasure case) has seen a number of recent studies which present both upper and lower bounds on its capacity. In this work, we give a full characterization of the capacity as a function of $q,p$, and $p^{*}$.
Bit-Planes: Dense Subpixel Alignment of Binary Descriptors
Venue: arXiv cs.CV 2016
Year: 2016

Binary descriptors have been instrumental in the recent evolution of computationally efficient sparse image alignment algorithms. Increasingly, however, the vision community is interested in dense image alignment methods, which are more suitable for estimating correspondences from high frame rate cameras as they do not rely on exhaustive search. However, classic dense alignment approaches are sensitive to illumination change. In this paper, we propose an easy to implement and low complexity dense binary descriptor, which we refer to as bit-planes, that can be seamlessly integrated within a multi-channel Lucas & Kanade framework. This novel approach combines the robustness of binary descriptors with the speed and accuracy of dense alignment methods. The approach is demonstrated on a template tracking problem achieving state-of-the-art robustness and faster than real-time performance on consumer laptops (400+ fps on a single core Intel i7) and hand-held mobile devices (100+ fps on an iPad Air 2).
Bandits meet Computer Architecture: Designing a Smartly-allocated Cache
Venue: arXiv cs.LG 2016
Year: 2016

In many embedded systems, such as imaging sys- tems, the system has a single designated purpose, and same threads are executed repeatedly. Profiling thread behavior, allows the system to allocate each thread its resources in a way that improves overall system performance. We study an online resource al- locationproblem,wherearesourcemanagersimulta- neously allocates resources (exploration), learns the impact on the different consumers (learning) and im- proves allocation towards optimal performance (ex- ploitation). We build on the rich framework of multi- armed bandits and present online and offline algo- rithms. Through extensive experiments with both synthetic data and real-world cache allocation to threads we show the merits and properties of our al- gorithms
Visualizing Large-scale and High-dimensional Data
Venue: arXiv cs.LG 2016
Year: 2016

We study the problem of visualizing large-scale and high-dimensional data in a low-dimensional (typically 2D or 3D) space. Much success has been reported recently by techniques that first compute a similarity structure of the data points and then project them into a low-dimensional space with the structure preserved. These two steps suffer from considerable computational costs, preventing the state-of-the-art methods such as the t-SNE from scaling to large-scale and high-dimensional data (e.g., millions of data points and hundreds of dimensions). We propose the LargeVis, a technique that first constructs an accurately approximated K-nearest neighbor graph from the data and then layouts the graph in the low-dimensional space. Comparing to t-SNE, LargeVis significantly reduces the computational cost of the graph construction step and employs a principled probabilistic model for the visualization step, the objective of which can be effectively optimized through asynchronous stochastic gradient descent with a linear time complexity. The whole procedure thus easily scales to millions of high-dimensional data points. Experimental results on real-world data sets demonstrate that the LargeVis outperforms the state-of-the-art methods in both efficiency and effectiveness. The hyper-parameters of LargeVis are also much more stable over different data sets.
Is collaboration among scientists related to the citation impact of papers because their quality increases with collaboration? An analysis based on data from F1000Prime and normalized citation scores
Venue: arXiv cs.DL 2016
Year: 2016

In recent years, the relationship of collaboration among scientists and the citation impact of papers have been frequently investigated. Most of the studies show that the two variables are closely related: an increasing collaboration activity (measured in terms of number of authors, number of affiliations, and number of countries) is associated with an increased citation impact. However, it is not clear whether the increased citation impact is based on the higher quality of papers which profit from more than one scientist giving expert input or other (citation-specific) factors. Thus, the current study addresses this question by using two comprehensive datasets with publications (in the biomedical area) including quality assessments by experts (F1000Prime member scores) and citation data for the publications. The study is based on nearly 10,000 papers. Robust regression models are used to investigate the relationship between number of authors, number of affiliations, and number of countries, respectively, and citation impact - controlling for the papers' quality (measured by F1000Prime expert ratings). The results point out that the effect of collaboration activities on impact is largely independent of the papers' quality. The citation advantage is apparently not quality-related; citation specific factors (e.g. self-citations) seem to be important here.
Compressed Sensing for Implantable Neural Recordings Using Co-sparse Analysis Model and Weighted $\ell_1$-Optimization
Venue: arXiv cs.IT 2016
Year: 2016

Reliable and energy-efficient wireless data transmission remains a major challenge in resource-constrained wireless neural recording tasks, where data compression is generally adopted to relax the burdens on the wireless data link. Recently, Compressed Sensing (CS) theory has successfully demonstrated its potential in neural recording application. The main limitation of CS, however, is that the neural signals have no good sparse representation with commonly used dictionaries and learning a reliable dictionary is often data dependent and computationally demanding. In this paper, a novel CS approach for implantable neural recording is proposed. The main contributions are: 1) The co-sparse analysis model is adopted to enforce co-sparsity of the neural signals, therefore overcoming the drawbacks of conventional synthesis model and enhancing the reconstruction performance. 2) A multi-fractional-order difference matrix is constructed as the analysis dictionary, thus avoiding the dictionary learning procedure and reducing the need for previously acquired data and computational resources. 3) By exploiting the statistical priors of the analysis coefficients, a weighted analysis $\ell_1$-minimization (WALM) algorithm is proposed to reconstruct the neural signals. Experimental results on Leicester neural signal database reveal that the proposed approach outperforms the state-of-the-art CS-based methods. On the challenging high compression ratio task, the proposed approach still achieves high reconstruction performance and spike classification accuracy.
Efficiently Correcting Matrix Products
Venue: arXiv cs.DS 2016
Year: 2016

We study the problem of efficiently correcting an erroneous product of two $n\times n$ matrices over a ring. Among other things, we provide a randomized algorithm for correcting a matrix product with at most $k$ erroneous entries running in $\tilde{O}(n^2+kn)$ time and a deterministic $\tilde{O}(kn^2)$-time algorithm for this problem (where the notation $\tilde{O}$ suppresses polylogarithmic terms in $n$ and $k$).
Simulation Problems Over One-Counter Nets
Venue: arXiv cs.LO 2016
Year: 2016

One-counter nets (OCN) are finite automata equipped with a counter that can store non-negative integer values, and that cannot be tested for zero. Equivalently, these are exactly 1-dimensional vector addition systems with states. We show that both strong and weak simulation preorder on OCN are PSPACE-complete.
Information-Centric Connectivity
Venue: arXiv cs.NI 2016
Year: 2016

Mobile devices are often presented with multiple connectivity options usually making a selection either randomly or based on load/wireless conditions metrics, as is the case of current offloading schemes. In this paper we claim that link-layer connectivity can be associated with information-availability and in this respect connectivity decisions should be information-aware. This constitutes a next step for the Information-Centric Networking paradigm, realizing the concept of Information-Centric Connectivity (ICCON). We elaborate on different types of information availability and connectivity decisions in the context of ICCON, present specific use cases and discuss emerging opportunities, challenges and technical approaches. We illustrate the potential benefits of ICCON through preliminary simulation and numerical results in an example use case.
Improving PIE's performance over high-delay paths
Venue: arXiv cs.NI 2016
Year: 2016

Bufferbloat is excessive latency due to over- provisioned network buffers. PIE and CoDel are two recently proposed Active Queue Management (AQM) algorithms, designed to tackle bufferbloat by lowering the queuing delay without degrading the bottleneck utilization. PIE uses a proportional integral controller to maintain the average queuing delay at a desired level; however, large Round Trip Times (RTT) result in large spikes in queuing delays, which induce high dropping probability and low utilization. To deal with this problem, we propose Maximum and Average queuing Delay with PIE (MADPIE). Loosely based on the drop policy used by CoDel to keep queuing delay bounded, MADPIE is a simple extension to PIE that adds deterministic packet drops at controlled intervals. By means of simulations, we observe that our proposed change does not affect PIE's performance when RTT < 100 ms. The deterministic drops are more dominant when the RTT increases, which results in lower maximum queuing delays and better performance for VoIP traffic and small file downloads, with no major impact on bulk transfers.
Fast Computation of Minimal Interpolation Bases in Popov Form for Arbitrary Shifts
Venue: arXiv cs.SC 2016
Year: 2016

We compute minimal bases of solutions for a general interpolation problem, which encompasses Hermite-Padé approximation and constrained multivariate interpolation, and has applications in coding theory and security. This problem asks to find univariate polynomial relations between $m$ vectors of size $σ$; these relations should have small degree with respect to an input degree shift. For an arbitrary shift, we propose an algorithm for the computation of an interpolation basis in shifted Popov normal form with a cost of $\mathcal{O}\tilde{~}(m^{ω-1} σ)$ field operations, where $ω$ is the exponent of matrix multiplication and the notation $\mathcal{O}\tilde{~}(\cdot)$ indicates that logarithmic terms are omitted. Earlier works, in the case of Hermite-Padé approximation and in the general interpolation case, compute non-normalized bases. Since for arbitrary shifts such bases may have size $Θ(m^2 σ)$, the cost bound $\mathcal{O}\tilde{~}(m^{ω-1} σ)$ was feasible only with restrictive assumptions on the shift that ensure small output sizes. The question of handling arbitrary shifts with the same complexity bound was left open. To obtain the target cost for any shift, we strengthen the properties of the output bases, and of those obtained during the course of the algorithm: all the bases are computed in shifted Popov form, whose size is always $\mathcal{O}(m σ)$. Then, we design a divide-and-conquer scheme. We recursively reduce the initial interpolation problem to sub-problems with more convenient shifts by first computing information on the degrees of the intermediate bases.
Detection and localization of change points in temporal networks with the aid of stochastic block models
Venue: arXiv cs.SI 2016
Year: 2016

A framework based on generalized hierarchical random graphs (GHRGs) for the detection of change points in the structure of temporal networks has recently been developed by Peel and Clauset [1]. We build on this methodology and extend it to also include the versatile stochastic block models (SBMs) as a parametric family for reconstructing the empirical networks. We use five different techniques for change point detection on prototypical temporal networks, including empirical and synthetic ones. We find that none of the considered methods can consistently outperform the others when it comes to detecting and locating the expected change points in empirical temporal networks. With respect to the precision and the recall of the results of the change points, we find that the method based on a degree-corrected SBM has better recall properties than other dedicated methods, especially for sparse networks and smaller sliding time window widths.
Towards a topological fingerprint of music
Venue: arXiv cs.SD 2016
Year: 2016

Can music be represented as a meaningful geometric and topological object? In this paper, we propose a strategy to describe some music features as a polyhedral surface obtained by a simplicial interpretation of the \textit{Tonnetz}. The \textit{Tonnetz} is a graph largely used in computational musicology to describe the harmonic relationships of notes in equal tuning. In particular, we use persistent homology in order to describe the \textit{persistent} properties of music encoded in the aforementioned model. Both the relevance and the characteristics of this approach are discussed by analyzing some paradigmatic compositional styles. Eventually, the task of automatic music style classification is addressed by computing the hierarchical clustering of the topological fingerprints associated with some collections of compositions.
Distance-Sensitive Planar Point Location
Venue: arXiv cs.CG 2016
Year: 2016

Let $\mathcal{S}$ be a connected planar polygonal subdivision with $n$ edges that we want to preprocess for point-location queries, and where we are given the probability $γ_i$ that the query point lies in a polygon $P_i$ of $\mathcal{S}$. We show how to preprocess $\mathcal{S}$ such that the query time for a point~$p\in P_i$ depends on~$γ_i$ and, in addition, on the distance from $p$ to the boundary of~$P_i$---the further away from the boundary, the faster the query. More precisely, we show that a point-location query can be answered in time $O\left(\min \left(\log n, 1 + \log \frac{\mathrm{area}(P_i)}{γ_i Δ_{p}^2}\right)\right)$, where $Δ_{p}$ is the shortest Euclidean distance of the query point~$p$ to the boundary of $P_i$. Our structure uses $O(n)$ space and $O(n \log n)$ preprocessing time. It is based on a decomposition of the regions of $\mathcal{S}$ into convex quadrilaterals and triangles with the following property: for any point $p\in P_i$, the quadrilateral or triangle containing~$p$ has area $Ω(Δ_{p}^2)$. For the special case where $\mathcal{S}$ is a subdivision of the unit square and $γ_i=\mathrm{area}(P_i)$, we present a simpler solution that achieves a query time of $O\left(\min \left(\log n, \log \frac{1}{Δ_{p}^2}\right)\right)$. The latter solution can be extended to convex subdivisions in three dimensions.