OpenRaiser/Intern-Atlas huggingface dataset:
Hashing Pursuit for Online Identification of Heavy-Hitters in High-Speed Network Streams
Venue: arXiv cs.CR 2014
Year: 2014

Distributed Denial of Service (DDoS) attacks have become more prominent recently, both in frequency of occurrence, as well as magnitude. Such attacks render key Internet resources unavailable and disrupt its normal operation. It is therefore of paramount importance to quickly identify malicious Internet activity. The DDoS threat model includes characteristics such as: (i) heavy-hitters that transmit large volumes of traffic towards "victims", (ii) persistent-hitters that send traffic, not necessarily large, to specific destinations to be used as attack facilitators, (iii) host and port scanning for compiling lists of un-secure servers to be used as attack amplifiers, etc. This conglomeration of problems motivates the development of space/time efficient summaries of data traffic streams that can be used to identify heavy-hitters associated with the above attack vectors. This paper presents a hashing-based framework and fast algorithms that take into account the large-dimensionality of the incoming network stream and can be employed to quickly identify the culprits. The algorithms and data structures proposed provide a synopsis of the network stream that is not taxing to fast-memory, and can be efficiently implemented in hardware due to simple bit-wise operations. The methods are evaluated using real-world Internet data from a large academic network.
Intelligent Indoor Mobile Robot Navigation Using Stereo Vision
Venue: arXiv cs.RO 2014
Year: 2014

Majority of the existing robot navigation systems, which facilitate the use of laser range finders, sonar sensors or artificial landmarks, has the ability to locate itself in an unknown environment and then build a map of the corresponding environment. Stereo vision, while still being a rapidly developing technique in the field of autonomous mobile robots, are currently less preferable due to its high implementation cost. This paper aims at describing an experimental approach for the building of a stereo vision system that helps the robots to avoid obstacles and navigate through indoor environments and at the same time remaining very much cost effective. This paper discusses the fusion techniques of stereo vision and ultrasound sensors which helps in the successful navigation through different types of complex environments. The data from the sensor enables the robot to create the two dimensional topological map of unknown environments and stereo vision systems models the three dimension model of the same environment.
Short Paths on the Voronoi Graph and the Closest Vector Problem with Preprocessing
Venue: arXiv cs.DS 2014
Year: 2014

Improving on the Voronoi cell based techniques of Micciancio and Voulgaris (SIAM J. Comp. 13), and Sommer, Feder and Shalvi (SIAM J. Disc. Math. 09), we give a Las Vegas $\tilde{O}(2^n)$ expected time and space algorithm for CVPP (the preprocessing version of the Closest Vector Problem, CVP). This improves on the $\tilde{O}(4^n)$ deterministic runtime of the Micciancio Voulgaris algorithm, henceforth MV, for CVPP (which also solves CVP) at the cost of a polynomial amount of randomness (which only affects runtime, not correctness). As in MV, our algorithm proceeds by computing a short path on the Voronoi graph of the lattice, where lattice points are adjacent if their Voronoi cells share a common facet, from the origin to a closest lattice vector. Our main technical contribution is a randomized procedure that given the Voronoi relevant vectors of a lattice - the lattice vectors inducing facets of the Voronoi cell - as preprocessing and any "close enough" lattice point to the target, computes a path to a closest lattice vector of expected polynomial size. This improves on the $\tilde{O}(4^n)$ path length given by the MV algorithm. Furthermore, as in MV, each edge of the path can be computed using a single iteration over the Voronoi relevant vectors. As a byproduct of our work, we also give an optimal relationship between geometric and path distance on the Voronoi graph, which we believe to be of independent interest.
Manycore processing of repeated k-NN queries over massive moving objects observations
Venue: arXiv cs.DC 2014
Year: 2014

