Traditionally, building a classifier requires two sets of examples: positive examples and negative examples. This paper studies the problem of building a text classifier using positive examples (P) and unlabeled examples (U). The unlabeled examples are mixed with both positive and negative examples. Since no negative example is given explicitly, the task of building a reliable text classifier becomes far more challenging. Simply treating all of the unlabeled examples as negative examples and building a classifier thereafter is undoubtedly a poor approach to tackling this problem. Generally speaking, most of the studies solved this problem by a two-step heuristic: first, extract negative examples (N) from U. Second, build a classifier based on P and N. Surprisingly, most studies did not try to extract positive examples from U. Intuitively, enlarging P by P' (positive examples extracted from U) and building a classifier thereafter should enhance the effectiveness of the classifier. Throughout our study, we find that extracting P' is very difficult. A document in U that possesses the features exhibited in P does not necessarily mean that it is a positive example, and vice versa. The very large size of and very high diversity in U also contribute to the difficulties of extracting P'. In this paper, we propose a labeling heuristic called PNLH to tackle this problem. PNLH aims at extracting high quality positive examples and negative examples from U and can be used on top of any existing classifiers. Extensive experiments based on several benchmarks are conducted. The results indicated that PNLH is highly feasible, especially in the situation where |P| is extremely small.

Quantile computation has many applications including data mining and financial data analysis. It has been shown that an /spl epsi/-approximate summary can be maintained so that, given a quantile query (/spl phi/,/spl epsi/), the data item at rank /spl lceil//spl phi/N/spl rceil/ may be approximately obtained within the rank error precision /spl epsi/N over all N data items in a data stream or in a sliding window. However, scalable online processing of massive continuous quantile queries with different /spl phi/ and /spl epsi/ poses a new challenge because the summary is continuously updated with new arrivals of data items. In this paper, first we aim to dramatically reduce the number of distinct query results by grouping a set of different queries into a cluster so that they can be processed virtually as a single query while the precision requirements from users can be retained. Second, we aim to minimize the total query processing costs. Efficient algorithms are developed to minimize the total number of times for reprocessing clusters and to produce the minimum number of clusters, respectively. The techniques are extended to maintain near-optimal clustering when queries are registered and removed in an arbitrary fashion against whole data streams or sliding windows. In addition to theoretical analysis, our performance study indicates that the proposed techniques are indeed scalable with respect to the number of input queries as well as the number of items and the item arrival rate in a data stream.

Summarizing topological relations is fundamental to many spatial applications including spatial query optimization. In this article, we present several novel techniques to effectively construct cell density based spatial histograms for range (window) summarizations restricted to the four most important level-two topological relations: contains, contained, overlap, and disjoint. We first present a novel framework to construct a multiscale Euler histogram in 2D space with the guarantee of the exact summarization results for aligned windows in constant time. To minimize the storage space in such a multiscale Euler histogram, an approximate algorithm with the approximate ratio 19/12 is presented, while the problem is shown NP-hard generally. To conform to a limited storage space where a multiscale histogram may be allowed to have only k Euler histograms, an effective algorithm is presented to construct multiscale histograms to achieve high accuracy in approximately summarizing aligned windows. Then, we present a new approximate algorithm to query an Euler histogram that cannot guarantee the exact answers; it runs in constant time. We also investigate the problem of nonaligned windows and the problem of effectively partitioning the data space to support nonaligned window queries. Finally, we extend our techniques to 3D space. Our extensive experiments against both synthetic and real world datasets demonstrate that the approximate multiscale histogram techniques may improve the accuracy of the existing techniques by several orders of magnitude while retaining the cost efficiency, and the exact multiscale histogram technique requires only a storage space linearly proportional to the number of cells for many popular real datasets.

Decision support systems issue a large number of online analytical processing (OLAP) queries to access very large databases. A data warehouse needs to precompute or materialize some of such OLAP queries in order to improve the system throughput, since many coming queries can benefit greatly from these materialized views. Materialized view selection with resource constraint is one of the most important issues in the management of data warehouses. It addresses how to fully utilize the limited resource, disk space, or maintenance time to minimize the total query processing cost. This paper revisits the problem of materialized view selection under a disk-space constraint S. Many efficient greedy algorithms have been developed to address this problem. The quality of greedy solutions is guaranteed by a lower bound. However, it is observed that, when S is small, this lower bound can be very small and even be negative. In such cases, their solution quality will not be guaranteed well. In order to improve further the solution quality in such cases, a new competitive A/sup */ algorithm is proposed. It is shown that it is just the distinctive topological structure of the dependent lattice that makes the A/sup */ search a very competitive strategy for this problem. Both theoretical and experimental results show that the proposed algorithm is a powerful, efficient, and flexible approach to this problem.

