Faculty of Engineering and Computing header
Faculty of Engineering and Computing
Trie of Rules Offers Breakthrough in Association Rule Mining Efficiency

Trie of Rules Offers Breakthrough in Association Rule Mining Efficiency

Dr Mikhail Kudriavtsev, Prof Mark Roantree, Dr Marija Bezbradica and Dr Andrew McCarren from the School of Computing at Dublin City University, together with Dr Vuong Ngo from Trinity College Dublin, have unveiled an innovative method for storing and managing association rules, a core output of data mining techniques widely applied in areas from retail analytics to medical diagnostics. Their study, published in the Journal of Intelligent Information Systems, introduces the “Trie of Rules”, a prefix-tree-based data structure designed to overcome the inefficiencies of conventional approaches.

Association rule mining generates large volumes of rules that reveal relationships between items in datasets. The speed and quality of insight extraction depend heavily on how these rules are stored. Conventional formats such as tables or dataframes can be slow to search and cumbersome to work with, particularly for large-scale datasets. The Trie of Rules addresses these challenges by representing rules as paths in a prefix tree, merging overlapping segments to remove redundancy. Each node stores essential metrics such as support and confidence, enabling not only faster searches but also direct calculation of confidence for complex rules without reprocessing the data.

The team compared the Trie of Rules against commonly used formats, including Pandas DataFrames and NumPy arrays, using datasets ranging from supermarket transaction logs to extensive retail records. Across all tests, the Trie of Rules delivered substantial performance gains. In one experiment, a search that took over a second in a DataFrame was completed in less than three thousandths of a second using the Trie. On the largest dataset assessed, the Trie traversed all rules in just 9.4 seconds, compared with hours for the other methods, while also achieving notable memory savings.

In addition to speed and efficiency, the Trie’s graph-like design paves the way for advanced visual and graph-based exploration techniques. The authors plan to investigate further optimisation of item ordering within the structure to enhance performance and to explore integration with interactive visualisation tools to support intuitive analysis of complex data patterns.

Funded by Science Foundation Ireland through the Centre for Research Training in Artificial Intelligence, this work showcases the potential of purpose-built data structures to transform large-scale knowledge discovery, offering researchers and practitioners a faster, more efficient way to unlock insights from association rule mining.

Read the full paper: Exploring the trie of rules: a fast data structure for the representation of association rules, Journal of Intelligent Information Systems here.