OpenRaiser/Intern-Atlas huggingface dataset:
Implementation of the fast table grid user interface element for working with large database tables
Venue: arXiv cs.DB 2016
Year: 2016

Table grid user interface element with a vertical scrollbar is a standard way of working with database table records. There are two basic operations each grid should support: scrolling records with vertical scrollbar and positioning to a record with a given primary key. This paper addresses the case when the number of records is so large that it is not feasible to load them all into memory, and database functions like "select..offset" work insufficiently fast and put undue load on RDBMS. Our main idea is to use only queries that involve index lookup (a O(Log(N)-fast operation) and to use statistic properties of hypergeometric distribution to "guess" primary keys of records given their ordinal numbers. The proposed method allows us to implement a grid with O(Log(N))-fast scrolling and positioning performance.
Optimal Rebuilding of Multiple Erasures in MDS Codes
Venue: arXiv cs.IT 2016
Year: 2016

MDS array codes are widely used in storage systems due to their computationally efficient encoding and decoding procedures. An MDS code with $r$ redundancy nodes can correct any $r$ node erasures by accessing all the remaining information in the surviving nodes. However, in practice, $e$ erasures is a more likely failure event, for $1\le e<r$. Hence, a natural question is how much information do we need to access in order to rebuild $e$ storage nodes? We define the rebuilding ratio as the fraction of remaining information accessed during the rebuilding of $e$ erasures. In our previous work we constructed MDS codes, called zigzag codes, that achieve the optimal rebuilding ratio of $1/r$ for the rebuilding of any systematic node when $e=1$, however, all the information needs to be accessed for the rebuilding of the parity node erasure. The (normalized) repair bandwidth is defined as the fraction of information transmitted from the remaining nodes during the rebuilding process. For codes that are not necessarily MDS, Dimakis et al. proposed the regenerating codes framework where any $r$ erasures can be corrected by accessing some of the remaining information, and any $e=1$ erasure can be rebuilt from some subsets of surviving nodes with optimal repair bandwidth. In this work, we study 3 questions on rebuilding of codes: (i) We show a fundamental trade-off between the storage size of the node and the repair bandwidth similar to the regenerating codes framework, and show that zigzag codes achieve the optimal rebuilding ratio of $e/r$ for MDS codes, for any $1\le e\le r$. (ii) We construct systematic codes that achieve optimal rebuilding ratio of $1/r$, for any systematic or parity node erasure. (iii) We present error correction algorithms for zigzag codes, and in particular demonstrate how these codes can be corrected beyond their minimum Hamming distances.
New Convex Programs for Fisher's Market Model and its Generalizations
Venue: arXiv cs.GT 2016
Year: 2016

We present the following results pertaining to Fisher's market model: -We give two natural generalizations of Fisher's market model: In model M_1, sellers can declare an upper bound on the money they wish to earn (and take back their unsold good), and in model M_2, buyers can declare an upper bound on the amount to utility they wish to derive (and take back the unused part of their money). -We derive convex programs for the linear case of these two models by generalizing a convex program due to Shmyrev and the Eisenberg-Gale program, respectively. -We generalize the Arrow-Hurwicz theorem to the linear case of these two models, hence deriving alternate convex programs. -For the special class of convex programs having convex objective functions and linear constraints, we derive a simple set of rules for constructing the dual program (as simple as obtaining the dual of an LP). Using these rules we show a formal relationship between the two seemingly different convex programs for linear Fisher markets, due to Eisenberg-Gale and Shmyrev; the duals of these are the same, upto a change of variables.
Minimax Design and Order Estimation of FIR Filters for Extending the Bandwidth of ADCs
Venue: arXiv cs.IT 2016
Year: 2016

The bandwidth of the sampling systems, especially for time-interleaved analog-to-digital converters, needs to be extended along with the rapid increase of the sampling rate. A digitally assisted technique becomes a feasible approach to extend the analog bandwidth, as it is impractical to implement the extension in analog circuits. This paper derives accurate order estimation formulas for the bandwidth extension filter, which is designed in the minimax sense with the ripple constraints as the design criteria. The derived filter order estimation is significant in evaluating the computational complexity from the viewpoint of the top-level system design. Moreover, with the proposed order estimates, one can conveniently obtain the minimal order that satisfies the given ripple constraints, which contributes to reducing the design time. Both the performance of the extension filter and its order estimation are illustrated and demonstrated through simulation examples.
A Bayesian Model of Multilingual Unsupervised Semantic Role Induction
Venue: arXiv cs.CL 2016
Year: 2016

We propose a Bayesian model of unsupervised semantic role induction in multiple languages, and use it to explore the usefulness of parallel corpora for this task. Our joint Bayesian model consists of individual models for each language plus additional latent variables that capture alignments between roles across languages. Because it is a generative Bayesian model, we can do evaluations in a variety of scenarios just by varying the inference procedure, without changing the model, thereby comparing the scenarios directly. We compare using only monolingual data, using a parallel corpus, using a parallel corpus with annotations in the other language, and using small amounts of annotation in the target language. We find that the biggest impact of adding a parallel corpus to training is actually the increase in mono-lingual data, with the alignments to another language resulting in small improvements, even with labeled data for the other language.
Analyzing Games with Ambiguous Player Types using the ${\rm MINthenMAX}$ Decision Model
Venue: arXiv cs.GT 2016
Year: 2016

In many common interactive scenarios, participants lack information about other participants, and specifically about the preferences of other participants. In this work, we model an extreme case of incomplete information, which we term games with type ambiguity, where a participant lacks even information enabling him to form a belief on the preferences of others. Under type ambiguity, one cannot analyze the scenario using the commonly used Bayesian framework, and therefore he needs to model the participants using a different decision model. In this work, we present the ${\rm MINthenMAX}$ decision model under ambiguity. This model is a refinement of Wald's MiniMax principle, which we show to be too coarse for games with type ambiguity. We characterize ${\rm MINthenMAX}$ as the finest refinement of the MiniMax principle that satisfies three properties we claim are necessary for games with type ambiguity. This prior-less approach we present her also follows the common practice in computer science of worst-case analysis. Finally, we define and analyze the corresponding equilibrium concept assuming all players follow ${\rm MINthenMAX}$. We demonstrate this equilibrium by applying it to two common economic scenarios: coordination games and bilateral trade. We show that in both scenarios, an equilibrium in pure strategies always exists and we analyze the equilibria.
Sentiment Analysis in Scholarly Book Reviews
Venue: arXiv cs.CL 2016
Year: 2016

So far different studies have tackled the sentiment analysis in several domains such as restaurant and movie reviews. But, this problem has not been studied in scholarly book reviews which is different in terms of review style and size. In this paper, we propose to combine different features in order to be presented to a supervised classifiers which extract the opinion target expressions and detect their polarities in scholarly book reviews. We construct a labeled corpus for training and evaluating our methods in French book reviews. We also evaluate them on English restaurant reviews in order to measure their robustness across the domains and languages. The evaluation shows that our methods are enough robust for English restaurant reviews and French book reviews.
Getting More Out Of Syntax with PropS
Venue: arXiv cs.CL 2016
Year: 2016

Semantic NLP applications often rely on dependency trees to recognize major elements of the proposition structure of sentences. Yet, while much semantic structure is indeed expressed by syntax, many phenomena are not easily read out of dependency trees, often leading to further ad-hoc heuristic post-processing or to information loss. To directly address the needs of semantic applications, we present PropS -- an output representation designed to explicitly and uniformly express much of the proposition structure which is implied from syntax, and an associated tool for extracting it from dependency trees.
SourcererCC and SourcererCC-I: Tools to Detect Clones in Batch mode and During Software Development
Venue: arXiv cs.SE 2016
Year: 2016

Given the availability of large source-code repositories, there has been a large number of applications for large-scale clone detection. Unfortunately, despite a decade of active research, there is a marked lack in clone detectors that scale to big software systems or large repositories, specifically for detecting near-miss (Type 3) clones where significant editing activities may take place in the cloned code. This paper demonstrates: (i) SourcererCC, a token-based clone detector that targets the first three clone types, and exploits an index to achieve scalability to large inter-project repositories using a standard workstation. It uses an optimized inverted-index to quickly query the potential clones of a given code block. Filtering heuristics based on token ordering are used to significantly reduce the size of the index, the number of code-block comparisons needed to detect the clones, as well as the number of required token-comparisons needed to judge a potential clone, and (ii) SourcererCC-I, an Eclipse plug-in, that uses SourcererCC's core engine to identify and navigate clones (both inter and intra project) in real-time during software development. In our experiments, comparing SourcererCC with the state-of-the-art tools, we found that it is the only clone detection tool to successfully scale to 250 MLOC on a standard workstation with 12 GB RAM and efficiently detect the first three types of clones (precision 86% and recall 86-100%). Link to the demo: https://youtu.be/l7F_9Qp-ks4
Frequent-Itemset Mining using Locality-Sensitive Hashing
Venue: arXiv cs.DB 2016
Year: 2016

The Apriori algorithm is a classical algorithm for the frequent itemset mining problem. A significant bottleneck in Apriori is the number of I/O operation involved, and the number of candidates it generates. We investigate the role of LSH techniques to overcome these problems, without adding much computational overhead. We propose randomized variations of Apriori that are based on asymmetric LSH defined over Hamming distance and Jaccard similarity.
Smart Procurement of Naturally Generated Energy (SPONGE) for Plug-in Hybrid Electric Buses
Venue: arXiv cs.SY 2016
Year: 2016

We discuss a recently introduced ECO-driving concept known as SPONGE in the context of Plug-in Hybrid Electric Buses (PHEB)'s.Examples are given to illustrate the benefits of this approach to ECO-driving. Finally, distributed algorithms to realise SPONGE are discussed, paying attention to the privacy implications of the underlying optimisation problems.
Concentrated Differential Privacy
Venue: arXiv cs.DS 2016
Year: 2016

We introduce Concentrated Differential Privacy, a relaxation of Differential Privacy enjoying better accuracy than both pure differential privacy and its popular "(epsilon,delta)" relaxation without compromising on cumulative privacy loss over multiple computations.
A matter of words: NLP for quality evaluation of Wikipedia medical articles
Venue: arXiv cs.IR 2016
Year: 2016

Automatic quality evaluation of Web information is a task with many fields of applications and of great relevance, especially in critical domains like the medical one. We move from the intuition that the quality of content of medical Web documents is affected by features related with the specific domain. First, the usage of a specific vocabulary (Domain Informativeness); then, the adoption of specific codes (like those used in the infoboxes of Wikipedia articles) and the type of document (e.g., historical and technical ones). In this paper, we propose to leverage specific domain features to improve the results of the evaluation of Wikipedia medical articles. In particular, we evaluate the articles adopting an "actionable" model, whose features are related to the content of the articles, so that the model can also directly suggest strategies for improving a given article quality. We rely on Natural Language Processing (NLP) and dictionaries-based techniques in order to extract the bio-medical concepts in a text. We prove the effectiveness of our approach by classifying the medical articles of the Wikipedia Medicine Portal, which have been previously manually labeled by the Wiki Project team. The results of our experiments confirm that, by considering domain-oriented features, it is possible to obtain sensible improvements with respect to existing solutions, mainly for those articles that other approaches have less correctly classified. Other than being interesting by their own, the results call for further research in the area of domain specific features suitable for Web data quality assessment.
Towards Enabling Broadband for a Billon Plus Population with TV White Spaces
Venue: arXiv cs.NI 2016
Year: 2016

One of the major impediments to providing broadband connectivity in semi-urban and rural India is the lack of robust and affordable backhaul. Fiber connectivity in terms of backhaul that is being planned (or provided) by the Government of India would reach only till rural offices (named Gram Panchayat) in the Indian rural areas. In this exposition, we articulate how TV white space can address the challenge in providing broadband connectivity to a billion plus population within India. The villages can form local Wi-Fi clusters. The problem of connecting the Wi-Fi clusters to the optical fiber points can be addressed using a TV white space based backhaul (middle-mile) network. The amount of TV white space present in India is very large when compared with the developed world. Therefore, we discuss a backhaul architecture for rural India, which utilizes TV white spaces. We also showcase results from our TV white space testbed, which support the effectiveness of backhaul by using TV white spaces. Our testbed provides a broadband access network to rural population in thirteen villages. The testbed is deployed over an area of $25$km$^2$, and extends seamless broadband connectivity from optical fiber locations or Internet gateways to remote (difficult to connect) rural regions. We also discuss standards and TV white space regulations, which are pertinent to the backhaul architecture mentioned above.
From A to Z: Supervised Transfer of Style and Content Using Deep Neural Network Generators
Venue: arXiv cs.CV 2016
Year: 2016

We propose a new neural network architecture for solving single-image analogies - the generation of an entire set of stylistically similar images from just a single input image. Solving this problem requires separating image style from content. Our network is a modified variational autoencoder (VAE) that supports supervised training of single-image analogies and in-network evaluation of outputs with a structured similarity objective that captures pixel covariances. On the challenging task of generating a 62-letter font from a single example letter we produce images with 22.4% lower dissimilarity to the ground truth than state-of-the-art.
Position paper: Towards an observer-oriented theory of shape comparison
Venue: arXiv cs.CG 2016
Year: 2016

In this position paper we suggest a possible metric approach to shape comparison that is based on a mathematical formalization of the concept of observer, seen as a collection of suitable operators acting on a metric space of functions. These functions represent the set of data that are accessible to the observer, while the operators describe the way the observer elaborates the data and enclose the invariance that he/she associates with them. We expose this model and illustrate some theoretical reasons that justify its possible use for shape comparison.
Self-stabilizing Balls & Bins in Batches
Venue: arXiv cs.DC 2016
Year: 2016

A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modeled as static balls into bins processes, where $m$ balls (tasks) are to be distributed to $n$ bins (servers). In a seminal work, Azar et al. proposed the sequential strategy \greedy{d} for $n=m$. When thrown, a ball queries the load of $d$ random bins and is allocated to a least loaded of these. Azar et al. showed that $d=2$ yields an exponential improvement compared to $d=1$. Berenbrink et al. extended this to $m\gg n$, showing that the maximal load difference is independent of $m$ for $d=2$ (in contrast to $d=1$). We propose a new variant of an \emph{infinite} balls into bins process. Each round an expected number of $λn$ new balls arrive and are distributed (in parallel) to the bins. Each non-empty bin deletes one of its balls. This setting models a set of servers processing incoming requests, where clients can query a server's current load but receive no information about parallel requests. We study the \greedy{d} distribution scheme in this setting and show a strong self-stabilizing property: For \emph{any} arrival rate $λ=λ(n)<1$, the system load is time-invariant. Moreover, for \emph{any} (even super-exponential) round $t$, the maximum system load is (w.h.p.) $O(\frac{1}{1-λ}\cdot\log\frac{n}{1-λ})$ for $d=1$ and $O(\log\frac{n}{1-λ})$ for $d=2$. In particular, \greedy{2} has an exponentially smaller system load for high arrival rates.
Gaussian Process Regression for Out-of-Sample Extension
Venue: arXiv cs.LG 2016
Year: 2016

Manifold learning methods are useful for high dimensional data analysis. Many of the existing methods produce a low dimensional representation that attempts to describe the intrinsic geometric structure of the original data. Typically, this process is computationally expensive and the produced embedding is limited to the training data. In many real life scenarios, the ability to produce embedding of unseen samples is essential. In this paper we propose a Bayesian non-parametric approach for out-of-sample extension. The method is based on Gaussian Process Regression and independent of the manifold learning algorithm. Additionally, the method naturally provides a measure for the degree of abnormality for a newly arrived data point that did not participate in the training process. We derive the mathematical connection between the proposed method and the Nystrom extension and show that the latter is a special case of the former. We present extensive experimental results that demonstrate the performance of the proposed method and compare it to other existing out-of-sample extension methods.
Problem Solving in Sprego
Venue: arXiv cs.SE 2016
Year: 2016

Sprego is a programming tool for novice and end-user programmers within graphical spreadsheet environments. The main idea of Sprego is to use as few general purpose functions as possible, and based on these functions we create multilevel formulas to solve real world programmable spreadsheet problems. Beyond providing the framework for the theoretic background and the tools which support Sprego, in order to demonstrate the power which lies within it, we present a converted authentic table and, based on this table, data retrieval tasks, their algorithms, and coding in full details.
What slows you down? Your network or your device?
Venue: arXiv cs.NI 2016
Year: 2016

This study takes a close look at mobile web performance. The two main parameters determining web page load time are the network speed and the computing power of the end-user device. Based on data from real users, this paper quantifies the relative importance of network and device. The findings suggest that increased processing power of latest generation smart phones and optimized browsers have a significant impact on web performance; up to 56% reduction in median page load time from one generation to the following. The cellular networks, on the other hand, have become so mature that the median page load time on one fiber-to-the-home network (using wifi for the last meter) is only 18-28% faster than cellular and the median page load time on one DSL network is 19% slower compared to a well-deployed cellular network.
TTC: A high-performance Compiler for Tensor Transpositions
Venue: arXiv cs.MS 2016
Year: 2016

We present TTC, an open-source parallel compiler for multidimensional tensor transpositions. In order to generate high-performance C++ code, TTC explores a number of optimizations, including software prefetching, blocking, loop-reordering, and explicit vectorization. To evaluate the performance of multidimensional transpositions across a range of possible use-cases, we also release a benchmark covering arbitrary transpositions of up to six dimensions. Performance results show that the routines generated by TTC achieve close to peak memory bandwidth on both the Intel Haswell and the AMD Steamroller architectures, and yield significant performance gains over modern compilers. By implementing a set of pruning heuristics, TTC allows users to limit the number of potential solutions; this option is especially useful when dealing with high-dimensional tensors, as the search space might become prohibitively large. Experiments indicate that when only 100 potential solutions are considered, the resulting performance is about 99% of that achieved with exhaustive search.
Aggregated evaluation of operation quality of complex hierarchical network systems
Venue: arXiv cs.SY 2016
Year: 2016

The main approaches for the formation of generalized conclusions about operation quality of complex hierarchical network systems are analized. Advantages and drawbacks of the "weakest" element method and a weighted linear aggregation method are determined. Nonlinear aggregation method is proposed for evaluating the quality of the systems, which consist of elements of the same priority. Hybrid approaches to form generalized conclusions are developed based on the main aggregation methods. It is shown that they allow to obtain more reliable aggregation results.