OpenRaiser/Intern-Atlas huggingface dataset:
DBC based Face Recognition using DWT
Venue: arXiv cs.CV 2012
Year: 2012

The applications using face biometric has proved its reliability in last decade. In this paper, we propose DBC based Face Recognition using DWT (DBC- FR) model. The Poly-U Near Infra Red (NIR) database images are scanned and cropped to get only the face part in pre-processing. The face part is resized to 100*100 and DWT is applied to derive LL, LH, HL and HH subbands. The LL subband of size 50*50 is converted into 100 cells with 5*5 dimention of each cell. The Directional Binary Code (DBC) is applied on each 5*5 cell to derive 100 features. The Euclidian distance measure is used to compare the features of test image and database images. The proposed algorithm render better percentage recognition rate compared to the existing algorithm.
Matching with Commitments
Venue: arXiv cs.DS 2012
Year: 2012

We consider the following stochastic optimization problem first introduced by Chen et al. in \cite{chen}. We are given a vertex set of a random graph where each possible edge is present with probability p_e. We do not know which edges are actually present unless we scan/probe an edge. However whenever we probe an edge and find it to be present, we are constrained to picking the edge and both its end points are deleted from the graph. We wish to find the maximum matching in this model. We compare our results against the optimal omniscient algorithm that knows the edges of the graph and present a 0.573 factor algorithm using a novel sampling technique. We also prove that no algorithm can attain a factor better than 0.898 in this model.
Reconfigurable Controller Design For Actuator Faults In A Four-Tank System Benchmark
Venue: arXiv cs.SY 2012
Year: 2012

The purpose of this work is to design a state feedback controller using Parametric Eigenstructure Assignment (PAE) technique that has the capacity to be reconfigured in the case that partial actuator faults occur. The proposed controller is capable of compensating the gain losses in actuators and maintaining the control performance in faulty situations. Simulations show the performance enhancement in comparison to the non-reconfigurable controller through Integral Absolute Error (IAE) index for different fault scenarios.
Derivatives of Approximate Regular Expressions
Venue: arXiv cs.FL 2012
Year: 2012

Our aim is to construct a finite automaton recognizing the set of words that are at a bounded distance from some word of a given regular language. We define new regular operators, the similarity operators, based on a generalization of the notion of distance and we introduce the family of regular expressions extended to similarity operators, that we call AREs (Approximate Regular Expressions). We set formulae to compute the Brzozowski derivatives and the Antimirov derivatives of an ARE, which allows us to give a solution to the ARE membership problem and to provide the construction of two recognizers for the language denoted by an ARE. As far as we know, the family of approximative regular expressions is introduced for the first time in this paper. Classical approximate regular expression matching algorithms are approximate matching algorithms on regular expressions. Our approach is rather to process an exact matching on approximate regular expressions.
Goal Directed Relative Skyline Queries in Time Dependent Road Networks
Venue: arXiv cs.NI 2012
Year: 2012

The Wireless GIS technology is progressing rapidly in the area of mobile communications. Location-based spatial queries are becoming an integral part of many new mobile applications. The Skyline queries are latest apps under Location-based services. In this paper we introduce Goal Directed Relative Skyline queries on Time dependent (GD-RST) road networks. The algorithm uses travel time as a metric in finding the data object by considering multiple query points (multi-source skyline) relative to user location and in the user direction of travelling. We design an efficient algorithm based on Filter phase, Heap phase and Refine Skyline phases. At the end, we propose a dynamic skyline caching (DSC) mechanism which helps to reduce the computation cost for future skyline queries. The experimental evaluation reflects the performance of GD-RST algorithm over the traditional branch and bound algorithm for skyline queries in real road networks.
Design Space Exploration to Find the Optimum Cache and Register File Size for Embedded Applications
Venue: arXiv cs.AR 2012
Year: 2012

In the future, embedded processors must process more computation-intensive network applications and internet traffic and packet-processing tasks become heavier and sophisticated. Since the processor performance is severely related to the average memory access delay and also the number of processor registers affects the performance, cache and register file are two major parts in designing embedded processor architecture. Although increasing cache and register file size leads to performance improvement in embedded applications and packet-processing tasks in high traffic networks with too much packets, the increased area, power consumption and memory hierarchy delay are the overheads of these techniques. Therefore, implementing these components in the optimum size is of significant interest in the design of embedded processors. This paper explores the effect of cache and register file size on the processor performance to calculate the optimum size of these components for embedded applications. Experimental results show that although having bigger cache and register file is one of the performance improvement approaches in embedded processors, however, by increasing the size of these parameters over a threshold level, performance improvement is saturated and then, decreased.
Hamiltonian Annealed Importance Sampling for partition function estimation
Venue: arXiv cs.LG 2012
Year: 2012

