OpenRaiser/Intern-Atlas huggingface dataset:
Avatar: A Time- and Space-Efficient Self-Stabilizing Overlay Network
Venue: arXiv cs.DC 2015
Year: 2015

Overlay networks present an interesting challenge for fault-tolerant computing. Many overlay networks operate in dynamic environments (e.g. the Internet), where faults are frequent and widespread, and the number of processes in a system may be quite large. Recently, self-stabilizing overlay networks have been presented as a method for managing this complexity. \emph{Self-stabilizing overlay networks} promise that, starting from any weakly-connected configuration, a correct overlay network will eventually be built. To date, this guarantee has come at a cost: nodes may either have high degree during the algorithm's execution, or the algorithm may take a long time to reach a legal configuration. In this paper, we present the first self-stabilizing overlay network algorithm that does not incur this penalty. Specifically, we (i) present a new locally-checkable overlay network based upon a binary search tree, and (ii) provide a randomized algorithm for self-stabilization that terminates in an expected polylogarithmic number of rounds \emph{and} increases a node's degree by only a polylogarithmic factor in expectation.
Weighted Sampling Without Replacement from Data Streams
Venue: arXiv cs.DS 2015
Year: 2015

Weighted sampling without replacement has proved to be a very important tool in designing new algorithms. Efraimidis and Spirakis (IPL 2006) presented an algorithm for weighted sampling without replacement from data streams. Their algorithm works under the assumption of precise computations over the interval [0,1]. Cohen and Kaplan (VLDB 2008) used similar methods for their bottom-k sketches. Efraimidis and Spirakis ask as an open question whether using finite precision arithmetic impacts the accuracy of their algorithm. In this paper we show a method to avoid this problem by providing a precise reduction from k-sampling without replacement to k-sampling with replacement. We call the resulting method Cascade Sampling.
Metric Dimension Parameterized by Max Leaf Number
Venue: arXiv cs.DS 2015
Year: 2015

The metric dimension of a graph is the size of the smallest set of vertices whose distances distinguish all pairs of vertices in the graph. We show that this graph invariant may be calculated by an algorithm whose running time is linear in the input graph size, added to a function of the largest possible number of leaves in a spanning tree of the graph.
Motion Planning in Non-Gaussian Belief Spaces (M3P): The Case of a Kidnapped Robot
Venue: arXiv cs.RO 2015
Year: 2015

Planning under uncertainty is a key requirement for physical systems due to the noisy nature of actuators and sensors. Using a belief space approach, planning solutions tend to generate actions that result in information seeking behavior which reduce state uncertainty. While recent work has dealt with planning for Gaussian beliefs, for many cases, a multi-modal belief is a more accurate representation of the underlying belief. This is particularly true in environments with information symmetry that cause uncertain data associations which naturally lead to a multi-modal hypothesis on the state. Thus, a planner cannot simply base actions on the most-likely state. We propose an algorithm that uses a Receding Horizon Planning approach to plan actions that sequentially disambiguate the multi-modal belief to a uni-modal Gaussian and achieve tight localization on the true state, called a Multi-Modal Motion Planner (M3P). By combining a Gaussian sampling-based belief space planner with M3P, and introducing a switching behavior in the planner and belief representation, we present a holistic end-to-end solution for the belief space planning problem. Simulation results for a 2D ground robot navigation problem are presented that demonstrate our method's performance.
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter
Venue: arXiv cs.DS 2015
Year: 2015

The radius and diameter are fundamental graph parameters. They are defined as the minimum and maximum of the eccentricities in a graph, respectively, where the eccentricity of a vertex is the largest distance from the vertex to another node. In directed graphs, there are several versions of these problems. For instance, one may choose to define the eccentricity of a node in terms of the largest distance into the node, out of the node, the sum of the two directions (i.e. roundtrip) and so on. All versions of diameter and radius can be solved via solving all-pairs shortest paths (APSP), followed by a fast postprocessing step. Solving APSP, however, on $n$-node graphs requires $Ω(n^2)$ time even in sparse graphs, as one needs to output $n^2$ distances. Motivated by known and new negative results on the impossibility of computing these measures exactly in general graphs in truly subquadratic time, under plausible assumptions, we search for \emph{approximation} and \emph{fixed parameter subquadratic} algorithms, and for reasons why they do not exist. Our results include: - Truly subquadratic approximation algorithms for most of the versions of Diameter and Radius with \emph{optimal} approximation guarantees (given truly subquadratic time), under plausible assumptions. In particular, there is a $2$-approximation algorithm for directed Radius with one-way distances that runs in $\tilde{O}(m\sqrt{n})$ time, while a $(2-δ)$-approximation algorithm in $O(n^{2-ε})$ time is unlikely. - On graphs with treewidth $k$, we can solve the problems in $2^{O(k\log{k})}n^{1+o(1)}$ time. We show that these algorithms are near optimal since even a $(3/2-δ)$-approximation algorithm that runs in time $2^{o(k)}n^{2-ε}$ would refute the plausible assumptions.
Content Translation: Computer-assisted translation tool for Wikipedia articles
Venue: arXiv cs.CL 2015
Year: 2015

