OpenRaiser/Intern-Atlas huggingface dataset:
Bandwidth-efficient Storage Services for Mitigating Side Channel Attack
Venue: arXiv cs.CR 2017
Year: 2017

Data deduplication is able to effectively identify and eliminate redundant data and only maintain a single copy of files and chunks. Hence, it is widely used in cloud storage systems to save storage space and network bandwidth. However, the occurrence of deduplication can be easily identified by monitoring and analyzing network traffic, which leads to the risk of user privacy leakage. The attacker can carry out a very dangerous side channel attack, i.e., learn-the-remaining-information (LRI) attack, to reveal users' privacy information by exploiting the side channel of network traffic in deduplication. Existing work addresses the LRI attack at the cost of the high bandwidth efficiency of deduplication. In order to address this problem, we propose a simple yet effective scheme, called randomized redundant chunk scheme (RRCS), to significantly mitigate the risk of the LRI attack while maintaining the high bandwidth efficiency of deduplication. The basic idea behind RRCS is to add randomized redundant chunks to mix up the real deduplication states of files used for the LRI attack, which effectively obfuscates the view of the attacker, who attempts to exploit the side channel of network traffic for the LRI attack. Our security analysis shows that RRCS could significantly mitigate the risk of the LRI attack. We implement the RRCS prototype and evaluate it by using three large-scale real-world datasets. Experimental results demonstrate the efficiency and efficacy of RRCS.
Block Compressive Sensing of Image and Video with Nonlocal Lagrangian Multiplier and Patch-based Sparse Representation
Venue: arXiv cs.CV 2017
Year: 2017

Although block compressive sensing (BCS) makes it tractable to sense large-sized images and video, its recovery performance has yet to be significantly improved because its recovered images or video usually suffer from blurred edges, loss of details, and high-frequency oscillatory artifacts, especially at a low subrate. This paper addresses these problems by designing a modified total variation technique that employs multi-block gradient processing, a denoised Lagrangian multiplier, and patch-based sparse representation. In the case of video, the proposed recovery method is able to exploit both spatial and temporal similarities. Simulation results confirm the improved performance of the proposed method for compressive sensing of images and video in terms of both objective and subjective qualities.
Randomly coloring simple hypergraphs with fewer colors
Venue: arXiv cs.DM 2017
Year: 2017

We study the problem of constructing a (near) uniform random proper $q$-coloring of a simple $k$-uniform hypergraph with $n$ vertices and maximum degree $Δ$. (Proper in that no edge is mono-colored and simple in that two edges have maximum intersection of size one). We show that if $q\geq \max\{C_k\log n,500k^3Δ^{1/(k-1)}\}$ then the Glauber Dynamics will become close to uniform in $O(n\log n)$ time, given a random (improper) start. This improves on the results in Frieze and Melsted [5].
Fuzzy Rankings: Properties and Applications
Venue: arXiv cs.AI 2017
Year: 2017

In practice, a ranking of objects with respect to given set of criteria is of considerable importance. However, due to lack of knowledge, information of time pressure, decision makers might not be able to provide a (crisp) ranking of objects from the top to the bottom. Instead, some objects might be ranked equally, or better than other objects only to some degree. In such cases, a generalization of crisp rankings to fuzzy rankings can be more useful. The aim of the article is to introduce the notion of a fuzzy ranking and to discuss its several properties, namely orderings, similarity and indecisiveness. The proposed approach can be used both for group decision making or multiple criteria decision making when uncertainty is involved.
Algebraic Foundations of Proof Refinement
Venue: arXiv cs.LO 2017
Year: 2017

We contribute a general apparatus for dependent tactic-based proof refinement in the LCF tradition, in which the statements of subgoals may express a dependency on the proofs of other subgoals; this form of dependency is extremely useful and can serve as an algorithmic alternative to extensions of LCF based on non-local instantiation of schematic variables. Additionally, we introduce a novel behavioral distinction between refinement rules and tactics based on naturality. Our framework, called Dependent LCF, is already deployed in the nascent RedPRL proof assistant for computational cubical type theory.
Consumers and Curators: Browsing and Voting Patterns on Reddit
Venue: arXiv cs.SI 2017
Year: 2017

As crowd-sourced curation of news and information become the norm, it is important to understand not only how individuals consume information through social news Web sites, but also how they contribute to their ranking systems. In the present work, we introduce and make available a new dataset containing the activity logs that recorded all activity for 309 Reddit users for one year. Using this newly collected data, we present findings that highlight the browsing and voting behavior of the study's participants. We find that most users do not read the article that they vote on, and that, in total, 73% of posts were rated (ie, upvoted or downvoted) without first viewing the content. We also show evidence of cognitive fatigue in the browsing sessions of users that are most likely to vote.
A Real-Time Millimeter-Wave Phased Array MIMO Channel Sounder
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we present a novel real-time MIMO channel sounder for 28 GHz. Until now, the common practice to investigate the directional characteristics of millimeter-wave channels has been using a rotating horn antenna. The sounder presented here is capable of performing horizontal and vertical beam steering with the help of phased arrays. Thanks to fast beam-switching capability, the proposed sounder can perform measurements that are directionally resolved both at the transmitter (TX) and receiver (RX) as fast as 1.44 milliseconds compared to the minutes or even hours required for rotating horn antenna sounders. This does not only enable us to measure more points for better statistical inference but also allows to perform directional analysis in dynamic environments. Equally importantly, the short measurement time combined with the high phase stability of our setup limits the phase drift between TX and RX, enabling phase-coherent sounding of all beam pairs even when TX and RX are physically separated and have no cabled connection for synchronization. This ensures that the measurement data is suitable for high-resolution parameter extraction algorithms. Along with the system design and specifications, this paper also discusses the measurements performed for verification of the sounder. Furthermore, we present sample measurements from a channel sounding campaign performed on a residential street.
Refining Image Categorization by Exploiting Web Images and General Corpus
Venue: arXiv cs.MM 2017
Year: 2017

Studies show that refining real-world categories into semantic subcategories contributes to better image modeling and classification. Previous image sub-categorization work relying on labeled images and WordNet's hierarchy is not only labor-intensive, but also restricted to classify images into NOUN subcategories. To tackle these problems, in this work, we exploit general corpus information to automatically select and subsequently classify web images into semantic rich (sub-)categories. The following two major challenges are well studied: 1) noise in the labels of subcategories derived from the general corpus; 2) noise in the labels of images retrieved from the web. Specifically, we first obtain the semantic refinement subcategories from the text perspective and remove the noise by the relevance-based approach. To suppress the search error induced noisy images, we then formulate image selection and classifier learning as a multi-class multi-instance learning problem and propose to solve the employed problem by the cutting-plane algorithm. The experiments show significant performance gains by using the generated data of our way on both image categorization and sub-categorization tasks. The proposed approach also consistently outperforms existing weakly supervised and web-supervised approaches.
Efficient Online Learning for Optimizing Value of Information: Theory and Application to Interactive Troubleshooting
Venue: arXiv cs.AI 2017
Year: 2017

We consider the optimal value of information (VoI) problem, where the goal is to sequentially select a set of tests with a minimal cost, so that one can efficiently make the best decision based on the observed outcomes. Existing algorithms are either heuristics with no guarantees, or scale poorly (with exponential run time in terms of the number of available tests). Moreover, these methods assume a known distribution over the test outcomes, which is often not the case in practice. We propose an efficient sampling-based online learning framework to address the above issues. First, assuming the distribution over hypotheses is known, we propose a dynamic hypothesis enumeration strategy, which allows efficient information gathering with strong theoretical guarantees. We show that with sufficient amount of samples, one can identify a near-optimal decision with high probability. Second, when the parameters of the hypotheses distribution are unknown, we propose an algorithm which learns the parameters progressively via posterior sampling in an online fashion. We further establish a rigorous bound on the expected regret. We demonstrate the effectiveness of our approach on a real-world interactive troubleshooting application and show that one can efficiently make high-quality decisions with low cost.
What makes papers visible on social media? An analysis of various document characteristics
Venue: arXiv cs.DL 2017
Year: 2017

