OpenRaiser/Intern-Atlas huggingface dataset:
Composing Differential Privacy and Secure Computation: A case study on scaling private record linkage
Venue: arXiv cs.DB 2017
Year: 2017

Private record linkage (PRL) is the problem of identifying pairs of records that are similar as per an input matching rule from databases held by two parties that do not trust one another. We identify three key desiderata that a PRL solution must ensure: 1) perfect precision and high recall of matching pairs, 2) a proof of end-to-end privacy, and 3) communication and computational costs that scale subquadratically in the number of input records. We show that all of the existing solutions for PRL - including secure 2-party computation (S2PC), and their variants that use non-private or differentially private (DP) blocking to ensure subquadratic cost - violate at least one of the three desiderata. In particular, S2PC techniques guarantee end-to-end privacy but have either low recall or quadratic cost. In contrast, no end-to-end privacy guarantee has been formalized for solutions that achieve subquadratic cost. This is true even for solutions that compose DP and S2PC: DP does not permit the release of any exact information about the databases, while S2PC algorithms for PRL allow the release of matching records. In light of this deficiency, we propose a novel privacy model, called output constrained differential privacy, that shares the strong privacy protection of DP, but allows for the truthful release of the output of a certain function applied to the data. We apply this to PRL, and show that protocols satisfying this privacy model permit the disclosure of the true matching records, but their execution is insensitive to the presence or absence of a single non-matching record. We find that prior work that combine DP and S2PC techniques even fail to satisfy this end-to-end privacy model. Hence, we develop novel protocols that provably achieve this end-to-end privacy guarantee, together with the other two desiderata of PRL.
Automating Image Analysis by Annotating Landmarks with Deep Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

Image and video analysis is often a crucial step in the study of animal behavior and kinematics. Often these analyses require that the position of one or more animal landmarks are annotated (marked) in numerous images. The process of annotating landmarks can require a significant amount of time and tedious labor, which motivates the need for algorithms that can automatically annotate landmarks. In the community of scientists that use image and video analysis to study the 3D flight of animals, there has been a trend of developing more automated approaches for annotating landmarks, yet they fall short of being generally applicable. Inspired by the success of Deep Neural Networks (DNNs) on many problems in the field of computer vision, we investigate how suitable DNNs are for accurate and automatic annotation of landmarks in video datasets representative of those collected by scientists studying animals. Our work shows, through extensive experimentation on videos of hawkmoths, that DNNs are suitable for automatic and accurate landmark localization. In particular, we show that one of our proposed DNNs is more accurate than the current best algorithm for automatic localization of landmarks on hawkmoth videos. Moreover, we demonstrate how these annotations can be used to quantitatively analyze the 3D flight of a hawkmoth. To facilitate the use of DNNs by scientists from many different fields, we provide a self contained explanation of what DNNs are, how they work, and how to apply them to other datasets using the freely available library Caffe and supplemental code that we provide.
Invariance in Constrained Switching
Venue: arXiv cs.SY 2017
Year: 2017

We study discrete time linear constrained switching systems with additive disturbances, in which the switching may be on the system matrices, the disturbance sets, the state constraint sets or a combination of the above. In our general setting, a switching sequence is admissible if it is accepted by an automaton. For this family of systems, stability does not necessarily imply the existence of an invariant set. Nevertheless, it does imply the existence of an invariant multi-set, which is a relaxation of invariance and the object of our work. First, we establish basic results concerning the characterization, approximation and computation of the minimal and the maximal admissible invariant multi-set. Second, by exploiting the topological properties of the directed graph which defines the switching constraints, we propose invariant multi-set constructions with several benefits. We illustrate our results in benchmark problems in control.
Analysing Temporal Evolution of Interlingual Wikipedia Article Pairs
Venue: arXiv cs.CL 2017
Year: 2017

Wikipedia articles representing an entity or a topic in different language editions evolve independently within the scope of the language-specific user communities. This can lead to different points of views reflected in the articles, as well as complementary and inconsistent information. An analysis of how the information is propagated across the Wikipedia language editions can provide important insights in the article evolution along the temporal and cultural dimensions and support quality control. To facilitate such analysis, we present MultiWiki - a novel web-based user interface that provides an overview of the similarities and differences across the article pairs originating from different language editions on a timeline. MultiWiki enables users to observe the changes in the interlingual article similarity over time and to perform a detailed visual comparison of the article snapshots at a particular time point.
Complexity-Aware Scheduling for an LDPC Encoded C-RAN Uplink
Venue: arXiv cs.IT 2017
Year: 2017

Centralized Radio Access Network (C-RAN) is a new paradigm for wireless networks that centralizes the signal processing in a computing cloud, allowing commodity computational resources to be pooled. While C-RAN improves utilization and efficiency, the computational load occasionally exceeds the available resources, creating a computational outage. This paper provides a mathematical characterization of the computational outage probability for low-density parity check (LDPC) codes, a common class of error-correcting codes. For tractability, a binary erasures channel is assumed. Using the concept of density evolution, the computational demand is determined for a given ensemble of codes as a function of the erasure probability. The analysis reveals a trade-off: aggressively signaling at a high rate stresses the computing pool, while conservatively backing-off the rate can avoid computational outages. Motivated by this trade-off, an effective computationally aware scheduling algorithm is developed that balances demands for high throughput and low outage rates.
DCT-like Transform for Image Compression Requires 14 Additions Only
Venue: arXiv cs.MM 2017
Year: 2017

A low-complexity 8-point orthogonal approximate DCT is introduced. The proposed transform requires no multiplications or bit-shift operations. The derived fast algorithm requires only 14 additions, less than any existing DCT approximation. Moreover, in several image compression scenarios, the proposed transform could outperform the well-known signed DCT, as well as state-of-the-art algorithms.
HoloClean: Holistic Data Repairs with Probabilistic Inference
Venue: arXiv cs.DB 2017
Year: 2017

We introduce HoloClean, a framework for holistic data repairing driven by probabilistic inference. HoloClean unifies existing qualitative data repairing approaches, which rely on integrity constraints or external data sources, with quantitative data repairing methods, which leverage statistical properties of the input data. Given an inconsistent dataset as input, HoloClean automatically generates a probabilistic program that performs data repairing. Inspired by recent theoretical advances in probabilistic inference, we introduce a series of optimizations which ensure that inference over HoloClean's probabilistic model scales to instances with millions of tuples. We show that HoloClean scales to instances with millions of tuples and find data repairs with an average precision of ~90% and an average recall of above ~76% across a diverse array of datasets exhibiting different types of errors. This yields an average F1 improvement of more than 2x against state-of-the-art methods.
The Value of Inferring the Internal State of Traffic Participants for Autonomous Freeway Driving
Venue: arXiv cs.AI 2017
Year: 2017

Safe interaction with human drivers is one of the primary challenges for autonomous vehicles. In order to plan driving maneuvers effectively, the vehicle's control system must infer and predict how humans will behave based on their latent internal state (e.g., intentions and aggressiveness). This research uses a simple model for human behavior with unknown parameters that make up the internal states of the traffic participants and presents a method for quantifying the value of estimating these states and planning with their uncertainty explicitly modeled. An upper performance bound is established by an omniscient Monte Carlo Tree Search (MCTS) planner that has perfect knowledge of the internal states. A baseline lower bound is established by planning with MCTS assuming that all drivers have the same internal state. MCTS variants are then used to solve a partially observable Markov decision process (POMDP) that models the internal state uncertainty to determine whether inferring the internal state offers an advantage over the baseline. Applying this method to a freeway lane changing scenario reveals that there is a significant performance gap between the upper bound and baseline. POMDP planning techniques come close to closing this gap, especially when important hidden model parameters are correlated with measurable parameters.
Video Salient Object Detection via Fully Convolutional Networks
Venue: arXiv cs.CV 2017
Year: 2017

This paper proposes a deep learning model to efficiently detect salient regions in videos. It addresses two important issues: (1) deep video saliency model training with the absence of sufficiently large and pixel-wise annotated video data, and (2) fast video saliency training and detection. The proposed deep video saliency network consists of two modules, for capturing the spatial and temporal saliency information, respectively. The dynamic saliency model, explicitly incorporating saliency estimates from the static saliency model, directly produces spatiotemporal saliency inference without time-consuming optical flow computation. We further propose a novel data augmentation technique that simulates video training data from existing annotated image datasets, which enables our network to learn diverse saliency information and prevents overfitting with the limited number of training videos. Leveraging our synthetic video data (150K video sequences) and real videos, our deep video saliency model successfully learns both spatial and temporal saliency cues, thus producing accurate spatiotemporal saliency estimate. We advance the state-of-the-art on the DAVIS dataset (MAE of .06) and the FBMS dataset (MAE of .07), and do so with much improved speed (2fps with all steps).
ReLiC: Entity Profiling by using Random Forest and Trustworthiness of a Source - Technical Report
Venue: arXiv cs.IR 2017
Year: 2017

The digital revolution has brought most of the world on the world wide web. The data available on WWW has increased many folds in the past decade. Social networks, online clubs and organisations have come into existence. Information is extracted from these venues about a real world entity like a person, organisation, event, etc. However, this information may change over time, and there is a need for the sources to be up-to-date. Therefore, it is desirable to have a model to extract relevant data items from different sources and merge them to build a complete profile of an entity (entity profiling). Further, this model should be able to handle incorrect or obsolete data items. In this paper, we propose a novel method for completing a profile. We have developed a two phase method-1) The first phase (resolution phase) links records to the queries. We have proposed and observed that the use of random forest for entity resolution increases the performance of the system as this has resulted in more records getting linked to the correct entity. Also, we used trustworthiness of a source as a feature to the random forest. 2) The second phase selects the appropriate values from records to complete a profile based on our proposed selection criteria. We have used various metrics for measuring the performance of the resolution phase as well as for the overall ReLiC framework. It is established through our results that the use of biased sources has significantly improved the performance of the ReLiC framework. Experimental results show that our proposed system, ReLiC outperforms the state-of-the-art.
Multi-level computational methods for interdisciplinary research in the HathiTrust Digital Library
Venue: arXiv cs.DL 2017
Year: 2017

We show how faceted search using a combination of traditional classification systems and mixed-membership topic models can go beyond keyword search to inform resource discovery, hypothesis formulation, and argument extraction for interdisciplinary research. Our test domain is the history and philosophy of scientific work on animal mind and cognition. The methods can be generalized to other research areas and ultimately support a system for semi-automatic identification of argument structures. We provide a case study for the application of the methods to the problem of identifying and extracting arguments about anthropomorphism during a critical period in the development of comparative psychology. We show how a combination of classification systems and mixed-membership models trained over large digital libraries can inform resource discovery in this domain. Through a novel approach of "drill-down" topic modeling---simultaneously reducing both the size of the corpus and the unit of analysis---we are able to reduce a large collection of fulltext volumes to a much smaller set of pages within six focal volumes containing arguments of interest to historians and philosophers of comparative psychology. The volumes identified in this way did not appear among the first ten results of the keyword search in the HathiTrust digital library and the pages bear the kind of "close reading" needed to generate original interpretations that is the heart of scholarly work in the humanities. Zooming back out, we provide a way to place the books onto a map of science originally constructed from very different data and for different purposes. The multilevel approach advances understanding of the intellectual and societal contexts in which writings are interpreted.
Inconsistency in the ordinal pairwise comparisons method with and without ties
Venue: arXiv cs.DM 2017
Year: 2017

Comparing alternatives in pairs is a well-known method of ranking creation. Experts are asked to perform a series of binary comparisons and then, using mathematical methods, the final ranking is prepared. As experts conduct the individual assessments, they may not always be consistent. The level of inconsistency among individual assessments is widely accepted as a measure of the ranking quality. The higher the ranking quality, the greater its credibility. One way to determine the level of inconsistency among the paired comparisons is to calculate the value of the inconsistency index. One of the earliest and most widespread inconsistency indexes is the consistency coefficient defined by Kendall and Babington Smith. In their work, the authors consider binary pairwise comparisons, i.e., those where the result of an individual comparison can only be: better or worse. The presented work extends the Kendall and Babington Smith index to sets of paired comparisons with ties. Hence, this extension allows the decision makers to determine the inconsistency for sets of paired comparisons, where the result may also be "equal." The article contains a definition and analysis of the most inconsistent set of pairwise comparisons with and without ties. It is also shown that the most inconsistent set of pairwise comparisons with ties represents a special case of the more general set cover problem.
A Survey of Advances in Botnet Technologies
Venue: arXiv cs.CR 2017
Year: 2017

