Introduction

The open data movement brings increasingly many datasets to the Web, many of which are in the RDF format. Reusing these datasets is of great importance to researchers and developers. In order to enable the reuse there is a pressing need in effective search techniques for finding the right data on demand. A promising approach is to query for datasets with keywords as in Google Dataset Search [1] and to present each retrieved RDF dataset as a snippet, its small representative subset [2]. Dataset snippets aim at concisely explaining to the user why this dataset fulfils their demand and in particular can illustrate the main content of the dataset and explain its relevance to the user's query.

Computing optimal snippets is a non-trivial task and a number of approaches have emerged to address this or related problems [2][3][4][5][6]. In [7], we presented four metrics for evaluating the quality of a dataset snippet. In this short paper, we report our ongoing work on snippets that address multiple facets of optimality. In particular, in order to improve the quality of a snippet for dataset search, we formulate the selection of RDF triples as a combinatorial optimization problem that directly optimizes three evaluation metrics proposed in [7]. A dataset snippet generated by our approach, which we refer to as KSD, is expected to have a good coverage of the query Keywords and the content of the dataset at both the Schema and the Data level. We solve the problem with a greedy algorithm, and our evaluation demonstrates that KSD outperforms the baselines reported in [7] and that there is still a considerable room for quality improvement.

The remainder of this paper is structured as follows. Section 2 defines the problem and reviews the evaluation metrics proposed in [7]. Section 3 describes the implementation of KSD. Section 4 presents evaluation results. Section 5 concludes the paper with future work.

Preliminaries

Problem Statement

An RDF dataset is a set of RDF triples denoted by T = {t 1 , t

Q = {q 1 , q 2 , • • • , q m }.

Given a dataset T , a keyword query Q, and a positive integer k as the size bound, a dataset snippet is an optimum subset of triples selected from T , denoted by S ⊆ T , satisfying |S| ≤ k. We will give our definition of optimality in Section 3.

Evaluation Metrics

We briefly review the four metrics proposed in [7] for evaluating the quality of a dataset snippet S: coKyw, coCnx, coSkm, and coDat, all in the range of [0, 1].

Coverage of Query Keywords (coKyw). A resource r covers a keyword q if r's textual form (e.g., rdfs:label of an IRI or blank node, lexical form of a literal) contains a keyword match for q. A triple t covers a keyword q, denoted by t ≺ q, if r covers q for any r ∈ {t s , t p , t o }. For a snippet S, the coKyw metric evaluates its coverage of query keywords:

coKyw(S) = 1 |Q| • |{q ∈ Q : ∃t ∈ S, t ≺ q}| .(1)

Coverage of Connections between Query Keywords (coCnx). A snippet S covers the connection between two keywords q i , q j ∈ Q, denoted by S ≺ (q i , q j ), if there is a path in the RDF graph representation of S that connects two resources: one covering q i and the other covering q j . For S, the coCnx metric evaluates its coverage of connections between query keywords:

coCnx(S) = 1 ( |Q| 2 ) • |{{q i , q j } ⊆ Q : q i = q j and S ≺ (q i , q j )}| if |Q| > 1 , coKyw(S) if |Q| = 1 .

(

)2

When there is only one keyword, coCnx is meaningless and we set it to coKyw. Coverage of Data Schema (coSkm). Consider the RDF schema of a dataset. The relative frequency of a class c observed in a dataset T is

frqCls(c) = |{t ∈ T : t p = rdf:type and t o = c}| |{t ∈ T : t p = rdf:type}| .(3)

Analogously, the relative frequency of a property p observed in T is

frqPrp(p) = |{t ∈ T : t p = p}| |T | . (4)

For a snippet S, its coverage of the schema of T is the harmonic mean (hm) of the total relative frequency of the classes and properties it contains:

coSkm(S) = hm( c∈Cls(S) frqCls(c), p∈Prp(S) frqPrp(p)) ,(5)

where Cls(S) is the set of classes instantiated in S and Prp(S) is the set of properties instantiated in S.

Coverage of Data (coDat). Central entities represent the key content of a dataset. Let d + (e) and d − (e) be the out-degree and in-degree of an entity e in the RDF graph representation of a dataset T , respectively. For a snippet S, its coverage of the entities in T is the harmonic mean (hm) of the mean normalized out-degree and in-degree of the entities it contains: ) ,

where Ent(X) is the set of entities that appear in a set of triples X.

Approach

Given the evaluation metrics presented in Section 2.2, a straightforward idea is to formulate the selection of RDF triples as a combinatorial optimization problem, and directly optimize these evaluation metrics. Our current work considers three metrics: coKyw, coSkm, and coDat, leaving coCnx as future work. The three selected metrics all require a snippet to cover some elements: query keywords in coKyw, classes and properties in coSkm, and entities in coDat. Furthermore, the classes, properties, and entities to cover are with different weights. It inspires us to formulate an instance of the weighted maximum coverage problem. We formalize this idea in Section 3.1, and present a solution in Section 3.2.

Algorithm 1 Greedy Algorithm

