OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Testing of Excluded Subgraphs
Venue: arXiv cs.DC 2016
Year: 2016

We study property testing in the context of distributed computing, under the classical CONGEST model. It is known that testing whether a graph is triangle-free can be done in a constant number of rounds, where the constant depends on how far the input graph is from being triangle-free. We show that, for every connected 4-node graph H, testing whether a graph is H-free can be done in a constant number of rounds too. The constant also depends on how far the input graph is from being H-free, and the dependence is identical to the one in the case of testing triangles. Hence, in particular, testing whether a graph is K_4-free, and testing whether a graph is C_4-free can be done in a constant number of rounds (where K_k denotes the k-node clique, and C_k denotes the k-node cycle). On the other hand, we show that testing K_k-freeness and C_k-freeness for k>4 appear to be much harder. Specifically, we investigate two natural types of generic algorithms for testing H-freeness, called DFS tester and BFS tester. The latter captures the previously known algorithm to test the presence of triangles, while the former captures our generic algorithm to test the presence of a 4-node graph pattern H. We prove that both DFS and BFS testers fail to test K_k-freeness and C_k-freeness in a constant number of rounds for k>4.
Sub-vector Extraction and Cascade Post-Processing for Speaker Verification Using MLLR Super-vectors
Venue: arXiv cs.SD 2016
Year: 2016

In this paper, we propose a speaker-verification system based on maximum likelihood linear regression (MLLR) super-vectors, for which speakers are characterized by m-vectors. These vectors are obtained by a uniform segmentation of the speaker MLLR super-vector using an overlapped sliding window. We consider three approaches for MLLR transformation, based on the conventional $1$-best automatic transcription, on the lattice word transcription, or on a simple global universal background model (UBM). Session variability compensation is performed in a post-processing module with probabilistic linear discriminant analysis (PLDA) or the eigen factor radial (EFR). Alternatively, we propose a cascade post-processing for the MLLR super-vector based speaker-verification system. In this case, the m-vectors or MLLR super-vectors are first projected onto a lower-dimensional vector space generated by linear discriminant analysis (LDA). Next, PLDA session variability compensation and scoring is applied to the reduced-dimensional vectors. This approach combines the advantages of both techniques and makes the estimation of PLDA parameters easier. Experimental results on telephone conversations of the NIST 2008 and 2010 speaker recognition evaluation (SRE) indicate that the proposed m-vector system performs significantly better than the conventional system based on the full MLLR super-vectors. Cascade post-processing further reduces the error rate in all cases. Finally, we present the results of fusion with a standard i-vector system in the feature, as well as in the score domain, demonstrating that the m-vector system is both competitive and complementary with it.
Fast Graph-Based Object Segmentation for RGB-D Images
Venue: arXiv cs.CV 2016
Year: 2016

Object segmentation is an important capability for robotic systems, in particular for grasping. We present a graph- based approach for the segmentation of simple objects from RGB-D images. We are interested in segmenting objects with large variety in appearance, from lack of texture to strong textures, for the task of robotic grasping. The algorithm does not rely on image features or machine learning. We propose a modified Canny edge detector for extracting robust edges by using depth information and two simple cost functions for combining color and depth cues. The cost functions are used to build an undirected graph, which is partitioned using the concept of internal and external differences between graph regions. The partitioning is fast with O(NlogN) complexity. We also discuss ways to deal with missing depth information. We test the approach on different publicly available RGB-D object datasets, such as the Rutgers APC RGB-D dataset and the RGB-D Object Dataset, and compare the results with other existing methods.
A new system of coordinates for the tilings $\{p,3\}$ and $\{p$$-$$2,4\}$
Venue: arXiv cs.CG 2016
Year: 2016

In this paper, we indicate a new way to define coordinates for the tiles of the tilings $\{p,3\}$ and $\{p$$-$$2,4\}$ where the natural number $p$ satisfies $p\geq 7$.
Backward-Shifted Strategies Based on SVC for HTTP Adaptive Video Streaming
Venue: arXiv cs.MM 2016
Year: 2016

