Making Use of Empty Intersections to Improve the Performance of CbO-Type Algorithms

ANDREWS, Simon (2017). Making Use of Empty Intersections to Improve the Performance of CbO-Type Algorithms. In: Formal Concept Analysis : 14th International Conference, ICFCA 2017, Rennes, France, June 13-16, 2017, Proceedings. Lecture notes in artificial intelligence (10308). Springer, 56-71.

Preview

PDF Andrews Making Use of Empty Intersections.pdf - Accepted Version All rights reserved. Download (377kB) | Preview

Abstract

This paper describes how improvements in the performance of Close-by-One type algorithms can be achieved by making use of empty intersections in the computation of formal concepts. During the computation, if the intersection between the current concept extent and the next attribute-extent is empty, this fact can be simply inherited by subsequent children of the current concept. Thus subsequent intersections with the same attribute-extent can be skipped. Because these intersections require the testing of each object in the current extent, significant time savings can be made by avoiding them. The paper also shows how further time savings can be made by forgoing the traditional canonicity test for new extents, if the intersection is empty. Finally, the paper describes how, because of typical optimizations made in the implementation of CbO-type algorithms, even more time can be saved by amalgamating inherited attributes with inherited empty intersections into a single, simple test.

Item Type:	Book Section
Research Institute, Centre or Group - Does NOT include content added after October 2018:	Cultural Communication and Computing Research Institute > Communication and Computing Research Centre
Identification Number:	https://doi.org/10.1007/978-3-319-59271-8_4
Page Range:	56-71
Depositing User:	Carmel House
Date Deposited:	24 Aug 2017 10:42
Last Modified:	18 Mar 2021 04:04
URI:	https://shura.shu.ac.uk/id/eprint/16441

Actions (login required)

View Item

Downloads

Publication Metrics