The ability to timely process significant amounts of continuously updated spatial data is mandatory for an increasing number of applications. In this paper we focus on a specific data-intensive problem concerning the repeated processing of huge amounts of k nearest neighbours (k-NN) queries over massive sets of moving objects, where the spatial extents of queries and the position of objects are continuously modified over time. In particular, we propose a novel hybrid CPU/GPU pipeline that significantly accelerate query processing thanks to a combination of ad-hoc data structures and non-trivial memory access patterns. To the best of our knowledge this is the first work that exploits GPUs to efficiently solve repeated k-NN queries over massive sets of continuously moving objects, even characterized by highly skewed spatial distributions. In comparison with state-of-the-art sequential CPU-based implementations, our method highlights significant speedups in the order of 10x-20x, depending on the datasets, even when considering cheap GPUs.
Small Field Size for Secure Network Coding
Venue: arXiv cs.IT 2014
Year: 2014

In network coding, information transmission often encounters wiretapping attacks. Secure network coding is introduced to prevent information from being leaked to adversaries. For secure linear network codes (SLNCs), the required field size is a very important index, because it largely determines the computational and space complexities of a SLNC, and it is also very important for the process of secure network coding from theoretical research to practical application. In this letter, we further discuss the required field size of SLNCs, and obtain a new lower bound. This bound shows that the field size of SLNCs can be reduced further, and much smaller than the known results for almost all cases.
The simplified weighted sum function and its average sensitivity
Venue: arXiv cs.CC 2014
Year: 2014

In this paper we simplify the definition of the weighted sum Boolean function which used to be inconvenient to compute and use. We show that the new function has essentially the same properties as the previous one. In particular, the bound on the average sensitivity of the weighted sum Boolean function remains unchanged after the simplification.
Multiprocessor System Dedicated to Multi-Rotor Mini-UAV Capable of 3D flying
Venue: arXiv cs.CE 2014
Year: 2014

The paper describes an electronic multiprocessor system that assures functionality of a miniature UAV capable of 3D flying. The apparatus consists of six independently controlled brushless DC motors, each having a propeller attached to it. Since the brushless motor requires complex algorithms in order to achieve maximum torque, efficiency and response time a DSP must be used. All the motors are then controlled by a main microprocessor which is capable of reading sensors (Inertial Measurement Unit (IMU)-orientation and GPS), receiving input commands (remote controller or trajectory plan) and sending independent commands to each of the six motors. The apparatus contains a total of eight microcontrollers: the main unit, the IMU mathematical processor and one microcontroller for each of the six brushless DC motors. Applications for such an apparatus could include not only military, but also search-and-rescue, geodetics, aerial photography and aerial assistance.
Sequential Equilibrium in Computational Games
Venue: arXiv cs.GT 2014
Year: 2014

