OpenRaiser/Intern-Atlas huggingface dataset:
Improving the Load Balance of MapReduce Operations based on the Key Distribution of Pairs
Venue: arXiv cs.DC 2014
Year: 2014

Load balance is important for MapReduce to reduce job duration, increase parallel efficiency, etc. Previous work focuses on coarse-grained scheduling. This study concerns fine-grained scheduling on MapReduce operations. Each operation represents one invocation of the Map or Reduce function. Scheduling MapReduce operations is difficult due to highly screwed operation loads, no support to collect workload statistics, and high complexity of the scheduling problem. So current implementations adopt simple strategies, leading to poor load balance. To address these difficulties, we design an algorithm to schedule operations based on the key distribution of intermediate pairs. The algorithm involves a sub-program for selecting operations for task slots, and we name it the Balanced Subset Sum (BSS) problem. We discuss properties of BSS and design exact and approximation algorithms for it. To transparently incorporate these algorithms into MapReduce, we design a communication mechanism to collect statistics, and a pipeline within Reduce tasks to increase resource utilization. To the best of our knowledge, this is the first work on scheduling MapReduce workload at this fine-grained level. Experiments on PUMA [T+12] benchmarks show consistent performance improvement. The job duration can be reduced by up to 37%, compared with standard MapReduce.
Quantitative Comparison Between Crowd Models for Evacuation Planning and Evaluation
Venue: arXiv cs.MA 2014
Year: 2014

Crowd simulation is rapidly becoming a standard tool for evacuation planning and evaluation. However, the many crowd models in the literature are structurally different, and few have been rigorously calibrated against real-world egress data, especially in emergency situations. In this paper we describe a procedure to quantitatively compare different crowd models or between models and real-world data. We simulated three models: (1) the lattice gas model, (2) the social force model, and (3) the RVO2 model, and obtained the distributions of six observables: (1) evacuation time, (2) zoned evacuation time, (3) passage density, (4) total distance traveled, (5) inconvenience, and (6) flow rate. We then used the DISTATIS procedure to compute the compromise matrix of statistical distances between the three models. Projecting the three models onto the first two principal components of the compromise matrix, we find the lattice gas and RVO2 models are similar in terms of the evacuation time, passage density, and flow rates, whereas the social force and RVO2 models are similar in terms of the total distance traveled. Most importantly, we find that the zoned evacuation times of the three models to be very different from each other. Thus we propose to use this variable, if it can be measured, as the key test between different models, and also between models and the real world. Finally, we compared the model flow rates against the flow rate of an emergency evacuation during the May 2008 Sichuan earthquake, and found the social force model agrees best with this real data.
Counting Terms in the Binary Lambda Calculus
Venue: arXiv cs.LO 2014
Year: 2014

In a paper entitled Binary lambda calculus and combinatory logic, John Tromp presents a simple way of encoding lambda calculus terms as binary sequences. In what follows, we study the numbers of binary strings of a given size that represent lambda terms and derive results from their generating functions, especially that the number of terms of size n grows roughly like 1.963447954^n.
Hybrid Approach to Face Recognition System using Principle component and Independent component with score based fusion process
Venue: arXiv cs.CV 2014
Year: 2014

Hybrid approach has a special status among Face Recognition Systems as they combine different recognition approaches in an either serial or parallel to overcome the shortcomings of individual methods. This paper explores the area of Hybrid Face Recognition using score based strategy as a combiner/fusion process. In proposed approach, the recognition system operates in two modes: training and classification. Training mode involves normalization of the face images (training set), extracting appropriate features using Principle Component Analysis (PCA) and Independent Component Analysis (ICA). The extracted features are then trained in parallel using Back-propagation neural networks (BPNNs) to partition the feature space in to different face classes. In classification mode, the trained PCA BPNN and ICA BPNN are fed with new face image(s). The score based strategy which works as a combiner is applied to the results of both PCA BPNN and ICA BPNN to classify given new face image(s) according to face classes obtained during the training mode. The proposed approach has been tested on ORL and other face databases; the experimented results show that the proposed system has higher accuracy than face recognition systems using single feature extractor.
Faster SVD-Truncated Least-Squares Regression
Venue: arXiv cs.DS 2014
Year: 2014