Although HTTP-based video streaming can easily penetrate firewalls and profit from Web caches, the underlying TCP may introduce large delays in case of a sudden capacity loss. To avoid an interruption of the video stream in such cases we propose the Backward-Shifted Coding (BSC). Based on Scalable Video Coding (SVC), BSC adds a time-shifted layer of redundancy to the video stream such that future frames are downloaded at any instant. This pre-fetched content maintains a fluent video stream even under highly variant network conditions and leads to high Quality of Experience (QoE). We characterize this QoE gain by analyzing initial buffering time, re-buffering time and content resolution using the Ballot theorem. The probability generating functions of the playback interruption and of the initial buffering latency are provided in closed form. We further compute the quasi-stationary distribution of the video quality, in order to compute the average quality, as well as temporal variability in video quality. Employing these analytic results to optimize QoE shows interesting trade-offs and video streaming at outstanding fluency.
Spotting the diffusion of New Psychoactive Substances over the Internet
Venue: arXiv cs.CY 2016
Year: 2016

Online availability and diffusion of New Psychoactive Substances (NPS) represent an emerging threat to healthcare systems. In this work, we analyse drugs forums, online shops, and Twitter. By mining the data from these sources, it is possible to understand the dynamics of drugs diffusion and their endorsement, as well as timely detecting new substances. We propose a set of visual analytics tools to support analysts in tackling NPS spreading and provide a better insight about drugs market and analysis.
Noisy Parallel Approximate Decoding for Conditional Recurrent Language Model
Venue: arXiv cs.CL 2016
Year: 2016

Recent advances in conditional recurrent language modelling have mainly focused on network architectures (e.g., attention mechanism), learning algorithms (e.g., scheduled sampling and sequence-level training) and novel applications (e.g., image/video description generation, speech recognition, etc.) On the other hand, we notice that decoding algorithms/strategies have not been investigated as much, and it has become standard to use greedy or beam search. In this paper, we propose a novel decoding strategy motivated by an earlier observation that nonlinear hidden layers of a deep neural network stretch the data manifold. The proposed strategy is embarrassingly parallelizable without any communication overhead, while improving an existing decoding algorithm. We extensively evaluate it with attention-based neural machine translation on the task of En->Cz translation.
Cross-Section Evidence-based Timelines for Software Process Improvement Retrospectives: A Case Study of User eXperience Integration
Venue: arXiv cs.SE 2016
Year: 2016

Although integrating UX practices into software development processes is a type of Software Process Improvement (SPI) activity, this has not yet been taken into account in UX publications. In this study, we approach UX integration in a software development company in Sweden from a SPI perspective. Following the guidelines in SPI literature, we performed a retrospective meeting at the company to reflect on their decade of SPI activities for enhancing UX integration. The aim of the meeting was to reflect on, learn from, and coordinate various activities spanned across various organizational units and projects. We therefore supported the meeting by a pre- generated timeline of the main activities in the organization that is different from common project retrospective meetings in SPI. This approach is a refinement of a similar approach that is used in Agile projects, and is shown to improve effectiveness of, and decrease memory bias. We hypothesized that this method can be useful in the context of UX integration, and in this broader scope. To evaluate the method we gathered practitioners' view through a questionnaire. The findings showed our hypothesis to be plausible. Here, we present that UX integration research and practice can benefit from the SPI body of knowledge; We also show that such cross-section evidence-based timeline retrospective meetings are useful for UX integration, and in a larger scale than one project, especially for identifying and reflecting on 'organizational issues'. This approach also provides a cross- section longitudinal overview of the SPI activities that cannot easily be gained in other common SPI learning approaches.
Pulse Shaping Diversity to Enhance Throughput in Ultra-Dense Small Cell Networks
Venue: arXiv cs.IT 2016
Year: 2016