This paper presents a new solution for the problem of building a text classifier with a small yet of labeled positive documents (P) and a large set of unlabeled documents (U). Here, the unlabeled documents are mixed with both of the positive and negative documents. In other words, no document is labeled as negative. This makes the task of building a reliable text classifier challenging. In general, the existing approaches for solving this kind of problem use a two-step approach: i) extract the negative documents (N) from U; and ii) build a classifier based on P and N. However, none of the reported studies tries to further extract any positive documents (P') from U. Intuitively, extracting P' from U will increase the reliability of the classifier. However, extracting P' from U is difficult. A document in U that possesses some of the features exhibited in P does not necessarily mean that it is a positive document, and vice versa. It is very sensitive to extract positive documents, because those extracted positive samples may become noises. The very large size of U and the very high diversity exhibited there also contribute to the difficulty of extracting any positive documents. In this paper, we propose a partition-based heuristic which aims at extracting both of the positive and negative documents in U. Extensive experiments based on three benchmarks are conducted. The favorable results indicated that our proposed heuristic outperforms all of the existing approaches significantly, especially in the case where the size of P is extremely small.

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.

Mammalian genomes are typically 3 Gbps (gibabase pairs) in size. The largest public database NCBI (National Center for Biotechnology Information (http://www.ncbi.nlm.nih.gov)) of DNA contains more than 20 Gbps. Suffix trees are widely acknowledged as a data structure to support exact/approximate sequence matching queries as well as repetitive structure finding efficiently when they can reside in main memory. But, it has been shown as difficult to handle long DNA sequences using suffix trees due to the so-called memory bottleneck problems. The most space efficient main-memory suffix tree construction algorithm takes nine hours and 45 GB memory space to index the human genome [S. Kurtz (1999)]. We show that suffix trees for long DNA sequences can be efficiently constructed on disk using small bounded main memory space and, therefore, all existing algorithms based on suffix trees can be used to handle long DNA sequences that cannot be held in main memory. We adopt a two-phase strategy to construct a suffix tree on disk: 1) to construct a diskbase suffix-tree without suffix links and 2) rebuild suffix links upon the suffix-tree being constructed on disk, if needed. We propose a new disk-based suffix tree construction algorithm, called DynaCluster, which shows O(nlogn) experimental behavior regarding CPU cost and linearity for I/O cost. DynaCluster needs 16 MB main memory only to construct more than 200 Mbps DNA sequences and significantly outperforms the existing disk-based suffix-tree construction algorithms using prepartitioning techniques in terms of both construction cost and query processing cost. We conducted extensive performance studies and report our findings in this paper.

XML is emerging as a major standard for representing data on the World Wide Web. Recently, many XML storage models have been proposed to manage XML data. In order to assess an XML database's abilities to deal with XML queries, several benchmarks have also been proposed, including XMark and XMach. However, no reported studies using those benchmarks were found that can provide users with insights on the impacts of a variety of storage models on XML query performance. In this article, we report our first set of results on benchmarking a set of XML database implementations using two XML benchmarks. The selected implementations represent a wide range of approaches, including RDBMS-based systems with document-independent and document-dependent XML-relational schema mapping approaches, and XML native engines based on an Object-Oriented Model and the Document Object Model. Comprehensive experiments were conducted to study relative performance of different approaches and the important issues that affect XML query performance, such as path expression query processing, effectiveness of various partitioning, label-path, and indexing structures.

Statistics over the most recently observed data elements are often required in applications involving data streams, such as intrusion detection in network monitoring, stock price prediction in financial markets, Web log mining for access prediction, and user click stream mining for personalization. Among various statistics, computing quantile summary is probably most challenging because of its complexity. We study the problem of continuously maintaining quantile summary of the most recently observed N elements over a stream so that quantile queries can be answered with a guaranteed precision of /spl epsiv/N. We developed a space efficient algorithm for predefined N that requires only one scan of the input data stream and O(log(/spl epsiv//sup 2/N)//spl epsiv/+1//spl epsiv//sup 2/) space in the worst cases. We also developed an algorithm that maintains quantile summaries for most recent N elements so that quantile queries on any most recent n elements (n /spl les/ N) can be answered with a guaranteed precision of /spl epsiv/n. The worst case space requirement for this algorithm is only O(log/sup 2/(/spl epsiv/N)//spl epsiv//sup 2/). Our performance study indicated that not only the actual quantile estimation error is far below the guaranteed precision but the space requirement is also much less than the given theoretical bound.

An XML twig query, represented as a labeled tree, is essentially a complex selection predicate on both structure and content of an XML document. Twig query matching has been identified as a core operation in querying tree-structured XML data. A number of algorithms have been proposed recently to process a twig query holistically. Those algorithms, however, only deal with twig queries without OR-predicates. A straightforward approach that first decomposes a twig query with OR-predicates into multiple twig queries without OR-predicates and then combines their results is obviously not optimal in most cases. In this paper, we study novel holistic-processing algorithms for twig queries with OR-predicates without decomposition. In particular, we present a merge-based algorithm for sorted XML data and an index-based algorithm for indexed XML data. We show that holistic processing is much more efficient than the decomposition approach. Furthermore, we show that using indexes can significantly improve the performance for matching twig queries with OR-predicates, especially when the queries have large inputs but relatively small outputs.

Materialized view selection with resource constraint is one of the most important issues in the management of data warehouses. In this paper, we revisit the problem of materialized view selection under disk-space constraint S. Many efficient greedy algorithms have been developed. However, we observe that when S is small, their solution quality will not be well guaranteed. In order to further improve solution quality in such cases, we develop a competitive A* algorithm. Both theory and experiment results show that our algorithm is a powerful, efficient and flexible scheme for this problem.

Mining frequent patterns is a fundamental and important problem in many data mining applications. Many of the algorithms adopt the pattern growth approach, which is shown to be superior to the candidate generate-and-test approach significantly. We identify the key factors that influence the performance of the pattern growth approach, and optimize them to further improve the performance. Our algorithm uses a simple while compact data structure-ascending frequency ordered prefixtree (AFOPT) to organize the conditional databases, in which we use arrays to store single branches to further save space. We traverse our prefix-tree structure using a top-down strategy. Our experiment results show that the combination of the top-down traversal strategy and the ascending frequency item ordering method achieves significant performance improvement over previous works.

Various models and approaches have been proposed for mapping XML data into relational tables recently. Most of those approaches produce relational schema for given XML data, based on pre-defined rules, heuristics, and user specifications, without considering workload As the result, the schema obtained is often not optimal with respect to query performance. In this paper, we present a cost-driven approach to generate a near-optimal relational schema fir a given XML data and expected workload, in the presence of space constraint. An efficient heuristic algorithm based on Hill Climbing is proposed together with a set of state transformation operations. Experimental study using the prototype system implementing the proposed algorithm, indicates that the produced schema can provide better performance than those well-known mapping approaches published in the literature.

XML documents are typically queried with a combination of value search and structure search. While querying by values can leverage traditional database technologies, evaluating structural relationship, specifically parent-child or ancestor-descendant relationship, between XML element sets has imposed a great challenge on efficient XML query processing. We propose XR-tree, namely, XML region tree, which is a dynamic external memory index structure specially designed for strictly nested XML data. The unique feature of XR-tree is that, for a given element, all its ancestors (or descendants) in an element set indexed by an XR-tree can be identified with optimal worst case I/O cost. We then propose a new structural join algorithm that can evaluate the structural relationship between two XR-tree indexed element sets by effectively skipping ancestors and descendants that do not participate in the join. Our extensive performance study shows that the XR-tree based join algorithm significantly outperforms previous algorithms.

XML is emerging as a major standard for representing data on the World-Wide-Web. Recently, many XML storage models have been proposed to manage XML data. We propose several benchmarks including XMark and XMach in order to assess an XML database's abilities to deal with XML queries. We report our first set of results on benchmarking a set of XML database implementations using two XML benchmarks. In general, XML data can be managed as text files, by existing DBMSs, or by the so-called native XML engines. We implemented three XML database systems. VXMLR, and XParent were built on top of RDBMS, and XBase was implemented as a native XML engine. For each approach, variations on schema mapping and storage methods were also implemented for comparison.

We address issue related to containment join processing in tree-structured data such as XML documents. A containment join takes two sets of XML node elements as input and returns pairs of elements such that the containment relationship holds between them. While there are previous algorithms for processing containment joins, they require both element sets either sorted or indexed. We propose a novel and complete containment query processing framework based on a new coding scheme, PBiTree code. The PBiTree code allows us to determine the ancestor-descendant relationship between two elements from their PBiTree-based codes efficiently. We present algorithms in the framework that are optimized for various combinations of settings. In particular, the newly proposed partitioning based algorithms can process containment joins efficiently without sorting or indexes. Experimental results indicate that the containment join processing algorithms based on the proposed coding scheme outperform existing algorithms significantly.

Semisupervised learning methods construct classifiers using both labeled and unlabeled training data samples. While unlabeled data samples can help to improve the accuracy of trained models to certain extent, existing methods still face difficulties when labeled data is not sufficient and biased against the underlying data distribution. We present a clustering based classification (CBC) approach. Using this approach, training data, including both the labeled and unlabeled data, is first clustered with the guidance of the labeled data. Some of unlabeled data samples are then labeled based on the clusters obtained. Discriminative classifiers can subsequently be trained with the expanded labeled dataset. The effectiveness of the proposed method is justified analytically. Our experimental results demonstrated that CBC outperforms existing algorithms when the size of labeled dataset is very small.

Use of path expressions is a common feature in most XML query languages, and many evaluation methods for path expression queries have been proposed recently. However, there are few researches on the issue of optimizing regular path expression queries. In this paper, two kinds of path expression optimization principles are proposed, named path shortening and path complementing, respectively. The path shortening principle reduces the querying cost by shortening the path expressions with the knowledge of XML schema. While the path complementing principle substitutes the user queries with the equivalent lower-cost path expressions. The experimental results show that these two techniques can largely improve the performance of path expression query processing.

Extensive efforts have been devoted to developing efficient algorithms for mining frequent patterns. However, frequent pattern mining remains a time-consuming process, especially for very large datasets. It is therefore desirable to adopt a "mining once and using many times" strategy. Unfortunately, there has been little work reported on managing and organizing a large set of patterns for future use. In this paper, we propose a disk-based data structure, CFP-tree (Condensed Frequent Pattern Tree), for organizing frequent patterns discovered from transactional databases. In addition to an efficient algorithm for CFP-tree construction, we also developed algorithms to efficiently support two important types of queries, namely queries with minimum support constraints and queries with item constraints, against the stored patterns, as these two types of queries are basic building blocks for complex frequent pattern related mining tasks. Comprehensive experimental study has been conducted to demonstrate the effectiveness of CFP-tree and efficiency of related algorithms.

Feature selection is frequently used in data preprocessing for data mining. It decreases number of features, removes irrelevant or noisy data, and increases mining performance such as predictive accuracy and comprehensibility. This work investigates active sampling in feature selection in a filter model setting. Three versions of active sampling are proposed and empirically evaluated: two employ class information and the other utilizes feature variance. They are applied to a widely used, efficient feature selection algorithm Relief. In comparison with random sampling, we conduct extensive experiments with benchmark data sets.

Most existing clustering algorithms cluster highly related data objects such as Web pages and Web users separately. The interrelation among different types of data objects is either not considered, or represented by a static feature space and treated in the same ways as other attributes of the objects. In this paper, we propose a novel clustering approach for clustering multi-type interrelated data objects, ReCoM (Reinforcement Clustering of Multi-type Interrelated data objects). Under this approach, relationships among data objects are used to improve the cluster quality of interrelated data objects through an iterative reinforcement clustering process. At the same time, the link structure derived from relationships of the interrelated data objects is used to differentiate the importance of objects and the learned importance is also used in the clustering process to further improve the clustering results. Experimental results show that the proposed approach not only effectively overcomes the problem of data sparseness caused by the high dimensional relationship space but also significantly improves the clustering accuracy.

Recent years witnessed an increasing interest in researches in XML, partly due to the fact that XML has now become the de facto standard for data interchange over the internet. A large amount of work has been reported on XML storage models and query processing techniques. However, few works have addressed issues of XML query optimization. In this paper, we report our study on one of the challenges in XML query optimization: containment join size estimation. Containment join is well accepted as an important operation in XML query processing. Estimating the size of its results is no doubt essential to generate efficient XML query processing plans. We propose two models, the interval model and the position model, and a set of estimation methods based on these two models. Comprehensive performance studies were conducted. The results not only demonstrate the advantages of our new algorithms over existing algorithms, but also provide valuable insights into the tradeoff among various parameters.

In control and other modeling applications, fuzzy system with B-spline membership functions and CMAC neural network with B-spline basis functions are sometimes desired to approximate not only the assigned smooth function as well as its derivatives. In this paper, by designing the fuzzy system and CMAC neural network with B-spline basis functions, we prove that such a fuzzy system and CMAC can universally approximate a smooth function and its derivatives, that is to say, for a given accuracy, we can approximate an arbitrary smooth function by such fuzzy system and CMAC that not only the function is approximated within this accuracy, but its derivatives are approximated as well. The conclusions here provide solid theoretical foundation for their extensive applications.

Most of the previous studies on mining association rules are on mining intratransaction associations, i.e., the associations among items within the same transaction. We extend the scope to include multidimensional, intertransaction associations. In a database of stock price information, an example of such an association is "if (company) A's stock goes up on day one, B's stock will go down on day two but go up on day four:" whether we treat company or day as the unit of transaction, the items belong to different transactions. Moreover, such an intertransaction association can be extended to associate multiple properties in the same rule, so that multidimensional intertransaction associations can also be defined and discovered. Mining intertransaction associations pose more challenges on efficient processing than mining intratransaction associations because the number of potential association rules is extremely large. We introduce the notion of intertransaction association rule and develop an efficient algorithm, FITI (first intra then inter), for mining intertransaction associations, which adopts two major ideas: 1) an intertransaction frequent itemset contains only the frequent itemsets of its corresponding intratransaction counterpart; and 2) a special data structure is built among intratransaction frequent itemsets for efficient mining of intertransaction frequent itemsets.

Web access prediction is an active research topic with many applications. Various approaches have been proposed for Web access prediction in the domain of individual Web servers but they have to be tailored to the domain of proxy servers to satisfy its special requirements in prediction efficiency and scalability. In this paper, the design and implementation of proxy-based prediction service (PPS) is presented. For prediction efficiency, PPS applies a new prediction scheme which employs a two-layer navigation model to capture both inter-site and intra-site access patterns, incorporated with a bottom-up prediction mechanism that exploits reference locality in proxy logs. For system scalability, PPS manages the navigation model in disk database and adopts a predictive cache replacement strategy for data shipping between the model database and cache. We show the superiority of our prediction scheme over existing approaches and validate our model management and caching strategies, with a detailed performance study using real-world data.

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.

Although wrapper generation work has been reported in the literature, there seem no standard ways to evaluate the performance of such systems. We conducted a series of experiments to evaluate the usability, correctness and efficiency of SG-WRAP. The usability tests selected a number of users to use the system. The results indicated that, with minimal introduction of the system, DTD definition and structure of HTML pages, even naive users could quickly generate wrappers without much difficulty. For correctness, we adapted the precision and recall metrics in information retrieval to data extraction. The results show that, with the refining process, the system can generate wrappers with very high accuracy. Finally, the efficiency tests indicated that the wrapper generation process is fast enough even with large size Web pages.

Pre-computed data cube facilitates OLAP (on-line analytical processing). It is well-known that data cube computation is an expensive operation. While most algorithms have been devoted to optimizing memory management and reducing computation costs, less work has addressed a fundamental issue: the size of a data cube is huge when a large base relation with a large number of attributes is involved. In this paper, we propose a new concept, called a condensed data cube. The condensed cube is of much smaller size than a complete non-condensed cube. More importantly, it is a fully pre-computed cube without compression, and, hence, it requires neither decompression nor further aggregation when answering queries. Several algorithms for computing a condensed cube are proposed. Results of experiments on the effectiveness of condensed data cube are presented, using both synthetic and real-world data. The results indicate that the proposed condensed cube can reduce both the cube size and therefore its computation time.

With the rapid growth of textual information available on the Internet, having a good model for classifying and managing documents automatically is undoubtedly important. When more documents are archived, new terms, new concepts and concept-drift will frequently appear Without a doubt, updating the classification model frequently, rather than using the old model for a very long period is absolutely essential. Here, the challenges are: a) obtain a high accuracy classification model; b) consume low computational time for both model training and operation; and c) occupy low storage space. However, none of the existing classification approaches could achieve all of these requirements. In this paper, we propose a novel text classification approach, called discriminative category matching, which could achieve all of the stated characteristics. Extensive experiments using two benchmarks and a large real-life collection are conducted. The encouraging results indicated that our approach is highly feasible.

