Recent research has shown the Linked Data cloud to be a potentially ideal basis for improving user experience when interacting with Web content across di erent applications and domains. Using the explicit knowledge of datasets, however, is neither su cient nor straightforward. Dataset knowledge is often not uniformly organized, thus it is generally unknown how to query for it. To deal with these issues, we propose a dataset analysis approach based on knowledge patterns, and show how the recognition of patterns can support querying datasets even if their vocabularies are previously unknown. Finally, we discuss results from experimenting on three multimedia-related datasets.
The constant expansion trend of Linked Data (LD) is broadening the
potential exploitation range of their datasets for improving search through related
data. Current research [
We propose an approach to examine LD with these problems in mind. It employs a strategy for inspecting datasets and identifying emerging knowlege patterns (KPs). A key step of this method is the construction of a formal logical architecture, or dataset knowledge architecture, which summarizes the key features and gures of one or more datasets, thus addressing requirement (1). This, in turn, relies on the notions of KPs and type-property paths. We identify the central properties and types, i.e. those able to capture most of the knowledge in a dataset, and extract KPs based on the central types. In other words, we extract the dataset vocabulary and analyse the way the data are used in terms of patterns. We also associate general-purpose measures, such as betweenness and centrality, to the knowledge architecture components of a dataset for performing empirical analysis. These notions and measures will be de ned throughout the paper. Using KPs and paths, we can provide prototypical ready-to-use queries for core and concealed knowledge to emerge, thus addressing requirement (2). Although the method applies to datasets whose logical structure is not known a priori, it is meant to analyse LD for serendipitous knowledge. Unlike a mere reverse-engineering exercise, our method discovers new knowledge about datasets, such as their central types and properties and emerging patterns.
The method was partly applied manually and our claims on it are observed empirically, yet it can be generalised and fully automated, as the construction of a dataset architecture and computation of its measures are all derived by directly querying the data using metalevel constructs from RDF and OWL.
The paper is organized as follows. In Section 2 we discuss the general approach for data retrieval and analysis, compounded with our leading hypotheses and basic de nitions of recurring terms in our methodology. In Section 3 we describe the dataset knowledge architecture, the evaluation measures and an overview of the datasets speci cally considered in this analysis. In Section 4 we present and discuss the results of our empirical study, including an example of query, knowledge pattern and dataset gures. After an overview on related work in Section 5, we present our conclusions and future work in Section 6. 2
Linked Data typically combine types and properties de ned either in in-house ontologies, or in widespread existing ones e.g. FOAF4, DC5 or GeoNames6. It may occur, though, that in-house ontologies have not been formalized, or are not disclosed. Even when the ontologies are available, they do not tell which relevant part of them is actually used in a dataset, and what links are drawn (through the data) between entities across various ontologies. Knowing these details about a dataset is a pre-condition for evaluating its adequateness for being reused in a certain context, for inspecting its content, for integrating it with other (possibly legacy) knowledge; in other words, for using it. We hypothesize that employing KPs for analysing and possibly authoring LD addresses this problem. In this paper, we focus on querying a dataset when its vocabulary is previously unknown, by proceeding as follows: { we de ne a method and an ontology for analyzing a dataset and producing a synthesis of it i.e. a modular abstraction named dataset knowledge architecture, that highlights how a dataset knowledge is organized, and what its core knowledge components (e.g. central types and associated KPs) are; { we show how this general method and ontology can be exploited for identifying principal KPs extracted from a dataset for producing prototypical queries, through which we are able to retrieve a dataset core knowledge.
As another premise to our approach to be described in Section 2, we de ne a few terms that are used throughout the remainder of this paper.
A knowledge pattern (KP) for a type in an RDF graph includes: (i) the properties by which instances of this type relate to other individuals; (ii)
the types of such individuals for each property. A KP is an invariance across
observed data or objects that allows a formal or cognitive interpretation [
A path is an ordered type-property sequence that can be traversed in an RDF graph. Note the use of types in lieu of their instances, which instead denote multiple occurrences of the same path. The length of a path is the number of properties involved (possibly even with repetitions).
Our approach uses a strategy aimed at modelling, inspecting, and summarizing Linked Data sets, thereby drawing what we call their knowledge architecture, which relies on the notions of paths and KPs de ned above. The application of this approach is sketched in Figure 1, and can be synthesized as follows: 1. Gather property usage statistics for a chosen dataset and store them as
ABox of the knowledge architecture ontology ; 2. Query the dataset for extracting paths. Store all paths with length up to 4, with their usage statistics, in the knowledge architecture dataset7; 3. Identify central types and central properties based on their frequencies in a key position in paths, i.e. betweenness, and number of instantiations; 4. Extract emerging KPs based on the dataset's central types and properties; 5. Select clustering factors among central properties, i.e. those properties occupying the same position in a set of paths, and construct path clusters; The following section illustrates how the components of a dataset knowledge architecture are constructed for performing the steps of our method. 3
Our method described in Section 2 focuses on two main empirical results: (1) building a knowledge architecture of a dataset able to summarize its key 7 The choice of maximum path length 4 was dictated by computational boundaries and the extreme redundancy empirically observed in longer paths (cf. Section 3). features; and (2) extracting the central KPs of a dataset. In this Section we focus on what a dataset knowledge architecture is and how to construct it. 3.1
A dataset knowledge architecture is an ontology that expresses a dataset vocabulary in a modular way. Its components are selected based on measures that indicate their importance in capturing the core knowledge in a dataset. In other words, it is an abstraction over an RDF graph, which o ers a modular view as opposed to the usual \class-property" view provided by vocabularies and ontologies, since it is open to queries that are agnostic to speci c types and properties used in the dataset. To populate it, we inspect a dataset for (i) the types and properties it uses, (ii) its typical paths i.e. type-property sequences, and (iii) quantitative statistics about their usage. The knowledge architecture schema is available online8. This formalism allows us to empirically analyse a dataset architecture through SPARQL queries. Figure 2 depicts the main entities de ned by the dataset knowledge architecture ontology. With the help of this ontology, we aim at deriving, in a bottom-up way, the ontology actually employed for representing the data in a LD dataset and produce additional useful knowledge about a dataset e.g., its central types. We identify (i) the properties used in a dataset triples, and model them through the class Property; (ii) the types (classes or literals) of the subject and object resources of such triples, and model them through the class Type; and (iii) the typical paths that connect triples in a dataset, and model them through the class Path.
A Path is an ordered set fT1; p1; :::; pl; Tl+1g, where Ti is a Type, pi is a property, and l is the path length. Each ordered subset fTi; pi; Ti+1g of a Path of length l is called PathElement, and is associated with its position i = 1; ::l, 8 http://www.ontologydesignpatterns.org/ont/lod-analysis-properties.owl, which imports the paths module as well. in the path. For example, one DBTune Jamendo9 instance of Path is:
fmo:MusicArtist foaf:made mo:Record mo:available as mo:Torrentg has length= 2, and is composed of the following PathElements:
fmo:MusicArtist, foaf:made, mo:Recordg (position 1) fmo:Record, mo:available as, mo:Torrentg (position 2) where mo: and foaf: are pre xes for the Music Ontology (i.e., http://purl. org/ontology/mo/) and FOAF namespaces (i.e., http://xmlns.com/foaf/0. 1/). We then de ne four properties describing PathElement: hasProperty, hasPosition, hasPathElementObjectType and hasPathElementSubjectType. Each Path is associated to an instance of PathOccurrencesInDataset, which indicates the observed number of occurrences of that path in a Dataset.
We also de ne the concepts CentralType and CentralProperty, which identify the entities capturing most of the knowledge in a dataset. The type KnowledgePattern is used for storing the emerging knowledge patterns. 3.2
Table 1 illustrates the measures that we associate to the knowledge architecture of a dataset to empirically analyse and interpret them to support our conclusive statements in Section 4. Measures from #Triples to #PathOcc hold for a dataset as a whole, while the others are related to a type or property and can be computed either for one dataset or across multiple datasets. Most of the measures have been computed by combining SPARQL queries and software scripting10.
The measures for identifying the central types and properties of a dataset are also shown. Type betweenness and Property betweenness are simpli cations of centrality measures used in graph theory. Although we do not model the knowledge architecture of a dataset as a graph, its structure approximates it through the notion of directed paths and based on the empirical observation that all paths longer than 3 are composed of the observed shorter paths.
We can then compute betweenness of types by counting the participation of types as subjects in paths of length 2 at position 2, and betweenness of properties by counting the participation of properties in paths of length 3 in position 2.
The combination of betweenness values and number of instances indicates the value of centrality of a type or property for a dataset. Central types and properties are able to capture most of the knowledge expressed in a dataset. 3.3
We initially examined several datasets including general-purpose, cross-domain and multimedia domain-speci c datasets. As selection criteria for ensuring us a statistically relevant sample for our experiments, we selected datasets: 1. addressing a speci c knowledge domain;
2. addressing the same speci c domain, or a conceptually related one - hence leading to possible cross-relations among them; 3. with di erent sizes 4. that use third-party as well as in-house ontologies.
We eventually chose three datasets related to the multimedia domain.
Jamendo11 is an online distributor of independent musical artists. The represented data focus on record authorship, release and distribution over internet channels. Being part of the DBTune service, its data representation relies on the Music Ontology12 and parts of FOAF, Dublin Core, Event13, Timeline14 and Tags15 ontologies. The indie nature of its hosted artists, who are scarcely represented in other datasets, makes Jamendo a primary source for its content.
John Peel Sessions (JPeel)16 includes data related to live musical performances for the John Peel Show aired on BBC Radio One, and the resulting record releases. It is also a DBTune dataset, but being more event-focused, it mostly reuses a di erent portion of the Music Ontology vocabulary than Jamendo does. 11 Jamendo DBTune home, http://dbtune.org/jamendo 12 The Music ontology, http://purl.org/ontology/mo/ 13 Event Ontology, http://purl.org/NET/c4dm/event.owl# 14 Timeline ontology, http://purl.org/NET/c4dm/timeline.owl# 15 Tag vocabulary, http://www.holygoat.co.uk/owl/redwood/0.1/tags/ 16 John Peel DBTune home, http://dbtune.org/bbc/peel
LinkedMDB (LMDB)17 is a tripli ed database of the lm industry domain. It encompasses the entities involved with lm production and release, plus additional metadata concerning ratings and events such as lm festivals. The LinkedMDB ontology is unpublished18 and almost entirely in-house, with a few exceptions such as FOAF and Dublin Core terms.
These datasets address domain-speci c knowledge, thus satisfying our criterion 1. They also address criterion 2 as Jamendo and JPeel share the music production domain (albeit with di erent data and perspectives), while LMDB addresses the movie production domain, which is related to music e.g. through soundtrack authorship. Table 2 shows how they di er in dimensions, thus satisfying criterion 3. Finally, as for criterion 4 Jamendo and JPeel heavily reuse external ontologies, while LMDB mainly uses a proprietary one. Additionally, their vocabulary usage has little to no overlap.
We excluded general-purpose and cross-domain datasets, e.g. DBPedia and
GeoNames, based on the already existing research experience on applying
patterns to them. Examples are [
For each dataset we computed the measures from Table 1. They provided us with a means to objectively describe datasets according to our selection criteria. 17 LinkedMDB home, http://www.linkedmdb.org/ 18 The base namespace http://data.linkedmdb.org/resource/movie/ would not resolve as of August 2011, thus forcing us to assume an implicit schema for the dataset. 19 WordNet, http://wordnet.princeton.edu/ 20 Geographic Names, http://www.getty.edu/research/tools/vocabularies/tgn/ By the gures in Table 3, the three datasets are not very sparse, due to their high property usage values. This favours the identi cation of central types and properties. Additionally, datasets di er by several orders of magnitude in number of paths and their occurrences, thus con rming their variety in size. The full list of types and properties used in the three datasets is available online21. 4
Based on the described entities and the associated measures (cf. Sections 3.2 and 3.3), we can compute each dataset's central types and properties and extract their most representative Paths, to the aim of building prototypical queries. These can be constructed by identifying a set of path elements that allow us to retrieve the relevant knowledge about central types.
We extract all emerging KPs through querying all distinct paths of length 1 and group them by their subject types. The KP of a type C (i.e., KP (C)) includes the type C, all the properties used for describing its instances, and the object types connected to them. The list of KPs extracted from the three datasets is published online22.
A prototypical query has to provide an e ective summarization of a dataset knowledge about a central type. Such e ective summarization includes more than the properties used for describing such type's instances, that is, we need a way to identify an interesting neighborhood of the types' instances. To this aim, we exploit the notion of central properties and their clusters of paths of length 3 (where the property is at position 2). Examples of clusters, the queries used for retrieving them, and the full list of extracted KPs are available online23.
We identify the types and properties through which most of the dataset knowledge transits (i.e., central types and properties, respectively), and show that they have a primary role for selecting KPs and paths for building prototypical queries. We report here the statistics computed for these types and properties in Jamendo24. Figures 4(a) and 4(b) show the metrics used for identifying central types; that is, as our task is to build prototypical queries, we look at types with both high betweenness and many individuals, thereby addressing centrality and recall. In the case of Jamendo, we select mo:Playlist, Track, and Signal. Figures 4(c) and 4(d) show the metric values for identifying central types, i.e. the number of triples that instantiate a property and the betweenness of properties. By adopting the same policy as for central types, we select mo:available as, mo:published as, and foaf:made.
A prototypical query, which provides a meaningful summarization of a dataset knowledge about a central type, is built by combining KPs and central properties' clusters of paths of length 3, by implementing the following algorithm: 21 http://stlab.istc.cnr.it/stlab/LOD-Analysis-TypesAndProperties 22 List of KPs extracted from Jamendo (10 KPs), JPeel (8 KPs), and LMDB (51 KPs), http://stlab.istc.cnr.it/stlab/LOD-Analysis-EmergingKP 23 Example clusters at http://stlab.istc.cnr.it/stlab/LOD-Analysis-Clusters 24 Webpage http://stlab.istc.cnr.it/stlab/LOD-Analysis-Graphs contains the complete charts; http://stlab.istc.cnr.it/stlab/LOD-Analysis-Statistics shows the same data as tables, along with the queries for computing them.
Let us exemplify the generation of a prototypical query, following the algorithm above, for C=mo:Track, which is a central type in Jamendo. Based on KP (mo : T rack), P E will be initialized by 4 paths, characterized by the properties fdc:title, mo:available as, mo:license, mo:track numberg25. Among them, only mo:available as is a central property in Jamendo, hence we pick up its cluster of paths (of length 3) in order to enrich the set P E that will be used for building the prototypical query. From such cluster, we collect 3 additional paths as they are connected to mo:Track. Two of them identify incoming links to mo:Track (i.e., mo:track and mo:pulished as), and one identi es one link in the neighborhood of mo:Track (i.e., dc:format), which reaches a 2-degree distance from it in its knowledge graph. This additional link in the neighborhood shows how this approach allows to build queries that capture more meaningful knowledge than a simple SPARQL DESCRIBE. An interesting investigation that we have planned in our future work is to study the cognitive soundness of these queries with respect to user interaction tasks.
The result of the described procedure is the following query. Figure 3 shows the resulting graph if such a query would be applied to a speci c instance of mo:Track, http://dbtune.org/jamendo/track/7593 in this speci c case. construct { ?t a mo:Track . ?t dc:title ?t1 . ?t mo:available_as ?t2 . ?t2 dc:format ?f . ?t mo:license ?t3 . ?t mo:track_number ?t4 . ?s a mo:Signal . ?s mo:published_as ?t . ?r a mo:Record . ?r mo:track ?t . } from jamendo_dataset where { ?t a mo:Track . ?t dc:title ?t1 . {{OPTIONAL { ?t mo:available_as ?t2 . ?t2 dc:format ?f }} UNION {OPTIONAL { ?t mo:license ?t3 }} UNION {OPTIONAL { ?t mo:track_number ?t4 }} UNION {OPTIONAL { ?s a mo:Signal . ?s mo:published_as ?t }} UNION {OPTIONAL { ?r a mo:Record . ?r mo:track ?t }}} }
These steps allow us to build a summary of a dataset, which supports the retrieval of the most representative knowledge for its domain as (i) paths of length 3 are enough for capturing all knowledge structures, (ii) central types catch most representative knowledge of the dataset, (iii) KPs convey the description of types, and (iv) central properties link the most representative KPs of a dataset. This analytic approach showed that we can summarize a dataset through a relatively small knowledge architecture, thus limiting the impact of empirical analysis on computational complexity. In our three experiments of Section 3.3, we built a 25 For the sake of readability we omit the object types of the path elements. knowledge architecture dataset of 130; 373 triples representing three datasets whose combined size sums up to over 7 106 triples. The architecture is available online26.
mo:MusicArtist mo:Record mo:Lyrics tags2:Tag mo:Torrent mo:ED2K time:Interval mo:Signal mo:Track mo:Playlist foaf:maker foaf:made mo:track mo:time mo:published_as tags2:taggedWithTag mo:available_as mo:Lyrics tags2:Tag mo:Torrent mo:ED2K time:Interval mo:Signal mo:Playlist mo:MusicArtist mo:Track mo:Record tags2:taggedWithTag mo:time mo:track mo:published_as mo:available_as foaf:maker foaf:made 0 20000 40000 60000 80000 100000 120000 0 2 4 6 8 10 12 (a) Number of individuals (b) Type betweenness 0 20000 40000 60000 80000 100000 120000 140000 0 2 4 6 8 10 12 (c) Number of triples
(d) Property betweenness
There has been valuable research work on understanding the LD cloud
recently, which highlights di erent approaches, perspectives, and speci c goals.
Some work focus on providing macroscopic analysis on LD as a whole such as
[
Works such as [
Other research e orts exploit LD for supporting user interaction with
contentintensive applications, such as [
Finally, [
We have shown how to summarize Linked Data sets by treating them as sets of connected knowledge patterns, in order to identify their core knowledge components. We have experimented on three datasets from the LD cloud, and showed how to build prototypical queries for them even when the ontologies that model them are unknown. We have planned, in our future work, to compare ontologies explicitly published and used for a dataset with the knowledge architecture that arises from our analysis.
Our ongoing and future work focuses on extending our strategy, in order to (i) demonstrate how by aligning emerging KPs of a dataset to general KPs improves interoperability across datasets, and detects incompatibility issues (ii) compare analysis data about di erent datasets, and (iii) improve user interaction in searches for relevant content. We have planned to improve the method by performing additional analysis on an extensive coverage of the multimedia domain, and subsequently evaluate the cross-domain portability of our approach. Acknowledgements This work has been part-funded by the European Commission under grant agreement FP7-ICT-2007-3/ No. 231527 (IKS - Interactive Knowledge Stack)