The quality and quantity of articles in each Wikipedia language varies greatly. Translating from another Wikipedia is a natural way to add more content, but the translation process is not properly supported in the software used by Wikipedia. Past computer-assisted translation tools built for Wikipedia are not commonly used. We created a tool that adapts to the specific needs of an open community and to the kind of content in Wikipedia. Qualitative and quantitative data indicates that the new tool helps users translate articles easier and faster.
Smart Geographic object: Toward a new understanding of GIS Technology in Ubiquitous Computing
Venue: arXiv cs.HC 2015
Year: 2015

One of the fundamental aspects of ubiquitous computing is the instrumentation of the real world by smart devices. This instrumentation constitutes an opportunity to rethink the interactions between human beings and their environment on the one hand, and between the components of this environment on the other. In this paper we discuss what this understanding of ubiquitous computing can bring to geographic science and particularly to GIS technology. Our main idea is the instrumentation of the geographic environment through the instrumentation of geographic objects composing it. And then investigate how this instrumentation can meet the current limitations of GIS technology, and offers a new stage of rapprochement between the earth and its abstraction. As result, the current research work proposes a new concept we named Smart Geographic Object SGO. The latter is a convergence point between the smart objects and geographic objects, two concepts appertaining respectively to t
Smart Meter Privacy with an Energy Harvesting Device and Instantaneous Power Constraints
Venue: arXiv cs.IT 2015
Year: 2015

A smart meter (SM) periodically measures end-user electricity consumption and reports it to a utility provider (UP). Despite the advantages of SMs, their use leads to serious concerns about consumer privacy. In this paper, SM privacy is studied by considering the presence of an energy harvesting device (EHD) as a means of masking the user's input load. The user can satisfy part or all of his/her energy needs from the EHD, and hence, less information can be leaked to the UP via the SM. The EHD is typically equipped with a rechargeable energy storage device, i.e., a battery, whose instantaneous energy content limits the user's capability in covering his/her energy usage. Privacy is measured by the information leaked about the user's real energy consumption when the UP observes the energy requested from the grid, which the SM reads and reports to the UP. The minimum information leakage rate is characterized as a computable information theoretic single-letter expression when the EHD battery capacity is either infinite or zero. Numerical results are presented for a discrete binary input load to illustrate the potential privacy gains from the existence of a storage device.
Similarity, Cardinality and Entropy for Bipolar Fuzzy Set in the Framework of Penta-valued Representation
Venue: arXiv cs.AI 2015
Year: 2015

In this paper one presents new similarity, cardinality and entropy measures for bipolar fuzzy set and for its particular forms like intuitionistic, paraconsistent and fuzzy set. All these are constructed in the framework of multi-valued representations and are based on a penta-valued logic that uses the following logical values: true, false, unknown, contradictory and ambiguous. Also a new distance for bounded real interval was defined.
A novel magic LSB substitution method (M-LSB-SM) using multi-level encryption and achromatic component of an image
Venue: arXiv cs.MM 2015
Year: 2015

Image Steganography is a thriving research area of information security where secret data is embedded in images to hide its existence while getting the minimum possible statistical detectability. This paper proposes a novel magic least significant bit substitution method (M-LSB-SM) for RGB images. The proposed method is based on the achromatic component (I-plane) of the hue-saturation-intensity (HSI) color model and multi-level encryption (MLE) in the spatial domain. The input image is transposed and converted into an HSI color space. The I-plane is divided into four sub-images of equal size, rotating each sub-image with a different angle using a secret key. The secret information is divided into four blocks, which are then encrypted using an MLE algorithm (MLEA). Each sub-block of the message is embedded into one of the rotated sub-images based on a specific pattern using magic LSB substitution. Experimental results validate that the proposed method not only enhances the visual quality of stego images but also provides good imperceptibility and multiple security levels as compared to several existing prominent methods.
The ICT predicament of new ICT-enabled service
Venue: arXiv cs.CY 2015
Year: 2015