We propose a framework for mining frequent patterns from large transactional databases. The core of the framework is a coded prefix-path tree with two representations, namely, a memory-based prefix-path tree and a disk-based prefix-path tree. The disk-based prefix-path tree is simple in its data structure yet rich in information contained, and is small in size. The memory-based prefix-path tree is simple and compact. Based on the memory-based prefix-path tree, a new depth-first frequent pattern discovery algorithm, called PP-Mine, is proposed that outperforms FP-growth significantly. The memory-based prefix-path tree can be stored on disk using a disk-based prefix-path tree with assistance of the new coding scheme. We present loading algorithms to load the minimal required disk-based prefix-path tree into main memory. Our technique is to push constraints into the loading process, which has not been well studied yet.

With the rapid development of the Internet and the World Wide Web (WWW), very large amount of information is available and ready for downloading, most of which are free of charge. At the same time, hard disks with large capacity are available at affordable prices. Most of us nowadays often dump a large number of various types of documents into our computers without much thinking. On the other hand, file systems have not changed too much during the past decades. Most of them organize files in directories that form a tree structure, and a file is identified by its name and pathname in the directory tree. Remembering name of files created sometime ago and digging them out from a disk with dozen gigabytes of data in hundred thousands of files becomes never an easy task. Tools available for helping such a search are still far from satisfactory.Xbase (XML-based document BASE) is a prototype system aiming at addressing the above problem. By XML-based, we meant that XML is used to define the metadata. The current version of XBase stores text-based files, including semi-structured data such as XML, HTML, plain text documents (e.g., tex files, computer programs) and those files that can be converted into text (e.g., postscript files, PDF files). In XBase, file name is optional. Users can just load a file into XBase without giving a name and the directory where it should be stored. XBase will automatically associate it with attributes such as the time when the file was saved, its source, its size and type, and etc., To retrieve those files, XBase provides three access methods, explorative browsing, querying using query languages, and keyword based search.

