Abstract
This paper presents a parallel algorithm for computing fixpoints of Galois connections induced by object-attribute relational data. The algorithm results as a parallelization of CbO (Kuznetsov 1999) in which we process disjoint sets of fixpoints simultaneously. One of the distinctive features of the algorithm compared to other parallel algorithms is that it avoids synchronization which has positive impacts on its speed and implementation. We describe the parallel algorithm, prove its correctness, and analyze its asymptotic complexity. Furthermore, we focus on implementation issues, scalability of the algorithm, and provide an evaluation of its efficiency on various data sets.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Asuncion, A., Newman, D: UCI Machine learning repository. School of Information and Computer Sciences, University of California, Irvine (2007)
Baklouti, F., Levy G.: A distributed version of the Ganter algorithm for general Galois Lattices. In: Belohlavek, R., Snasel, V. (eds.) Proc. CLA, pp. 207–221 (2005)
Belohlavek, R., Vychodil V.: Discovery of optimal factors in binary data via a novel method of matrix decomposition. J. Comput. Syst. Sci. 76, 3–20 (2010)
Berry, A., Bordat, J.-P., Sigayret, A.: A local approach to concept generation. Ann. Math. Artif. Intell. 49, 117–136 (2007)
Carpineto, C., Romano, G.: Concept Data Analysis. Theory and Applications. Wiley, New York (2004)
Fu, H., Mephu Nguifo, E.: A Parallel Algorithm to Generate Formal Concepts for Large Data. ICFCA, LNCS 2961, 394–401 (2004)
Ganter, B.: Two basic algorithms in concept analysis. (Technical Report FB4-Preprint No. 831). TH Darmstadt (1984)
Ganter, B., Wille, R.: Formal Concept Analysis. Mathematical Foundations. Springer, Berlin (1999)
Grätzer G. et al.: General Lattice Theory, 2nd edn. Birkhäuser, Basel (2003)
Hettich, S., Bay, S.D.: The UCI KDD Archive University of California, Irvine, School of Information and Computer Sciences (1999)
Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On generating all maximal independent sets. Inf. Process. Lett. 27(3), 119–123 (1988)
Kengue J. F. D., Valtchev P., Djamégni C. T.: A parallel algorithm for lattice construction. ICFCA, LNCS 3403, 249–264 (2005)
Kuznetsov, S.: Interpretation on graphs and complexity characteristics of a search for specific patterns. Autom. Doc. Math. Linguist. 24(1), 37–45 (1989)
Kuznetsov, S.: A fast algorithm for computing all intersections of objects in a finite semi-lattice (Быстрый алгоритм построения всех пересечений обIектов из конечной полурешетки, in Russian). Automatic Documentation and Mathematical Linguistics, 27(5), 11–21 (1993)
Kuznetsov, S.: Learning of simple conceptual graphs from positive and negative examples. PKDD, pp. 384–391 (1999)
Kuznetsov, S., Obiedkov, S.: Comparing performance of algorithms for generating concept lattices. J. Exp. Theor. Artif. Int. 14, 189–216 (2002)
Lindig, C.: Fast concept analysis. Working with Conceptual Structures—Contributions to ICCS 2000, pp. 152–161. Shaker, Aachen (2000)
Norris, E.M.: An Algorithm for computing the maximal rectangles in a binary relation. Rev. Roum. Math. Pures. Appl. 23(2), 243–250 (1978)
Wille, R.: Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts. Ordered Sets, pp. 445–470, Reidel, Dordrecht (1982)
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by research plan MSM 6198959214. Partly supported by grant P103/10/1056 of the Czech Science Foundation.
Rights and permissions
About this article
Cite this article
Krajca, P., Outrata, J. & Vychodil, V. Parallel algorithm for computing fixpoints of Galois connections. Ann Math Artif Intell 59, 257–272 (2010). https://doi.org/10.1007/s10472-010-9199-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-010-9199-5