9605213
Probabilistic Optimization of Top N Queries
The problem of nding the best answers to a query quickly, rather than nding all answers, is of increasing importance as relational databases are applied in multimedia and decision-support domains. An approach to eeciently answering such \Top N" queries is to augment the query with an additional selection that prunes away the unwanted portion of the answer set. The risk is that if the selection returns fewer than the desired number of answers, the execution must be restarted (with a less selective lter). We propose a new, probabilistic approach to query optimization that quantiies this risk and seeks to minimize overall cost including the cost of possible restarts. We also present an extensive experimental study to demonstrate that probabilistic Top N query optimization can signiicantly reduce the average query execution time with relatively modest increases in the optimization time.
12672663
Sequence query processing
Many applications require the ability to manipulate sequences of data. We motivate the importance of sequence query processing, and present a framework for the optimization of sequence queries based on several novel techniques. These include query transformations, optimizations that utilize meta-data, and caching of intermediate results. We present a bottom-up algorithm that generates an efficient query evaluation plan based on cost estimates. This work also identifies a number of directions in which future research can be directed.
17596786
Mass Collaboration: A Case Study
We present an overview of a novel customer support system developed at QUIQ between 1999 and 2003. The application was perhaps the first systematic use of mass collaboration, which builds on the observation that large communities of users can be effectively leveraged to help each other, and to advance the interests of the community as a whole. In recent years, mass collaboration has been proposed for uses such as information integration and even program debugging, and shows much promise. In this paper, we outline the main ideas and technical challenges, and describe the QUIQ architecture. Technically, the main achievements include a novel DB-IR engine; a scalable notification engine for a rich class of user-specified alerts; a powerful access control mechanism with support for roles, dynamic groups, and field-level access control; and techniques for editing navigation hierarchies in dynamic sites.
24189746
Mass collaboration and data mining
Mass Collaboration is a new "P2P"-style approach to large-scale knowledge sharing, with applications in customer support, focused community development, and capturing knowledge distributed within large organizations. Effectively supporting this paradigm raises many technical challenges, and offers intriguing opportunities for mining massive amounts of data captured continually from user interactions. Data mining offers the promise of increased business intelligence, and also improved user experiences, leading to increased participation and greater quality in the knowledge that is captured, both of which are central objectives in Mass Collaboration. In this talk, I will introduce Mass Collaboration and discuss some important data mining related issues.
10786183
CACTUS—clustering categorical data using summaries
Clustering is an important data mining problem. Most of the earlier work on clustering focussed on numeric attributes which have a natural ordering on their attribute values. Recently, clustering data with categorical attributes, whose attribute values do not have a natural ordering, has received some attention. However, previous algorithms do not give a formal description of the clusters they discover and some of them assume that the user post-processes the output of the algorithm to identify the final clusters. In this paper, we introduce a novel formalization of a cluster for categorical attributes by generalizing a definition of a cluster for numerical attributes. We then describe a very fast summarizationbased algorithm called CACTUS that discovers exactly such clusters in the data. CACTUS has two important characteristics. First, the algorithm requires only two scans of the dataset, and hence is very fast and scalable. Our experiments on a variety of datasets show that CACTUS outperforms previous work by a factor of 3 to 10. Second, CACTUS can find clusters in subsets of all attributes and can thus perform a subspace clustering of the data. This feature is important if clusters do not span all attributes, a likely scenario if the number of attributes is very large. In a thorough experimental evaluation, we study the performance of CACTUS on real and synthetic datasets.
10580966
SRQL: Sorted Relational Query Language
A relation is an unordered collection of records. Often, however there is an underlying order (e.g., a sequence of stock prices), and users want to pose queries that reflect this order (e.g., find a weekly moving average). SQL provides no support for posing such queries. We show how a rich class of queries reflecting sort order can be naturally expressed and efficiently executed with simple extensions to SQL.
18797575
Scaling mining algorithms to large databases
Which insights about data structure make it possible to analyze the very large databases collected by Internet, business, scientific, and government applications?