Abstract

Fuzzy association rules use fuzzy logic to convert numerical attributes to fuzzy attributes, like ldquoIncome = Highrdquo, thus maintaining the integrity of information conveyed by such numerical attributes. On the other hand, crisp association rules use sharp partitioning to transform numerical attributes to binary ones like ldquoIncome = [100 K and above]rdquo, and can potentially introduce loss of information due to these sharp ranges. Fuzzy A priori and its different variations are the only popular fuzzy association rule mining (ARM) algorithms available today. Like the crisp version of Apriori, fuzzy A priori is a very slow and inefficient algorithm for very large datasets (in the order of millions of transactions). Hence, we have come up with a new fuzzy ARM algorithm meant for fast and efficient performance on very large datasets. As compared to fuzzy A priori, our algorithm is 8-19 times faster for the very large standard real-life dataset we have used for testing with various mining workloads, both typical and extreme ones. A novel combination of features like two-phased multiple-partition tidlist-style processing, byte-vector representation of tidlists, and fast compression of tidlists contribute a lot to the efficiency in performance. In addition, unlike most two-phased ARM algorithms, the second phase is totally different from the first one in the method of processing (individual itemset processing as opposed to simultaneous itemset processing at each k-level), and is also many times faster. Our algorithm also includes an effective preprocessing technique for converting a crisp dataset to a fuzzy dataset

Abstract

We describe improved mechanisms to accurately clas-sify days when news for topics receive unexpectedly high amount of coverage. We further investigate the factors which influence this classification using ‘Pres-idential Elections’ as the topic of interest. This help sin bringing out useful trends and relations between days with hot topics by varying variables like history window size,van-ratio etc. We also propose a statisti-cal scheme to approximate major events related to the topic. We then try to approximate the chain of event srelated to the major events. This can support a news alert service and also serve the purpose of automati-cally tracking news which follow up major events.

Abstract

In this paper, we present RBNBC, a Repeat Based Naive Bayes Classifier of bio-sequences that uses maximal fre-quent subsequences as features. RBNBC’s design is based on generic ideas that can apply to other domains where the data is organized as collections of sequences. Specifically,RBNBC uses a novel formulation of Naive Bayes that incor-porates repeated occurrences of subsequences within each sequence. Our extensive experiments on two collections of protein families show that it performs as well as existing state-of-the-art probabilistic classifiers for bio-sequences.This is surprising as it is a pure data mining based generic classifier that does not require domain-specific background knowledge. We note that domain-specific ideas could fur-ther increase its performance.

Abstract

An important problem in biological data analysis is to pre-dict the family of a newly discovered sequence like a pro-tein or DNA sequence, using the collection of available se-quences. In this paper we tackle this problem and presentREBMEC, a Repeat Based Maximum Entropy Classifier of biological sequences. Maximum entropy models are known to be theoretically robust and yield high accuracy,but are slow. This makes them useful as benchmarks to evaluate other classifiers. Specifically, REBMEC is based on the classical Generalized Iterative Scaling (GIS) al-gorithm and incorporates repeated occurrences of subse-quences within each sequence. REBMEC uses maximal frequent subsequences as features but can support other types of features as well. Our extensive experiments on two collections of protein families show that REBMEC performs as well as existing state-of-the-art probabilistic classifiers for biological sequences without using domain-specific background knowledge such as multiple align-ment, data transformation and complex feature extraction methods. The design of REBMEC is based on genericideas that can apply to other domains where data is orga-nized as collections of sequences.

Abstract

The problem of search and retrieval of images using relevance feedback has attracted tremendous attention in recent years from the research community. A real-world-deployable interactive image retrieval system must (1) be accurate, (2) require minimal user-interaction, (3) be efficient, (4) be scalable to large collections (millions) of images, and (5) support multi-user sessions. For good accuracy, we need effective methods for learning the relevance of image features based on user feedback, both within a user-session and across sessions. Efficiency and scalability require a good index structure for retrieving results. The index structure must allow for the relevance of image features to continually change with fresh queries and user-feedback. The state-of-the-art methods available today each address only a subset of these issues. In this paper, we build a complete system FISH - Fast Image Search in Huge databases. In FISH, we integrate selected techniques available in the literature, while adding a few of our own. We perform extensive experiments on real datasets to demonstrate the accuracy, efficiency and scalability of FISH. Our results show that the system can easily scale to millions of images while maintaining interactive response time.

Abstract

In this paper we consider the problem of extracting the spe-cial properties of any given record in a dataset. We are interested in determining what makes a given record unique or different from the ma-jority of the records in a dataset. In the real world, records typically represent objects or people and it is often worthwhile to know what spe-cial properties are present in each object or person, so that we can make the best use of them. This problem has not been considered earlier inthe research literature. We approach this problem using ideas from clus-tering, attribute oriented induction (AOI) and frequent itemset mining.Most of the time consuming work is done in a preprocessing stage and the online computation of the uniqueness of a given record is instantaneous

Abstract

In this paper, we consider the problem of finding the k most similar objects given a query object, in large multimedia datasets. We focus on scenarios where the similarity measure itself is not fixed, but is continuously being refined with user feedback. Conventional database techniques for efficient similarity search are not effective in this environment as they take a specific similarity/distance measure as input and build index structures tuned for that measure. Our approach works effectively in this environment as validated by the experimental study where we evaluate it over a wide range of datasets. The experiments show it to be efficient and scalable. In fact, on all our datasets, the response times were within a few seconds, making our approach suitable for interactive applications.

Abstract

No Results Found

Abstract

Joins on set-valued attributes (set joins) have numerous database applications. In this paper we propose PRETTI (PREfix Tree based seT joIn) – a suite of set join algorithms for containment, overlap and equality join predicates.Our algorithms use prefix trees and inverted indices. These structures are constructed on-the-fly if they are not already precomputed. This feature makes ouralgorithms usable for relations without indices and when joining intermediate results during join queries with more than two relations. Another feature of ouralgorithms is that results are output continuously during their execution and notjust at the end. Experiments on real life datasets show that the total executiontime of our algorithms is significantly less than that of previous approaches, even when the indices required by our algorithms are not precomputed.

Abstract

In this paper, we first focus our attention on the question of how much space remains for performance improvement over current association rule mining algorithms. Our strategy is to compare their performance against an “Oracle algorithm” that knows in advance the identities of all frequent itemsets in the database and only needs to gather their actual supports to complete the mining process. Our experimental results show that current mining algorithms do not perform uniformly well with respect to the Oracle for all database characteristics and support thresholds. In many cases there is a substantial gap between the Oracle’s performance and that of the current mining algorithms. Second, we present a new mining algorithm, called ARMOR, that is constructed by making minimal changes to the Oracle algorithm. ARMOR consistently performs within a factor of two of the Oracle on both real and synthetic datasets over practical ranges of support specifications.