We develop a fast algorithm for computing the "SVD-truncated" regularized solution to the least-squares problem: $ \min_{\x} \TNorm{\matA \x - \b}. $ Let $\matA_k$ of rank $k$ be the best rank $k$ matrix computed via the SVD of $\matA$. Then, the SVD-truncated regularized solution is: $ \x_k = \pinv{\matA}_k \b. $ If $\matA$ is $m \times n$, then, it takes $O(m n \min\{m,n\})$ time to compute $\x_k $ using the SVD of \math{\matA}. We give an approximation algorithm for \math{\x_k} which constructs a rank-\math{k} approximation $\tilde{\matA}_{k}$ and computes $ \tilde{\x}_{k} = \pinv{\tilde\matA}_{k} \b$ in roughly $O(\nnz(\matA) k \log n)$ time. Our algorithm uses a randomized variant of the subspace iteration. We show that, with high probability: $ \TNorm{\matA \tilde{\x}_{k} - \b} \approx \TNorm{\matA \x_k - \b}$ and $\TNorm{\x_k - \tilde\x_k} \approx 0. $
CloudFridge: A Testbed for Smart Fridge Interactions
Venue: arXiv cs.HC 2014
Year: 2014

We present a testbed for exploring novel smart refrigerator interactions, and identify three key adoption-limiting interaction shortcomings of state-of-the-art smart fridges: lack of 1) user experience focus, 2) low-intrusion object recognition and 2) automatic item position detection. Our testbed system addresses these limitations by a combination of sensors, software filters, architectural components and a RESTful API to track interaction events in real-time, and retrieve current state and historical data to learn patterns and recommend user actions. We evaluate the accuracy and overhead of our system in a realistic interaction flow. The accuracy was measured to 83-88% and the overhead compared to a representative state-of-the-art barcode scanner improved by 27%. We also showcase two applications built on top of our testbed, one for finding expired items and ingredients of dishes; and one to monitor your health. The pattern that these applications have in common is that they cast the interaction as an item-recommendation problem triggered when the user takes something out. Our testbed could help reveal further user-experience centric interaction patterns and new classes of applications for smart fridges that inherently, by relying on our testbed primitives, mitigate the issues with existing approaches.
Cylindrical Algebraic Sub-Decompositions
Venue: arXiv cs.SC 2014
Year: 2014

Cylindrical algebraic decompositions (CADs) are a key tool in real algebraic geometry, used primarily for eliminating quantifiers over the reals and studying semi-algebraic sets. In this paper we introduce cylindrical algebraic sub-decompositions (sub-CADs), which are subsets of CADs containing all the information needed to specify a solution for a given problem. We define two new types of sub-CAD: variety sub-CADs which are those cells in a CAD lying on a designated variety; and layered sub-CADs which have only those cells of dimension higher than a specified value. We present algorithms to produce these and describe how the two approaches may be combined with each other and the recent theory of truth-table invariant CAD. We give a complexity analysis showing that these techniques can offer substantial theoretical savings, which is supported by experimentation using an implementation in Maple.
Critical Nodes In Directed Networks
Venue: arXiv cs.SI 2014
Year: 2014

Critical nodes or "middlemen" have an essential place in both social and economic networks when considering the flow of information and trade. This paper extends the concept of critical nodes to directed networks. We identify strong and weak middlemen. Node contestability is introduced as a form of competition in networks; a duality between uncontested intermediaries and middlemen is established. The brokerage power of middlemen is formally expressed and a general algorithm is constructed to measure the brokerage power of each node from the networks adjacency matrix. Augmentations of the brokerage power measure are discussed to encapsulate relevant centrality measures. We use these concepts to identify and measure middlemen in two empirical socio-economic networks, the elite marriage network of Renaissance Florence and Krackhardt's advice network.
Determining the Possibilities and Certainties in Network Participation for MANETS
Venue: arXiv cs.NI 2014
Year: 2014

