15242556
AFOPT: An Efficient Implementation of Pattern Growth Approach
In this paper, we revisit the frequent itemset mining (FIM) problem and focus on studying the pattern growth approach. Existing pattern growth algorithms differ in several dimensions: (1) item search order; (2) conditional database representation; (3) conditional database construction strategy; and (4) tree traversal strategy. They adopted different strategies on these dimensions. Several adaptive algorithms were proposed to try to find good strategies for general situations. In this paper, we described the implementation techniques of an adaptive pattern growth algorithm, called AFOPT, which demonstrated good performance on all tested datasets. We also extended the algorithm to mine closed and maximal frequent itemsets. Comprehensive experiments were conducted to demonstrate the efficiency of the proposed algorithms.
6564567
Stabbing the sky: efficient skyline computation over sliding windows
We consider the problem of efficiently computing the skyline against the most recent N elements in a data stream seen so far. Specifically, we study the n-of-N skyline queries; that is, computing the skyline for the most recent n (/spl forall/n/spl les/N) elements. Firstly, we developed an effective pruning technique to minimize the number of elements to be kept. It can be shown that on average storing only O(log/sup d/ N) elements from the most recent N elements is sufficient to support the precise computation of all n-of-N skyline queries in a d-dimension space if the data distribution on each dimension is independent. Then, a novel encoding scheme is proposed, together with efficient update techniques, for the stored elements, so that computing an n-of-N skyline query in a d-dimension space takes O(log N+s) time that is reduced to O(d log log N+s) if the data distribution is independent, where s is the number of skyline points. Thirdly, a novel trigger based technique is provided to process continuous n-of-N skyline queries with O(/spl delta/) time to update the current result per new data element and O(log s) time to update the trigger list per result change, where /spl delta/ is the number of element changes from the current result to the new result. Finally, we extend our techniques to computing the skyline against an arbitrary window in the most recent N element. Besides theoretical performance guarantees, our extensive experiments demonstrated that the new techniques can support on-line skyline query computation over very rapid data streams.
3416923
Efficient Computation of the Skyline Cube
Skyline has been proposed as an important operator for multi-criteria decision making, data mining and visualization, and user-preference queries. In this paper. we consider the problem of efficiently computing a SKYCUBE, which consists of skylines of all possible non-empty subsets of a given set of dimensions. While existing skyline computation algorithms can be immediately extended to computing each skyline query independently, such "shared-nothing" algorithms are inefficient. We develop several computation sharing strategies based on effectively identifying the computation dependencies among multiple related skyline queries. Based on these sharing strategies, two novel algorithms, Bottom-Up and Top-Down algorithms, are proposed to compute SKYCUBE efficiently. Finally, our extensive performance evaluations confirm the effectiveness of the sharing strategies. It is shown that new algorithms significantly outperform the naive ones.
11539721
XParent: an efficient RDBMS-Based XML database system
Presents, XParent, an XML document management system built on top of RDBMS. It is based on an efficient, model-mapping-based approach that uses a fixed database schema to store any XML documents without assistance of DTD. The visual query interface of XParent provides both expressive power for professionals and user friendliness for naive users. The proposed multi-level query translation scheme makes it possible to develop a generic XML application that supports multiple XML query languages and mapping schemas.
11973783
Answering Approximate Range Aggregate Queries on OLAP Data Cubes with Probabilistic Guarantees
Approximate range aggregate queries are one of the most frequent and useful kinds of queries for Decision Support Systems (DSS). Traditionally, sampling- based techniques have been proposed to tackle this problem. However, its effectiveness will degrade when the underlying data distribution is skewed. Another approach based on the outlier management can limit the effect of data skew but fails to address other requirements of approximate range aggregate queries, such as error guarantees and query processing efficiency. In this paper, we present a technique that provide approximate answers to range aggregate queries on OLAP data cubes efficiently with theoretical error guarantees. Our basic idea is to build different data structures for outliers and the rest of the data. Experimental results verified the effectiveness of our proposed methods.
2266606
Space-efficient Relative Error Order Sketch over Data Streams
We consider the problem of continuously maintaining order sketches over data streams with a relative rank error guarantee ∊. Novel space-efficient and one-scan randomised techniques are developed. Our first randomised algorithm can guarantee such a relative error precision ∊ with confidence 1 - \delta using O( 1\_ \in \frac{1} {2}2 log 1d log ∊^2N) space, where N is the number of data elements seen so far in a data stream. Then, a new one-scan space compression technique is developed. Combined with the first randomised algorithm, the one-scan space compression technique yields another one-scan randomised algorithm that guarantees the space requirement is O( 1\frac{1} { \in } log(1\frac{1}{ \in } log 1\begin{gathered} \frac{1}{\delta } \hfill \\ \hfill \\ \end{gathered} )\frac{{\log ^{2 + \alpha } \in N}} {{1 - 1/2^\alpha }} (for\alpha \gt 0) on average while the worst case space remains O( \frac{1}{{ \in ^2 }}\log \frac{1} {\delta }\log \in ^2 N). These results are immediately applicable to approximately computing quantiles over data streams with a relative error guarantee \in and significantly improve the previous best space bound O( \frac{1} {{ \in ^3 }}\log \frac{1}{\delta }\log N). Our extensive experiment results demonstrate that both techniques can support an on-line computation against high speed data streams.
14320982
Sequential Pattern Mining in Multi-Databases via Multiple Alignment
To efficiently find global patterns from a multi-database, information in each local database must first be mined and summarized at the local level. Then only the summarized information is forwarded to the global mining process. However, conventional sequential pattern mining methods based on support cannot summarize the local information and is ineffective for global pattern mining from multiple data sources. In this paper, we present an alternative local mining approach for finding sequential patterns in the local databases of a multi-database. We propose the theme of approximate sequential pattern mining roughly defined as identifying patterns approximately shared by many sequences. Approximate sequential patterns can effectively summerize and represent the local databases by identifying the underlying trends in the data. We present a novel algorithm, ApproxMAP, to mine approximate sequential patterns, called consensus patterns, from large sequence databases in two steps. First, sequences are clustered by similarity. Then, consensus patterns are mined directly from each cluster through multiple alignment. We conduct an extensive and systematic performance study over synthetic and real data. The results demonstrate that ApproxMAP is effective and scalable in mining large sequences databases with long patterns. Hence, ApproxMAP can efficiently summarize a local database and reduce the cost for global mining. Furthremore, we present an elegant and uniform model to identify both high vote sequential patterns and exceptional sequential patterns from the collection of these consensus patterns from each local databases.
11994567
Enhancing Levin's method for computing quadric-surface intersections
Levin's method produces a parameterization of the intersection curve of two quadrics in the form p(u) = a(u) ± d(u) √s(u), where a(u) and d(u) are vector valued polynomials, and s(u) is a quartic polynomial. This method, however, is incapable of classifying the morphology of the intersection curve, in terms of reducibility, singularity, and the number of connected components, which is critical structural information required by solid modeling applications. We study the theoretical foundation of Levin's method, as well as the parameterization p(u) it produces. The following contributions are presented in this paper: (1) It is shown how the roots of s(u) can be used to classify the morphology of an irreducible intersection curve of two quadric surfaces. (2) An enhanced version of Levin's method is proposed that, besides classifying the morphology of the intersection curve of two quadrics, produces a rational parameterization of the curve if the curve is singular. (3) A simple geometric proof is given for the existence of a real ruled quadric in any quadric pencil, which is the key result on which Levin's method is based. These results enhance the capability of Levin's method in processing the intersection curve of two general quadrics within its own self-contained framework.
10163897
Accelerating approximate subsequence search on large protein sequence databases
In this paper, we study the problem on how to build a persistent index structure for protein sequences to support approximate match. The suffix tree has been proposed as a solution to index sequence database and has been deployed on organizing DNA sequences (Hunt et al. (2001)). Unfortunately, it suffers from the problem of "memory bottleneck" that prevents it from being applied efficiently to a large database. The performance even degrades further for protein database due to a larger fanout at each node. Here, we employ an indexing structure, called BASS-tree, to support approximate match in sublinear time on a large protein database. We call this indexing method the sequence approximate match index method. The search of approximate matches can be properly directed to the portion in the database with a high potential of matching quickly. It is demonstrated in our experiments that the potential performance improvement is in an order of magnitude over alternative methods such as the BLAST algorithm and the suffix tree.
33629250
Robust Visual Tracking Via Incremental Maximum Margin Criterion
Robust visual object tracking is one of the key problems in computer vision. Subspace based tracking method is a promising approach in handling appearance variability. Linear Discriminant Analysis(LDA) has been applied to this problem, but LDA is not a stable algorithm especially for visual tracking. Maximum Margin Criterion(MMC) is a recently proposed discriminant criterion. Its promising specialities make it a better choice for the tracking problem. In this paper, we present a novel subspace tracking algorithm based on MMC. We also proposed an incremental version of the corresponding algorithm so that the tracker can update in realtime. Experiments show our tracking algorithm is able to track objects well under large lighting, pose and expression variation.
14374205
Understanding Social Welfare Service Patterns Using Sequential Analysis
Classical exploratory data analysis methods in statistics and many of the earlier KDD methods tend to focus only on basic data types, (interval or categorical data) as the unit of analysis. However, some information cannot be interpreted unless the data is treated as a unit. For example, viewing the data as sequences of sets can reveal useful information that could not be extracted in any other way. Analyzing suitable databases from such a perspective can assist many social scientists in their work.