In this study we have investigated the relationship between different document characteristics and the number of Mendeley readership counts, tweets, Facebook posts, mentions in blogs and mainstream media for 1.3 million papers published in journals covered by the Web of Science (WoS). It aims to demonstrate that how factors affecting various social media-based indicators differ from those influencing citations and which document types are more popular across different platforms. Our results highlight the heterogeneous nature of altmetrics, which encompasses different types of uses and user groups engaging with research on social media.
DropRegion Training of Inception Font Network for High-Performance Chinese Font Recognition
Venue: arXiv cs.CV 2017
Year: 2017

Chinese font recognition (CFR) has gained significant attention in recent years. However, due to the sparsity of labeled font samples and the structural complexity of Chinese characters, CFR is still a challenging task. In this paper, a DropRegion method is proposed to generate a large number of stochastic variant font samples whose local regions are selectively disrupted and an inception font network (IFN) with two additional convolutional neural network (CNN) structure elements, i.e., a cascaded cross-channel parametric pooling (CCCP) and global average pooling, is designed. Because the distribution of strokes in a font image is non-stationary, an elastic meshing technique that adaptively constructs a set of local regions with equalized information is developed. Thus, DropRegion is seamlessly embedded in the IFN, which enables end-to-end training; the proposed DropRegion-IFN can be used for high performance CFR. Experimental results have confirmed the effectiveness of our new approach for CFR.
rTraceroute: Réunion Traceroute Visualisation
Venue: arXiv cs.NI 2017
Year: 2017

Traceroute is the main tools to explore Internet path. It provides limited information about each node along the path. However, Traceroute cannot go further in statistics analysis, or \emph{Man-Machine Interface (MMI)}. Indeed, there are no graphical tool that is able to draw all paths used by IP routes. We present a new tool that can handle more than 1,000 Traceroute results, map them, identify graphically MPLS links, get information of usage of all routes (in percent) to improve the knowledge between countries' links. rTraceroute want to go deeper in usage of atomic traces. In this paper, we will discuss the concept of rTraceroute and present some example of usage.
Implicit Gradient Neural Networks with a Positive-Definite Mass Matrix for Online Linear Equations Solving
Venue: arXiv cs.NE 2017
Year: 2017

Motivated by the advantages achieved by implicit analogue net for solving online linear equations, a novel implicit neural model is designed based on conventional explicit gradient neural networks in this letter by introducing a positive-definite mass matrix. In addition to taking the advantages of the implicit neural dynamics, the proposed implicit gradient neural networks can still achieve globally exponential convergence to the unique theoretical solution of linear equations and also global stability even under no-solution and multi-solution situations. Simulative results verify theoretical convergence analysis on the proposed neural dynamics.
Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings
Venue: arXiv cs.DM 2017
Year: 2017

Ortho-Radial drawings are a generalization of orthogonal drawings to grids that are formed by concentric circles and straight-line spokes emanating from the circles' center. Such drawings have applications in schematic graph layouts, e.g., for metro maps and destination maps. A plane graph is a planar graph with a fixed planar embedding. We give a combinatorial characterization of the plane graphs that admit a planar ortho-radial drawing without bends. Previously, such a characterization was only known for paths, cycles, and theta graphs, and in the special case of rectangular drawings for cubic graphs, where the contour of each face is required to be a rectangle. The characterization is expressed in terms of an ortho-radial representation that, similar to Tamassia's orthogonal representations for orthogonal drawings describes such a drawing combinatorially in terms of angles around vertices and bends on the edges. In this sense our characterization can be seen as a first step towards generalizing the Topology-Shape-Metrics framework of Tamassia to ortho-radial drawings.
A Visual Web Tool to Perform What-If Analysis of Optimization Approaches
Venue: arXiv cs.AI 2017
Year: 2017