Decision tree induction is one of the widely used classification approaches. It constructs a tree in which an internal node is split based on values of a selected attribute. Depending on the attribute selected at each level of the tree, a training dataset could lead to many different trees. Consequently, it is possible that an unseen case is classified into different and conflict classes using different trees. On the other band, recently developed association role based classifications are able to generate more interesting and useful rules than decision trees. However, the large number of rules without appropriate data structure brings the issue of efficiency. In this paper, we propose to unify decision tree classification with association-based classification using generalized decision trees (GDT). GDT generalizes the concept of decision tree to encode all interesting classification rules discovered based on association in a tree form. it inherits the merits of both approaches and removes their drawbacks. The data structure and related algorithms are discussed. Results of an experimental study are presented to indicate the advantages of GDT.

The switching regression problems are attracting more and more attention in a variety of disciplines such as pattern recognition, economics and databases. To solve switching regression problems, many approaches have been investigated. In this paper, we present a new integrated clustering algorithm GFC that combines gravity-based clustering algorithm GC with fuzzy clustering. GC, as a new hard clustering algorithm presented here, is based on the well-known Newton's Gravity Law. Our theoretic analysis shows that GFC can converge to a local minimum of the object function. Our experimental results illustrate that GFC for switching regression problems has better performance than standard fuzzy clustering algorithms, especially in terms of convergence speed. Hence GFC is a new more efficient algorithm for switching regression problems.

