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.

[img]
Preview
PDF
Andrews Making Use of Empty Intersections.pdf - Accepted Version
Available under License All rights reserved.

Download (377kB) | Preview
Official URL: https://link.springer.com/chapter/10.1007/978-3-31...
Link to published version:: 10.1007/978-3-319-59271-8_4

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: Cultural Communication and Computing Research Institute > Communication and Computing Research Centre
Identification Number: 10.1007/978-3-319-59271-8_4
Related URLs:
Depositing User: Carmel House
Date Deposited: 24 Aug 2017 10:42
Last Modified: 24 Aug 2017 11:30
URI: http://shura.shu.ac.uk/id/eprint/16441

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics