OpenRaiser/Intern-Atlas huggingface dataset:
Packet Reception Probabilities in Vehicular Communications Close to Intersections
Venue: arXiv cs.SY 2016
Year: 2016

Vehicular networks allow vehicles to share information and are expected to be an integral part in future intelligent transportation system (ITS). In order to guide and validate the design process, analytical expressions of key performance metrics such as packet reception probabilities and throughput are necessary, in particular for accident-prone scenarios such as intersections. In this paper, we analyze the impact of interference in an intersection scenario with two perpendicular roads using tools from stochastic geometry. We present a general procedure to analytically determine the packet reception probability and throughput of a selected link, taking into account the geographical clustering of vehicles close to the intersection. We consider both Aloha and CSMA MAC protocols, and show how the procedure can be used to model different propagation environments of practical relevance. We show how different path loss functions and fading distributions can be incorporated in the analysis to model propagation conditions typical to both rural and urban intersections. Our results indicate that the procedure is general and flexible to deal with a variety of scenarios. Thus, it can serve as a useful design tool for communication system engineers, complementing simulations and experiments, to obtain quick insights into the network performance.
k-fingerprinting: a Robust Scalable Website Fingerprinting Technique
Venue: arXiv cs.CR 2016
Year: 2016

Website fingerprinting enables an attacker to infer which web page a client is browsing through encrypted or anonymized network connections. We present a new website fingerprinting technique based on random decision forests and evaluate performance over standard web pages as well as Tor hidden services, on a larger scale than previous works. Our technique, k-fingerprinting, performs better than current state-of-the-art attacks even against website fingerprinting defenses, and we show that it is possible to launch a website fingerprinting attack in the face of a large amount of noisy data. We can correctly determine which of 30 monitored hidden services a client is visiting with 85% true positive rate (TPR), a false positive rate (FPR) as low as 0.02%, from a world size of 100,000 unmonitored web pages. We further show that error rates vary widely between web resources, and thus some patterns of use will be predictably more vulnerable to attack than others.
Finding the Leftmost Critical Factorization on Unordered Alphabet
Venue: arXiv cs.DS 2016
Year: 2016

We present a linear time and space algorithm computing the leftmost critical factorization of a given string on an unordered alphabet.
Semantic Amodal Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

Common visual recognition tasks such as classification, object detection, and semantic segmentation are rapidly reaching maturity, and given the recent rate of progress, it is not unreasonable to conjecture that techniques for many of these problems will approach human levels of performance in the next few years. In this paper we look to the future: what is the next frontier in visual recognition? We offer one possible answer to this question. We propose a detailed image annotation that captures information beyond the visible pixels and requires complex reasoning about full scene structure. Specifically, we create an amodal segmentation of each image: the full extent of each region is marked, not just the visible pixels. Annotators outline and name all salient regions in the image and specify a partial depth order. The result is a rich scene structure, including visible and occluded portions of each region, figure-ground edge information, semantic labels, and object overlap. We create two datasets for semantic amodal segmentation. First, we label 500 images in the BSDS dataset with multiple annotators per image, allowing us to study the statistics of human annotations. We show that the proposed full scene annotation is surprisingly consistent between annotators, including for regions and edges. Second, we annotate 5000 images from COCO. This larger dataset allows us to explore a number of algorithmic ideas for amodal segmentation and depth ordering. We introduce novel metrics for these tasks, and along with our strong baselines, define concrete new challenges for the community.
Sample Efficient Path Integral Control under Uncertainty
Venue: arXiv cs.SY 2016
Year: 2016

We present a data-driven optimal control framework that can be viewed as a generalization of the path integral (PI) control approach. We find iterative feedback control laws without parameterization based on probabilistic representation of learned dynamics model. The proposed algorithm operates in a forward-backward manner which differentiate from other PI-related methods that perform forward sampling to find optimal controls. Our method uses significantly less samples to find optimal controls compared to other approaches within the PI control family that relies on extensive sampling from given dynamics models or trials on physical systems in model-free fashions. In addition, the learned controllers can be generalized to new tasks without re-sampling based on the compositionality theory for the linearly-solvable optimal control framework. We provide experimental results on three different systems and comparisons with state-of-the-art model-based methods to demonstrate the efficiency and generalizability of the proposed framework.
Approximation of the Quadratic Knapsack Problem
Venue: arXiv cs.DS 2016
Year: 2016

For any given $ε>0$ we provide an algorithm for the Quadratic Knapsack Problem that has an approximation ratio within $O(n^{2/5+ε})$ and a run time within $O(n^{9/ε})$.
An end-to-end generative framework for video segmentation and recognition
Venue: arXiv cs.CV 2016
Year: 2016