Botnets have come a long way since their inception a few decades ago. Originally toy programs written by network hobbyists, modern-day botnets can be used by cyber criminals to steal billions of dollars from users, corporations, and governments. This paper will look at cutting-edge botnet features and detection strategies from over a dozen research papers, supplemented by a few additional sources. With this data, I will then hypothesize what the future of botnets might hold.
Extraction of Evolution Descriptions from the Web
Venue: arXiv cs.CL 2017
Year: 2017

The evolution of named entities affects exploration and retrieval tasks in digital libraries. An information retrieval system that is aware of name changes can actively support users in finding former occurrences of evolved entities. However, current structured knowledge bases, such as DBpedia or Freebase, do not provide enough information about evolutions, even though the data is available on their resources, like Wikipedia. Our \emph{Evolution Base} prototype will demonstrate how excerpts describing name evolutions can be identified on these websites with a promising precision. The descriptions are classified by means of models that we trained based on a recent analysis of named entity evolutions on Wikipedia.
A longitudinal dataset of five years of public activity in the Scratch online community
Venue: arXiv cs.CY 2017
Year: 2017

Scratch is a programming environment and an online community where young people can create, share, learn, and communicate. In collaboration with the Scratch Team at MIT, we created a longitudinal dataset of public activity in the Scratch online community during its first five years (2007-2012). The dataset comprises 32 tables with information on more than 1 million Scratch users, nearly 2 million Scratch projects, more than 10 million comments, more than 30 million visits to Scratch projects, and more. To help researchers understand this dataset, and to establish the validity of the data, we also include the source code of every version of the software that operated the website, as well as the software used to generate this dataset. We believe this is the largest and most comprehensive downloadable dataset of youth programming artifacts and communication.
QoS Analysis of Cognitive Radios Employing HARQ
Venue: arXiv cs.IT 2017
Year: 2017

Recently, the demand for faster and more reliable data transmission has brought up complex communications systems. As a result, it has become more difficult to carry out closed-form solutions that can provide insight about performance levels. In this paper, different from the existing research, we study a cognitive radio system that employs hybrid-automatic-repeat-request (HARQ) protocols under quality-of-service (QoS) constraints. We assume that the secondary users access the spectrum by utilizing a strategy that is a combination of underlay and interweave access techniques. Considering that the secondary users imperfectly perform channel sensing in order to detect the active primary users and that there is a transmission deadline for each data packet at the secondary transmitter buffer, we formulate the state-transition model of the system. Then, we obtain the state-transition probabilities when HARQ-chase combining is adopted. Subsequently, we provide the packet-loss rate in the channel and achieve the effective capacity. Finally, we substantiate our analytical derivations with numerical results.
Large-scale Image Geo-Localization Using Dominant Sets
Venue: arXiv cs.CV 2017
Year: 2017

This paper presents a new approach for the challenging problem of geo-locating an image using image matching in a structured database of city-wide reference images with known GPS coordinates. We cast the geo-localization as a clustering problem on local image features. Akin to existing approaches on the problem, our framework builds on low-level features which allow partial matching between images. For each local feature in the query image, we find its approximate nearest neighbors in the reference set. Next, we cluster the features from reference images using Dominant Set clustering, which affords several advantages over existing approaches. First, it permits variable number of nodes in the cluster which we use to dynamically select the number of nearest neighbors (typically coming from multiple reference images) for each query feature based on its discrimination value. Second, as we also quantify in our experiments, this approach is several orders of magnitude faster than existing approaches. Thus, we obtain multiple clusters (different local maximizers) and obtain a robust final solution to the problem using multiple weak solutions through constrained Dominant Set clustering on global image features, where we enforce the constraint that the query image must be included in the cluster. This second level of clustering also bypasses heuristic approaches to voting and selecting the reference image that matches to the query. We evaluated the proposed framework on an existing dataset of 102k street view images as well as a new dataset of 300k images, and show that it outperforms the state-of-the-art by 20% and 7%, respectively, on the two datasets.
Generalized piggybacking codes for distributed storage systems
Venue: arXiv cs.IT 2017
Year: 2017

This paper generalizes the piggybacking constructions for distributed storage systems by considering various protected instances and piggybacked instances. Analysis demonstrates that the proportion of protected instances determines the average repair bandwidth for a systematic node. By optimizing the proportion of protected instances, the repair ratio of generalized piggybacking codes approaches zero instead of 50% as the number of parity check nodes tends to infinity. Furthermore, the computational complexity for repairing a single systematic node cost by generalized piggybacking codes is less than that of the existing piggybacking designs.