We examine sequential equilibrium in the context of computational games, where agents are charged for computation. In such games, an agent can rationally choose to forget, so issues of imperfect recall arise. In this setting, we consider two notions of sequential equilibrium. One is an ex ante notion, where a player chooses his strategy before the game starts and is committed to it, but chooses it in such a way that it remains optimal even off the equilibrium path. The second is an interim notion, where a player can reconsider at each information set whether he is doing the "right" thing, and if not, can change his strategy. The two notions agree in games of perfect recall, but not in games of imperfect recall. Although the interim notion seems more appealing, \fullv{Halpern and Pass [2011] argue that there are some deep conceptual problems with it in standard games of imperfect recall. We show that the conceptual problems largely disappear in the computational setting. Moreover, in this setting, under natural assumptions, the two notions coincide.
Numerical simulation of liver perfusion: from CT scans to FE model
Venue: arXiv cs.CE 2014
Year: 2014

We use a collection of Python programs for numerical simulation of liver perfusion. We have an application for semi-automatic generation of a finite element mesh of the human liver from computed tomography scans and for reconstruction of the liver vascular structure. When the real vascular trees can not be obtained from the CT data we generate artificial trees using the constructive optimization method. The generated FE mesh and vascular trees are imported into SfePy (Simple Finite Elements in Python) and numerical simulations are performed in order to get the pressure distribution and perfusion flows in the liver tissue. In the post-processing steps we calculate transport of a contrast fluid through the liver parenchyma.
Grounding Hierarchical Reinforcement Learning Models for Knowledge Transfer
Venue: arXiv cs.LG 2014
Year: 2014

Methods of deep machine learning enable to to reuse low-level representations efficiently for generating more abstract high-level representations. Originally, deep learning has been applied passively (e.g., for classification purposes). Recently, it has been extended to estimate the value of actions for autonomous agents within the framework of reinforcement learning (RL). Explicit models of the environment can be learned to augment such a value function. Although "flat" connectionist methods have already been used for model-based RL, up to now, only model-free variants of RL have been equipped with methods from deep learning. We propose a variant of deep model-based RL that enables an agent to learn arbitrarily abstract hierarchical representations of its environment. In this paper, we present research on how such hierarchical representations can be grounded in sensorimotor interaction between an agent and its environment.
Network Coded Multi-Hop Wireless Communication Networks: Channel Estimation and Training Design
Venue: arXiv cs.IT 2014
Year: 2014

User cooperation based multi-hop wireless communication networks (MH-WCNs) as the key communication technological component of mobile social networks (MSNs) should be exploited to enhance the capability of accumulating data rates and extending coverage flexibly. As one of the most promising and efficient user cooperation techniques, network coding can increase the potential cooperation performance gains among selfishly driven users in MSNs. To take full advantages of network coding in MH-WCNs, a network coding transmission strategy and its corresponding channel estimation technique are studied in this paper. Particularly, a $4-$hop network coding transmission strategy is presented first, followed by an extension strategy for the arbitrary $2N-$hop scenario ($N\geq 2$). The linear minimum mean square error (LMMSE) and maximum-likelihood (ML) channel estimation methods are designed to improve the transmission quality in MH-WCNs. Closed form expressions in terms of the mean squared error (MSE) for the LMMSE channel estimation method are derived, which allows the design of the optimal training sequence. Unlike the LMMSE method, it is difficult to obtain closed-form MSE expressions for the nonlinear ML channel estimation method. In order to accomplish optimal training sequence design for the ML method, the Cramér-Rao lower bound (CRLB) is employed. Numerical results are provided to corroborate the proposed analysis, and the results demonstrate that the analysis is accurate and the proposed methods are effective.
On the Entity Hardening Problem in Multi-layered Interdependent Networks
Venue: arXiv cs.NI 2014
Year: 2014

The power grid and the communication network are highly interdependent on each other for their well being. In recent times the research community has shown significant interest in modeling such interdependent networks and studying the impact of failures on these networks. Although a number of models have been proposed, many of them are simplistic in nature and fail to capture the complex interdependencies that exist between the entities of these networks. To overcome the limitations, recently an Implicative Interdependency Model that utilizes Boolean Logic, was proposed and a number of problems were studied. In this paper we study the entity hardening problem, where by entity hardening we imply the ability of the network operator to ensure that an adversary (be it Nature or human) cannot take a network entity from operative to inoperative state. Given that the network operator with a limited budget can only harden k entities, the goal of the entity hardening problem is to identify the set of k entities whose hardening will ensure maximum benefit for the operator, i.e. maximally reduce the ability of the adversary to degrade the network. We show that the problem is solvable in polynomial time for some cases, whereas for others it is NP-complete. We provide the optimal solution using ILP, and propose a heuristic approach to solve the problem. We evaluate the efficacy of our heuristic using power and communication network data of Maricopa County, Arizona. The experiments show that our heuristic almost always produces near optimal results.
Correlation of Data Reconstruction Error and Shrinkages in Pair-wise Distances under Principal Component Analysis (PCA)
Venue: arXiv cs.LG 2014
Year: 2014

In this on-going work, I explore certain theoretical and empirical implications of data transformations under the PCA. In particular, I state and prove three theorems about PCA, which I paraphrase as follows: 1). PCA without discarding eigenvector rows is injective, but looses this injectivity when eigenvector rows are discarded 2). PCA without discarding eigen- vector rows preserves pair-wise distances, but tends to cause pair-wise distances to shrink when eigenvector rows are discarded. 3). For any pair of points, the shrinkage in pair-wise distance is bounded above by an L1 norm reconstruction error associated with the points. Clearly, 3). suggests that there might exist some correlation between shrinkages in pair-wise distances and mean square reconstruction error which is defined as the sum of those eigenvalues associated with the discarded eigenvectors. I therefore decided to perform numerical experiments to obtain the corre- lation between the sum of those eigenvalues and shrinkages in pair-wise distances. In addition, I have also performed some experiments to check respectively the effect of the sum of those eigenvalues and the effect of the shrinkages on classification accuracies under the PCA map. So far, I have obtained the following results on some publicly available data from the UCI Machine Learning Repository: 1). There seems to be a strong cor- relation between the sum of those eigenvalues associated with discarded eigenvectors and shrinkages in pair-wise distances. 2). Neither the sum of those eigenvalues nor pair-wise distances have any strong correlations with classification accuracies. 1
Bi-directional Shape Correspondences (BSC): A Novel Technique for 2-d Shape Warping in Quadratic Time?
Venue: arXiv cs.CV 2014
Year: 2014

