A new method for inheriting canonicity test failures in Close-by-One type algorithms

ANDREWS, Simon (2018). A new method for inheriting canonicity test failures in Close-by-One type algorithms. In: IGNATOV, Dmitry I. and NOURINE, Lhouari, (eds.) CLA 2018 : The 14th International Conference on Concept Lattices and Their Applications, proceedings. Springer, 255-266.

Preview

PDF Andrews-NewMethodForInhereting(AM).pdf - Accepted Version All rights reserved. Download (273kB) | Preview

Abstract

Close-by-One type algorithms are effcient algorithms for computing formal concepts. They use a mathematical canonicity test to avoid the repeated computation of the same concept, which is far more effcient than methods based on searching. Nevertheless, the canonicity test is still the most labour intensive part of Close-by-One algorithms and various means of avoiding the test have been devised, including the ability to inherit test failures at the next level of recursion. This paper presents a new method for inheriting canonicity test failures in Close- by-One type algorithms. The new method is simpler than the existing method and can be amalgamated with other algorithm features to further improve effciency. The paper recaps an existing algorithm that does not feature test failure inheritance and an algorithm that features the existing method. The paper then presents the new method and a new algorithm that incorporates it. The three algorithms are implemented on a `level playing field' with the same level of optimisation. Experiments are carried out on the implemented algorithms, using a representative range of data sets, to compare the number of inherited canonicity test failures and the computation times. It is shown that the new algorithm, incorporating the new method of inheriting canonicity test failures, gives the best performance.

Item Type:	Book Section
Additional Information:	Paper of poster presented at CLA 2018 : The 14th International Conference on Concept Lattices and Their Applications, June 12–14, 2018 Olomouc, Czech Republic. Book Series ISSN: 0302-9743
Research Institute, Centre or Group - Does NOT include content added after October 2018:	Cultural Communication and Computing Research Institute > Communication and Computing Research Centre
Page Range:	255-266
Depositing User:	Jill Hazard
Date Deposited:	16 May 2018 11:31
Last Modified:	17 Mar 2021 17:01
URI:	https://shura.shu.ac.uk/id/eprint/21248

Actions (login required)

View Item

Downloads

Publication Metrics