We introduce an extension to annealed importance sampling that uses Hamiltonian dynamics to rapidly estimate normalization constants. We demonstrate this method by computing log likelihoods in directed and undirected probabilistic image models. We compare the performance of linear generative models with both Gaussian and Laplace priors, product of experts models with Laplace and Student's t experts, the mc-RBM, and a bilinear generative model. We provide code to compare additional models.
Dynamic Grouping of Web Users Based on Their Web Access Patterns using ART1 Neural Network Clustering Algorithm
Venue: arXiv cs.OH 2012
Year: 2012

In this paper, we propose ART1 neural network clustering algorithm to group users according to their Web access patterns. We compare the quality of clustering of our ART1 based clustering technique with that of the K-Means and SOM clustering algorithms in terms of inter-cluster and intra-cluster distances. The results show the average inter-cluster distance of ART1 is high compared to K-Means and SOM when there are fewer clusters. As the number of clusters increases, average inter-cluster distance of ART1 is low compared to K-Means and SOM which indicates the high quality of clusters formed by our approach.
Expressivity of Time-Varying Graphs and the Power of Waiting in Dynamic Networks
Venue: arXiv cs.DC 2012
Year: 2012

In infrastructure-less highly dynamic networks, computing and performing even basic tasks (such as routing and broadcasting) is a very challenging activity due to the fact that connectivity does not necessarily hold, and the network may actually be disconnected at every time instant. Clearly the task of designing protocols for these networks is less difficult if the environment allows waiting (i.e., it provides the nodes with store-carry-forward-like mechanisms such as local buffering) than if waiting is not feasible. No quantitative corroborations of this fact exist (e.g., no answer to the question: how much easier?). In this paper, we consider these qualitative questions about dynamic networks, modeled as time-varying (or evolving) graphs, where edges exist only at some times. We examine the difficulty of the environment in terms of the expressivity of the corresponding time-varying graph; that is in terms of the language generated by the feasible journeys in the graph. We prove that the set of languages $L_{nowait}$ when no waiting is allowed contains all computable languages. On the other end, using algebraic properties of quasi-orders, we prove that $L_{wait}$ is just the family of regular languages. In other words, we prove that, when waiting is no longer forbidden, the power of the accepting automaton (difficulty of the environment) drops drastically from being as powerful as a Turing machine, to becoming that of a Finite-State machine. This (perhaps surprisingly large) gap is a measure of the computational power of waiting. We also study bounded waiting; that is when waiting is allowed at a node only for at most $d$ time units. We prove the negative result that $L_{wait[d]} = L_{nowait}$; that is, the expressivity decreases only if the waiting is finite but unpredictable (i.e., under the control of the protocol designer and not of the environment).
Maximum Spanning Tree Model on Personalized Web Based Collaborative Learning in Web 3.0
Venue: arXiv cs.OH 2012
Year: 2012

Web 3.0 is an evolving extension of the current web environme bnt. Information in web 3.0 can be collaborated and communicated when queried. Web 3.0 architecture provides an excellent learning experience to the students. Web 3.0 is 3D, media centric and semantic. Web based learning has been on high in recent days. Web 3.0 has intelligent agents as tutors to collect and disseminate the answers to the queries by the students. Completely Interactive learner's query determine the customization of the intelligent tutor. This paper analyses the Web 3.0 learning environment attributes. A Maximum spanning tree model for the personalized web based collaborative learning is designed.
Sparse Approximation via Penalty Decomposition Methods
Venue: arXiv cs.LG 2012
Year: 2012

In this paper we consider sparse approximation problems, that is, general $l_0$ minimization problems with the $l_0$-"norm" of a vector being a part of constraints or objective function. In particular, we first study the first-order optimality conditions for these problems. We then propose penalty decomposition (PD) methods for solving them in which a sequence of penalty subproblems are solved by a block coordinate descent (BCD) method. Under some suitable assumptions, we establish that any accumulation point of the sequence generated by the PD methods satisfies the first-order optimality conditions of the problems. Furthermore, for the problems in which the $l_0$ part is the only nonconvex part, we show that such an accumulation point is a local minimizer of the problems. In addition, we show that any accumulation point of the sequence generated by the BCD method is a saddle point of the penalty subproblem. Moreover, for the problems in which the $l_0$ part is the only nonconvex part, we establish that such an accumulation point is a local minimizer of the penalty subproblem. Finally, we test the performance of our PD methods by applying them to sparse logistic regression, sparse inverse covariance selection, and compressed sensing problems. The computational results demonstrate that our methods generally outperform the existing methods in terms of solution quality and/or speed.
AGEM: Adaptive Greedy-Compass Energy-aware Multipath Routing Protocol for WMSNs
Venue: arXiv cs.NI 2012
Year: 2012