A mobile ad hoc network is a self organized cooperative network that works without any permanent infrastructure. This infrastructure less design makes it complex compared to other wireless networks. Lot of attacks and misbehavior obstruct the growth and implementation. The majority of attacks and misbehavior can be handled by existing protocols. But these protocols reduce the total strength of nodes in a network because they isolate nodes from network participation having lesser reputation value. To cope with this problem we have presented the Possibility and Certainty model. This model uses reputation value to determine the possibilities and certainties in network participation. The proposed model classifies nodes into three classes such as certain or HIGH grade possible or MED grade and not possible or LOW grade. Choosing HIGH grade nodes in network activities improves the Packet Delivery Ratio which enhances the throughput of the MANET. On the other hand when node strength is poor we choose MED grade nodes for network activities. Thus the proposed model allows communication in the worst scenario with the possibility of success. It protects a network from misbehavior by isolating LOW grade nodes from routing paths.
Spectrum Hole Prediction Based On Historical Data: A Neural Network Approach
Venue: arXiv cs.NE 2014
Year: 2014

The concept of cognitive radio pioneered by Mitola promises to change the future of wireless communication especially in the area of spectrum management. Currently, the command and control strategy employed in spectrum assignment is too rigid and needs to be reviewed. Recent studies have shown that assigned spectrum is underutilized spectrally and temporally. Cognitive radio provides a viable solution whereby licensed users can share the spectrum with unlicensed users opportunistically without causing interference. Unlicensed users must be able to sense weather the channel is busy or idle, failure to do so will lead to interference to the licensed user. In this paper, a neural network based prediction model for predicting the channel status using historical data obtained during a spectrum occupancy measurement is presented. Genetic algorithm is combined with LM BP for increasing the probability of obtaining the best weights thus optimizing the network. The results obtained indicate high prediction accuracy over all bands considered
A survey on the importance of visualization and social collaboration in academic digital libraries
Venue: arXiv cs.DL 2014
Year: 2014

From more than half a century ago indexing scientific articles has been studied intensively to provide a more efficient data retrieval and to conserve researchers invaluable time. In the last two decades with the emergence of the World Wide Web and the rapid growth in the number of scientific documents online many academic databases and search engines were launched with almost similar structure in order to reduce the difficulty in finding, relating and sorting of the existing scientific documents published online. The dramatic increase of the scientific documents in the last few years makes it necessary that the retrieved information by the search engines be analyzed and more organized and interpretable representation be displayed to the users. Information visualization is a great way for exploration of large and complex data sets, therefore it can be a natural candidate for the purpose of generating more comprehensible search results for the citation and academic databases. In this survey the usage pattern of the participants and their demands and ideas for the existence of other beneficial methods for literature review has been questioned and the results are quantitatively analyzed.
Semantic A-translation and Super-consistency entail Classical Cut Elimination
Venue: arXiv cs.LO 2014
Year: 2014

We show that if a theory R defined by a rewrite system is super-consistent, the classical sequent calculus modulo R enjoys the cut elimination property, which was an open question. For such theories it was already known that proofs strongly normalize in natural deduction modulo R, and that cut elimination holds in the intuitionistic sequent calculus modulo R. We first define a syntactic and a semantic version of Friedman's A-translation, showing that it preserves the structure of pseudo-Heyting algebra, our semantic framework. Then we relate the interpretation of a theory in the A-translated algebra and its A-translation in the original algebra. This allows to show the stability of the super-consistency criterion and the cut elimination theorem.
Factor Graph Based LMMSE Filtering for Colored Gaussian Processes
Venue: arXiv cs.IT 2014
Year: 2014