In Operation Research, practical evaluation is essential to validate the efficacy of optimization approaches. This paper promotes the usage of performance profiles as a standard practice to visualize and analyze experimental results. It introduces a Web tool to construct and export performance profiles as SVG or HTML files. In addition, the application relies on a methodology to estimate the benefit of hypothetical solver improvements. Therefore, the tool allows one to employ what-if analysis to screen possible research directions, and identify those having the best potential. The approach is showcased on two Operation Research technologies: Constraint Programming and Mixed Integer Linear Programming.
Fast Non-Monotone Submodular Maximisation Subject to a Matroid Constraint
Venue: arXiv cs.DS 2017
Year: 2017

In this work we present the first practical $\left(\frac{1}{e}-ε\right)$-approximation algorithm to maximise a general non-negative submodular function subject to a matroid constraint. Our algorithm is based on combining the decreasing-threshold procedure of Badanidiyuru and Vondrak (SODA 2014) with a smoother version of the measured continuous greedy algorithm of Feldman et al. (FOCS 2011). This enables us to obtain an algorithm that requires $O(\frac{nr^2}{ε^4} \big(\frac{a+b}{a}\big)^2 \log^2({\frac{n}ε}))$ value oracle calls, where $n$ is the cardinality of the ground set, $r$ is the matroid rank, and $ b, a \in \mathbb{R}^+$ are the absolute values of the minimum and maximum marginal values that the function $f$ can take i.e.: $ -b \leq f_S(i) \leq a$, for all $i\in E$ and $S\subseteq E$, (here, $E$ is the ground set). The additional value oracle calls with respect to the work of Badanidiyuru and Vondrak come from the greater spread in the sampling of the multilinear extension that the possibility of negative marginal values introduce.
Self-approaching paths in simple polygons
Venue: arXiv cs.CG 2017
Year: 2017

We study self-approaching paths that are contained in a simple polygon. A self-approaching path is a directed curve connecting two points such that the Euclidean distance between a point moving along the path and any future position does not increase, that is, for all points $a$, $b$, and $c$ that appear in that order along the curve, $|ac| \ge |bc|$. We analyze the properties, and present a characterization of shortest self-approaching paths. In particular, we show that a shortest self-approaching path connecting two points inside a polygon can be forced to use a general class of non-algebraic curves. While this makes it difficult to design an exact algorithm, we show how to find a self-approaching path inside a polygon connecting two points under a model of computation which assumes that we can calculate involute curves of high order. Lastly, we provide an algorithm to test if a given simple polygon is self-approaching, that is, if there exists a self-approaching path for any two points inside the polygon.
Global Entity Ranking Across Multiple Languages
Venue: arXiv cs.IR 2017
Year: 2017

We present work on building a global long-tailed ranking of entities across multiple languages using Wikipedia and Freebase knowledge bases. We identify multiple features and build a model to rank entities using a ground-truth dataset of more than 10 thousand labels. The final system ranks 27 million entities with 75% precision and 48% F1 score. We provide performance evaluation and empirical evidence of the quality of ranking across languages, and open the final ranked lists for future research.
Roots multiplicity without companion matrices
Venue: arXiv cs.SC 2017
Year: 2017

We show a method for constructing a polynomial interpolating roots' multiplicities of another polynomial, that does not use companion matrices. This leads to a modification to Guersenzvaig--Szechtman square-free decomposition algorithm that is more efficient both in theory and in practice.
Chaotic-Based Processor for Communication and Multimedia Applications
Venue: arXiv cs.ET 2017
Year: 2017

