A linear delay algorithm for building concept lattices

Martin Farach-Colton, Yang Huang

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    Concept lattices (also called Galois lattices) have been applied in numerous areas, and several algorithms have been proposed to construct them. Generally, the input for lattice construction algorithms is a binary matrix with size |G||M| representing binary relation I ⊆ G × M . In this paper, we consider polynomial delay algorithms for building concept lattices. Although the concept lattice may be of exponential size, there exist polynomial delay algorithms for building them. The current best delay-time complexity is O(|G||M|2). In this paper, we introduce the notion of irregular concepts, the combinatorial structure of which allows us to develop a linear delay lattice construction algorithm, that is, we give an algorithm with delay time of O(|G||M|). Our algorithm avoids the union operation for the attribute set and does not require checking if new concepts are already generated. In addition, we propose a compact representation for concept lattices and a corresponding construction algorithm. Although we are not guaranteed to achieve optimal compression, the compact representation can save significant storage space compared to the full representation normally used for concept lattices.

    Original languageEnglish (US)
    Title of host publicationCombinatorial Pattern Matching - 19th Annual Symposium, CPM 2008, Proceedings
    Number of pages13
    StatePublished - 2008
    Event19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008 - Pisa, Italy
    Duration: Jun 18 2008Jun 20 2008

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume5029 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Conference19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'A linear delay algorithm for building concept lattices'. Together they form a unique fingerprint.

    Cite this