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.
|
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
Downloads per month over past year