Abstract
Galois lattices (or concept lattices), which are lattices built on a binary relation, are now used in many fields, such as Data Mining and hierarchy organization, but may be of exponential size. In this paper, we propose a decomposition of a Galois sub-hierarchy which is of small size but contains useful inheritance information. We show how to efficiently maintain this information when an element is added to or removed from the relation, using a dynamic domination table which describes the underlying graph with which we encode the lattice.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Berry, A., Bordat, J.-P.: Orthotreillis et séparabilité dans un graphe non-orienté. Mathématiques, Informatique et Sciences Humaines, 146 (1999) 5–17.
Berry, A., Sigayret, A.: Representing a concept lattice by a graph. Workshop on Discrete Mathematics for Data Mining, Proc. 2nd SIAM Workshop on Data Mining, Arlington (VA), April 11–13, (2002).
Chen, J.-B., Lee, S. C.: Generation and Reorganization of Subtype Hierarchies. Journal of Object Oriented Programming, 8(8) (1996).
Godin, R.: Complexité de Structures de Treillis. Annales des Sciences Mathématiques du Québec, 13(1) (1989) 19–38.
Godin, R., Mili, H.: Building and Maintaining Analysis-Level Class Hierarchies Using Galois Lattices. Proceedings of ACM OOPSLA’93, Special issue of Sigplan Notice, 28(10) (1993) 394–410.
Godin, R., Missaoui, R., April, A.: Experimental Comparison of Navigation in a Galois Lattice with Conventional Information Retrieval Methods. International Journal of Man-Machine Studies, 38 (1993) 747–767.
Godin, R., Saunders, E., Gecsei, J.: Lattice Model of Browsable Data Spaces. Information Sciences, 40 (1986) 89–116.
Hager, M.: On Halin-Lattices in Graphs. Discrete Mathematics, 47 (1983) 235–246.
Halin, R.: Lattices of cuts in graphs. Abh. Math. Sem. Univ. Hamburg, 61 (1991) 217–230.
Huchard, M., Dicky, H., Leblanc, H.: Galois lattice as a framework to specify building class hierarchies algorithms. Theoretical Informatics and Applications, 34 (2000) 521–548.
Pfaltz, J. L., Taylor, C. M.: Scientific Knowledge Discovery through Iterative Transformation of Concept Lattices. Workshop on Discrete Mathematics for Data Mining, Proc. 2nd SIAM Workshop on Data Mining, Arlington (VA), April 11–13, (2002).
Polat, N.: Treillis de séparation des graphes. Can. J. Math., vol. XXVIII No 4 (1976) 725–752.
Valtchef, P., Missaoui, R., Godin, R.: A Framework for Incremental Generation of Frequent Closed Item Sets. Workshop on Discrete Mathematics for Data Mining, Proc. 2nd SIAM Workshop on Data Mining, Arlington (VA), April 11–13, (2002).
Yahia, A., Lakhal, L., Bordat, J.-P.: Designing Class Hierarchies of Object Database Schemes. Proceedings 13e journées Bases de Données avancées (BDA’97), (1997).
Zaki, M. J., Parthasarathy, S., Ogihara M., Li, W.: New Algorithms for Fast Discovery of Association Rules. Proceedings of 3rd Int. Conf. on Database Systems for Advanced Applications, April, (1997).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Berry, A., Sigayret, A. (2002). Maintaining Class Membership Information. In: Bruel, JM., Bellahsene, Z. (eds) Advances in Object-Oriented Information Systems. OOIS 2002. Lecture Notes in Computer Science, vol 2426. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46105-1_3
Download citation
DOI: https://doi.org/10.1007/3-540-46105-1_3
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44088-8
Online ISBN: 978-3-540-46105-0
eBook Packages: Springer Book Archive