34436430
An Integrated Data Structure with Multiple Access Paths for Database Systems and its Performance
Abstract In the past a number of file organizations have been proposed for processing different types of queries efficiently. To our knowledge none of the existing file organizations is capable of supporting all types of accesses equally efficiently. In this paper we have taken a different approach for designing an integated data structure which offers multiple access paths for processing different types of queries efficiently. The data structure reported here can be implemented on disk based as well as main memory database systems, however, in this paper we report its behavior mainly in main memory database environment. Our approach is to fuse those data structures which offer an efficient access paths for a particular type. To show the feasibility of our scheme we fused the B+-tree, the grid file and extendible hashing structures, using a proper interface. We implemented and measured its performance through simulation modeling. Our results show that the data structure does improve concurrency and offers a higher throughput for a variety of transaction processing workloads. We argue that our scheme is different than creating secondary indexes for improving concurrency. In the absence of a data strucure which can provide all types of access equally efficiently, an integrated data structure is an acceptable solution which offers an efficient way for increasing the performance of database management systems.
11125586
The Behavior of Database Concurrency Control Mechanisms under Bursty Arrivals
The robustness and sensitivity of four two-phase databases concurrency control mechanisms are studied under a dynamically changing workload due to the bursty arrival of transactions. The concurrency control mechanisms are studied under closely controlled conditions in which the only variable is the coefficient of variance of the arrival rate distribution. This paper shows that bursty traffic does impact the performance of the concurrency control mechanisms at both high and low loads, and that the degree of this impact is different for the different mechanisms investigated. We also show that the behavior of some CCMs change significantly under such environment.
42935672
Performance Measurement of Main Memory Database Recovery Algorithms Based on Update-in-Place and Shadow Approaches
The authors present a performance study of two main memory database recovery algorithms, one using a shadow approach and the other update-in-place. The results show that in main memory databases, shadow approach performs better than update-in-place. The authors introduce minor improvements to the shadow scheme and show that the modified algorithm does show further performance improvement. >
35078097
An adaptive location management algorithm for mobile computing
In mobile computing mobile hosts or mobile units move randomly from one place to another within a well-defined geographical area. This requires some mechanism for identifying the exact location of a mobile host. Such mechanisms are usually referred to as location management and is one of the essential components for supporting mobility. In the past a number of efficient location management schemes have been suggested but they lack adaptability. We believe that an adaptable location management scheme is more desirable because of frequent change in the location of mobile hosts. In this paper, we report a location management algorithm, which adapts to the constant changing scenario. Our algorithm makes use of some of the concepts of location management schemes proposed in the past.
18803353
Performance of Multiversion and Distributed Two-Phase Locking Concurrency Control Mechanisms in Distributed Databases
In this paper, we have presented a detailed simulation study of a distributed multiversion and a distributed two-phase locking concurrency control mechanism (CCM). Our experiment concentrated on measuring the effect of message overhead, read:write ratios, data partitioning, and partial replication on the performance of these mechanisms. The effect of these parameters has not been investigated in any previous work. We simultated a blind-write model for two reasons: (a) all other works studied the behavior of multiversion CCMs under read-before-write model and observed a similar result, and (b) the performance of any multiversion CCM has not been studied under a blind-write model. A blind-write model is not unrealistic, and intutively the multiversion should provide much better performance. We observed that multiversion outperforms wound-wait (WW) in both partitioned and partially replicated databases. Multi version (MV) handles read-only and write-only transactions efficiently, and after a certain write percentage the throughput improves with this percentage. The message overhead progressively becomes less significant as the MPL (multiprogramming level) increases, indicating that in a heavily loaded system the throughput is least sensitive to message cost. We found that in the partially replicated case, 50% write does not show the lowest performance, as observed in the partitioned case.
39362526
Main memory database recovery algorithms and their performance
In main memory systems recovery becomes more complex mainly due to the volatility of main memory and the elimination of the separation of data storage (disk) and data processing locations (main memory). In a disk based database system, it is the disk copy that represents the stable database restored after a system failure; but in MDBSs, the main memory copy of the database must be recovered. The paper discusses the recovery issues in MDBSs and presents a somewhat detailed performance study of two recovery algorithms, one using a shadow approach and the other update-in-place.<<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)].
41766531
High Performance Data Mining
The current decade has seen an explosive growth in database technology and the amount of data collected. This has created an unprecedented opportunity for ”data mining,” which is a process of efficient supervised or unsupervised discovery of interesting information hidden in the data. The focus of this symposium is to bring together experts from the academia and the industry, including reseachers and practitioners, to discuss issues in this important area. Owing to the huge size of data and computation involved in data mining algorithms, parallel processing is often considered an essential component for a successful data mining solution - which will be a special emphasis of the symposium. Talks in this mini-symposium will cover both the current state-of the-practice as well as state-of-the-research in data mining. A highlight of the symposium is a panel discussion on the theory and practice of data mining.
5542960
Metrics for analysis and optimization of grasps and fixtures
We develop two quality measures for the analysis and optimization of grasps and fixtures. The first metric is a measure of stability and is obtained by analyzing the effect of small perturbations in the position of the grasped object or small disturbance forces on the grasped object The second metric is a measure of robustness to errors in the positions of the fixture elements. In addition, we explore the effect that the stiffness of the fixture elements has on these two quality measures and propose a design optimization approach to maximize stability and robustness to errors.
32920382
Kinematic modeling of head-neck movements
The main objective is to generate kinematic models for the head and neck movements. The motivation comes from our study of individuals with quadriplegia and the need to design rehabilitation aiding devices such as robots and teletheses that can be controlled by head-neck movements. It is then necessary to develop mathematical models for the head and neck movements. Two identification methods have been applied to study the kinematics of head-neck movements of able-body as well as neck-injured subjects. In particular, sagittal plane movements are well modeled by a planar two-revolute-joint linkage. In fact, the motion in joint space seems to indicate that sagittal plane movements may be classified as a single DOF motion. Finally, a spatial three-revolute-joint system has been employed to model 3D head-neck movements.
38425944
Scheduling on Unrelated Machines Under Tree-Like Precedence Constraints
We present polylogarithmic approximations for the R|prec|Cmax and R|prec|∑jwjCj problems, when the precedence constraints are “treelike” – i.e., when the undirected graph underlying the precedences is a forest. We also obtain improved bounds for the weighted completion time and flow time for the case of chains with restricted assignment – this generalizes the job shop problem to these objective functions. We use the same lower bound of “congestion+dilation”, as in other job shop scheduling approaches. The first step in our algorithm for the R|prec|Cmax problem with treelike precedences involves using the algorithm of Lenstra, Shmoys and Tardos to obtain a processor assignment with the congestion + dilation value within a constant factor of the optimal. We then show how to generalize the random delays technique of Leighton, Maggs and Rao to the case of trees. For the weighted completion time, we show a certain type of reduction to the makespan problem, which dovetails well with the lower bound we employ for the makespan problem. For the special case of chains, we show a dependent rounding technique which leads to improved bounds on the weighted completion time and new bicriteria bounds for the flow time.