This paper presents an Adaptive Greedy-compass Energy-aware Multipath protocol (AGEM), a novel routing protocol for wireless multimedia sensors networks (WMSNs). AGEM uses sensors node positions to make packet forwarding decisions. These decisions are made online, at each forwarding node, in such a way that there is no need for global network topology knowledge and maintenance. AGEM routing protocol performs load-balancing to minimize energy consumption among nodes using twofold policy: (1) smart greedy forwarding, based on adaptive compass and (2) walking back forwarding to avoid holes. Performance evaluations of AGEM compared to GPSR (Greedy Perimeter Stateless Routing) show that AGEM can: (a) maximize the network lifetime, (b) guarantee quality of service for video stream transmission, and (c) scale better on densely deployed wireless sensors network.
Dynamic Loop Parallelisation
Venue: arXiv cs.PL 2012
Year: 2012

Regions of nested loops are a common feature of High Performance Computing (HPC) codes. In shared memory programming models, such as OpenMP, these structure are the most common source of parallelism. Parallelising these structures requires the programmers to make a static decision on how parallelism should be applied. However, depending on the parameters of the problem and the nature of the code, static decisions on which loop to parallelise may not be optimial, especially as they do not enable the exploitation of any runtime characteristics of the execution including changes to the iterations of the loops to be parallelised. We have developed a system that allows a code to make a dynamic choice, at runtime, of what parallelism is applied to nested loops. Our method for providing dynamic decisions on which loop to parallelise significantly outperforms the standard methods for acheiving this through OpenMP (using if clauses).
CloudMonitor: Profiling Power Usage
Venue: arXiv cs.DC 2012
Year: 2012

In Cloud Computing platforms the addition of hardware monitoring devices to gather power usage data can be impractical or uneconomical due to the large number of machines to be metered. CloudMonitor, a monitoring tool that can generate power models for software-based power estimation, can provide insights to the energy costs of deployments without additional hardware. Accurate power usage data leads to the possibility of Cloud providers creating a separate tariff for power and therefore incentivizing software developers to create energy-efficient applications.
Low Complexity Damped Gauss-Newton Algorithms for CANDECOMP/PARAFAC
Venue: arXiv cs.NA 2012
Year: 2012

The damped Gauss-Newton (dGN) algorithm for CANDECOMP/PARAFAC (CP) decomposition can handle the challenges of collinearity of factors and different magnitudes of factors; nevertheless, for factorization of an $N$-D tensor of size $I_1\times I_N$ with rank $R$, the algorithm is computationally demanding due to construction of large approximate Hessian of size $(RT \times RT)$ and its inversion where $T = \sum_n I_n$. In this paper, we propose a fast implementation of the dGN algorithm which is based on novel expressions of the inverse approximate Hessian in block form. The new implementation has lower computational complexity, besides computation of the gradient (this part is common to both methods), requiring the inversion of a matrix of size $NR^2\times NR^2$, which is much smaller than the whole approximate Hessian, if $T \gg NR$. In addition, the implementation has lower memory requirements, because neither the Hessian nor its inverse never need to be stored in their entirety. A variant of the algorithm working with complex valued data is proposed as well. Complexity and performance of the proposed algorithm is compared with those of dGN and ALS with line search on examples of difficult benchmark tensors.
Logical Inference Algorithms and Matrix Representations for Probabilistic Conditional Independence
Venue: arXiv cs.AI 2012
Year: 2012

Logical inference algorithms for conditional independence (CI) statements have important applications from testing consistency during knowledge elicitation to constraintbased structure learning of graphical models. We prove that the implication problem for CI statements is decidable, given that the size of the domains of the random variables is known and fixed. We will present an approximate logical inference algorithm which combines a falsification and a novel validation algorithm. The validation algorithm represents each set of CI statements as a sparse 0-1 matrix A and validates instances of the implication problem by solving specific linear programs with constraint matrix A. We will show experimentally that the algorithm is both effective and efficient in validating and falsifying instances of the probabilistic CI implication problem.
The Temporal Logic of Causal Structures
Venue: arXiv cs.AI 2012
Year: 2012

Computational analysis of time-course data with an underlying causal structure is needed in a variety of domains, including neural spike trains, stock price movements, and gene expression levels. However, it can be challenging to determine from just the numerical time course data alone what is coordinating the visible processes, to separate the underlying prima facie causes into genuine and spurious causes and to do so with a feasible computational complexity. For this purpose, we have been developing a novel algorithm based on a framework that combines notions of causality in philosophy with algorithmic approaches built on model checking and statistical techniques for multiple hypotheses testing. The causal relationships are described in terms of temporal logic formulae, reframing the inference problem in terms of model checking. The logic used, PCTL, allows description of both the time between cause and effect and the probability of this relationship being observed. We show that equipped with these causal formulae with their associated probabilities we may compute the average impact a cause makes to its effect and then discover statistically significant causes through the concepts of multiple hypothesis testing (treating each causal relationship as a hypothesis), and false discovery control. By exploring a well-chosen family of potentially all significant hypotheses with reasonably minimal description length, it is possible to tame the algorithm's computational complexity while exploring the nearly complete search-space of all prima facie causes. We have tested these ideas in a number of domains and illustrate them here with two examples.
Counting Belief Propagation
Venue: arXiv cs.AI 2012
Year: 2012

