16163881
An architecture for location dependent query processing
As the mobility of people increases, anytime, anywhere computing has become a must. With the advances in wireless communications, the geographical position of the mobile user can be estimated accurately enough to be used to access data dependent on it. Location awareness then enables new kinds of services specific to localized information. While this provides great flexibility for the end user, it creates many challenges for the content providers and wireless operators. We propose an architecture, location dependent services manager (LDSM), between the mobile user and the service/content providers to service location dependent applications which access location dependent data. The proposed middleware does location translation which we call location leveling, to adjust the location granularities and to solve the location mismatch problem. Quality of query results and the complicated queries involving more than one service provider is also supported in this middleware. We give an overview of the proposed architecture, examine the query processing issues and discuss the future work plans.
29393244
Semantic Caching and Query Processing
Semantic caching is very attractive for use in distributed systems due to the reduced network traffic and the improved response time. It is particularly efficient for a mobile computing environment, where the bandwidth of wireless links is a major performance bottleneck. Previous work either does not provide a formal semantic caching model, or lacks efficient query processing strategies. This paper extends the existing research in three ways: formal definitions associated with semantic caching are presented, query processing strategies are investigated and, finally, the performance of the semantic cache model is examined through a detailed simulation study.
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.
16958826
Recent Advances and Research Problems in Data Warehousing
In the recent years, the database community has witnessed the emergence of a new technology, namely data warehousing. A data warehouse is a global repository that stores pre-processed queries on data which resides in multiple, possibly heterogeneous, operational or legacy sources. The information stored in the data warehouse can be easily and efficiently accessed for making effective decisions. The On-Line Analytical Processing (OLAP) tools access data from the data warehouse for complex data analysis, such as multidimensional data analysis, and decision support activities. Current research has lead to new developments in all aspects of data warehousing, however, there are still a number of problems that need to be solved for making data warehousing effective. In this paper, we discuss recent developments in data warehouse modelling, view maintenance, and parallel query processing. A number of technical issues for exploratory research are presented and possible solutions are discussed.
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.
8261257
TCOT-A Timeout-Based Mobile Transaction Commitment Protocol
We present a transaction commit protocol, "Transaction Commit On Timeout (TCOT)," based on a "timeout" approach for Mobile Database Systems (MDS), which can be universally used to reach a final transaction termination decision (e.g., commit, abort, etc.) in any message-oriented system. Particularly suited for a wireless environment, a timeout mechanism is the only way to minimize the impact of the slow and unreliable wireless link. We compare TCOT to a modified version of 2PC to show its superiority based on commit time.
47057582
Covering Rectilinear Polygons with Axis-Parallel Rectangles
We give an $O(\sqrt{\log n})$ factor approximation algorithm for covering a rectilinear polygon with holes using axis-parallel rectangles. This is the first polynomial time approximation algorithm for this problem with an $o(\log n)$ approximation factor.
16866072
Metrics and Connections for Rigid-Body Kinematics
The set of rigid-body motions forms a Lie group called SE(3), the special Euclidean group in three dimensions. In this paper, we investigate possilble choices of Riemannian metrics and affine connections on SE(3) for applications to kinematic analysis and robot-trajectory planning. In the first part of the paper, we study metrics whose geodesics are screw motions. We prove that no Riemannian metrics call have such geodesics, and we show that the metrics whose geodesics are screw motions form a two-parameter family of semi-Riemannan metrics. In the second part of the paper, we investigate affine connections which through the covariant derivative give the correct expression for the acceleration of a rigid body. We prove that there is a unique symmetric connection with this property. Furthermore, we show that there is a family of Riemannian metrics that are compatible with such a connection. These metrics are products of the bi-invariant metric on the group of rotations and a positive-definite constant metric on the group of translations.
12696238
Clustering Based On Association Rule Hypergraphs
Clustering in data mining is a discovery process that groups a set of data such that the intracluster similarity is maximized and the intercluster similarity is minimized. These discovered clusters are used to explain the characteristics of the data distribution. In this paper we propose a new methodology for clustering related items using association rules, and clustering related transactions using clusters of items. Our approach is linearly scalable with respect to the number of transactions. The frequent item-sets used to derive association rules are also used to group items into a hypergraph edge, and a hypergraph partitioning algorithm is used to nd the clusters. Our experiments indicate that clustering using association rule hypergraphs holds great promise in several application domains. Our experiments with stock-market data and congressional voting data show that this clustering scheme is able to successfully group items that belong to the same group. Clustering of items can also be used to cluster the transactions containing these items. Our experiments with congressional voting data show that this method is quite e ective in nding clusters of transactions that correspond to either democrat or republican voting patterns. Compared to the existing clustering algorithmAutoclass, our algorithm produced comparable quality clusters in the congressional voting data. This work was supported by NSF grant ASC-9634719, Army Research O ce contract DA/DAAH04-95-1-0538, Cray Research Inc. Fellowship, and IBM partnership award, the content of which does not necessarily re ect the policy of the government, and no ofcial endorsement should be inferred. Access to computing facilities was provided by AHPCRC, Minnesota Supercomputer Institute, Cray Research Inc., and NSF grant CDA-9414015. See http://www.cs.umn.edu/ han for an extended version of this paper and other related papers.
206537669
Optimal control of systems with unilateral constraints
Problems in robotics and biomechanics such as trajectory planning or resolution of redundancy can be effectively solved using optimal control. Such systems are often subject to unilateral constraints. Examples include tasks involving contacts (e.g., walking, running, multifingered or multiarm manipulation), and other tasks that may not involve contacts but in which the system state or the inputs must satisfy inequality conditions (e.g., limits on actuator forces). This paper shows how problems of optimal control in robotics that involve unilateral constraints can be efficiently solved by first formulating the constrained optimal control problem as an unconstrained problem of the calculus of variations and then solving it using an integral formulation. This method has several advantages over the Pontryagin minimum principle which is traditionally employed to solve such problems. An example of two-arm manipulation with inequality constraints due to Coulomb friction is used to demonstrate the formulation of the problem and the algorithms.
5480787
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. In this paper, 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. We also provide the analysis of the cost of computation and communication of the proposed hybrid method. Moreover, experimental results on an IBM SP-2 demonstrate excellent speedups and scalability.