Spatial multiplexing (SM) gains in multiple input multiple output (MIMO) cellular networks are limited when used in combination with ultra-dense small cell networks. This limitation is due to large spatial correlation among channel pairs. More specifically, it is due to i) line-of-sight (LOS) communication between user equipment (UE) and base station (BS) and ii) in-sufficient spacing between antenna elements. We propose to shape transmit signals at adjacent antennas with distinct interpolating filters which introduces pulse shaping diversity eventually leading to improved SINR and throughput at the UEs. In this technique, each antenna transmits its own data stream with a relative offset with respect to adjacent antenna. The delay which must be a fraction of symbol period is interpolated with the pulse shaped signal and generates a virtual MIMO channel that leads to improved diversity and SINR at the receiver. Note that non-integral sampling periods with inter-symbol interference (ISI) should be mitigated at the receiver. For this, we propose to use a fractionally spaced equalizer (FSE) designed based on the minimum mean squared error (MMSE) criterion. Simulation results show that for a 2x2 MIMO and with inter-site-distance (ISD) of 50 m, the median received SINR and throughput at the UE improves by a factor of 11 dB and 2x, respectively, which verifies that pulse shaping can overcome poor SM gains in ultra-dense small cell networks.
Secure and trusted white-box verification
Venue: arXiv cs.CR 2016
Year: 2016

Verification is the process of checking whether a product has been implemented according to its prescribed specifications. We study the case of a designer (the developer) that needs to verify its design by a third party (the verifier), by making publicly available a limited amount of information about the design, namely a diagram of interconnections between the different design components, but not the components themselves or the intermediate values passed between components. We formalize this notion of limited information using tabular expressions as the description method for both the specifications and the design. Treating verification as a process akin to testing, we develop protocols that allow for the design to be verified on a set of inputs generated by the verifier, using any test-case generating algorithm that can take advantage of this extra available information (partially white-box testing), and without compromising the developer's secret information. Our protocols work with both trusted and untrusted developers, and allow for the checking of the correctness of the verification process itself by any third party, and at any time.
Competitive analysis of the top-K ranking problem
Venue: arXiv cs.DS 2016
Year: 2016

Motivated by applications in recommender systems, web search, social choice and crowdsourcing, we consider the problem of identifying the set of top $K$ items from noisy pairwise comparisons. In our setting, we are non-actively given $r$ pairwise comparisons between each pair of $n$ items, where each comparison has noise constrained by a very general noise model called the strong stochastic transitivity (SST) model. We analyze the competitive ratio of algorithms for the top-$K$ problem. In particular, we present a linear time algorithm for the top-$K$ problem which has a competitive ratio of $\tilde{O}(\sqrt{n})$; i.e. to solve any instance of top-$K$, our algorithm needs at most $\tilde{O}(\sqrt{n})$ times as many samples needed as the best possible algorithm for that instance (in contrast, all previous known algorithms for the top-$K$ problem have competitive ratios of $\tildeΩ(n)$ or worse). We further show that this is tight: any algorithm for the top-$K$ problem has competitive ratio at least $\tildeΩ(\sqrt{n})$.
Afterburner: The Case for In-Browser Analytics
Venue: arXiv cs.DB 2016
Year: 2016

This paper explores the novel and unconventional idea of implementing an analytical RDBMS in pure JavaScript so that it runs completely inside a browser with no external dependencies. Our prototype, called Afterburner, generates compiled query plans that exploit typed arrays and asm.js, two relatively recent advances in JavaScript. On a few simple queries, we show that Afterburner achieves comparable performance to MonetDB running natively on the same machine. This is an interesting finding in that it shows how far JavaScript has come as an efficient execution platform. Beyond a mere technical curiosity, we discuss how our techniques could support ubiquitous in-browser interactive analytics (potentially integrating with browser-based notebooks) and also present interesting opportunities for split-execution strategies where query operators are distributed between the browser and backend servers.
Energy Optimization of Memory Intensive Parallel workloads
Venue: arXiv cs.DC 2016
Year: 2016

