A ‘Best-of-Breed’ approach for designing a fast algorithm for computing fixpoints of Galois Connections

ANDREWS, Simon (2015). A ‘Best-of-Breed’ approach for designing a fast algorithm for computing fixpoints of Galois Connections. Information Sciences, 295 (20), 633-649.

Andrews_a_best_of_breed_approach_for_designing2015.pdf - Accepted Version
Available under License All rights reserved.

Download (1MB) | Preview
Official URL: http://dx.doi.org/10.1016/j.ins.2014.10.011
Link to published version:: 10.1016/j.ins.2014.10.011


The fixpoints of Galois Connections form patterns in binary relational data, such as object-attribute relations, that are important in a number of data analysis fields, including Formal Concept Analysis (FCA), Boolean factor analysis and frequent itemset mining. However, the large number of such fixpoints present in a typical dataset requires efficient computation to make analysis tractable, particularly since any particular fixpoint may be computed many times. Because they can be computed in a canonical order, testing the canonicity of fixpoints to avoid duplicates has proven to be a key factor in the design of efficient algorithms. The most efficient of these algorithms have been variants of the Close-By-One (CbO) algorithm. In this article, the algorithms CbO, FCbO, In-Close, In-Close2 and a new variant, In-Close3, are presented together for the first time, with in-Close2 and In-Close3 being the results of breeding In-Close with FCbO. To allow them to be easily compared, the algorithms are presented in the same style and notation. The important advances in CbO are described and compared graphically using a simple example. For the first time, the algorithms are implemented using the same structures and techniques to provide a level playing field for evaluation. Their performance is tested and compared using a range of data sets and the most important features identified for a CbO ‘Best-of-Breed’. This article also presents, for the first time, the ‘partial-closure’ canonicity test.

Item Type: Article
Additional Information:

Author has permission to use Article in press version.

Accepted 6 October 2014

Research Institute, Centre or Group: Cultural Communication and Computing Research Institute > Communication and Computing Research Centre
Identification Number: 10.1016/j.ins.2014.10.011
Depositing User: Helen Garner
Date Deposited: 05 Nov 2014 16:55
Last Modified: 19 Aug 2015 17:20
URI: http://shura.shu.ac.uk/id/eprint/8677

Actions (login required)

View Item View Item


Downloads per month over past year

View more statistics