A pyramidal approach for parallel computation of the Luxenburger basis

This paper introduces a novel pyramidal, divide-and-conquer algorithm for computing the Luxenburger basis of association rules. We develop a ‘recombination operator’ to synthesize partial bases in parallel, aiming to make the computation feasible for contexts with many attributes.

Keywords

Luxenburger basis, Pyramidal algorithm, Divide and conquer, Parallel computation, Association rules, Recombination operator

The Luxenburger basis provides a concise representation of all valid association rules in a dataset, but its computation can be intensive for contexts with many attributes. This paper introduces a novel pyramidal, divide-and-conquer algorithm for computing the Luxenburger basis. Inspired by similar strategies for concept lattice construction, our method partitions the attribute set, computes the basis for each partition in parallel, and then synthesizes these partial bases to reconstruct the full Luxenburger basis of the original context. The core of our contribution is the development of a sound and complete “recombination” operator for Luxenburger bases. We prove the correctness of this operator and demonstrate that our pyramidal approach offers significant speedups, especially on multi-core systems, making the computation of the complete association rule basis feasible for wider contexts.

Introduction

The Luxenburger basis is a cornerstone of Formal Concept Analysis, as it is the most compact representation from which all valid association rules (with their exact confidence and support) can be derived. It is constructed from pairs of concepts in a covering relation in the concept lattice. Consequently, its computation is often tied to the expensive process of first building the entire lattice.

While parallel algorithms for lattice construction exist, a direct parallel strategy for the Luxenburger basis is less explored. Drawing a parallel to the pyramidal strategy for lattice construction , we propose to apply the same divide-and-conquer philosophy directly to the computation of the association rule basis.

Our contributions are:

1. A formal pyramidal algorithm for computing the Luxenburger basis.
2. The definition and proof of correctness of a recombination operator that merges the Luxenburger bases of two disjoint sub-contexts.
3. An empirical evaluation showing the scalability and performance benefits of the parallel approach.

Methodology and expected theoretical results

Let a formal context $\mathbb{K}=(G, M, I)$ be partitioned into $\mathbb{K}_1=(G, M_1, I_1)$ and $\mathbb{K}_2=(G, M_2, I_2)$, where $M = M_1 \cup M_2$ and $M_1 \cap M_2 = \emptyset$. Let $\mathcal{L}_1$ and $\mathcal{L}_2$ be the Luxenburger bases of $\mathbb{K}_1$ and $\mathbb{K}_2$, respectively.

The recombination operator

The main theoretical challenge is to define an operator $\oplus$ such that $\mathcal{L}_1 \oplus \mathcal{L}_2$ produces the Luxenburger basis of $\mathbb{K}$. This is not a simple union. A rule in $\mathcal{L}_1$ might be altered or become redundant when considering the attributes in $M_2$. * Main theoretical result: We will define the recombination operator $\oplus$. It will likely involve a process where for each rule $A \to B$ from $\mathcal{L}_1$, we analyze how its support and the corresponding concept closures are affected by the attributes in $M_2$, potentially splitting or modifying the rule. The proof will demonstrate that this process is sufficient to generate all and only the rules of the full Luxenburger basis.

The pyramidal algorithm

1. Recursively partition the attribute set $M$ down to a manageable size.
2. At the base case, compute the Luxenburger basis for the small sub-contexts (e.g., via lattice construction). This step is highly parallelizable.
3. Recursively apply the recombination operator $\oplus$ up the pyramidal tree to merge the bases until the basis for the original context $\mathbb{K}$ is obtained.

Work plan

• Months 1-5: Develop the theory of the recombination operator $\oplus$ and prove its correctness.
• Months 6-8: Implement the pyramidal algorithm, with support for parallel computation.
• Months 9-11: Benchmark the algorithm against standard (monolithic) methods for computing the Luxenburger basis.
• Month 12: Write the manuscript.

Potential target journals

1. Information Sciences (Q1): A great fit for a novel, parallel algorithm for a fundamental data mining task.
2. Journal of Parallel and Distributed Computing (Q1): An excellent venue if the paper heavily emphasizes the parallel implementation and scalability analysis.
3. Data Mining and Knowledge Discovery (Q1): A top choice for its focus on foundational algorithms in knowledge discovery.

Minimum viable article (MVA) strategy

• Paper 1 (The MVA):
  • Scope: The complete paper as described. The core novelty is the recombination operator and the pyramidal algorithm that enables parallelization.
  • Goal: To introduce a new, efficient, and parallelizable method for a core data mining task.
  • Target venue: Information Sciences.