Energy consumption is an important concern in modern multicore processors. The energy consumed during the execution of an application can be minimized by tuning the hardware state utilizing knobs such as frequency, voltage etc. The existing theoretical work on energy mini- mization using Global DVFS (Dynamic Voltage and Frequency Scaling), despite being thorough, ignores the energy consumed by the CPU on memory accesses and the dynamic energy consumed by the idle cores. This article presents an analytical model for the performance and the overall energy consumed by the CPU chip on CPU instructions as well as the memory accesses without ignoring the dynamic energy consumed by the idle cores. We present an analytical framework around our energy-performance model to predict the operating frequencies for global DVFS that minimize the overall CPU energy consumption within a performance budget. Finally, we suggest a scheduling criteria for energy aware scheduling of memory intensive parallel applications.
Estimating the number of receiving nodes in 802.11 networks via machine learning techniques
Venue: arXiv cs.NI 2016
Year: 2016

Nowadays, most mobile devices are equipped with multiple wireless interfaces, causing an emerging research interest in device to device (D2D) communication: the idea behind the D2D paradigm is to exploit the proper interface to directly communicate with another user, without traversing any network infrastructure. A first issue related to this paradigm consists in the need for a coordinator, called controller, able to decide when activating a D2D connection is appropriate and eventually able to manage such connection. In this view, the paradigm of Software Defined Networking (SDN), can be exploited both to handle the data flows among the devices and to interact directly with every device. This work is focused on a scenario where a device is selected by the SDN controller, in order to become the master node of a WiFi-Direct network. The remaining nodes, called clients, can exchange data with other nodes through the master. The objective is to infer, through different Machine Learning approaches, the number of nodes actively involved in receiving data, exploiting only the information available at the client side and without modifying any standard communication protocol. The information about the number of client nodes is crucial when, e.g., a user desires a precise prediction of the transmission estimated time of arrival (ETA) while downloading a file.
Searching Lattice Data Structures of Varying Degrees of Sortedness
Venue: arXiv cs.DS 2016
Year: 2016

Lattice data structures are space efficient and cache-suitable data structures. The basic searching, insertion, and deletion operations are of time complexity $O(\sqrt{N})$. We give a jump searching algorithm of time complexity $O(J(L)\log(N))$, where $J(L)$ is the jump factor of the lattice. $J(L)$ approaches $4$ when the degree of sortedness of the lattice approaches $\sqrt{N}$. A sorting procedure of time complexity $O(\sqrt{N})$ that can be used, during the system idle time, to increase the degree of sortedness of the lattice is given.
Semantometrics: Towards Fulltext-based Research Evaluation
Venue: arXiv cs.DL 2016
Year: 2016

Over the recent years, there has been a growing interest in developing new research evaluation methods that could go beyond the traditional citation-based metrics. This interest is motivated on one side by the wider availability or even emergence of new information evidencing research performance, such as article downloads, views and Twitter mentions, and on the other side by the continued frustrations and problems surrounding the application of purely citation-based metrics to evaluate research performance in practice. Semantometrics are a new class of research evaluation metrics which build on the premise that full-text is needed to assess the value of a publication. This paper reports on the analysis carried out with the aim to investigate the properties of the semantometric contribution measure, which uses semantic similarity of publications to estimate research contribution, and provides a comparative study of the contribution measure with traditional bibliometric measures based on citation counting.
Robust On-line Matrix Completion on Graphs
Venue: arXiv cs.IT 2016
Year: 2016

We study online robust matrix completion on graphs. At each iteration a vector with some entries missing is revealed and our goal is to reconstruct it by identifying the underlying low-dimensional subspace from which the vectors are drawn. We assume there is an underlying graph structure to the data, that is, the components of each vector correspond to nodes of a certain (known) graph, and their values are related accordingly. We give algorithms that exploit the graph to reconstruct the incomplete data, even in the presence of outlier noise. The theoretical properties of the algorithms are studied and numerical experiments using both synthetic and real world datasets verify the improved performance of the proposed technique compared to other state of the art algorithms.
Anytime Inference in Valuation Algebras
Venue: arXiv cs.AI 2016
Year: 2016