Chaos is a phenomenon that attracted much attention in the past ten years. In this paper, we analyze chaos-based signal processing, and proposed a chaos processor to take advantage of chaos phenomenon. We also analyzed and demonstrated two of its practical applications in communication and sound synthesis.
Risk Proneness Estimation Method Developed in Relation to the Decision Taker that Controls the Robotic System
Venue: arXiv cs.RO 2017
Year: 2017

This work suggests the estimation method developed in relation to the position of the robotic system (RS) operator, showing his degree of risk proneness. The base models are: Hurwitz pessimism/optimism criterion and decision trees. The problem is solved using the reverse setting: we estimate pessimism/optimism parameter of the operator (decision taker) by observing what decisions he makes when controlling the RS. The solution context of such decision taker position estimation problems can be: using RS in emergency situations, in military actions and other situations connected with the uncertainty of the situation.
Preserving Data-Privacy with Added Noises: Optimal Estimation and Privacy Analysis
Venue: arXiv cs.IT 2017
Year: 2017

Networked system often relies on distributed algorithms to achieve a global computation goal with iterative local information exchanges between neighbor nodes. To preserve data privacy, a node may add a random noise to its original data for information exchange at each iteration. Nevertheless, a neighbor node can estimate other's original data based on the information it received. The estimation accuracy and data privacy can be measured in terms of $(ε, δ)$-data-privacy, defined as the probability of $ε$-accurate estimation (the difference of an estimation and the original data is within $ε$) is no larger than $δ$ (the disclosure probability). How to optimize the estimation and analyze data privacy is a critical and open issue. In this paper, a theoretical framework is developed to investigate how to optimize the estimation of neighbor's original data using the local information received, named optimal distributed estimation. Then, we study the disclosure probability under the optimal estimation for data privacy analysis. We further apply the developed framework to analyze the data privacy of the privacy-preserving average consensus algorithm and identify the optimal noises for the algorithm.
Curriculum Dropout
Venue: arXiv cs.NE 2017
Year: 2017

Dropout is a very effective way of regularizing neural networks. Stochastically "dropping out" units with a certain probability discourages over-specific co-adaptations of feature detectors, preventing overfitting and improving network generalization. Besides, Dropout can be interpreted as an approximate model aggregation technique, where an exponential number of smaller networks are averaged in order to get a more powerful ensemble. In this paper, we show that using a fixed dropout probability during training is a suboptimal choice. We thus propose a time scheduling for the probability of retaining neurons in the network. This induces an adaptive regularization scheme that smoothly increases the difficulty of the optimization problem. This idea of "starting easy" and adaptively increasing the difficulty of the learning problem has its roots in curriculum learning and allows one to train better models. Indeed, we prove that our optimization strategy implements a very general curriculum scheme, by gradually adding noise to both the input and intermediate feature representations within the network architecture. Experiments on seven image classification datasets and different network architectures show that our method, named Curriculum Dropout, frequently yields to better generalization and, at worst, performs just as well as the standard Dropout method.
Prio: Private, Robust, and Scalable Computation of Aggregate Statistics
Venue: arXiv cs.CR 2017
Year: 2017

This paper presents Prio, a privacy-preserving system for the collection of aggregate statistics. Each Prio client holds a private data value (e.g., its current location), and a small set of servers compute statistical functions over the values of all clients (e.g., the most popular location). As long as at least one server is honest, the Prio servers learn nearly nothing about the clients' private data, except what they can infer from the aggregate statistics that the system computes. To protect functionality in the face of faulty or malicious clients, Prio uses secret-shared non-interactive proofs (SNIPs), a new cryptographic technique that yields a hundred-fold performance improvement over conventional zero-knowledge approaches. Prio extends classic private aggregation techniques to enable the collection of a large class of useful statistics. For example, Prio can perform a least-squares regression on high-dimensional client-provided data without ever seeing the data in the clear.