28096769
Efficient Group Pattern Mining Using Data Summarization
In group pattern mining, we discover group patterns from a given user movement database based on their spatio-temporal distances. When both the number of users and the logging duration are large, group pattern mining algorithms become very inefficient. In this paper, we therefore propose a spherical location summarization method to reduce the overhead of mining valid 2-groups. In our experiments, we show that our group mining algorithm using summarized data may require much less execution time than that using non-summarized data.
6288169
Consulting past exceptions to facilitate workflow exception handling
In this paper, we propose an architecture model that deals with both expected and unexpected exceptions in the context of workflow management. Expected exceptions and their handling approaches are specified by ECA rules, while cases of unexpected exceptions are characterized by their features and resolution approaches. The handling of unexpected exceptions is then assisted by the system providing information about how recent similar cases were resolved. The ways in which the previous exception cases were handled provides useful information in determining how to handle the current one. Quantifying the similarity of exception cases is described, and three algorithms for efficiently searching for similar exception cases are proposed and evaluated both theoretically and by experimenting with synthetic data sets. D 2002 Elsevier B.V. All rights reserved.
13958377
Myriad: Design and Implementation of a Federated Database Prototype
SUMMARY A key problem in providing ‘enterprise-wide’ information is the integration of databases that have been independently developed. An important requirement is to accommodate heterogeneity and maintain the autonomy of component databases. Myriad is a federated database prototype developed at the University of Minnesota, to provide a testbed for investigating alternatives in architecture and algorithms for database integration, query processing and optimization, and concurrency control and recovery. The system incorporates our group’s research results in these areas. This paper describes our experiences in the design and implementation of Myriad, and in the project management. Special emphasis is given to discussing design alternatives and their impact on Myriad. This paper also presents the software engineering principles and the project management techniques we used in developing Myriad and the lessons we learned. We believe these lessons would be useful for practitioners who wish to develop a similar system. Handling heterogeneity and autonomy were prime objectives throughout the prototyping effort. We are convinced that a prototype federated database is an important infrastructural requirement for the overall goal of ‘enterprise-integration’, and believe Myriad to be a significant contribution towards this.
24326593
An algebraic transformation framework for multidatabase queries
Existence of semantic conflicts between component databases severely impacts query processing in a multidatabase system. In this paper, we describe two types of semantic conflicts that have to be dealt with in the integration of databases modeling information about related sets of real-world entities. These are the entityidentification problem and theattribute value conflict problem. While thetwo-way outerjoin operation has been commonly used for resolving entity identification problem between two component relations, outerjoins using regular equality comparisons between component relation keys is shown to produce counter-intuitive entity identification result. We remedy this by defining a newkey-equality comparator in place of regular equality comparator, for outerjoins. For the attribute value conflict problem, we define aGeneralized Attribute Derivation (GAD) operation which allows user-defined attribute derivation functions to be used to compute new attributes from the component relations' attributes. By adding two-way outerjoin andGAD to the set of relational operations, the traditional algebraic transformation framework for relational queries is no longer adequate for multidatabase query processing and optimization. As a result, we introduceconstrained query tree as the multidatabase query representation. We show that some knowledge about query predicates and attribute derivation functions can be used to simplify queries. Such knowledge is modeled as an outerjoin graph attached to every outerjoin operation in the query tree. Based on this, we further extend the traditional algebraic transformation framework to include two-way outerjoins andGAD operations. Our framework demonstrates that properties of selection/join predicates and attribute derivation functions can be used to provide interesting transformation alternatives. This framework also serves as a formal ground for developing optimization strategies for multidatabase queries.
2759516
A Case for Analytical Customer Relationship Management
The Internet has emerged as a low cost, low latency and high bandwidth customer communication channel. Its interactive nature provides an organization the ability to enter into a close, personalized dialog with individual customers. The simultaneous maturation of data management technologies like data warehousing, and data mining, have created the ideal environment for making customer relationship management (CRM) a much more systematic effort than it has been in the past. In this paper we described how data analytics can be used to make various CRM functions like customer segmentation, communication targeting, retention, and loyalty much more effective. We briefly describe the key technologies needed to implement analytical CRM, and the organizational issues that must be carefully handled to make CRM a reality. Our goal is to illustrate problems that exist with current CRM efforts, and how using data analytics techniques can address them. Our hope is to get the data mining community interested in this important application domain.
1401362
On the discovery of process models from their instances
A thorough understanding of the way in which existing business processes currently practice is essential from the perspectives of both process reengineering and workflow management. In this paper, we present a framework and algorithms that derive the underlying process model from past executions. The process model employs a directed graph for representing the control dependencies among activities and associates a Boolean function on each edge to indicate the condition under which the edge is to be enabled. By modeling the execution of an activity as an interval, we have developed an algorithm that derives the directed graph in a faster, more accurate manner. This algorithm is further enhanced with a noise handling mechanism to tolerate noise, which frequently occur in the real world. Experimental results show that the proposed algorithm outperforms the existing ones in terms of efficiency and quality.
1987744
Clustering High Dimensional Massive Scientific Datasets
Many scientific applications can benefit from an efficient clustering algorithm of massively large high dimensional datasets. However most of the developed algorithms are impractical to use when the amount of data is very large. Given N objects each defined by an M-dimensional feature vector, any clustering technique for handling very large datasets in high dimensional space should run in time O(MN) at best, and O(MN log N) in the worst case, using no more than O(MN) storage, for it to be practical. We introduce a hybrid algorithm, called HyCeltyc, for clustering massively large high dimensional datasets in O(MN) time which is linear in the size of the data. HyCeltyc, which stands for HybridCell Density Clustering method, combines a cell-density based algorithm with a hierarchical agglomerative method to identify clusters in linear time. The main steps of the algorithm involve sampling, dimensionality reduction, selection of significant features on which to cluster the data and a grid-based clustering algorihm that is linear in the data size.
14754194
Enabling soft queries for data retrieval
Data retrieval finding relevant data from large databases - has become a serious problem as myriad databases have been brought online in the Web. For instance, querying the for-sale houses in Chicago from realtor.com returns thousands of matching houses. Similarly, querying ''digital camera'' in froogle.com returns hundreds of thousand of results. This data retrieval is essentially an online ranking problem, i.e., ranking data results according to the user's preference effectively and efficiently. This paper proposes a new rank query framework, for effectively incorporating ''user-friendly'' rank-query formulation into ''data base (DB)-friendly'' rank-query processing, in order to enable ''soft'' queries on databases. Our framework assumes, as the ''back-end,'' the score-based ranking model for expressive and efficient query processing. On top of the score-based model, as the ''front-end,'' we adopt an SVM-ranking mechanism for providing intuitive and exploratory query formulation. In essence, our framework enables users to formulate queries simply by ordering some sample objects, while learning the ''DB-friendly'' ranking function F from the partial orders. Such learned functions can then be processed and optimized by existing database systems. We demonstrate the efficiency and effectiveness of our framework using real-life user queries and datasets: our results show that the system effectively learns quantitative ranking functions from qualitative feedback from users with efficient online processing.