Computing an n-attribute datacube requires the computation of an aggregate function over all groups generated by 2/sup n/ interrelated GROUP-BYs. In this paper, we focus on multi-cube computation. We extend the algorithms for single datacube computation to process multiple datacubes simultaneously. The issue we intend to explore is the memory utilization. We propose two multi-cube algorithms, namely, a sort-based algorithm and a hash-based algorithm. Different data skews and sparsities are investigated. Results from our extensive performance studies are reported.

Methods for efficient mining of frequent patterns have been studied extensively by many researchers. However, the previously proposed methods still encounter some performance bottlenecks when mining databases with different data characteristics, such as dense vs. sparse, long vs. short patterns, memory-based vs. disk-based, etc. In this study, we propose a simple and novel hyper-linked data structure, H-struct and a new mining algorithm, H-mine, which takes advantage of this data structure and dynamically adjusts links in the mining process. A distinct feature of this method is that it has very limited and precisely predictable space overhead and runs really fast in memory-based setting. Moreover it can be scaled up to very large databases by database partitioning, and when the data set becomes dense, (conditional) FP-trees can be constructed dynamically as part of the mining process. Our study shows that H-mine has high performance in various kinds of data, outperforms the previously developed algorithms in different settings, and is highly scalable in mining large databases. This study also proposes a new data mining methodology, space-preserving mining, which may have strong impact in the future development of efficient and scalable data mining methods.

Various tools and systems for knowledge discovery and data mining have been developed and are available for applications. However, when there are many databases, an immediate question is where one should start mining. It is not true that data mining is better the more databases there are. It is only true when the databases involved are relevant to the task at hand. By breaking away from the conventional data mining assumption that many databases should be joined into one, we argue that the first step for multidatabase mining is to identify databases that are most relevant to an application; without doing so, the mining process can be lengthy, aimless, and ineffective. A measure of relevance is thus proposed for mining tasks with the objective of finding patterns or regularities of certain attributes. An efficient algorithm for identifying relevant databases is described. Experiments are conducted to verify the measure's performance and to exemplify its application.

Nave Bayes (NB) classifier has long been considered a core methodology in text classification mainly due to its simplicity and computational efficiency. There is an increasing need however for methods that can achieve higher classification accuracy while maintaining the ability to process large document collections. In this paper we examine text categorization methods from a perspective that considers the tradeoff between accuracy and scalability to large data sets and large feature sizes. We start from the observation that Support Vector Machines, one of the best text categorization methods cannot scale up to handle the large document collections involved in many real word problems. We then consider bayesian extensions to NB that achieve higher accuracy by relaxing its strong independence assumptions. Our experimental results show that LB, an association-based lazy classifier can achieve a good tradeoff between high classification accuracy and scalability to large document collections...

