Exploring the Trie of Rules: a fast data structure for the representation of association rules

• URL: http://arxiv.org/abs/2310.17355v2
• Date: Tue, 21 Nov 2023 13:27:01 GMT
• Title: Exploring the Trie of Rules: a fast data structure for the representation of association rules
• Authors: Mikhail Kudriavtsev, Marija Bezbradica, Andrew McCarren
• Abstract summary: Association rule mining techniques can generate a large volume of sequential data when implemented on transactional databases. This paper proposes a novel data structure, called the Trie of rules, for storing a ruleset that is generated by association rule mining. It compresses a ruleset with almost no data loss and benefits in terms of time for basic operations such as searching for a specific rule and sorting.
• Score: 0.3683202928838613
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Association rule mining techniques can generate a large volume of sequential data when implemented on transactional databases. Extracting insights from a large set of association rules has been found to be a challenging process. When examining a ruleset, the fundamental question is how to summarise and represent meaningful mined knowledge efficiently. Many algorithms and strategies have been developed to address issue of knowledge extraction; however, the effectiveness of this process can be limited by the data structures. A better data structure can sufficiently affect the speed of the knowledge extraction process. This paper proposes a novel data structure, called the Trie of rules, for storing a ruleset that is generated by association rule mining. The resulting data structure is a prefix-tree graph structure made of pre-mined rules. This graph stores the rules as paths within the prefix-tree in a way that similar rules overlay each other. Each node in the tree represents a rule where a consequent is this node, and an antecedent is a path from this node to the root of the tree. The evaluation showed that the proposed representation technique is promising. It compresses a ruleset with almost no data loss and benefits in terms of time for basic operations such as searching for a specific rule and sorting, which is the base for many knowledge discovery methods. Moreover, our method demonstrated a significant improvement in traversing time, achieving an 8-fold increase compared to traditional data structures.

Related papers

• Mining Path Association Rules in Large Property Graphs (with Appendix) [15.11494401922146]
  Association rule mining successfully discovers regular patterns in item sets and substructures. We introduce the problem of path association rule mining (PARM) We develop an efficient and scalable algorithm PIONEER that exploits an anti-monotonicity property to effectively prune the search space.
  arXiv  Detail & Related papers  (2024-08-04T13:39:57Z)
• From Chain to Tree: Refining Chain-like Rules into Tree-like Rules on Knowledge Graphs [26.237564631208354]
  We propose the concept of tree-like rules on knowledge graphs to expand the application scope. We propose an effective framework for refining chain-like rules into tree-like rules.
  arXiv  Detail & Related papers  (2024-03-08T07:55:42Z)
• PipeNet: Question Answering with Semantic Pruning over Knowledge Graphs [56.5262495514563]
  We propose a grounding-pruning-reasoning pipeline to prune noisy computation nodes. We also propose a graph attention network (GAT) based module to reason with the subgraph data.
  arXiv  Detail & Related papers  (2024-01-31T01:37:33Z)
• ChatRule: Mining Logical Rules with Large Language Models for Knowledge Graph Reasoning [107.61997887260056]
  We propose a novel framework, ChatRule, unleashing the power of large language models for mining logical rules over knowledge graphs. Specifically, the framework is initiated with an LLM-based rule generator, leveraging both the semantic and structural information of KGs. To refine the generated rules, a rule ranking module estimates the rule quality by incorporating facts from existing KGs.
  arXiv  Detail & Related papers  (2023-09-04T11:38:02Z)
• Self-Supervised Temporal Graph learning with Temporal and Structural Intensity Alignment [53.72873672076391]
  Temporal graph learning aims to generate high-quality representations for graph-based tasks with dynamic information. We propose a self-supervised method called S2T for temporal graph learning, which extracts both temporal and structural information. S2T achieves at most 10.13% performance improvement compared with the state-of-the-art competitors on several datasets.
  arXiv  Detail & Related papers  (2023-02-15T06:36:04Z)
• Efficient learning of large sets of locally optimal classification rules [0.0]
  Conventional rule learning algorithms aim at finding a set of simple rules, where each rule covers as many examples as possible. In this paper, we argue that the rules found in this way may not be the optimal explanations for each of the examples they cover. We propose an efficient algorithm that aims at finding the best rule covering each training example in a greedy optimization consisting of one specialization and one generalization loop.
  arXiv  Detail & Related papers  (2023-01-24T11:40:28Z)
• RulE: Knowledge Graph Reasoning with Rule Embedding [69.31451649090661]
  We propose a principled framework called textbfRulE (stands for Rule Embedding) to leverage logical rules to enhance KG reasoning. RulE learns rule embeddings from existing triplets and first-order rules by jointly representing textbfentities, textbfrelations and textbflogical rules in a unified embedding space. Results on multiple benchmarks reveal that our model outperforms the majority of existing embedding-based and rule-based approaches.
  arXiv  Detail & Related papers  (2022-10-24T06:47:13Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)
• Building Rule Hierarchies for Efficient Logical Rule Learning from Knowledge Graphs [20.251630903853016]
  We propose new methods for pruning unpromising rules using rule hierarchies. We show that the application of HPMs is effective in removing unpromising rules.
  arXiv  Detail & Related papers  (2020-06-29T16:33:30Z)
• Towards Learning Instantiated Logical Rules from Knowledge Graphs [20.251630903853016]
  We present GPFL, a probabilistic learner rule optimized to mine instantiated first-order logic rules from knowledge graphs. GPFL utilizes a novel two-stage rule generation mechanism that first generalizes extracted paths into templates that are acyclic abstract rules. We reveal the presence of overfitting rules, their impact on the predictive performance, and the effectiveness of a simple validation method filtering out overfitting rules.
  arXiv  Detail & Related papers  (2020-03-13T00:32:46Z)
• Graph Inference Learning for Semi-supervised Classification [50.55765399527556]
  We propose a Graph Inference Learning framework to boost the performance of semi-supervised node classification. For learning the inference process, we introduce meta-optimization on structure relations from training nodes to validation nodes. Comprehensive evaluations on four benchmark datasets demonstrate the superiority of our proposed GIL when compared against state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-01-17T02:52:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.