We describe an end-to-end generative approach for the segmentation and recognition of human activities. In this approach, a visual representation based on reduced Fisher Vectors is combined with a structured temporal model for recognition. We show that the statistical properties of Fisher Vectors make them an especially suitable front-end for generative models such as Gaussian mixtures. The system is evaluated for both the recognition of complex activities as well as their parsing into action units. Using a variety of video datasets ranging from human cooking activities to animal behaviors, our experiments demonstrate that the resulting architecture outperforms state-of-the-art approaches for larger datasets, i.e. when sufficient amount of data is available for training structured generative models.
Matrix Computations and Optimization in Apache Spark
Venue: arXiv cs.DC 2016
Year: 2016

We describe matrix computations available in the cluster programming framework, Apache Spark. Out of the box, Spark provides abstractions and implementations for distributed matrices and optimization routines using these matrices. When translating single-node algorithms to run on a distributed cluster, we observe that often a simple idea is enough: separating matrix operations from vector operations and shipping the matrix operations to be ran on the cluster, while keeping vector operations local to the driver. In the case of the Singular Value Decomposition, by taking this idea to an extreme, we are able to exploit the computational power of a cluster, while running code written decades ago for a single core. Another example is our Spark port of the popular TFOCS optimization package, originally built for MATLAB, which allows for solving Linear programs as well as a variety of other convex programs. We conclude with a comprehensive set of benchmarks for hardware accelerated matrix computations from the JVM, which is interesting in its own right, as many cluster programming frameworks use the JVM. The contributions described in this paper are already merged into Apache Spark and available on Spark installations by default, and commercially supported by a slew of companies which provide further services.
XCRUSH: A Family of ARX Block Ciphers
Venue: arXiv cs.CR 2016
Year: 2016

The XCRUSH family of non-Feistel, ARX block ciphers is designed to make efficient use of modern 64-bit general-purpose processors using a small number of encryption rounds which are simple to implement in software. The avalanche function, which applies one data-dependent, key-dependent rotation per 64-bit word of plaintext per round, allows XCRUSH to achieve an almost totally diffuse 256-bit block after just the first two rounds. Designed for speed in software, 3-round XCRUSH is measured at ~7.3 cycles/byte single-threaded on an Intel Haswell processor. A pseudorandom number generator, constructed using the avalanche function, serves as a key scheduling algorithm. No security claims are made in this paper.
Hiding the Rumor Source
Venue: arXiv cs.CR 2016
Year: 2016

Anonymous social media platforms like Secret, Yik Yak, and Whisper have emerged as important tools for sharing ideas without the fear of judgment. Such anonymous platforms are also important in nations under authoritarian rule, where freedom of expression and the personal safety of message authors may depend on anonymity. Whether for fear of judgment or retribution, it is sometimes crucial to hide the identities of users who post sensitive messages. In this paper, we consider a global adversary who wishes to identify the author of a message; it observes either a snapshot of the spread of a message at a certain time, sampled timestamp metadata, or both. Recent advances in rumor source detection show that existing messaging protocols are vulnerable against such an adversary. We introduce a novel messaging protocol, which we call adaptive diffusion, and show that under the snapshot adversarial model, adaptive diffusion spreads content fast and achieves perfect obfuscation of the source when the underlying contact network is an infinite regular tree. That is, all users with the message are nearly equally likely to have been the origin of the message. When the contact network is an irregular tree, we characterize the probability of maximum likelihood detection by proving a concentration result over Galton-Watson trees. Experiments on a sampled Facebook network demonstrate that adaptive diffusion effectively hides the location of the source even when the graph is finite, irregular and has cycles.
Empirical Big Data Research: A Systematic Literature Mapping
Venue: arXiv cs.DL 2016
Year: 2016

Background: Big Data is a relatively new field of research and technology, and literature reports a wide variety of concepts labeled with Big Data. The maturity of a research field can be measured in the number of publications containing empirical results. In this paper we present the current status of empirical research in Big Data. Method: We employed a systematic mapping method with which we mapped the collected research according to the labels Variety, Volume and Velocity. In addition, we addressed the application areas of Big Data. Results: We found that 151 of the assessed 1778 contributions contain a form of empirical result and can be mapped to one or more of the 3 V's and 59 address an application area. Conclusions: The share of publications containing empirical results is well below the average compared to computer science research as a whole. In order to mature the research on Big Data, we recommend applying empirical methods to strengthen the confidence in the reported results. Based on our trend analysis we consider Volume and Variety to be the most promising uncharted area in Big Data.
Estimating Absolute-Phase Maps Using ESPIRiT and Virtual Conjugate Coils
Venue: arXiv cs.CV 2016
Year: 2016

