38254367
Parallel formulations of decision-tree classification algorithms
Classification decision tree algorithms are used extensively for data mining in many domains such as retail target marketing, fraud detection, etc. Highly parallel algorithms for constructing classification decision trees are desirable for dealing with large data sets in reasonable amount of time. Algorithms for building classification decision trees have a natural concurrency, but are difficult to parallelize due to the inherent dynamic nature of the computation. We present parallel formulations of classification decision tree learning algorithm based on induction. We describe two basic parallel formulations. One is based on Synchronous Tree Construction Approach and the other is based on Partitioned Tree Construction Approach. We discuss the advantages and disadvantages of using these methods and propose a hybrid method that employs the good features of these methods. Experimental results on an IBM SP-2 demonstrate excellent speedups and scalability.
10015251
Repartitioning of Adaptive Meshes: Experiments with Multilevel Diffusion
For a large class of irregular grid applications, the structure of the mesh changes from one phase of the computation to the next. Eventually, as the graph evolves, the adapted mesh has to be repartitioned to ensure good load balance. If this new graph is partitioned from scratch, it will lead to an excessive migration of data among processors. In this paper, we present a new scheme for computing repartitionings of adaptively refined meshes. This scheme performs diffusion of vertices in a multilevel framework and minimizes vertex movement without significantly compromising the edge-cut.
31161437
An adaptive mobility system for the disabled
A proof-of-concept prototype walking chair for the disabled is proposed with the objective of demonstrating the feasibility of a completely new approach to mobility. Our prototype system consists of a chair equipped with wheels and legs and is capable of walking on uneven terrain and circumventing obstacles. The important design considerations, the system design and an experimental prototype of a chair, are discussed. Redundancy in actuation enables the online optimization of tractive forces which enhances the adaptability of the system.<<ETX>>
11619174
Provable algorithms for parallel sweep scheduling on unstructured meshes
We present provably efficient parallel algorithms for sweep scheduling on unstructured meshes. Sweep scheduling is a commonly used technique in radiation transport problems, and involves inverting an operator by iteratively sweeping across a mesh. Each sweep involves solving the operator locally at each cell. However, each direction induces a partial order in which this computation can proceed. On a distributed computing system, the goal is to schedule the computation, so that the length of the schedule is minimized. Several heuristics have been proposed for this problem; but none of the heuristics have worst case performance guarantees. We present a simple, almost linear time randomized algorithm which (provably) gives a schedule of length at most O(log/sup 2/n) times the optimal schedule for instances with n cells, when the communication cost is not considered, and a slight variant, which coupled with a much more careful analysis, gives a schedule of (expected) length O(logmlogloglogm) times the optimal schedule for m processors. These are the first such provable guarantees for this problem. We also design a priority based list schedule using these ideas, with the same theoretical guarantee, but much better performance in practice. We complement our theoretical results with extensive empirical analysis. The results show that (i) our algorithm performs very well and has significantly better performance guarantee in practice and (ii) the algorithm compares favorably with other natural and efficient parallel algorithms proposed in the literature [S. Pautz, (2002), S. Plimpton et al., (2001)].
45908534
KRISHNA - Concurrency Control Algorithms based on Dynamic Attributes
Three new concurrency control mechanisms that utilizes the dynamic attribute of concurrent transactions for resolving conflicts are presented. Our study shows that their performance is superior to all well-known two-phase concurrency control mechanisms. There are a large number of such algorithms but we report our findings since our approach has some unique features worth exploring.
18215048
Performance of Recovery Algorithms for Centralized Database Management Systems
Database recovery is responsible for preserving the database consistency after a failure of any kind (transaction, system or media). Relevant information solely for recovery is saved in a log during normal transaction processing. To recover from a failure, basically two operations: undo and redo are applied with the help of the log on the last consistent state of the database. These two operations can be combined in four different ways to define four different types of recovery algorithms: “undo-redo,” “no undo-redo,” “undo-no redo” and “no undo-no redo.” Each of these algorithms manages log and updates to the database differently, which affect the overall performance and the availability of the database. 
 
To our knowledge, not much work has been done on the performance of recovery algorithms. There are only six reports available and these works have concentrated their studies on only a few algorithms. They have mainly used a queuing approach, which we believe is not adequate for a detailed performance study. In this paper we investigate the relative performance of these four algorithms through simulation. The purpose of conducting this study is first, to verify the findings of earlier works, and second, to obtain a detailed comparison of the behavior of all recovery algorithms. Our simulation studies show that in most cases, undo-redo and no undo-redo deliver similar but better recovery performance than undo-no redo and no undo-no redo. We observe that the recovery times increase with multiprogramming level, but generally decrease as the number of checkpoints increases. The undo-no redo algorithm results in a greater number of transaction rollbacks, which creates a larger transaction log, and thus longer recovery times. Its performance increases against undo-redo and no undo-redo as input/output performance improves. Slow input/output performance is also attributed to be the cause of the no undo-no redo algorithm's poor recovery performance.
1926044
Real-time vision-based control of a nonholonomic mobile robot
This paper considers the problem of vision-based control of a nonholonomic mobile robot. We describe the design and implementation of real-time estimation and control algorithms on a car-like robot platform using a single omni-directional camera as a sensor without explicit use of odometry. We provide experimental results for each of these vision-based control objects. The algorithms are packaged as control modes and can be combined hierarchically to perform higher level tasks involving multiple robots.