The Experts below are selected from a list of 3828 Experts worldwide ranked by ideXlab platform

Huang Jinglian - One of the best experts on this subject based on the ideXlab platform.

  • efficient frequent item set mining algorithm based on Prefix Tree
    Computer Engineering, 2010
    Co-Authors: Huang Jinglian
    Abstract:

    Aiming at the problem of low time and space efficiencies for frequent item sets mining,an efficient frequent item sets mining algorithm based on Prefix Tree is proposed.To ensure the consistence of transactions sequence,the proposed algorithm pre-processes transaction sets to create index table and assign index identity.It creates compact Prefix Tree with the index information,and mines frequent item sets by bottom-to-up and projection methods.Experimental results show this algorithm has higher mining efficiency and expends less space.

Raj P Gopalan - One of the best experts on this subject based on the ideXlab platform.

  • ct itl efficient frequent item set mining using a compressed Prefix Tree with pattern growth
    Australasian Database Conference, 2003
    Co-Authors: Yudho Giri Sucahyo, Raj P Gopalan
    Abstract:

    Discovering association rules that identify relationships among sets of items is an important problem in data mining. Finding frequent item sets is computationally the most expensive step in association rule discovery and therefore it has attracted significant research attention. In this paper, we present a more efficient algorithm for mining complete sets of frequent item sets. In designing our algorithm, we have modified and synthesized a number of useful ideas that include Prefix Trees, pattern-growth, and tid-intersection. We extend the Prefix-Tree structure to store transaction groups and propose a new method to compress the Tree. Transaction-id intersection is modified to include the count of transaction groups. We present performance comparisons of our algorithm against the fastest Apriori algorithm, Eclat and the latest extension of FP-Growth known as OpportuneProject. To study the trade-offs in compressing transactions in the Prefix Tree, we compare the performance of our algorithm with and without using the modified compressed Prefix Tree. We have tested all the algorithms using several widely used test datasets. The performance study shows that the new algorithm significantly reduces the processing time for mining frequent item sets from dense data sets that contain relatively long patterns. We discuss the performance results in detail and also the strengths and limitations of our algorithm.

  • Treeitl mine mining frequent itemsets using pattern growth tid intersection and Prefix Tree
    Australian Joint Conference on Artificial Intelligence, 2002
    Co-Authors: Raj P Gopalan, Yudho Giri Sucahyo
    Abstract:

    An important problem in data mining is the discovery of association rules that identify relationships among sets of items. Finding frequent itemsets is computationally the most expensive step in association rules mining, and so most of the research attention has been focused on it. In this paper, we present a more efficient algorithm for mining frequent itemsets. In designing our algorithm, we have combined the ideas of pattern-growth, tid-intersection and Prefix Trees, with significant modifications. We present performance comparisons of our algorithm against the fastest Apriori algorithm, and the recently developed H-Mine algorithm. We have tested all the algorithms using several widely used test datasets. The performance results indicate that our algorithm significantly reduces the processing time for mining frequent itemsets in dense data sets that contain relatively long patterns.

Young Koo Lee - One of the best experts on this subject based on the ideXlab platform.

  • efficient single pass frequent pattern mining using a Prefix Tree
    Information Sciences, 2009
    Co-Authors: Syed Khairuzzaman Tanbeer, Chowdhury Farhan Ahmed, Byeong-soo Jeong, Young Koo Lee
    Abstract:

    The FP-growth algorithm using the FP-Tree has been widely studied for frequent pattern mining because it can dramatically improve performance compared to the candidate generation-and-test paradigm of Apriori. However, it still requires two database scans, which are not consistent with efficient data stream processing. In this paper, we present a novel Tree structure, called CP-Tree (compact pattern Tree), that captures database information with one scan (insertion phase) and provides the same mining performance as the FP-growth method (restructuring phase). The CP-Tree introduces the concept of dynamic Tree restructuring to produce a highly compact frequency-descending Tree structure at runtime. An efficient Tree restructuring method, called the branch sorting method, that restructures a Prefix-Tree branch-by-branch, is also proposed in this paper. Moreover, the CP-Tree provides full functionality for interactive and incremental mining. Extensive experimental results show that the CP-Tree is efficient for frequent pattern mining, interactive, and incremental mining with a single database scan.

  • Efficient frequent pattern mining over data streams
    Proceeding of the 17th ACM conference on Information and knowledge mining - CIKM '08, 2008
    Co-Authors: Syed Khairuzzaman Tanbeer, Chowdhury Farhan Ahmed, Byeong-soo Jeong, Young Koo Lee
    Abstract:

    This paper proposes a Prefix-Tree structure, called CPS-Tree (Compact Pattern Stream Tree) that efficiently discovers the exact set of recent frequent patterns from high-speed data stream. The CPS-Tree introduces the concept of dynamic Tree restructuring technique in handling stream data that allows it to achieve highly compact frequency-descending Tree structure at runtime and facilitates an efficient FP-growth-based [1] mining technique.

