Pato

PATO Partitioning Tool

The PATO partitioning tool was presented in the paper Structure-Based Partitioning of of Large Concept Hierarchies by Heiner Stuckenschmidt and Michel Klein. Extension to automatically adapt to given application requirements is presented in A Flexible Partitioning Tool for Large Ontologies at the Conference on Web Intelligence 2008 by Anne Schlicht and Heiner Stuckenschmidt.

Step 1: Create Dependency Graph: In the first step a dependency graph is extracted from an ontology source file. The idea is that elements of the ontology (concepts, relations, instances) are represented by nodes in the graph. Links are introduced between nodes if the corresponding elements are related in the ontology, e.g. because they appear in the same definition.
Step 2: Graph Partitioning: In the second step, the notion of a line island (a set of nodes of given minimal and maximal size for which the strength of the connection between the nodes inside the set is higher than the strength of any connection to nodes outside the set) is used to determine sets of ontology elements that should be in one module.
Step 3: Partition Realization: Finally, a distributed ontology is created based on the graph partitioning. In particular, a namespace is created for each ontology module and the namespace of each ontology element is changed accordingly. Depending on the users preferences, the algorithm outputs either a set of ontology files or one ontology file with adapted namespaces. If redundancies in the distributed representation of the ontology are allowed, each axiom may be copied to different modules to increase the degree of independency between the modules.
Criteria-Based Optimization:: Based on a set of criteria and their weights the configuration that maximizes the weighted sum of the criteria values is determined.

For calculating about the structural properties of the ontology and manupulating the modules, we use the graph analysis tool Pajek.
The tool is a Java application that performs the partitioning interactively through a graphical user interface. It requires Java 1.5 to run or compile.