Anytime inference is inference performed incrementally, with the accuracy of the inference being controlled by a tunable parameter, usually time. Such anytime inference algorithms are also usually interruptible, gradually converging to the exact inference value until terminated. While anytime inference algorithms for specific domains like probability potentials exist in the literature, our objective in this article is to obtain an anytime inference algorithm which is sufficiently generic to cover a wide range of domains. For this we utilise the theory of generic inference as a basis for constructing an anytime inference algorithm, and in particular, extending work done on ordered valuation algebras. The novel contribution of this work is the construction of anytime algorithms in a generic framework, which automatically gives us instantiations in various useful domains. We also show how to apply this generic framework for anytime inference in semiring induced valuation algebras, an important subclass of valuation algebras, which includes instances like probability potentials, disjunctive normal forms and distributive lattices. Keywords: Approximation; Anytime algorithms; Resource-bounded computation; Generic inference; Valuation algebras; Local computation; Binary join trees.
Simultaneous Surface Reflectance and Fluorescence Spectra Estimation
Venue: arXiv cs.CV 2016
Year: 2016

There is widespread interest in estimating the fluorescence properties of natural materials in an image. However, the separation between reflected and fluoresced components is difficult, because it is impossible to distinguish reflected and fluoresced photons without controlling the illuminant spectrum. We show how to jointly estimate the reflectance and fluorescence from a single set of images acquired under multiple illuminants. We present a framework based on a linear approximation to the physical equations describing image formation in terms of surface spectral reflectance and fluorescence due to multiple fluorophores. We relax the non-convex, inverse estimation problem in order to jointly estimate the reflectance and fluorescence properties in a single optimization step and we use the Alternating Direction Method of Multipliers (ADMM) approach to efficiently find a solution. We provide a software implementation of the solver for our method and prior methods. We evaluate the accuracy and reliability of the method using both simulations and experimental data. To acquire data to test the methods, we built a custom imaging system using a monochrome camera, a filter wheel with bandpass transmissive filters and a small number of light emitting diodes. We compared the system and algorithm performance with the ground truth as well as with prior methods. Our approach produces lower errors compared to earlier algorithms.
Color Homography
Venue: arXiv cs.CV 2016
Year: 2016

We show the surprising result that colors across a change in viewing condition (changing light color, shading and camera) are related by a homography. Our homography color correction application delivers improved color fidelity compared with the linear least-square.
The Densest k-Subhypergraph Problem
Venue: arXiv cs.DS 2016
Year: 2016

The Densest $k$-Subgraph (D$k$S) problem, and its corresponding minimization problem Smallest $p$-Edge Subgraph (S$p$ES), have come to play a central role in approximation algorithms. This is due both to their practical importance, and their usefulness as a tool for solving and establishing approximation bounds for other problems. These two problems are not well understood, and it is widely believed that they do not an admit a subpolynomial approximation ratio (although the best known hardness results do not rule this out). In this paper we generalize both D$k$S and S$p$ES from graphs to hypergraphs. We consider the Densest $k$-Subhypergraph problem (given a hypergraph $(V, E)$, find a subset $W\subseteq V$ of $k$ vertices so as to maximize the number of hyperedges contained in $W$) and define the Minimum $p$-Union problem (given a hypergraph, choose $p$ of the hyperedges so as to minimize the number of vertices in their union). We focus in particular on the case where all hyperedges have size 3, as this is the simplest non-graph setting. For this case we provide an $O(n^{4(4-\sqrt{3})/13 + ε}) \leq O(n^{0.697831+ε})$-approximation (for arbitrary constant $ε> 0$) for Densest $k$-Subhypergraph and an $\tilde O(n^{2/5})$-approximation for Minimum $p$-Union. We also give an $O(\sqrt{m})$-approximation for Minimum $p$-Union in general hypergraphs. Finally, we examine the interesting special case of interval hypergraphs (instances where the vertices are a subset of the natural numbers and the hyperedges are intervals of the line) and prove that both problems admit an exact polynomial time solution on these instances.