Input: A dataset T , a keyword query Q, and a size bound k Output: An optimum dataset snippet S ⊆ T 1: S ← ∅; 2: while |S| < k do 3: t * ← argmax t∈(T \S) (q(S ∪ {t}) − q(S)); 4:

S ← S ∪ {t * }; 5: end while 6: return S;

Snippet Generation as Weighted Maximum Coverage

Weighted Maximum Coverage. Given a collection of sets, a weighted maximum coverage (WMC) problem is to select a limited number of sets from the collection such that the total weight of the covered elements is maximized.

Snippet Generation as WMC. We formulate the generation of an optimum dataset snippet as an instance of the WMC problem. Each RDF triple t i ∈ T corresponds to a set denoted by cov(t i ) which consists of: the query keywords covered by t i , the class instantiated in t i , the property instantiated in t i , and the entities that appear in t i . The universe of elements is denoted by

Ω = Q ∪ Cls(T ) ∪ Prp(T ) ∪ Ent(T ) .(7)

Each element x ∈ Ω has a non-negative weight:

w(x) =            α • 1 |Q| x ∈ Q , β • frqCls(x) x ∈ Cls(T ) , β • frqPrp(x) x ∈ Prp(T ) , γ • ( log(d + (x)+1) e∈Ent(T ) log(d + (e)+1) + log(d − (x)+1) e∈Ent(T ) log(d − (e)+1) ) x ∈ Ent(T ) ,(8)

In our experiments, we set α = 2, β = 1, γ = 1, to balance between the coverage of query keywords in coKyw (α), the coverage of classes and properties in coSkm (β), and the coverage of entities in coDat (γ) in our objective function.

An optimum dataset snippet S ⊆ T is one that maximizes q(S) =

x∈ t i ∈S cov(ti) w(x) , subject to |S| ≤ k , (9)

where k is a predefined size bound, and q(•) is the objective function.

Solution

Algorithm 1 presents the greedy algorithm for the WMC problem which at each stage chooses a set that contains the maximum weight of uncovered elements. It achieves an approximation ratio of 1 − 1 e . Assuming q(S ∪ {t}) − q(S) is computed in O(1), the overall running time of a naive implementation of the algorithm is O(k • n), where n is the number of RDF triples in T . A more efficient implementation may use a priority queue to hold candidate triples, which is left as our future work.

Evaluation

Our evaluation reused the 387 query-dataset pairs in [7] where datasets were collected from DataHub and queries included 42 real queries submitted to data.gov.uk and 345 artificial queries comprising i category names in DMOZ referred to as DMOZ-i for i = 1, 2, 3, 4. We compared our proposed KSD with four baseline methods evaluated in [7], namely IlluSnip [2], TA+C [5], PrunedDP++ [6], and CES [4]. Following [7], we set k = 20, i.e., a snippet contained at most 20 triples.

Quality of Snippets

Table 1 presents the average scores of the four evaluation metrics over all the query-dataset pairs. Compared with the baselines, KSD achieved the highest overall score of 0.6211. In particular, its coverage of schema (coSkm = 0.8651) and data (coDat = 0.4247) were at the top. Its coverage of query keywords (coKyw = 0.8352) was close to TA+C, PrunedDP++, and CES which are queryfocused methods. Therefore, KSD achieved a satisfying trade-off between these evaluation metrics. On the other hand, its coCnx score was not high because coCnx was not explicitly considered in our approach.

Table 2 breaks down the scores of KSD into groups of query-dataset pairs. The scores on different groups were generally consistent with each other, demonstrating the robustness of our approach. One exception was the very high coCnx score on DMOZ-1, due to Eq. ( 2) where coCnx = coKyw when |Q| = 1.

Running Time

We tested the running time of our approach on an Intel Core i7-8700K (3.70GHz) with 10GB memory for the JVM.

Among all the 387 query-dataset pairs, for 234 (60.47%) a dataset snippet was generated within 1 second, and for 341 (88.11%) one was generated within 10 seconds. The median time was 0.51 second, showing promising performance for practical use. In the worst case, it took 150 seconds to process a large dataset containing more than 2 million RDF triples. Future work would be needed to improve the performance of our implementation to handle large datasets.

Conclusion and Future Work

In this ongoing work, we proposed KSD, a new approach to generating snippets for dataset search. By directly optimizing three evaluation metrics, KSD outperformed four baselines. It has established new state-of-the-art results for future work. We are working towards a full version of KSD which will also optimize coCnx. We will implement our approach in a prototype of a new dataset search engine, to help users conveniently judge the relevance of a retrieved dataset.

There are limitations in our work. First, the current version of KSD has considered three metrics but we exclude coCnx. The other three metrics are all about covering some elements with selected RDF triples, whereas coCnx is related to graph connectivity. The weighted maximum coverage problem seems not expressive enough to model coCnx. We will explore other possibilities. Second, although the running time of our current implementation is acceptable in most cases, its performance is not satisfying on large datasets. We will consider using priority queue and appropriate indexes to make the generation process faster.