The advancement of information and communication technologies (ICT) has triggered many ICT-enabled services. Regarding this service, the complementary ICT system involves with customers' devices, industry-wide ICT development and nation-wide ICT infrastructure, which are difficult for any individual organization to control. The ICT predicament is the phenomenon that the complementary ICT system is inferior in delivering the promised service quality of new ICT-enabled service. With the ICT predicament, companies face the decision-making dilemma in launching the new service or postponing the launch. This study proposes a process to resolve the decision-making dilemma regarding the ICT predicament.
Bayesian De-quantization and Data Compression for Low-Energy Physiological Signal Telemonitoring
Venue: arXiv cs.IT 2015
Year: 2015

We address the issue of applying quantized compressed sensing (CS) on low-energy telemonitoring. So far, few works studied this problem in applications where signals were only approximately sparse. We propose a two-stage data compressor based on quantized CS, where signals are compressed by compressed sensing and then the compressed measurements are quantized with only 2 bits per measurement. This compressor can greatly reduce the transmission bit-budget. To recover signals from underdetermined, quantized measurements, we develop a Bayesian De-quantization algorithm. It can exploit both the model of quantization errors and the correlated structure of physiological signals to improve the quality of recovery. The proposed data compressor and the recovery algorithm are validated on a dataset recorded on 12 subjects during fast running. Experiment results showed that an averaged 2.596 beat per minute (BPM) estimation error was achieved by jointly using compressed sensing with 50% compression ratio and a 2-bit quantizer. The results imply that we can effectively transmit n bits instead of n samples, which is a substantial improvement for low-energy wireless telemonitoring.
Thresholding for Top-k Recommendation with Temporal Dynamics
Venue: arXiv cs.IR 2015
Year: 2015

This work focuses on top-k recommendation in domains where underlying data distribution shifts overtime. We propose to learn a time-dependent bias for each item over whatever existing recommendation engine. Such a bias learning process alleviates data sparsity in constructing the engine, and at the same time captures recent trend shift observed in data. We present an alternating optimization framework to resolve the bias learning problem, and develop methods to handle a variety of commonly used recommendation evaluation criteria, as well as large number of items and users in practice. The proposed algorithm is examined, both offline and online, using real world data sets collected from the largest retailer worldwide. Empirical results demonstrate that the bias learning can almost always boost recommendation performance. We encourage other practitioners to adopt it as a standard component in recommender systems where temporal dynamics is a norm.
Boosting Optical Character Recognition: A Super-Resolution Approach
Venue: arXiv cs.CV 2015
Year: 2015

Text image super-resolution is a challenging yet open research problem in the computer vision community. In particular, low-resolution images hamper the performance of typical optical character recognition (OCR) systems. In this article, we summarize our entry to the ICDAR2015 Competition on Text Image Super-Resolution. Experiments are based on the provided ICDAR2015 TextSR dataset and the released Tesseract-OCR 3.02 system. We report that our winning entry of text image super-resolution framework has largely improved the OCR performance with low-resolution images used as input, reaching an OCR accuracy score of 77.19%, which is comparable with that of using the original high-resolution images 78.80%.
Nonlinear compressed sensing based on composite mappings and its pointwise linearization
Venue: arXiv cs.IT 2015
Year: 2015

Classical compressed sensing (CS) allows us to recover structured signals from far few linear measurements than traditionally prescribed, thereby efficiently decreasing sampling rates. However, if there exist nonlinearities in the measurements, is it still possible to recover sparse or structured signals from the nonlinear measurements? The research of nonlinear CS is devoted to answering this question. In this paper, unlike the existing research angles of nonlinear CS, we study it from the perspective of mapping decomposition, and propose a new concept, namely, nonlinear CS based on composite mappings. Through the analysis of two forms of a nonlinear composite mapping Phi, i.e., Phi(x) = F(Ax) and Phi(x) = AF(x), we give the requirements respectively for the sensing matrix A and the nonlinear mapping F when reconstructing all sparse signals exactly from the nonlinear measurements Phi(x). Besides, we also provide a special pointwise linearization method, which can turn the nonlinear composite mapping Phi, at each point in its domain, into an equivalent linear composite mapping. This linearization method can guarantee the exact recovery of all given sparse signals even if Phi is not an injection for all sparse signals. It may help us build an algorithm framework for the composite nonlinear CS in which we can take full advantage of the existing recovery algorithms belonging to linear CS.
Design and optimization of DBSCAN Algorithm based on CUDA
Venue: arXiv cs.DC 2015
Year: 2015