A major benefit of graphical models is that most knowledge is captured in the model structure. Many models, however, produce inference problems with a lot of symmetries not reflected in the graphical structure and hence not exploitable by efficient inference techniques such as belief propagation (BP). In this paper, we present a new and simple BP algorithm, called counting BP, that exploits such additional symmetries. Starting from a given factor graph, counting BP first constructs a compressed factor graph of clusternodes and clusterfactors, corresponding to sets of nodes and factors that are indistinguishable given the evidence. Then it runs a modified BP algorithm on the compressed graph that is equivalent to running BP on the original factor graph. Our experiments show that counting BP is applicable to a variety of important AI tasks such as (dynamic) relational models and boolean model counting, and that significant efficiency gains are obtainable, often by orders of magnitude.
Censored Exploration and the Dark Pool Problem
Venue: arXiv cs.LG 2012
Year: 2012

We introduce and analyze a natural algorithm for multi-venue exploration from censored data, which is motivated by the Dark Pool Problem of modern quantitative finance. We prove that our algorithm converges in polynomial time to a near-optimal allocation policy; prior results for similar problems in stochastic inventory control guaranteed only asymptotic convergence and examined variants in which each venue could be treated independently. Our analysis bears a strong resemblance to that of efficient exploration/ exploitation schemes in the reinforcement learning literature. We describe an extensive experimental evaluation of our algorithm on the Dark Pool Problem using real trading data.
REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
Venue: arXiv cs.LG 2012
Year: 2012

We provide an algorithm that achieves the optimal regret rate in an unknown weakly communicating Markov Decision Process (MDP). The algorithm proceeds in episodes where, in each episode, it picks a policy using regularization based on the span of the optimal bias vector. For an MDP with S states and A actions whose optimal bias vector has span bounded by H, we show a regret bound of ~O(HSpAT). We also relate the span to various diameter-like quantities associated with the MDP, demonstrating how our results improve on previous regret bounds.
Efficient Spatial Keyword Search in Trajectory Databases
Venue: arXiv cs.DB 2012
Year: 2012

An increasing amount of trajectory data is being annotated with text descriptions to better capture the semantics associated with locations. The fusion of spatial locations and text descriptions in trajectories engenders a new type of top-$k$ queries that take into account both aspects. Each trajectory in consideration consists of a sequence of geo-spatial locations associated with text descriptions. Given a user location $λ$ and a keyword set $ψ$, a top-$k$ query returns $k$ trajectories whose text descriptions cover the keywords $ψ$ and that have the shortest match distance. To the best of our knowledge, previous research on querying trajectory databases has focused on trajectory data without any text description, and no existing work has studied such kind of top-$k$ queries on trajectories. This paper proposes one novel method for efficiently computing top-$k$ trajectories. The method is developed based on a new hybrid index, cell-keyword conscious B$^+$-tree, denoted by \cellbtree, which enables us to exploit both text relevance and location proximity to facilitate efficient and effective query processing. The results of our extensive empirical studies with an implementation of the proposed algorithms on BerkeleyDB demonstrate that our proposed methods are capable of achieving excellent performance and good scalability.
A Comparative Study on the Performance of the Top DBMS Systems
Venue: arXiv cs.DB 2012
Year: 2012

Database management systems are today's most reliable mean to organize data into collections that can be searched and updated. However, many DBMS systems are available on the market each having their pros and cons in terms of reliability, usability, security, and performance. This paper presents a comparative study on the performance of the top DBMS systems. They are mainly MS SQL Server 2008, Oracle 11g, IBM DB2, MySQL 5.5, and MS Access 2010. The testing is aimed at executing different SQL queries with different level of complexities over the different five DBMSs under test. This would pave the way to build a head-to-head comparative evaluation that shows the average execution time, memory usage, and CPU utilization of each DBMS after completion of the test.
The model of information retrieval based on the theory of hypercomplex numerical systems
Venue: arXiv cs.IR 2012
Year: 2012

The paper provided a description of a new model of information retrieval, which is an extension of vector-space model and is based on the principles of the theory of hypercomplex numerical systems. The model allows to some extent realize the idea of fuzzy search and allows you to apply in practice the model of information retrieval practical developments in the field of hypercomplex numerical systems.