We propose a low complexity, graph based linear minimum mean square error (LMMSE) filter in which the non-white characteristics of a random process are taken into account. Our method corresponds to block LMMSE filtering, and has the advantage of complexity linearly increasing with the block length and the ease of incorporating the a priori information of the input signals whenever possible. The proposed method can be used with any random process with a known autocorrelation function with the help of an approximation to an autoregressive (AR) process. We show through extensive simulations that our method performs very close to the optimal block LMMSE filtering for Gaussian input signals.
Discovering Compressing Serial Episodes from Event Sequences
Venue: arXiv cs.DB 2014
Year: 2014

Most pattern mining methods output a very large number of frequent patterns and isolating a small but relevant subset is a challenging problem of current interest in frequent pattern mining. In this paper we consider discovery of a small set of relevant frequent episodes from data sequences. We make use of the Minimum Description Length principle to formulate the problem of selecting a subset of episodes. Using an interesting class of serial episodes with inter-event constraints and a novel encoding scheme for data using such episodes, we present algorithms for discovering small set of episodes that achieve good data compression. Using an example of the data streams obtained from distributed sensors in a composable coupled conveyor system, we show that our method is very effective in unearthing highly relevant episodes and that our scheme also achieves good data compression.
Learning optimization models in the presence of unknown relations
Venue: arXiv cs.AI 2014
Year: 2014

In a sequential auction with multiple bidding agents, it is highly challenging to determine the ordering of the items to sell in order to maximize the revenue due to the fact that the autonomy and private information of the agents heavily influence the outcome of the auction. The main contribution of this paper is two-fold. First, we demonstrate how to apply machine learning techniques to solve the optimal ordering problem in sequential auctions. We learn regression models from historical auctions, which are subsequently used to predict the expected value of orderings for new auctions. Given the learned models, we propose two types of optimization methods: a black-box best-first search approach, and a novel white-box approach that maps learned models to integer linear programs (ILP) which can then be solved by any ILP-solver. Although the studied auction design problem is hard, our proposed optimization methods obtain good orderings with high revenues. Our second main contribution is the insight that the internal structure of regression models can be efficiently evaluated inside an ILP solver for optimization purposes. To this end, we provide efficient encodings of regression trees and linear regression models as ILP constraints. This new way of using learned models for optimization is promising. As the experimental results show, it significantly outperforms the black-box best-first search in nearly all settings.
A Comparative Study of Downlink MIMO Cellular Networks with Co-located and Distributed Base-Station Antennas
Venue: arXiv cs.IT 2014
Year: 2014

Despite the common belief that substantial capacity gains can be achieved by using more antennas at the base-station (BS) side in cellular networks, the effect of BS antenna topology on the capacity scaling behavior is little understood. In this paper, we present a comparative study on the ergodic capacity of a downlink single-user multiple-input-multiple-output (MIMO) system where BS antennas are either co-located at the center or grouped into uniformly distributed antenna clusters in a circular cell. By assuming that the number of BS antennas and the number of user antennas go to infinity with a fixed ratio $L\gg 1$, the asymptotic analysis reveals that the average per-antenna capacities in both cases logarithmically increase with $L$, but in the orders of $\log_2 L$ and $\tfracα{2}\log_2 L$, for the co-located and distributed BS antenna layouts, respectively, where $α>2$ denotes the path-loss factor. The analysis is further extended to the multi-user case where a 1-tier (7-cell) MIMO cellular network with $K\gg 1$ uniformly distributed users in each cell is considered. By assuming that the number of BS antennas and the number of user antennas go to infinity with a fixed ratio $L\gg K$, an asymptotic analysis is presented on the downlink rate performance with block diagonalization (BD) adopted at each BS. It is shown that the average per-antenna rates with the co-located and distributed BS antenna layouts scale in the orders of $\log_2 \tfrac{L}{K}$ and $\log_2 \frac{(L-K+1)^{α/2}}{K}$, respectively. The rate performance of MIMO cellular networks with small cells is also discussed, which highlights the importance of employing a large number of distributed BS antennas for the next-generation cellular networks.
Dynamic Assignment in Microsimulations of Pedestrians
Venue: arXiv cs.CE 2014
Year: 2014

