Knowledge Discovery and Ontology-based services on the Grid

Mario Cannataro
University `Magna Græcia' of Catanzaro, 88100 Catanzaro, Italy
cannataro@unicz.it

Abstract

Main issues to be faced by next-generation Grids are the management and exploitation of the overwhelming amount of data produced by applications but also by Grid operation, and the intelligent use of Grid resources and services. To achieve these very ambitious goals, next-generation Grids should include knowledge discovery and knowledge management functionalities, for both applications and system management. The way how data and information available at different levels of Grid can be effectively acquired, represented, exchanged, integrated, and converted into useful knowledge is an emerging research field known as `Grid Intelligence'. Ontologies and metadata are the basic elements through which such Grid Intelligence can be deployed. Moreover Grids should offer semantic modeling of user's tasks/needs, available services, and data sources to support high level services and dynamic services finding and composition. This document describes some of these emerging services and a first implementation in the KNOWLEDGE GRID, an environment for the design and execution of geographically distributed high-performance knowledge discovery applications.

1. Introduction

The solutions that will be developed will certainly driven by the previous needs and requirements, but will also leverage and probably integrate some key technologies and methodologies emerging in many computer science fields, apparently far and unaware of Grids, such as peer-to-peer [8] and ubiquitous computing [9], ontology-based reasoning, and knowledge management. In particular, ontologies and metadata are the basic elements through which Grid Intelligence services can be deployed. Using ontologies, Grids may offer semantic modeling of user's tasks/needs, available services, and data sources to support high level services and dynamic services finding and composition [4]. Moreover, data mining and knowledge management techniques could enable high level services based on the semantics of stored data. Such services could be employed both at operation layer, where Grid management could gain from information hidden into data, and at application layer, where user could be able to exploit distributed data repository, using the Grid not only for high-performance access, movement and processing of data, but also to apply key analysis tools and instruments.

In this scenario, where resource ontologies and metadata allow intelligent searching and browsing, and knowledge discovery and management techniques allow high level services, peer-to-peer and ubiquitous computing, will be the orthogonal key technologies through which realize basic services such as presence management, resource discovery and sharing, collaboration and self-configuration.

Recent Grid developments [5] aim to simplify and structure the systematic building of Grid applications through the composition and reuse of software components and the development of knowledge-based services and tools. Following the trend emerged in the Web community the Open Grid Services Architecture (OGSA) introduced the service-oriented model [7, 10]. Semantic Grid focuses on the systematic adoption of metadata and ontologies to describe resources, services, data sources over the Grid, to enhance, and possibly automate, processes such as service discovery and negotiation, application composition, information extraction, and knowledge discovery [6]. Finally, Knowledge Grids [1] offer high-level tools and techniques for the distributed mining and extraction of knowledge from data repositories available on the Grid, leveraging semantic descriptions of components and data, as provided by Semantic Grid, and possibly offering knowledge discovery services as Grid Services.

Next section discusses some high-level services useful to build the emerging next-generation Grid. The KNOWLEDGE GRID, an environment for the design and execution of distributed knowledge discovery applications, is then briefly presented [2]. Finally we describe a case study where semantics and knowledge are used to enhance Grid functionalities and create new services: ontology-based semantic modelling is used to enhance component-based programming on the Grid.

2. Services for next-generation Grids

To face the growing complexity of Grids and the overwhelming amount of data to be managed, main requirements of future Grids will be:

knowledge discovery and knowledge management functionalities, for both user's needs (intelligent exploration of data, etc.) and system management;
semantic modeling of user's tasks/needs, Grid services, data sources, computing devices (from ambient sensors to high-performance computers), to offer high level services and dynamic services finding and composition;
pervasive and ubiquitous computing, through environment/context awareness and adaptation;
advanced forms of collaboration, through dynamic formation of virtual organizations;
self-configuration, autonomic management, dynamic resource discovery and fault tolerance.

In particular, to fulfill some of the requirements listed before, we envision that next-generation Grids should first provide the following three main classes of services and related architectural framework:

Knowledge management and ontology-based services. They are used to build, manipulate, and interoperate, in an homogeneous way, the Grid knowledge base. The term Grid knowledge base is used here to indicate all the data stored, maintained, and updated by the Grid, both for user, application, and operation purposes. It comprises, for example, the Globus MDS data and metadata, the Grid services usage data, the application data sources and results, etc. Many of these data are currently maintained by Grid middleware or by Grid applications, so the very main challenge for next-generation Grids will be their seamless integration and utilization. From an architectural point of view, technologies useful for building, manipulating, and reasoning on the Grid knowledge base are ontologies and logic programming. In such scenario, each `object' on the Grid (as in the Semantic Web) is classified through one or more ontologies into the knowledge base. Two important services that could be offered are: ontology-based Grid programming and request-resource matchmaking. In the next Section we will show a simple example of component-based programming based on domain ontology.
Knowledge discovery services. They are used to extract knowledge from the data stored inside the Grid knowledge base. These services will be used both to build high-level knowledge discovery applications, as in the case of the KNOWLEDGE GRID, and to enhance existing basic Grid services. Two examples of high level services needing distributed data mining functionalities and accessing distributed partitions of a knowledge base are, for example, an enhanced version of the GridFTP protocol that classifies GridFTP usage data with data mining techniques to choose best connection parameters, and a Grid-based document management applications.
Context-aware access to information and service adaptation. Semantic (lossy or lossless) compression and synthesis of Grid information (metadata) could be used to offer different views of the Grid knowledge base depending on many factors: user/service goals, scope of resource information. Other than usual compression techniques contents can be reorganised according to some aggregation functions (schema extraction and restructuring), resulting in a synthetic (compressed) yet meaningful version [3]. Synthesis techniques, e.g. based on Data Mining metadata exploration, could enable the provision of different views of Grid resources exposing different levels of details, allowing adapting the access and use of such information to different users/services goals. Moreover, adaptation techniques coming from the Adaptive Hypermedia research community [12] could be employed to adapt services to the user's computing environment on the basis of context.
Dynamic resource discovery. When the Grid goes beyond a static, well established configuration, becoming a Pervasive Grid, i.e. when new devices and resources are allowed to enter and exit the Grid in a very dynamic way, new services able to adapt themselves to the environment have to be developed. Peer-to-Peer technologies could be used to implement dynamic discovery algorithms.

Such services can be incrementally built leveraging current Grid efforts and projects. Figure 1 shows how the recent research initiatives in the Grid community (OGSA, Semantic Grid, and Knowledge Grids) could be composed to provide a coherent architecture of services. Although these initiatives present some overlapping, they complement each others. Some enabling technologies, such as ontologies and reasoning, knowledge management and knowledge discovery, are currently offered by the depicted layers, but their main impact will be really evident when they will be used internally to enhance Grid management and operation. On the other hand, peer-to-peer and ubiquitous computing techniques start to be used very recently. In our opinion peer-to-peer will be the orthogonal technology on which main tasks such as presence management, resource discovery and sharing, collaboration and self-configuration will be based [11].

fig1
Figure 1: Building Knowledge Discovery and Ontolgy-based services

3. The KNOWLEDGE GRID

Next-generation Grids must be able to produce, use and deploy knowledge as a basic element of advanced applications. In this scenario we designed the KNOWLEDGE GRID system as a joint research project of ICAR-CNR, University of Calabria, and University of Catanzaro, Italy, aiming at the development of an environment for geographically distributed high-performance knowledge discovery applications [2]. The KNOWLEDGE GRID is a high-level system for providing Grid-based knowledge discovery services. These services allow professionals and scientists to create and manage complex knowledge discovery applications composed as workflows that integrate data sets, mining tools, and computing and storage resources provided as distributed services on a Grid.

KNOWLEDGE GRID facilities allow users to compose, store, share, and execute these knowledge discovery workflows as well as publish them as new components and services on the Grid. The KNOWLEDGE GRID can be used to perform data mining on very large data sets available over Grids, to make scientific discoveries, improve industrial processes and organization models, and uncover business valuable information. Other examples of Knowledge Grids are shortly described in [12].

The KNOWLEDGE GRID provides a higher level of abstraction and a set of services based on the use of Grid resources to support all those phases of the knowledge discovery process. Therefore, it allows the end-users to concentrate on the knowledge discovery process they must develop without worrying about Grid infrastructure details.

The KNOWLEDGE GRID architecture is composed of a set of services divided in two layers:

The core K-Grid layer that contains metadata and ontologies about data sources and software components (data mining tools) and interfaces basic Grid middleware and services. It includes repositories that provide information about resource metadata, application workflows, and knowledge obtained as result of knowledge discovery applications. The core layer is a view over the KNOWLEDGE GRID knowledge base.
The high level K-Grid layer that interfaces the user by offering a set of services for the design and execution of knowledge discovery applications. In the KNOWLEDGE GRID environment, discovery processes are represented as workflows that a user may compose using both concrete and abstract Grid resources. Knowledge discovery workflows are defined using visual interface that shows resources (data, tools, hosts) to the user and offers mechanisms for integrating them in a workflow. The high level K-Grid layer uses some ontology-based services, as shown in the next Section, and allows to implement knowledge discovery services.

4. A case study: Ontology-based Programming on the Grid

In component-based Grid programming the user designs an application by composing available software components. However, choosing components (i.e., using domain knowledge) and enforcing constraints (i.e., using programming knowledge) are often left to the designer activity. In this case study we will show how ontologies can help users in designing and programming knowledge discovery applications on the KNOWLEDGE GRID. After a brief description of the developed domain ontology, we show how a designer can exploit that knowledge base to formulate its application and choose the software components.

Domain Ontology: a view over the Grid knowledge base. DAMON (DAta Mining ONtology) is an ontology for Data Mining domain that explicitly manages the knowledge about the domain of interest (Data Mining) and related software tools, offering users a reference model for the different classes of data mining tasks, methodologies, and software components available to solve a given problem [4]. The choice of how to structure an ontology determines what a system can know and reason about. We have built our ontology through a classification of data mining software that allows for selecting the most appropriate software to solve a KDD (Knowledge Discovery in Databases) problem. The ontology represents the features of the available data mining software by classifying their main components and evidencing the relationships and the constraints among them. The categorization of the data mining software has been made on the basis of the following classification parameters:

A (data mining discovery) Task represents a data mining technique for extracting patterns from data, that is a task specifies the goal of a data mining process.
A Method is a data mining methodology used to discover the knowledge; different methods serve different purposes. It can be thought as a structured manipulation of the input data to extract knowledge.
An Algorithm is the way through which a data mining task is performed.
A Software is an implementation (in a programming language) of a data mining algorithm.
A Suite implements a set of data mining algorithms: every algorithm may perform different tasks and employ different methods to achieve the goal.
A Data Source is the input on which data mining algorithms work to extract new knowledge.
The Human Interaction specifies how much human interaction with the discovery process is required and/or supported.

The Data Mining knowledge base used to support knowledge discovery programming has two conceptual layers: at the top layer the DAMON ontology gives general information about the Data Mining domain, whereas specific information about installed software components and data sources are maintained where resources resides. From an architectural point of view the ontology is a central resource, whereas specific metadata are distributed ones. As an example, DAMON stores the fact that the C5.0 Software implements the C5 Algorithm, that uses the Decision Tree method, that is a Classification method. The C5.0 Software node of ontology contains the URLs of the metadata files describing details about all the installed instances of that software.

Ontology-based programming: accessing the Grid knowledge base through ontology. DAMON is used as an ontology-based assistant that suggests the KNOWLEDGE GRID application designer what to do and what to use on the basis of his/her needs as well as a tool that makes possible semantic search of data mining software. In other words, it can be used to enhance the application formulation and design, helping the user to select and configure the most suitable Data Mining solution for a specific KDD process.

Information about Data Mining tasks/methodologies, and specific software components implementing data mining algorithms can be obtained by browsing or searching the ontology. In particular, semantic search (concept-based) of data mining software and others data mining resources has been implemented. The search and selection of the resources (data sources and software components, as well as the type of data mining tasks, methodologies and algorithms), to be used in a knowledge discovery application, are accomplished in the following steps:

Ontology-based resources selection. Browsing and searching the ontology allows a user to locate the more appropriate tasks, methods, algorithms and finally data mining software to be used in a certain phase of the KDD process. The user can navigate the ontology using different points of access, showing deeper levels of details. Moreover, the user can query very detailed information about Data Mining resources, using several kinds of inference that can serve to broaden queries including equivalence, inversion, generalization, and specialization. For example, if the query result set is empty, the user can at least find objects that partially satisfy the query: some classes can be replaced by their superclasses or subclasses.
Metadata access. The ontology gives the URLs of all instances of the selected resources available on the KNOWLEDGE GRID nodes, i.e. the URLs of the relevant metadata files stored in the Grid nodes. Such metadata are tightly bounded to the data mining software and data sources installed on a given physical node and contain all the information needed by a client to access and use them (technical parameters, availability, location and configuration of data mining software and tools).

As an example, a user logged on the KNOWLEDGE GRID node KU needs to perform a data mining application composed of two data mining tasks, clustering and classification, on the data set DBX stored on the KNOWLEDGE GRID node KD. The data set must be clustered using three different algorithms running in parallel on a copy of the data set. Clustering results must be analyzed by a classification algorithm that will be executed in parallel on three different nodes, generating three classification models of the same data set.

By using DAMON, the user first searches the clustering algorithms by browsing or querying the ontology on the basis of some user requirements (computational complexity of the algorithm, attitude to solve the given problem or the method used to perform the data mining task), then she/he searches the clustering software implementing the algorithms and working on the data set DBX, and finally locates the metadata URLs referring to the nodes KG1, KG2 and KG3, offering respectively the clustering software K-Means, Intelligent Miner, and AutoClass. Moreover, the user also finds the node KG4 that offers the C5.0 classifier. At this point the user can access specific information about the software by accessing the specific metadata on each identified node.

Such obtained information is then used for the visual composition of those software components and data sources through a graphic interface. The abstract description of this component-based application is then translated into the Grid submission language (RSL in the Globus case). After that the implemented application can be embodied into the DAMON ontology. In this way the knowledge base can be enriched and extended with new complex data mining tasks.

The programming example discussed here is just a case of how ontology-based services can be used for high-level programming of complex applications on Grids. This approach allows the re-use of previously developed applications and software components that can be integrated in new Grid applications.

Acknowledgements

This work has been partially supported by Project `FIRB GRID.IT' funded by MIUR.