Keun Ho Ryu - One of the best experts on this subject based on the ideXlab platform.

  • efficient frequent pattern mining based on linear Prefix Tree
    Knowledge Based Systems, 2014
    Co-Authors: Gwangbum Pyun, Unil Yun, Keun Ho Ryu
    Abstract:

    Outstanding frequent pattern mining guarantees both fast runtime and low memory usage with respect to various data with different types and sizes. However, it is hard to improve the two elements since runtime is inversely proportional to memory usage in general. Researchers have made efforts to overcome the problem and have proposed mining methods which can improve both through various approaches. Many of state-of-the-art mining algorithms use Tree structures, and they create nodes independently and connect them as pointers when constructing their own Trees. Accordingly, the methods have pointers for each node in the Trees, which is an inefficient way since they should manage and maintain numerous pointers. In this paper, we propose a novel Tree structure to solve the limitation. Our new structure, LP-Tree (Linear Prefix - Tree) is composed of array forms and minimizes pointers between nodes. In addition, LP-Tree uses minimum information required in mining process and linearly accesses corresponding nodes. We also suggest an algorithm applying LP-Tree to the mining process. The algorithm is evaluated through various experiments, and the experimental results show that our approach outperforms previous algorithms in term of the runtime, memory, and scalability.

  • An efficient mining algorithm for maximal weighted frequent patterns in transactional databases
    Knowledge-Based Systems, 2012
    Co-Authors: Unil Yun, Hyeon-il Shin, Keun Ho Ryu, Eunchul Yoon
    Abstract:

    In the field of data mining, there have been many studies on mining frequent patterns due to its broad applications in mining association rules, correlations, sequential patterns, constraint-based frequent patterns, graph patterns, emerging patterns, and many other data mining tasks. We present a new algorithm for mining maximal weighted frequent patterns from a transactional database. Our mining paradigm prunes unimportant patterns and reduces the size of the search space. However, maintaining the anti-monotone property without loss of information should be considered, and thus our algorithm prunes weighted infrequent patterns and uses a Prefix-Tree with weight-descending order. In comparison, a previous algorithm, MAFIA, exponentially scales to the longest pattern length. Our algorithm outperformed MAFIA in a thorough experimental analysis on real data. In addition, our algorithm is more efficient and scalable.