Purpose: To develop an ESPIRiT-based method to estimate coil sensitivities with image phase as a building block for efficient and robust image reconstruction with phase constraints. Theory and Methods: ESPIRiT is a new framework for calibration of the coil sensitivities and reconstruction in parallel Magnetic Resonance Imaging (MRI). Applying ESPIRiT to a combined set of physical and virtual conjugate coils (VCC-ESPIRiT) implicitly exploits conjugate symmetry in k-space similar to VCC-GRAPPA. Based on this method, a new post-processing step is proposed for the explicit computation of coil sensitivities that include the absolute phase of the image. The accuracy of the computed maps is directly validated using a test based on projection onto fully sampled coil images and also indirectly in phase-constrained parallel-imaging reconstructions. Results: The proposed method can estimate accurate sensitivities which include low-resolution image phase. In case of high-frequency phase variations VCC-ESPIRiT yields an additional set of maps that indicates the existence of a high-frequency phase component. Taking this additional set of maps into account can improve the robustness of phase-constrained parallel imaging. Conclusion: The extended VCC-ESPIRiT is a useful tool for phase-constrained imaging.
Semantic-Security Capacity for Wiretap Channels of Type II
Venue: arXiv cs.IT 2016
Year: 2016

The secrecy capacity of the type II wiretap channel (WTC II) with a noisy main channel is currently an open problem. Herein its secrecy-capacity is derived and shown to be equal to its semantic-security (SS) capacity. In this setting, the legitimate users communicate via a discrete-memoryless (DM) channel in the presence of an eavesdropper that has perfect access to a subset of its choosing of the transmitted symbols, constrained to a fixed fraction of the blocklength. The secrecy criterion is achieved simultaneously for all possible eavesdropper subset choices. The SS criterion demands negligible mutual information between the message and the eavesdropper's observations even when maximized over all message distributions. A key tool for the achievability proof is a novel and stronger version of Wyner's soft covering lemma. Specifically, a random codebook is shown to achieve the soft-covering phenomenon with high probability. The probability of failure is doubly-exponentially small in the blocklength. Since the combined number of messages and subsets grows only exponentially with the blocklength, SS for the WTC II is established by using the union bound and invoking the stronger soft-covering lemma. The direct proof shows that rates up to the weak-secrecy capacity of the classic WTC with a DM erasure channel (EC) to the eavesdropper are achievable. The converse follows by establishing the capacity of this DM wiretap EC as an upper bound for the WTC II. From a broader perspective, the stronger soft-covering lemma constitutes a tool for showing the existence of codebooks that satisfy exponentially many constraints, a beneficial ability for many other applications in information theoretic security.
Learning Contextual Dependencies with Convolutional Hierarchical Recurrent Neural Networks
Venue: arXiv cs.CV 2016
Year: 2016

Existing deep convolutional neural networks (CNNs) have shown their great success on image classification. CNNs mainly consist of convolutional and pooling layers, both of which are performed on local image areas without considering the dependencies among different image regions. However, such dependencies are very important for generating explicit image representation. In contrast, recurrent neural networks (RNNs) are well known for their ability of encoding contextual information among sequential data, and they only require a limited number of network parameters. General RNNs can hardly be directly applied on non-sequential data. Thus, we proposed the hierarchical RNNs (HRNNs). In HRNNs, each RNN layer focuses on modeling spatial dependencies among image regions from the same scale but different locations. While the cross RNN scale connections target on modeling scale dependencies among regions from the same location but different scales. Specifically, we propose two recurrent neural network models: 1) hierarchical simple recurrent network (HSRN), which is fast and has low computational cost; and 2) hierarchical long-short term memory recurrent network (HLSTM), which performs better than HSRN with the price of more computational cost. In this manuscript, we integrate CNNs with HRNNs, and develop end-to-end convolutional hierarchical recurrent neural networks (C-HRNNs). C-HRNNs not only make use of the representation power of CNNs, but also efficiently encodes spatial and scale dependencies among different image regions. On four of the most challenging object/scene image classification benchmarks, our C-HRNNs achieve state-of-the-art results on Places 205, SUN 397, MIT indoor, and competitive results on ILSVRC 2012.
Bandlimited Spatial Field Sampling with Mobile Sensors in the Absence of Location Information
Venue: arXiv cs.IT 2016
Year: 2016

Sampling of physical fields with mobile sensor is an emerging area. In this context, this work introduces and proposes solutions to a fundamental question: can a spatial field be estimated from samples taken at unknown sampling locations? Unknown sampling location, sample quantization, unknown bandwidth of the field, and presence of measurement-noise present difficulties in the process of field estimation. In this work, except for quantization, the other three issues will be tackled together in a mobile-sampling framework. Spatially bandlimited fields are considered. It is assumed that measurement-noise affected field samples are collected on spatial locations obtained from an unknown renewal process. That is, the samples are obtained on locations obtained from a renewal process, but the sampling locations and the renewal process distribution are unknown. In this unknown sampling location setup, it is shown that the mean-squared error in field estimation decreases as $O(1/n)$ where $n$ is the average number of samples collected by the mobile sensor. The average number of samples collected is determined by the inter-sample spacing distribution in the renewal process. An algorithm to ascertain spatial field's bandwidth is detailed, which works with high probability as the average number of samples $n$ increases. This algorithm works in the same setup, i.e., in the presence of measurement-noise and unknown sampling locations.
Expanded Parts Model for Semantic Description of Humans in Still Images
Venue: arXiv cs.CV 2016
Year: 2016