A generic method for dynamic assignment used with microsimulation of pedestrian dynamics is introduced. As pedestrians - unlike vehicles - do not move on a network, but on areas they in principle can choose among an infinite number of routes. To apply assignment algorithms one has to select for each OD pair a finite (realistically a small) number of relevant representatives from these routes. This geometric task is the main focus of this contribution. The main task is to find for an OD pair the relevant routes to be used with common assignment methods. The method is demonstrated for one single OD pair and exemplified with an example.
Towards A Domain-specific Language For Pick-And-Place Applications
Venue: arXiv cs.RO 2014
Year: 2014

Programming robots is a complicated and time-consuming task. A robot is essentially a real-time, distributed embedded system. Often, control and communication paths within the system are tightly coupled to the actual physical configuration of the robot. Thus, programming a robot is a very challenging task for domain experts who do not have a dedicated background in robotics. In this paper we present an approach towards a domain specific language, which is intended to reduce the efforts and the complexity which is required when developing robotic applications. Furthermore we apply a software product line approach to realize a configurable code generator which produces C++ code which can either be run on real robots or on a robot simulator.
Cortical prediction markets
Venue: arXiv cs.AI 2014
Year: 2014

We investigate cortical learning from the perspective of mechanism design. First, we show that discretizing standard models of neurons and synaptic plasticity leads to rational agents maximizing simple scoring rules. Second, our main result is that the scoring rules are proper, implying that neurons faithfully encode expected utilities in their synaptic weights and encode high-scoring outcomes in their spikes. Third, with this foundation in hand, we propose a biologically plausible mechanism whereby neurons backpropagate incentives which allows them to optimize their usefulness to the rest of cortex. Finally, experiments show that networks that backpropagate incentives can learn simple tasks.
Robust Proximity Search for Balls using Sublinear Space
Venue: arXiv cs.CG 2014
Year: 2014

Given a set of n disjoint balls b1, . . ., bn in IRd, we provide a data structure, of near linear size, that can answer (1 \pm ε)-approximate kth-nearest neighbor queries in O(log n + 1/ε^d) time, where k and εare provided at query time. If k and εare provided in advance, we provide a data structure to answer such queries, that requires (roughly) O(n/k) space; that is, the data structure has sublinear space requirement if k is sufficiently large.
Design & Development of the Graphical User Interface for Sindhi Language
Venue: arXiv cs.HC 2014
Year: 2014

This paper describes the design and implementation of a Unicode-based GUISL (Graphical User Interface for Sindhi Language). The idea is to provide a software platform to the people of Sindh as well as Sindhi diasporas living across the globe to make use of computing for basic tasks such as editing, composition, formatting, and printing of documents in Sindhi by using GUISL. The implementation of the GUISL has been done in the Java technology to make the system platform independent. The paper describes several design issues of Sindhi GUI in the context of existing software tools and technologies and explains how mapping and concatenation techniques have been employed to achieve the cursive shape of Sindhi script.
Forward and Inverse Kinematics Seamless Matching Using Jacobian
Venue: arXiv cs.GR 2014
Year: 2014

In this paper the problem of matching Forward Kinematics (FK) motion of a 3 Dimensional (3D) joint chain to the Inverse Kinematics (IK) movement and vice versa has been addressed. The problem lies at the heart of animating a 3D character having controller and manipulator based rig for animation within any 3D modeling and animation software. The seamless matching has been achieved through the use of pseudo-inverse of Jacobian Matrix. The Jacobian Matrix is used to determine the rotation values of each joint of character body part such as arms, between the inverse kinematics and forward kinematics motion. Then moving the corresponding kinematic joint system to the desired place, automatically eliminating the jumping or popping effect which would reduce the complexity of the system.