We propose Bidirectional Shape Correspondence (BSC) as a possible improvement on the famous shape contexts (SC) framework. Our proposals derive from the observation that the SC framework enforces a one-to-one correspondence between sample points, and that this leads to two possible drawbacks. First, this denies the framework the opportunity to effect advantageous many-to-many matching between points on the two shapes being compared. Second, this calls for the Hungarian algorithm which unfortunately usurps cubic time. While the dynamic-space-warping dynamic programming algorithm has provided a standard solution to the first problem above, it demands quintic time for general multi-contour shapes, and w times quadratic time for the special case of single-contour shapes, even after an heuristic search window of width w has been chosen. Therefore, in this work, we propose a simple method for computing "many-to-many" correspondences for the class of all 2-d shapes in quadratic time. Our approach is to explicitly let each point on the first shape choose a best match on the second shape, and vice versa. Along the way, we also propose the use of data-clustering techniques for dealing with the outliers problem, and, from another viewpoint, it turns out that this clustering can be seen as an autonomous, rather than pre-computed, sampling of shape boundary.
Performance comparison between Java and JNI for optimal implementation of computational micro-kernels
Venue: arXiv cs.PF 2014
Year: 2014

General purpose CPUs used in high performance computing (HPC) support a vector instruction set and an out-of-order engine dedicated to increase the instruction level parallelism. Hence, related optimizations are currently critical to improve the performance of applications requiring numerical computation. Moreover, the use of a Java run-time environment such as the HotSpot Java Virtual Machine (JVM) in high performance computing is a promising alternative. It benefits from its programming flexibility, productivity and the performance is ensured by the Just-In-Time (JIT) compiler. Though, the JIT compiler suffers from two main drawbacks. First, the JIT is a black box for developers. We have no control over the generated code nor any feedback from its optimization phases like vectorization. Secondly, the time constraint narrows down the degree of optimization compared to static compilers like GCC or LLVM. So, it is compelling to use statically compiled code since it benefits from additional optimization reducing performance bottlenecks. Java enables to call native code from dynamic libraries through the Java Native Interface (JNI). Nevertheless, JNI methods are not inlined and require an additional cost to be invoked compared to Java ones. Therefore, to benefit from better static optimization, this call overhead must be leveraged by the amount of computation performed at each JNI invocation. In this paper we tackle this problem and we propose to do this analysis for a set of micro-kernels. Our goal is to select the most efficient implementation considering the amount of computation defined by the calling context. We also investigate the impact on performance of several different optimization schemes which are vectorization, out-of-order optimization, data alignment, method inlining and the use of native memory for JNI methods.
On the Ozarow-Leung Scheme for the Gaussian Broadcast Channel with Feedback
Venue: arXiv cs.IT 2014
Year: 2014