We introduce an Expanded Parts Model (EPM) for recognizing human attributes (e.g. young, short hair, wearing suit) and actions (e.g. running, jumping) in still images. An EPM is a collection of part templates which are learnt discriminatively to explain specific scale-space regions in the images (in human centric coordinates). This is in contrast to current models which consist of a relatively few (i.e. a mixture of) 'average' templates. EPM uses only a subset of the parts to score an image and scores the image sparsely in space, i.e. it ignores redundant and random background in an image. To learn our model, we propose an algorithm which automatically mines parts and learns corresponding discriminative templates together with their respective locations from a large number of candidate parts. We validate our method on three recent challenging datasets of human attributes and actions. We obtain convincing qualitative and state-of-the-art quantitative results on the three datasets.
60 GHz Multi-Gigabit Indoor WLANs: Dream or Reality?
Venue: arXiv cs.NI 2016
Year: 2016

The millimeter-wave (mmWave) technology, recently standardized by IEEE 802.11ad, is emerging as an attractive alternative to the traditional 2.4/5GHz wireless systems, promising multi-Gigabit wireless throughput. However, the high attenuation and vulnerability to blockage of 60 GHz links have limited its applications (until recently) to short-range, line-of-sight, static scenarios. On the other hand, the question of whether it is feasible to build general-purpose WLANs out of mmWave radios in dynamic indoor environments with non-line-of-sight links remains largely unanswered. In this paper, through extensive measurements with COTS 802.11ad hardware in an indoor office environment, we investigate the question of whether the mmWave technology, in spite of its unique propagation characteristics, can serve as a viable choice for providing multi-Gigabit ubiquitous wireless indoor connectivity. We study the range of 60 GHz transmissions in indoor environments, the impact of antenna height, location, orientation, and distance on 60 GHz performance, the interaction among metrics from different layers of the network stack, the increased opportunities for spatial reuse, and the impact of human blockage. Our results reveal a number of challenges that we have to address for 60 GHz multi-gigabit WLANs to become a reality.
Energy-Efficient Cell Activation, User Association, and Spectrum Allocation in Heterogeneous Networks
Venue: arXiv cs.IT 2016
Year: 2016

Next generation (5G) cellular networks are expected to be supported by an extensive infrastructure with many-fold increase in the number of cells per unit area compared to today. The total energy consumption of base transceiver stations (BTSs) is an important issue for both economic and environmental reasons. In this paper, an optimization-based framework is proposed for energy-efficient global radio resource management in heterogeneous wireless networks. Specifically, with stochastic arrivals of known rates intended for users, the smallest set of BTSs is activated with jointly optimized user association and spectrum allocation to stabilize the network first and then minimize the delay. The scheme can be carried out periodically on a relatively slow timescale to adapt to aggregate traffic variations and average channel conditions. Numerical results show that the proposed scheme significantly reduces the energy consumption and increases the quality of service compared to existing schemes in the literature.
An Improved Algorithm for Eye Corner Detection
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, a modified algorithm for the detection of nasal and temporal eye corners is presented. The algorithm is a modification of the Santos and Proenka Method. In the first step, we detect the face and the eyes using classifiers based on Haar-like features. We then segment out the sclera, from the detected eye region. From the segmented sclera, we segment out an approximate eyelid contour. Eye corner candidates are obtained using Harris and Stephens corner detector. We introduce a post-pruning of the Eye corner candidates to locate the eye corners, finally. The algorithm has been tested on Yale, JAFFE databases as well as our created database.
Colored Non-Crossing Euclidean Steiner Forest
Venue: arXiv cs.CG 2016
Year: 2016

Given a set of $k$-colored points in the plane, we consider the problem of finding $k$ trees such that each tree connects all points of one color class, no two trees cross, and the total edge length of the trees is minimized. For $k=1$, this is the well-known Euclidean Steiner tree problem. For general $k$, a $kρ$-approximation algorithm is known, where $ρ\le 1.21$ is the Steiner ratio. We present a PTAS for $k=2$, a $(5/3+\varepsilon)$-approximation algorithm for $k=3$, and two approximation algorithms for general~$k$, with ratios $O(\sqrt n \log k)$ and $k+\varepsilon$.