FACT (Fast and ACcuraTe) is a query processing system aimed at providing users with facilities so that they can get the query results from the Web in a database-like fashion. The system takes user queries in the form of keywords (free text) and returns segments of Web pages that contain the required information. It works as follows. The input from a user is passed to a general- purpose search engine to obtain a set of URLs of Web pages that may contain the required information. The system later locates the query results from the Web pages reachable from these URLs. Since queries expressed in keywords may be not able to express query requirements precisely or may not guarantee the discovery of required information inherently, the user is asked to first browse a few pages, during which the system learns from her/him about the exact query requirements and heuristics of finding the required information through a series of hyperlinks. The system will process the rest URLs and present the results in the form of segments of Web pages to the user.

In this paper, we extend the scope of mining association rules from traditional single-dimensional intratransaction associations, to multidimensional intertransaction associations. Intratransaction associations are the associations among items with thesame transaction, where the notion of the transaction could be the items bought by thesame customer, the events happened on thesame day, and so on. However, an intertransaction association describes the association relationships amongdifferent transactions, such as “if(company) A's stock goes up on day 1, B's stock will go down on day 2, but go up on day 4.” In this case, whether we treat company or day as the unit of transaction, the associated items belong to different transactions. Moreover, such an intertransaction association can be extended to associate multiple contextual properties in the same rule, so thatmultidimensionalintertransaction associations can be defined and discovered. A two-dimensional intertransaction association rule example is“After McDonald and Burger King open branches, KFC will open a branch two months later and one mile away,”which involves two dimensions:time and space. Mining intertransaction associations poses more challenges on efficient processing than mining intratransaction associations. Interestingly, intratransaction association can be treated as a special case of intertransaction association from both a conceptual and algorithmic point of view. In this study, we introduce the notion of multidimensional intertransaction association rules, study their measurements—supportand confidence—and develop algorithms for mining intertransaction associations by extension of Apriori. We overview our experience using the algorithms on both real-life and synthetic data sets. Further extensions of multidimensional intertransaction association rules and potential applications are also discussed.

On-line analytical processing (OLAP) requires efficient processing of complex decision support queries over very large databases. It is well accepted that pre-computed data cubes can help reduce the response time of such queries dramatically.Avery important design issue of an efficient OLAP system is therefore the choice of the right data cubes to materialize. We call this problem the data cube schema design problem. In this paper we show that the problem of finding an optimal data cube schema for an OLAP system with limited memory is NP-hard. As a more computationally efficient alternative, we propose a greedy approximation algorithm cMP and its variants. Algorithm cMP consists of two phases. In the first phase, an initial schema consisting of all the cubes required to efficiently answer the user queries is formed. In the second phase, cubes in the initial schema are selectively merged to satisfy the memory constraint. We show that cMP is very effective in prunning the search space for an optimal schema. This leads to a highly efficient algorithm. We report

Multi-dimensional, inter-transaction association rules extend the traditional association rules to describe more general associations among items with multiple properties cross transactions. “After McDonald and Burger King open branches, KFC will open a branch two months later and one mile away” is an example of such rules. Since the number of potential inter-transaction association rules tends to be extremely large, mining inter-transaction associations poses more challenges on efficient processing than mining intra-transaction associations. In order to make such association mining truly practical and computationally tractable, in this study, we present a template model to help users declare the interesting inter-transaction associations to be mined. With the guidance of templates, several optimization techniques are devised to speed up the discovery of inter-transaction association rules. We show, through a series of experiments, that these optimization techniques can yield significant performance benefits.

Finding patterns from data sets is a fundamental task of data mining. If we categorize all patterns into strong, weak, and random, conventional data mining techniques are designed only to find strong patterns, which hold for numerous objects and are usually consistent with the expectations of experts. We address the problem of finding weak patterns (i.e., reliable exceptions) from databases. They are valid for a small number of objects. A simple approach is proposed which uses deviation analysis to identify interesting exceptions and explore reliable ones. It is also flexible in handling both subjective and objective exceptions. We demonstrate the effectiveness of the proposed approach through a benchmark data set.

This paper discusses our experiences of designing and implementing a pure Java database proxy server with a JDBC compatible driver for intranet/Internet database application development. In particular, we present a shared database connection strategy and flexible caching facilities to address the scalability problem. Web clients with the same access privilege can maintain their logical connections with shared physical connections to the database. Thus, not only a large number of users can be entertained by limited physical resource, the connection cost is also not indulged for each individual client. Web clients can also express their cache requirements explicitly in the JDBC protocol so that a large number of clients can be served with improved response time. The effectiveness of such strategies is demonstrated through a set of experiments.

A datacube on n attributes requires the computation of an aggregation function over all groups generated by 2/sup n/ interelated GROUP-BYs. Even n is not very large, and the computation could be very expensive if the database involved is large. Although a number of algorithms with various optimization techniques have been proposed, accurate estimation of memory requirement and efficient use of the available memory remain difficult issues. The difficulty of estimating memory requirement comes from data skews. We present a novel hash based approach for datacube computation. The approach effectively uses the available memory to maintain a minimum number of hash tables required for computing related cuboids and manages memory dynamically by shifting memory pages among hash tables. Therefore, no priori memory requirement estimation is necessary and all memory available can be fully utilized.

Most of the previous studies on mining association rules are on mining intro-transaction associations, i.e., the associations among items within the same transaction, where the notion of the transaction could be the items bought by the same customer, the events happened on the same day, etc.In this study, we break the barrier of transactions and extend the scope of mining association rules from traditional intratransaction associations to inter-transaction associations.Mining inter-transaction associations poses more challenges on efficient processing than mining intra-transaction associations because the number of potential association rules becomes extremely large after the boundary of transactions is broken.In this study, we introduce the notion of inter-transaction association rule, define its measurements: support and confidence, and develop an efficient algorithm, FITI (an acronym for "First Intra Then Inter"), for mining inter-transaction associations.We compare FITI with EH-Apriori, the best algorithm in our previous proposal, and demonstrate a substantial performance gain of FITI over EH- Apriori.