In this work, we consider linear-feedback schemes for the two-user Gaussian broadcast channel with noiseless feedback. We extend the transmission scheme of [Ozarow and Leung, 1984] by applying estimators with memory instead of the memoryless estimators used by Ozarow and Leung (OL) in their original work. A recursive formulation of the mean square errors achieved by the proposed estimators is provided, along with a proof for the existence of a fixed point. This enables characterizing the achievable rates of the extended scheme. Finally, via numerical simulations it is shown that the extended scheme can improve upon the original OL scheme in terms of achievable rates, as well as achieve a low probability of error after a finite number of channel uses.
Half-CNN: A General Framework for Whole-Image Regression
Venue: arXiv cs.CV 2014
Year: 2014

The Convolutional Neural Network (CNN) has achieved great success in image classification. The classification model can also be utilized at image or patch level for many other applications, such as object detection and segmentation. In this paper, we propose a whole-image CNN regression model, by removing the full connection layer and training the network with continuous feature maps. This is a generic regression framework that fits many applications. We demonstrate this method through two tasks: simultaneous face detection & segmentation, and scene saliency prediction. The result is comparable with other models in the respective fields, using only a small scale network. Since the regression model is trained on corresponding image / feature map pairs, there are no requirements on uniform input size as opposed to the classification model. Our framework avoids classifier design, a process that may introduce too much manual intervention in model development. Yet, it is highly correlated to the classification network and offers some in-deep review of CNN structures.
Coordinated Hybrid Automatic Repeat Request; Extended Version
Venue: arXiv cs.IT 2014
Year: 2014

We develop a coordinated hybrid automatic repeat request (HARQ) approach. With the proposed scheme, if a user message is correctly decoded in the first HARQ rounds, its spectrum is allocated to other users, to improve the network outage probability and the users' fairness. The results, which are obtained for single- and multiple-antenna setups, demonstrate the efficiency of the proposed approach in different conditions. For instance, with a maximum of M retransmissions and single transmit/receive antennas, the diversity gain of a user increases from M to (J+1)(M-1)+1 where J is the number of users helping that user.
Automatic Tuning of Local Memory Use on GPGPUs
Venue: arXiv cs.DC 2014
Year: 2014

The use of local memory is important to improve the performance of OpenCL programs. However, its use may not always benefit performance, depending on various application characteristics, and there is no simple heuristic for deciding when to use it. We develop a machine learning model to decide if the optimization is beneficial or not. We train the model with millions of synthetic benchmarks and show that it can predict if the optimization should be applied for a single array, in both synthetic and real benchmarks, with high accuracy.
Universal test for Hippocratic randomness
Venue: arXiv cs.IT 2014
Year: 2014

Hippocratic randomness is defined in a similar way to Martin-Lof randomness, however it does not assume computability of the probability and the existence of universal test is not assured. We introduce the notion of approximation of probability and show the existence of the universal test (Levin-Schnorr theorem) for Hippocratic randomness when the logarithm of the probability is approximated within additive constant.
The role of emotional variables in the classification and prediction of collective social dynamics
Venue: arXiv cs.SI 2014
Year: 2014

We demonstrate the power of data mining techniques for the analysis of collective social dynamics within British Tweets during the Olympic Games 2012. The classification accuracy of online activities related to the successes of British athletes significantly improved when emotional components of tweets were taken into account, but employing emotional variables for activity prediction decreased the classifiers' quality. The approach could be easily adopted for any prediction or classification study with a set of problem-specific variables.