DBSCAN is a very classic algorithm for data clus- tering, which is widely used in many fields. However, with the data scale growing much more bigger than before, the traditional serial algorithm can not meet the performance requirement. Recently, parallel computing based on CUDA has developed very fast and has great advantage on big data. This paper summarizes the algorithms proposed before and improves the performance of the old DBSCAN algorithm by using CUDA and parallel computing. The algorithm uses shared memory as much as possible compared with other algorithms and it has very good scalability. A data set is tested on the new version of DBSCAN. Finally, we analyze the results and give a conclusion that our algorithm is approximately 97 times faster than the serial version.
Knowledge Transfer Pre-training
Venue: arXiv cs.LG 2015
Year: 2015

Pre-training is crucial for learning deep neural networks. Most of existing pre-training methods train simple models (e.g., restricted Boltzmann machines) and then stack them layer by layer to form the deep structure. This layer-wise pre-training has found strong theoretical foundation and broad empirical support. However, it is not easy to employ such method to pre-train models without a clear multi-layer structure,e.g., recurrent neural networks (RNNs). This paper presents a new pre-training approach based on knowledge transfer learning. In contrast to the layer-wise approach which trains model components incrementally, the new approach trains the entire model as a whole but with an easier objective function. This is achieved by utilizing soft targets produced by a prior trained model (teacher model). Compared to the conventional layer-wise methods, this new method does not care about the model structure, so can be used to pre-train very complex models. Experiments on a speech recognition task demonstrated that with this approach, complex RNNs can be well trained with a weaker deep neural network (DNN) model. Furthermore, the new method can be combined with conventional layer-wise pre-training to deliver additional gains.
On Network Proximity in Web Applications
Venue: arXiv cs.CY 2015
Year: 2015

In this paper, we discuss one approach for development and deployment of web sites (web pages) devoted to the description of objects (events) with a precisely delineated geographic scope. This article describes the usage of context-aware programming models for web development. In our paper, we propose mechanisms to create mobile web applications which content links to some predefined geographic area. The accuracy of such a binding allows us to distinguish individual areas within the same indoor space. Target areas for such development are applications for Smart Cities and retail.
Visual Learning of Arithmetic Operations
Venue: arXiv cs.LG 2015
Year: 2015

A simple Neural Network model is presented for end-to-end visual learning of arithmetic operations from pictures of numbers. The input consists of two pictures, each showing a 7-digit number. The output, also a picture, displays the number showing the result of an arithmetic operation (e.g., addition or subtraction) on the two input numbers. The concepts of a number, or of an operator, are not explicitly introduced. This indicates that addition is a simple cognitive task, which can be learned visually using a very small number of neurons. Other operations, e.g., multiplication, were not learnable using this architecture. Some tasks were not learnable end-to-end (e.g., addition with Roman numerals), but were easily learnable once broken into two separate sub-tasks: a perceptual \textit{Character Recognition} and cognitive \textit{Arithmetic} sub-tasks. This indicates that while some tasks may be easily learnable end-to-end, other may need to be broken into sub-tasks.
Randomized Structural Sparsity based Support Identification with Applications to Locating Activated or Discriminative Brain Areas: A Multi-center Reproducibility Study
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we focus on how to locate the relevant or discriminative brain regions related with external stimulus or certain mental decease, which is also called support identification, based on the neuroimaging data. The main difficulty lies in the extremely high dimensional voxel space and relatively few training samples, easily resulting in an unstable brain region discovery (or called feature selection in context of pattern recognition). When the training samples are from different centers and have betweencenter variations, it will be even harder to obtain a reliable and consistent result. Corresponding, we revisit our recently proposed algorithm based on stability selection and structural sparsity. It is applied to the multi-center MRI data analysis for the first time. A consistent and stable result is achieved across different centers despite the between-center data variation while many other state-of-the-art methods such as two sample t-test fail. Moreover, we have empirically showed that the performance of this algorithm is robust and insensitive to several of its key parameters. In addition, the support identification results on both functional MRI and structural MRI are interpretable and can be the potential biomarkers.
StegBlocks: ensuring perfect undetectability of network steganography
Venue: arXiv cs.MM 2015
Year: 2015

The paper presents StegBlocks, which defines a new concept for performing undetectable hidden communication. StegBlocks is a general approach for constructing methods of network steganography. In StegBlocks, one has to determine objects with defined properties which will be used to transfer hidden messages. The objects are dependent on a specific network protocol (or application) used as a carrier for a given network steganography method. Moreover, the paper presents the approach to perfect undetectability of network steganography, which was developed based on the rules of undetectability for general steganography. The approach to undetectability of network steganography was used to show the possibility of developing perfectly undetectable network steganography methods using the StegBlocks concept.