Cedric Tedeschi - One of the best experts on this subject based on the ideXlab platform.

  • self stabilizing Prefix Tree based overlay networks
    International Journal of Foundations of Computer Science, 2016
    Co-Authors: Eddy Caron, Ajoy K Datta, Franck Petit, Cedric Tedeschi
    Abstract:

    In this paper, we focus on making tries self-stabilizing over such platforms, and propose a self-stabilizing maintenance algorithm for a Prefix Tree using a message passing model. The proof of self-stabilization is provided, and simulation results are given, to better capture its performances. Still based on simulations, we provide evidences that the protocol, beyond its capacity to repair the structure, can significantly improve the system’s availability, even when the system is not yet stabilized.

  • a practical study of self stabilization for Prefix Tree based overlay networks
    International Conference on High Performance Computing and Simulation, 2010
    Co-Authors: V Acretoaie, Eddy Caron, Cedric Tedeschi
    Abstract:

    Service discovery is crucial in the development of fully decentralized computational grids. Among the significant amount of work produced by the convergence of peer- to-peer (P2P) systems and grids, a new kind of overlay networks, based on Prefix Trees (a.k.a., tries), has emerged. In particular, the Distributed Lexicographic Placement Table (DLPT) approach is a decentralized and dynamic service discovery service. Fault-tolerance within the DLPT approach is achieved through best-effort policies relying on formal self-stabilization results. Self-stabilization means that the Tree can become transiently inconsistent, but is guaranteed to autonomously converge to a correct topology after arbitrary crashes, in a finite time. However, during convergence, the Tree may not be able to process queries correctly. In this paper, we present some simula- tion results having several objectives. First, we investigate the interest of self-stabilization for such architectures. Second, we explore, still based on simulation, a simple Time-To-Live policy to avoid useless processing during convergence time.

  • snap stabilizing Prefix Tree for peer to peer systems
    Parallel Processing Letters, 2010
    Co-Authors: Eddy Caron, Franck Petit, Frederic Desprez, Cedric Tedeschi
    Abstract:

    Several factors still hinder the deployment of computational grids over large scale platforms. Among them, the resource discovery is one crucial issue. New approaches, based on peer-to-peer technologies, tackle this issue. Because they efficiently allow range queries, Tries (a.k.a., Prefix Trees) appear to be among promising ways in the design of distributed data structures indexing resources. Despite their lack of robustness in dynamic settings, trie-structured approaches outperform other peer-to-peer fashioned technologies by efficiently supporting range queries. Within recent trie-based approaches, the fault-tolerance is handled by preventive mechanisms, intensively using replication. However, replication can be very costly in terms of computing and storage resources and does not ensure the recovery of the system after arbitrary failures. Self-stabilization is an efficient approach in the design of reliable solutions for dynamic systems. It ensures a system to converge to its intended behavior, regardless of its initial state, in a finite time. A snap-stabilizing algorithm guarantees that it always behaves according to its specification, once the protocol is launched. In this paper, we provide the first snap-stabilizing protocol for trie construction. We design particular tries called Proper Greatest Common Prefix (PGCP) Tree. The proposed algorithm arranges the n label values stored in the Tree, in average, in O(h + h′) rounds, where h and h′ are the initial and final heights of the Tree, respectively. In the worst case, the algorithm requires an O(n) extra space on each node, O(n) rounds and O(n2) actions. However, simulations allow to state that this worst case is far from being reached and to confirm the average complexities, showing the practical efficiency of this protocol.

  • Peer-to-Peer Prefix Tree for Large Scale Service Discovery
    2008
    Co-Authors: Cedric Tedeschi
    Abstract:

    The problem studied in this thesis is the service discovery on platforms distributed at large scale, a service being a computing service (software components, scientific computing libraries, or binaries) offered with some characteristics and a performance level related to the hardware supporting it. Traditional approaches, designed for reliable and small scale environments, rely upon centralized solutions, unable to scale well in geographically distributed unreliable platforms. Our contribution centers around three main parts. 1) We propose a novel approach called DLPT (Distributed Lexicographic Placement Table), whose design is inspired by peer-to-peer systems. It calls upon an indexing system structured as a Prefix Tree. This structure supports multi-attribute range queries. 2) We study the mapping of nodes of this Tree onto heterogeneous processors of the dynamic underlying network. We propose and adapt some load balancing heuristics for this kind of architectures. 3) Our architecture, targeted for platforms within which processors are unreliable and constantly joining and leaving the network, requires fault-tolerance mechanisms. Replication, usually used, is costly and unable to manage transient faults. We propose alternative best-effort mechanisms based on the self-stabilization theory for the construction and maintenance of Prefix Trees in a peer-to-peer environment. Among the mechanisms provided, one is proven to be snap-stabilizing. This means that the Tree is rebuilt in an optimal time after an arbitrary number of faults. This approach is written in a coarse grain communication model and assumes several restrictions on initial topology handled, making it hard to implement on real platforms. To address these drawbacks, another self-stabilizing protocol is given for actual message-passing environments. Finally, we present a software prototype of this architecture and its first promising experiments on the Grid'5000 platform.

  • snap stabilizing Prefix Tree for peer to peer systems
    International Conference on Stabilization Safety and Security of Distributed Systems, 2007
    Co-Authors: Eddy Caron, Franck Petit, Frederic Desprez, Cedric Tedeschi
    Abstract:

    Resource Discovery is a crucial issue in the deployment of computational grids over large scale peer-to-peer platforms. Because they efficiently allow range queries, Tries (a.k.a., Prefix Trees) appear to be among promising ways in the design of distributed data structures indexing resources. Self-stabilization is an efficient approach in the design of reliable solutions for dynamic systems. A snap-stabilizing algorithm guarantees that it always behaves according to its specification. In other words, a snap-stabilizing algorithm is also a self-stabilizing algorithm which stabilizes in 0 steps. In this paper, we provide the first snap-stabilizing protocol for trie construction. We design particular tries called Proper Greatest Common Prefix (PGCP) Tree. The proposed algorithm arranges the n label values stored in the Tree, in average, in O(h + h′) rounds, where h and h′ are the initial and final heights of the Tree, respectively. In the worst case, the algorithm requires an O(n) extra space on each node, O(n) rounds and O(n2) actions. However, simulations show that, using relevant data sets, this worst case is far from being reached and confirm the average complexities, making this algorithm efficient in practice.