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.

Preview

PDF Andrews - A Partial-Closure Canonicity test.pdf - Accepted Version All rights reserved. Download (715kB) | Preview

Abstract

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 - Does NOT include content added after October 2018:	Cultural Communication and Computing Research Institute > Communication and Computing Research Centre
Departments - Does NOT include content added after October 2018:	Faculty of Science, Technology and Arts > Department of Computing
Identification Number:	https://doi.org/10.1007/978-3-319-08389-6_5
Page Range:	37-50
Depositing User:	Helen Garner
Date Deposited:	29 Oct 2014 10:47
Last Modified:	18 Mar 2021 05:54
URI:	https://shura.shu.ac.uk/id/eprint/8607

Actions (login required)

View Item

Downloads

Publication Metrics