Browsing by Author "Guralnik, Valerie"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    A Scalable Algorithm for Clustering Sequential Data
    (2001-08-16) Guralnik, Valerie; Karypis, George
    In recent years, we have seen an enormous growth in the amount of available commercial and scientific data. Data from domains such as protein sequences, retail transactions,intrusion detection, and web-logs have an inherent sequential nature. Clustering of such data sets is useful for various purposes. For example, clustering of sequences from commercial data sets may help marketer identify different customer groups based upon their purchasing patterns. Grouping protein sequences that share similar structure helps in identifying sequences with similar functionality. Over the years, many methods have been developed for clustering objects according to their similarity. However these methods tend to have a computational complexity that is at least quadratic on the number of sequences, as they need to compute the pairwisesimilarity between all the sequences. In this paper we present an entirely different approach to sequence clustering that does not require an all-against-all analysis and uses a near-linear complexity $K$-means based clustering algorithm. Our experiments using data sets derived from sequences of purchasing transactions and protein sequences show that this approach is scalable and leads to reasonably good clusters.
  • Thumbnail Image
    Item
    Dynamic Load Balancing Algorithms for Sequence Mining
    (2001-05-08) Guralnik, Valerie; Karypis, George
    Discovery of sequential patterns is becoming increasingly useful and essential in many scientific and commercial domains. Enormous sizes of available datasets and possibly large number of mined patterns demand efficient and scalable algorithms. In this paper we present a parallel formulation of a serial sequential pattern discovery algorithm based on tree projection that uses a novel dynamic load balancing algorithm which is well suited for distributed memory parallel computers. Our experimental evaluation on a 32 processor IBM SP show that this algorithms are capable of achieving good speedups, substantially reducing the amount of the required work to find sequential patterns in large databases.
  • Thumbnail Image
    Item
    Parallel Formulations of Tree-Projection Based Sequence Mining Algorithms
    (2003-01-20) Guralnik, Valerie; Karypis, George
    Discovery of sequential patterns is becoming increasingly useful and essential in many scientific and commercialdomains. Enormous sizes of available datasets and possibly large number of mined patterns demand efficient,scalable, and parallel algorithms. Even though a number of algorithms have been developed to efficiently parallelizefrequent pattern discovery algorithms that are based on thecandidate-generation-and-counting framework, theproblem of parallelizing the more efficient projection-based algorithms has received relatively little attention and existing parallel formulations have been targeted only toward shared-memory architectures. The irregular and unstructured nature of the task-graph generated by these algorithms and the fact that these tasks operate on overlapping sub-databases makes it challenging to efficiently parallelize these algorithms on scalable distributed-memory parallel computing architectures. In this paper we present and study a variety of distributed-memory parallel algorithms for a tree-projection-based frequent sequence discovery algorithm that are able to minimize the various overheads associated with load imbalance, database overlap, and interprocessor communication. Our experimental evaluation on a32 processor IBM SP show that these algorithms are capable of achieving good speedups, substantially reducing theamount of the required work to find sequential patterns in large databases.
  • Thumbnail Image
    Item
    Parallel Tree Projection Algorithm for Sequence Mining
    (2001-03-29) Guralnik, Valerie; Garg, Nivea; Karypis, George
    Discovery of sequential patterns is becoming increasingly useful and essential in many scientific and commercial domains. Enormous sizes of available datasets and possibly large number of mined patterns demand efficient and scalable algorithms. In this paper we present two parallel formulations of a serial sequential pattern discovery algorithm based on tree projection that are well suited for distributed memory parallel computers. Our experimental evaluation on a 32 processor IBM SP show that these algorithms are capable of achieving good speedups, substantially reducing the amount of the required work to find sequential patterns in large databases.