Article BROOM: buffer replacement using online optimization by mining Share on Authors: Anthony K. H. Tung Dept. of Computer Science, National Univ. of Singapore Dept. of Computer Science, National Univ. of SingaporeView Profile , Y. C. Tay Dept. of Mathematics, National Univ. of Singapore Dept. of Mathematics, National Univ. of SingaporeView Profile , Hongjun Lu Dept. of Computer Science, National Univ. of Singapore Dept. of Computer Science, National Univ. of SingaporeView Profile Authors Info & Claims CIKM '98: Proceedings of the seventh international conference on Information and knowledge managementNovember 1998 Pages 185–192https://doi.org/10.1145/288627.288656Online:01 November 1998Publication History 5citation261DownloadsMetricsTotal Citations5Total Downloads261Last 12 Months5Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The problem of buffer management in database systems is concerned with efficient main memory allocation and replacement for answering database queries. The goal is to reduce disk operations and enhance the system throughput by utilizing a dedicated buffer pool for caching database pages. This paper provides an in-depth study of current buffer management techniques for database systems. Through surveying existing work, we propose a data mining based approach to buffer management. Different from previous approaches where limited knowledge of user access patterns is used, the proposed approach discovers knowledge from database access sequences and uses it to guide buffer management. To assess the performance of the proposed approach, we construct a simulation model and conduct a series of experiments. The results show that with the help of the discovered knowledge, the buffer hit ratio can be improved significantly.

We present a storage management system that has the ability to adapt to the data access characteristics of the application that uses it based on collection and analysis of runtime statistics. This feature is especially useful in the storage management layer of database systems, where applications exhibit relatively predictable access patterns. Adaptive reorganization is performed by the storage management system in a manner that optimizes the access patterns of the system for which it is used. We enhance the log-structured storage system that naturally caters for write optimization, with the addition of a statistics collection mechanism to determine data access patterns of applications. The storage system can serve as a testbed for a variety of statistics analysis and clustering mechanisms. Higher level application-specific data clustering mechanisms can be used to override the storage system's low-level clustering mechanisms. In addition, the analysis techniques and reorganization scheme can be used in other storage systems. Performance results from our prototype show potential response time speedups of up to 83 percent over the basic log-structured file system in the best case, using a combination of storage reorganization and prefetching.

We present a storage management system that has the ability to adapt to the data access characteristics of the application that uses it, based on collection and analysis of runtime statistics. Adaptive reorganization is performed by the storage management system in a manner that optimizes the access patterns of the system for which it is used. Application-specific data clustering mechanisms can also be specified to override the default mechanisms provided by our prototype. Performance results from our prototype show potential read time speedups of over 80% in the best case, using a combination of storage reorganization and prefetching.

Classification is one of the data mining problems receiving great attention recently in the database community. The paper presents an approach to discover symbolic classification rules using neural networks. Neural networks have not been thought suited for data mining because how the classifications were made is not explicitly stated as symbolic rules that are suitable for verification or interpretation by humans. With the proposed approach, concise symbolic rules with high accuracy can be extracted from a neural network. The network is first trained to achieve the required accuracy rate. Redundant connections of the network are then removed by a network pruning algorithm. The activation values of the hidden units in the network are analyzed, and classification rules are generated using the result of this analysis. The effectiveness of the proposed approach is clearly demonstrated by the experimental results on a set of standard data mining test problems.

The article proposes two ways to improve the sort merge based band join algorithm. The techniques proposed address issues that have not been previously discussed: to choose a right relation as the inner relation to achieve better performance and to optimally allocate and adjust buffer allocations to make the algorithms robust to data skew and estimation errors.>

To support temporal operators efficiently, indexing based on temporal attributes must be supported. The authors propose a dynamic and efficient index scheme called the time polygon (TP-index) for temporal databases. In the scheme, temporal data are mapped into a two-dimensional temporal space, where the data can be clustered based on time. The date space is then partitioned into time polygons where each polygon corresponds to a data page. The time polygon directory can be organized as a hierarchical index. The index handles long duration temporal data elegantly and efficiently. The performance analysis indicates that the time polygon index is efficient both in storage utilization and query search.>

Looks at how to effectively exploit pipelining for multi-join queries in shared-nothing systems. A multi-join query can be processed using an iterative approach. In each iteration, several relations are selected and are joined in a pipelined fashion. However, algorithms that are based on this approach have traditionally assumed that the relations are uniformly distributed or only slightly skewed. When this assumption is relaxed, i.e. when the data is skewed, some nodes may be assigned a larger amount of data than can fit into their memories. As such, pipelining cannot be effectively exploited, and performance may degenerate drastically. We propose four skew handling techniques to deal with data skew for multi-join queries. The results of a performance study show that a hybrid technique is superior in most cases.

This paper explores the pipeline processing of multi-way join queries using hash-based join algorithm. The basic approach that has been adopted in the literature is: "split" the join tree into segments and for each segment, split each base rela tion into buckets and pipeline the segment using the buckets. The effectiveness of the approach depends on two closely related factors - the number of buckets and the number of segments. We investigate how varying these factors may affect the system performance. Two greedy heuristics, proposed to generate query evalua tion plans with "optimal" pipeline length, are shown to perform best in most cases.