References

[1]: F. Berman. `From TeraGrid to Knowledge Grid'. CACM, Vol. 44, N. 11, pp. 27-28, 2001.
[2]: M. Cannataro and D. Talia, `KNOWLEDGE GRID An Architecture for Distributed Knowledge Discovery', CACM, Vol. 46, No. 1, pp. 89-93, January 2003.
[3]: Cannataro M., A. Guzzo and A. Pugliese, `Knowledge Management and XML: Derivation of Synthetic Views over Semistructured Data', ACM SIGAPP - Applied Computing Review Special Issue, Vol. 10, No. 1, pp.33-36, April 2002.
[4]: M. Cannataro and C. Comito, `A Data Mining Ontology for Grid Programming', 1st Int. Workshop on Semantics in Peer-to-Peer and Grid Computing (SemPGrid2003), pp. 113-134, May 2003. Available at www.isi.edu/~stefan/SemPGRID
[5]: D. de Roure, Baker M. A., Jennings, N. R. and Shadbolt, N. `The Evolution of the Grid', In F. Berman, A.J.G. Hey and G. Fox (eds), Grid Computing: Making The Global Infrastructure a Reality, pp. 65-100, John Wiley & Sons, 2003.
[6]: D. de Roure, Jennings, N. R., Shadbolt, N. `The Semantic Grid: A future e-Science infrastructure'. In F. Berman, A.J.G. Hey and G. Fox (eds), Grid Computing: Making The Global Infrastructure a Reality, pp. 437-470, John Wiley & Sons, 2003.
[7]: I. Foster, C. Kesselman, J. Nick, S. Tuecke, The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration. Open Grid Service Infrastructure WG, Global Grid Forum, June 22, 2002.
[8]: K. Lyytinen and Youngjin Yoo, `Issues and Challenges in Ubiquitous Computing', CACM, Vol. 45, No. 12, pp. 62-65, December 2002.
[9]: D. Schoder and K. Fischbach, Peer-to-Peer Prospects, CACM, Vol. 46, No. 2, pp. 27-29, February 2003.
[10]: D. Talia, `The Open Grid Services Architecture: Where the Grid Meets the Web', IEEE Internet Computing, Vol. 6, No. 6, pp. 67-71, 2002.
[11]: D. Talia, P. Trunfio, `Toward a Synergy Between P2P and Grids', IEEE Internet Computing, vol. 7, no. 4, pp. 94-96, 2003.
[12]: The Adaptive Web (Special issue on), CACM, Vol. 45, No. 5, May 2002.