A Partial-Closure Canonicity Test to Increase the Efficiency of CbO-Type Algorithms

ANDREWS, Simon (2014). A Partial-Closure Canonicity Test to Increase the Efficiency of CbO-Type Algorithms. In: HERNANDEZ, Nathalie, JÄSCHKE, Robert and CROITORU, Madalina, (eds.) Graph-Based Representation and Reasoning. Lecture Notes in Computer Science (8577). Springer, 37-50.

Andrews - A Partial-Closure Canonicity test.pdf - Accepted Version
Available under License All rights reserved.

Download (715kB) | Preview
Link to published version:: 10.1007/978-3-319-08389-6_5


Computing formal concepts is a fundamental part of Formal Concept Analysis and the design of increasingly efficient algorithms to carry out this task is a continuing strand of FCA research. Most approaches suffer from the repeated computation of the same formal concepts and, initially, algorithms concentrated on efficient searches through already computed results to detect these repeats, until the so-called canonicity test was introduced. The canonicity test meant that it was sufficient to examine the attributes of a computed concept to determine its newness: searching through previously computed concepts was no longer necessary. The employment of this test in Close-by-One type algorithms has proved to be highly effective. The typical CbO approach is to compute a concept and then test its canonicity. This paper describes a more efficient approach, whereby a concept need only be partially computed in order to carry out the test. Only if it passes the test does the computation of the concept need to be completed. This paper presents this ‘partial-closure’ canonicity test in the In-Close algorithm and compares it to a traditional CbO algorithm to demonstrate the increase in efficiency.

Item Type: Book Section
Additional Information: 21st International Conference on Conceptual Structures, ICCS 2014 Iași, Romania, July 27-30
Research Institute, Centre or Group: Cultural Communication and Computing Research Institute > Communication and Computing Research Centre
Identification Number: 10.1007/978-3-319-08389-6_5
Depositing User: Helen Garner
Date Deposited: 29 Oct 2014 10:47
Last Modified: 19 Oct 2016 23:26
URI: http://shura.shu.ac.uk/id/eprint/8607

Actions (login required)

View Item View Item


Downloads per month over past year

View more statistics