The support of the superclass-subclass concept in object-oriented databases (OODB) makes an instance of a subclass also an instance of its superclass. As a result, the access scope of a query against a class in general includes the access scope of all its subclasses, unless specified otherwise. To support the superclass-subclass relationship efficiently, the index must achieve two objectives. First, the index must support efficient retrieval of instances from a single class. Second, it must also support efficient retrieval of instances from classes in a hierarchy of classes. In this paper, we propose a new index called the H-tree that supports efficient retrieval of instances of a single class as well as retrieval of instances of a class and its subclasses. The unique feature of H-trees is that they capture the superclass-subclass relationships. A performance analysis is conducted and both experimental and analytical results indicate that the H-tree is an efficient indexing structure for OODB.

An efficient semantic query optimization algorithm is proposed, in which all possible transformations are tentatively applied to the query. Instead of physically modifying the query, the transformation process classifies the predicates into imperative, optional or redundant. At the end of the transformation process, all the imperative predicates are retained while the redundant predicates are eliminated. Optional predicates are retrained or discarded based on the estimated cost/benefit of retaining them. The issue of the grouping of semantic constraints to reduce the overhead of retrieving constraints and checking whether each constraint is relevant to the current query is also addressed. Based on the proposed algorithm, a prototype semantic query optimizer has been built and preliminary experiments show that the optimizer performs well for large databases.>

The authors investigated the effectiveness of load balancing when the buffer space requirement and the availability of buffers at different database sites are considered. New load-balancing algorithms are proposed and a simulation study was conducted. The results indicate that, by considering buffer space as a major system resource, load balancing is still an effective approach to improving system performance in locally distributed database systems. The results also indicate that no complicated information about buffer space requirement and availability is necessary to achieve satisfactory performance improvements.>

This paper presents our experience in designing and implementing a data/knowledge base management testbed. The testbed consists of two layers, the knowledge manager and the database management system, with the former at the top. The testbed is based on the logic programming paradigm, wherein data, knowledge, and queries are all expressed as Horn clauses. The knowledge manager compiles pure, function-free Horn clause queries into embedded-SQL programs, which are executed by the database management system to produce the query results. The database management system is a commercial relational database system and provides storage for both rules and facts. First, the testbed architecture and major data structures and algorithms are described. Then, several preliminary tests conducted using the current version of the testbed and the conclusions from the test results are presented. The principal contributions of this work have been to unify various concepts, both previously published and new ones we developed, into a real system and to present several insights into data/knowledge base management system design gleaned from the test results and our design and implementation experience.

Recursive query evaluation is a capability of deductively-augmented database systems that conventional database systems do not support well, if at all. Many recursive queries involve computation of the transitive closure of a relation. Previously published algorithms for transitive closure are iterative in nature, performing repeated joins, unions, and differences until convergence is obtained. In this paper, we present an adaptation of Warren's algorithm for computing the transitive closure of a relation. Warren's algorithm was originally designed for a bit matrix representation of a binary relation; we have adapted it for use with a binary relation represented as a set of tuples, as in a relational database management system. This adapted algorithm computes the transitive closure in two passes over the relation. We analyze the performance of this algorithm, and compare it to the performance of two algorithms based on relational algebra: an iterative algorithm, and an improved version of the iterative algorithm that eliminates unnecessary I/O at the expense of more computation. We evaluate the performance of the algorithms for different source relation sizes, available memory sizes, join selectivities, and maximum path length. Our results show that no algorithm has uniformly superior performance; the adaptation of Warren's algorithm is superior when the source and result relations are not too much larger than main memory. We conclude that in future systems with large main memory, Warren's algorithm generally performs best, and thus should be implemented with the option of switching to an iterative algorithm when the source or result sizes are very large.

The join operation is the most costly operation in relational database management systems. Distributed and parallel processing can effectively speed up the join operation. In this paper, we describe a number of highly parallel and pipelined multiprocessor join algorithms using sort-merge and hashing techniques. Among them, two algorithms are parallel and pipelined versions of traditional sort-merge join methods, two algorithms use both hashing and sort-merge techniques, and another two are variations of the hybrid hash join algorithms. The performance of those algorithms is evaluated analytically against a generic database machine architecture. The methodology used in the design and evaluation of these algorithms is also discussed.

The processing of recursive queries in relational database systems poses a great challenge in research on expert database systems. This paper uses both analytical and experimental methods to investigate the performance of several different algorithms in processing a recursive query in first-order recursive databases. The analytical method estimated the I/O and CPU cost and the storage needed in processing recursive queries. The experimental tests were performed on a synthetic relational database built on top of WISS (Wisconsin Storage System) on VAX 11/750. Both analytical and experimental results indicate that for efficient recursive database processing it is important to apply the following heuristics: performing selection first, making use of wavefront relations, and grouping those joins which reduce the size of intermediate results. The termination conditions for recursive queries are also discussed in the paper.

Most previous work on query optimization in distributed database systems has focused on finding optimal or near-optimal processing plans based solely on static system characteristics, and few researchers have addressed the problem of copy selection when data is replicated. This paper describes a new approach to query processing for locally distributed database systems. Our approach uses load information to select the processing site(s) for a query, dynamically choosing from among those sites that have copies of relations referenced by the query. Query compilation is used to produce a statically-optimized logical plan for the query, and then a dynamic optimization phase converts this logical plan into an executable physical plan at runtime. This paper motivates the separation of static and dynamic optimization, presents algorithms for the various phases of the optimization process, and describes a simulation study that was undertaken to investigate the performance of this approach. Our simulation results indicate that load-balanced query processing can provide improvements in both query response times and overall system throughput as compared to schemes where execution sites are either statistically or randomly selected.