Similarity joins and clustering for SPARQL

2.1.RDF and SPARQL

RDF is the standard graph-based data model for the Semantic Web. RDF terms can be either IRIs (I), literal values (L) or blank nodes (B). An RDF triple is a tuple (s,p,o)∈IB×I×IBL,22 where s is referred to as the subject, p as the predicate, and o as the object. A finite set of RDF triples makes an RDF graph.

SPARQL is the W3C standard query language for RDF [15]. The semantics of SPARQL operators are introduced by Pérez et al. [34], in terms of their evaluation over an RDF graph. The result of the evaluation of a SPARQL query is a set of solution mappings. Let V denote a set of query variables disjoint with IBL, a solution mapping is a partial function μ:V→IBL defined for a set of variables, called its domain, dom(μ). Two solution mappings μ1, μ2 are compatible, noted as μ1∼μ2, if for all v∈dom(μ1)∩dom(μ2), μ1(v)=μ2(v). Letting X and Y denote sets of solution mappings, the SPARQL algebra is defined as follows:

where f is a filter condition that, given a solution mapping, returns true, false, unbound or an error.

We denote the evaluation of a query Q over an RDF graph G as Q(G). Before defining Q(G), first let t=(s,p,o) denote a triple pattern, such that (s,p,o)∈VIL×VI×VIBL; then by vars(t) we denote the set of variables appearing in t and by μ(t) we denote the image of t under a solution mapping μ. Finally, we can define Q(G) recursively as follows:

2.2.Similarity search

In this section, we introduce the concept of similarity search over a universe of objects, as well as different similarity search operations.

Mathematically, similarity is modelled as a score. Let sx,y∈[0,1] be the similarity score between objects x and y, where the higher the score, the more similar x and y are. Similarity scores are often measured in terms of distances within a given space; two objects being more similar if the distance among them is small. In this work, we consider a class of distance functions called metrics:

Examples of metric distances are the Euclidean distance over real vectors, the edit distance over strings, and the Jaccard distance over sets.

Metric distances induce a topology over the set they are defined upon:

There are two main types of similarity search queries in metric spaces: range and nearest neighbours queries.

If instead of a single query object q we consider a set of query objects, we call this operation a similarity join. A similarity join is an operation defined over two comparable sets. Two sets are deemed comparable if a (metric) distance function can be defined over their Cartesian product.

Note that similarity search – also known as query-by-example – is a special case of similarity join where D2={y}. We may also refer to the special case of self similarity joins where D1=D2.

3.1.Similarity joins

The brute force method for computing a similarity join between D1 and D2 is called a nested loop, which computes for each x∈D1 the distance to each y∈D2, returning pairs that satisfy the similarity condition, thus performing |D1|·|D2| distance computations (or |D1|·|D2|/2 if it is a symmetric distance). For similarity joins over metric spaces, three strategies improve upon the brute force method: indexing, space partitioning, and/or approximation.

A common way to optimise similarity joins is to index the data using tree structures that divide the space in different ways (offline), then pruning distant pairs of objects from comparison (online). Several tree structures have been proposed as indexes for optimising similarity queries [14,31,41]. Among such approaches, we can find vantage-point Trees (vp-Trees) [48], which make recursive ball cuts of space centred on selected points, attempting to evenly distribute objects inside and outside the ball. vp-Trees have an average-case query-by-example search time of O(nα) on n objects, where 0⩽α⩽1 depends on the distance distribution and dimensionality of the space, among other factors [27], thus having an upper bound of O(n2α) for a similarity join. Other tree indexes, such as the D-Index [6] and the List of Twin Clusters [33], propose to use clustering techniques over the data.

Other space partitioning algorithms are not used for indexing but rather for evaluating similarity joins online. The Quickjoin (QJ) algorithm [17] was designed to improve upon grid-based partition algorithms [3,5]; it divides the space into ball cuts using random data objects as pivots, splitting the data into the vectors inside and outside the ball, proceeding recursively until the groups are small enough to perform a nested loop. It keeps window partitions in the boundaries of the ball in case there are pairs needed for the result with vectors assigned to different partitions. QJ requires O(n(1+w)⌈logn⌉) distance computations, where w is the average fraction of elements within the window partitions. QJ was intended for range-based similarity joins and extending QJ to compute a k-nn similarity join appears far from trivial, since its simulation with a range-based join would force most of the data to fall within the window partitions, thus meaning that QJ will reach its quadratic worst case.

Another alternative is to apply approximations to evaluate the similarity joins, trading the precision of the results for more efficient computation. FLANN [26] is a library that provides several approximate k-nn algorithms based on randomised k-d-forests, k-means trees, locality-sensitive hashing, etc.; it automatically selects the best algorithm to index based, for example, on a target precision, which can be traded-off to improve execution time.

3.2.Similarity in databases

Though similarity joins do not form part of standard query languages, such as SQL or SPARQL, a number of systems have integrated variations of such joins within databases. In the context of SQL, DBSimJoin [43] implements a range-based similarity join operator for PostgreSQL. This implementation claims to handle any metric space, thus supporting various metric distances; it is based on the aforementioned index-free Quickjoin algorithm.

In the more specific context of the Semantic Web, a number of works have proposed online computation of similarity joins in the context of domain-specific measures. Zhai et. al [50] use OWL to describe the spatial information of a map of a Chinese city, enabling geospatial SPARQL queries that include the computation of distances between places. The Parliament SPARQL engine [1] implements an OGC standard called GeoSPARQL, which aside from various geometric operators, also includes geospatial distance. Works on link discovery may also consider specific forms of similarity measures [40], often string similarity measures over labels and descriptions [44].

Other approaches pre-materialise distance values that can then be incorporated into SPARQL queries. IMGpedia [8] pre-computes a k-nn self-similarity join offline over images and stores the results as part of the graph. Similarity measures have also been investigated for the purposes of SPARQL query relaxation, whereby, in cases where a precise query returns no or few results, relaxation finds queries returning similar results to those sought [16,30].

Galvin et al. [10] propose a multiway similarity join operator for RDF; however, the notion of similarity considered is based on semantic similarity that tries to match different terms referring to the same real-world entity. Closer to this work lies iSPARQL [20], which extends SPARQL with IMPRECISE clauses that can include similarity joins on individual attributes. A variety of distance measures are proposed for individual dimensions/attributes, along with aggregators for combining dimensions. However, in terms of evaluation, distances are computed in an attribute-at-a-time manner and input into an aggregator. For the multidimensional setting, a (brute-force) nested loop needs to be performed; the authors leave optimisations in the multidimensional setting for future work [20].

3.3.Clustering

Clustering is a process through which a set of objects can be automatically partitioned into groups – called clusters – such that the distance between objects of a cluster is minimised, and the distance between objects in different clusters is maximised. Clustering algorithms can be roughly divided into distance-based, density-based, grid-based, distribution-based, and can also be hierarchical. A prime example of distance-based clustering algorithms is k-means [24], which first randomly selects k centroids and assigns each object to the cluster defined by the closest centroid; it then recomputes new centroids as the mean objects of each current cluster (which may not be a part of the set of objects), and reassigns the objects to the clusters defined by these new centroids until the centroids converge. The k-medoids algorithm is similar to k-means [19], but instead of centroids, it defines medoids: the element of a cluster such that its distance to every other element in the cluster is minimal. As for density-based algorithms, DBSCAN [7] groups together objects in dense regions (every object has several neighbours), separated by low density, sparse regions. DBSCAN also marks isolated objects as outliers, which are not included in any cluster. Grid-based methods, such as STING [46] and GriDBSCAN [25] divide the space into cells, aiming to quickly find dense areas to produce the clusters, and prune sparse areas as noise. However, these methods have been proven to not scale well with increasing dimensions [53]. Distribution-based methods assume that objects in the same cluster have a similar probability distribution: DBCLASD [47] assumes that the points inside a cluster are uniformly distributed. Finally, hierarchy-based approaches generate clusters within clusters forming a hierarchy that can be consumed at various levels. Hierarchical clustering methods include BIRCH [52], CURE [13], and Chameleon [18].

3.4.Clustering in databases

In databases, Ordonez and Omiecinski [32] provide an efficient disk-based k-means implementation for RDBMS using SQL INSERT and UPDATE queries. Also in SQL, Zhang and Huang [51] propose to extend the query language with a CLUSTER BY keyword, however, they do not provide an implementation. Li et al. [22] propose to extend SQL with fuzzy criteria for grouping and ordering, which they call clustering and ranking; they provide syntax and semantics, as well as a C++ implementation of the ranking and clustering algorithms based on so-called summary grids that provide a more time-efficient evaluation. Silva et al. [42] propose a similarity based GROUP BY that clusters the query results in three ways: 1) by defining in the query a maximum element separation or maximum cluster diameter, 2) by defining the centroids around which the data is clustered to, and 3) by defining a set of limit or threshold values. They provide a PostgreSQL implementation of these three clustering options.

Qi et al. [37] provide a k-means implementation for RDF data by using SPARQL Update queries. Ławrynowicz [21], proposed an extension to SPARQL 1.0, that introduces a CLUSTER BY solution modifier along with a clear syntax and semantics; however, they do not include an implementation nor evaluation, and it is not immediately clear how their proposal could be aligned with SPARQL 1.1 grouping and aggregates.

4.1.Syntax

To define the syntax for a similarity join, it is necessary to consider the syntax of other binary operators such as OPTIONAL or MINUS [15], as well as the required extra parameters: the variables representing the dimensions with respect to which the distance is to be computed, the distance function to be used, a fresh variable to bind the computed distances to, and the similarity parameter corresponding to a threshold distance (for range similarity joins) or to a threshold number of nearest neighbours (for k-nn similarity joins).

The syntax for the similarity join operator extends the SPARQL 1.1 EBNF grammar [15] by adding one production rule for SimilarityGraphPattern, and extending the rule for GraphPatternNotTriples. All other definitions are left unchanged. The exact changes to the grammar can be found in Fig. 2.

Fig. 2.

The extended production rules from SPARQL 1.1 to support similarity joins.

The keyword ON is used to define the variables in both graph patterns upon which the distance is computed; the keywords TOP and WITHIN denote a k-nn query and an r-range query respectively; the keyword DISTANCE specifies the IRI of the distance function to be used for the evaluation of the join, whose result will be bound to the variable indicated with AS, which is expected to be fresh, i.e., to not appear elsewhere in the SimilarityGraphPattern, similarly to BIND. The syntax may be extended in the future to provide further customisation, such as supporting different normalisation functions, or to define default parameters.

Depending on the metric, it could be possible, in principle, to express such queries as plain SPARQL 1.1 queries, by taking advantage of features such as variable binding, numeric expressions, sub-selects, etc. However, there are two key advantages of the dedicated syntax: (1) similarity join queries in vanilla syntax would be complex to express, particularly in the case of k-nn queries or metrics without the corresponding numeric operators in SPARQL; (2) optimising queries written in the vanilla syntax (beyond nested-loop performance) would be practically infeasible, requiring an engine that can prove equivalence between the distance metrics and semantics for which similarity join algorithms are optimised and the plethora of ways in which they can be expressed in vanilla syntax. This is why we propose to make similarity joins for multidimensional distances a first class feature, with dedicated syntax and physical operators offering sub-quadratic performance in average/typical cases.

4.2.Semantics

We now introduce some definitions to extend the SPARQL semantics defined in Section 2 to cover the similarity joins whose syntax is defined in Section 4.1. These definitions adapt the standard definitions of similarity joins as presented in Section 2.2 to make them compatible with the relational algebra underlying SPARQL, i.e., to perform an equi-join on shared variables, and a similarity join on other variables selected by the user.

We start with the definition of a similarity join expression, which indicates the criteria under which the similarity of two SPARQL solution mappings can be computed.

In the following, we present several definitions that build up to the formal specification of our similarity join operators. We begin with a definition that, given two compatible solutions from either side of the similarity join μ1 and μ2, and given a set of paired variables V, produces a set of pairs of constants projected from the solutions over which distances can be computed.

Note that per this definition, ⟦V⟧μ2μ1=⟦V⟧μ1μ2.

Next we define some useful notation for the result of a natural equi-join (applying a join with equality on shared variables, i.e., based on compatible solutions) that forms the basis of our similarity join operator.

We denote by [μ1,…,μn]∈X1⋈⋯⋈Xn the condition that μ1∈X1, …, μn∈Xn, and μi∼μj (for 1⩽i⩽n, 1⩽j⩽n). Thus [μ1,…,μn] denotes a solution mapping ⋃i=1nμi for the natural equi-join X1⋈⋯⋈Xn.

Given a set of solutions, we now define notation for the union and intersection of the domains of the solutions (the sets of variables for which a solution is defined).

In order words, udom(X) is the set of variables that are defined by some solution mapping μ∈X, while idom(X) is the set of variables that are defined for all solution mappings μ∈X.

The next definition allows us to define a solution mapping that maps specific variables to specific SPARQL terms (similar to BIND). This will be used to bind the distance value to a specified (fresh) variable.

With all these definitions in hand, we introduce the similarity join operators in SPARQL as follows:

Per Definition 4.6, more than k results can be returned for μ1 in the rare case of ties in distance, which keeps the semantics of the k-nn similarity joins deterministic.

An error is returned when v∈udom(X)∪udom(Y) to emulate a similar behaviour to BIND in SPARQL.

Bag semantics are defined for similarity joins in the natural way, where the multiplicity of μ∈X⋈sY is defined to be the product of the multiplicities of the solutions μ1∈X and μ2∈Y that produce it.

Next, given the semantics of the similarity join operators, we present several algebraic properties for the similarity join and its relationship with other SPARQL operators. These properties and equivalences are useful for query planning and optimisation. For instance, having a commutative and associative operator can allow the Query Planner to choose the best possible order in which to evaluate a given sequence of these operators; similarly, having equivalences between operators under certain circumstances can allow for query rewriting and further optimisation. Particularly for the case of similarity joins, some rewriting rules can help to reduce the sets of intermediate solutions considerably before applying the similarity join, and thus reduce query execution time. The proofs for each of the claims along with some illustrative examples can be found in the Appendix:

A key finding here is that properties that hold for (equi) joins in SPARQL do not necessarily hold for similarity joins (commutativity, associativity, distributivity), and these equivalences show how and why this is the case. This means that common optimisations applied in SPARQL engines (such as join reordering) cannot be applied as is for similarity joins, and thus there are interesting open challenges on how to optimise these queries.

4.3.Implementation

The implementation of the similarity join operators extends ARQ – the SPARQL engine of Apache Jena33 – which indexes an RDF dataset and receives as input a (similarity) query in the syntax discussed in Section 4.1. The steps of the evaluation of an extended SPARQL query follow a standard flow, namely Parsing, Algebra Optimisation, Algebra Execution, and Result Iteration. The implementation is available at https://github.com/scferrada/jena.

The Parsing stage receives the query string written by a user, and outputs the algebraic representation of the similarity query. Parsing is implemented by extending the Parser of Jena using JavaCC,44 wherein the new keywords and syntax rules are defined, as introduced in Section 4.1. The result of the Parsing stage is an abstract syntax tree of algebraic operators, e.g., knnsimjoin(leftjoin(…), triplepattern(…)).

In terms of physical operators to evaluate the similarity joins, initially we considered applying offline indexing of literal values in the RDF graph in order to allow lookups of similar values. However, we discarded this option for the following two reasons:

For this reason, we rather consider online physical operators that receive two sets of solution mappings and compute the similarity join. Some of these physical operators include indexing techniques, but these indexes are built online – for a specific query – over intermediate solutions rather than the RDF graph itself.

The similarity join physical operators apply a normalisation function to each of the dimensions of the space, in order to avoid differences in scale of these dimensions to affect disproportionately the similarity of two solution mappings. For example, a similarity join query computing distances w.r.t. the dimensions human development index, HDI, (a number in [0,1]) and population (ranging from thousands to even millions), as defined, the HDI dimension would have a negligible effect on the results of the similarity join. However, as a future direction, we might provide special syntax to allow users to decide if the data should be automatically normalised or not.

Algebra Optimisation then applies static rewriting rules over the query, further turning logical operators (e.g., knnsimjoin) into physical operators. In terms of the physical operators, we implement three variants:

Algebra Execution begins to evaluate the physical operators chosen in the previous step, with low-level triple/quad patterns and path expression operators feeding higher-level operators. Finally, Result Iteration streams the final results from the evaluation of the top-level physical operator. All physical similarity-join operators follow the same lazy evaluation strategy used for the existing join operators in Jena.

Besides the implementation of sub-quadratic average-case similarity join physical operators, there are other avenues for query optimisation, namely: query rewriting and result caching. As for rewriting rules, there is little opportunity for applying such rules because of a) similarity joins are a relatively expensive operation to compute, thus the best option is to reduce the size of the outputs of the sub-operands as early as possible and therefore, making typical rewriting rules impractical (such as delaying filters and optionals); and b) we see in Section 4.2 that the k-nn similarity join operator is not commutative nor associative, further preventing rewriting such as join reordering.

4.4.Use-case queries

Back in Section 1, we presented some motivating example queries that can be written using our proposed extension to SPARQL over a small artificial dataset. Now, in this section, we present three use-case queries demonstrating different capabilities of the extension, which are based on real-world data from Wikidata [45] and IMGpedia [8]. All prefixes used in the queries of this paper are listed in Table 1.

Fig. 3.

Query for non-metal chemical elements similar to metallic elements in terms of atomic properties.

Similar chemicals Chemical elements contain several numeric/ordinal properties, such as boiling and melting point, mass, electronegativity and so on. In Fig. 3 we request for metals similar to non-metals in terms of those properties, along with sample results of the similar metal/non-metal query. Figure 3 also presents a selection of results of the query, where we see that Selenium is most similar to Aluminium, and Hydrogen to Sodium.

Fig. 4.

Query requesting countries that have a number of Literature, Chemistry, Physics and Medicine Nobel Prizes similar to those of Canada.

Similar laureates: Figure 4, presents a more complex similarity query over the Nobel Prize Linked Dataset55 to find the 10 countries that have the most similar number of Nobel Prize laureates in literature, chemistry, physics and medicine than Canada. Figure 4 also presents the query results.

Fig. 5.

Query for the 10 images of towers most similar to each image of the Entel Tower in terms of the HOG visual descriptor.

Similar images: Figure 5 presents a similarity query over IMGpedia [8]: a multimedia Linked Dataset. The query retrieves images of the Entel Tower in Chile, and computes a 10-nn similarity join for images of towers based on a precomputed Histogram of Oriented Gradients (HOG) descriptor, which extracts the distribution of edge directions of an image. Note that this query uses a different distance funtion IRI than the previous two, since variables ?hog1 and ?hog2 are bound to string serializations of vectors, and thus the function sim:manhattanvec deals with the parsing of such strings as well. The figure includes a sample of the results for one of the images of the Entel Tower (in index 0), showing for each similar image, the related Wikidata entity, its label, and the distance to the source image.

5.1.Syntax

In order to support clustering in SPARQL, we must first define its syntax and semantics in a way that a user can express the clustering variables, and the algorithms and their required parameters. Ławrynowicz [21] proposes the following extension for SPARQL 1.0 [36], where the cluster identifier is bound AS a fresh variable (cf. Fig. 6).

Fig. 6.

Syntactic extension to the SPARQL 1.0 grammar for clustering [21].

The first thing that can be noticed from the definition is that, since the extension was conceived for SPARQL 1.0, it lacks the definition of the GROUP BY solution modifier. The definition of a clustering solution modifier for SPARQL 1.1 needs to take into account the existence of GROUP BY, and how it shall interact with CLUSTER BY.

Since clustering is the similarity-based version of grouping (which is based on exact matching), one alternative is to make the modifiers CLUSTER BY and GROUP BY be mutually exclusive in a query. However, the two modifiers can be made compatible by defining the clustering modifier as binding the cluster identifier of each mapping to a fresh variable, potentially allowing users to later group the results by the identifier value; in other words, CLUSTER BY extends the solution mappings with an extra variable bound to a cluster identifier, rather than directly grouping them. This decision is made since any new operation included into a query language should be as non-disruptive as possible, and to preclude the usage of GROUP BY when clustering is indeed disruptive.

Since the CLUSTER BY solution modifier is not mutually exclusive with GROUP BY, CLUSTER BY does not interact with the HAVING clause and the different aggregators, which can rather be computed after the clustering takes place. Conversely, in order to apply clustering with respect to values computed through aggregation functions, the aggregation must be computed in a subquery. Thus, following the SPARQL spec, the order of the solution modifiers including CLUSTER BY is: clustering, grouping, having, ordering, projection, distinct, reduced, offset, and limit.

Ławrynowicz [21] makes use of the SPARQL Query Results Clustering Ontology (SQRCO) to define the clustering algorithm and its parameters as a set of triples in the query. However, at the time of writing, the ontology is not found on the Web and is not registered in prefix.cc. We instead take a syntax-based approach, using special keywords for the clustering configuration, similarly to what is done with the similarity join operator.

Our proposed extension of the SPARQL 1.1 syntax that includes CLUSTER BY is presented in Fig. 7. The extension adds a new production rule, ClusterByClause, as an alternative in the SolutionModifier production rule. We make use of the Extension Function framework defined for SPARQL 1.1 to allow users to define the desired clustering algorithm and its parameters by using an iriOrFunction rule after the keyword WITH, thus allowing the function to be called without any parameters as well, which permits to define default values for each supported algorithm. Finally, we provide syntax to define the fresh variable on which the cluster identifier shall be bound AS. We permit only variables to be used as clustering attributes, but expressions could be supported in a future version. Nevertheless, expressions could be indirectly used for clustering by using the BIND function.

Fig. 7.

Syntactic extension to the SPARQL 1.1 grammar for clustering.

An example of a SPARQL query that uses this extension can be appreciated in Fig. 8, where the countries available in Wikidata are clustered based on their life expectancy and economic growth. The query specifies that the clustering shall use k-means returning 4 clusters. Notice that we also obtain the 2-letter ISO code for each country (property wdt:P297) and we are able to project that variable even if it is not part of the CLUSTER BY variables.

Fig. 8.

Example SPARQL query with the CLUSTER BY solution modifier.

5.2.Semantics

Given the SPARQL semantics presented in Section 2, as well as the discussed syntax for CLUSTER BY, we now propose the semantics for the CLUSTER BY solution modifier, per the following definition.

5.3.Implementation

Analogous to the similarity join operators, we implement the CLUSTER BY solution modifier on top of Apache Jena’s ARQ, where the code is publicly available in the following repository: https://github.com/scferrada/jena. The implementation supports three clustering algorithms: k-means, k-medoids, and DBSCAN. These algorithms are currently implemented in-memory. All three algorithms use the Manhattan distance as the dissimilarity measure. All three algorithms enumerate the clusters in no particular order using natural numbers starting from 1, and use said numbers as the identifiers of the clusters. For k-medoids we implemented the FastPAM1 algorithm proposed by Schubert and Rousseeuw [38] which is O(k) faster than the naive algorithm and uses O(k) extra memory.

Each algorithm requires different parameters, but the implementation offers default values for them, if the user does not wish to specify them. The parameters of each algorithm and the chosen default values are:

DBSCAN is different from k-means and k-medoids in that it does not require the number of clusters to be specified, but also may mark some objects as outliers, not being in any cluster. To comply with the semantics of CLUSTER BY, it assigns all solution mappings marked as outliers to a special cluster (with identifier −1). Notice that the default parameters for DBSCAN result in all objects marked as outliers. The implementation of DBSCAN uses vp-Trees in order to improve performance, since for each element a range-based similarity search must be conducted.

Other clustering algorithms were not chosen for various reasons: both grid-based and distribution-based methods do not scale well when dimension increases [53]. Hierarchical clustering methods are left for future versions, because given the syntax and semantics of the clustering solution modifier, it would be hard to add multiple variables bound to different levels of clustering. An initial option to support these methods would be to force the user to choose a clustering level to retrieve, but we argue that in most cases, the user might not know which level of clustering is most significant for their purposes.

5.4.Use-cases

Expanding on the motivating example queries of Section 1 (see Fig. 1d–1e), we now showcase three queries that use the clustering solution modifier here proposed in different domains. First, in Fig. 9 we display the result of the query presented in Fig. 8, that clusters the countries in Wikidata with respect to their life expectancy and economic growth rate. Some results were omitted to avoid clutter in the figure. Each point has a different colour and marker depending on their assigned cluster (whose identifier is bound to variable ?c). It can be seen in this case that, since there are differences in the magnitudes of the values of life expectancy and economic growth rate, the largest values tend to weigh more in the distance value and thus, in this example, we see a stronger division along the vertical axis. To prevent that any given dimension has a disproportionate influence over the distance function, it is recommended to normalise each dimension before clustering. Additionally, we note that, unlike GROUP BY, we can keep and project any variables that are not part of the CLUSTER BY clause. In Fig. 9 we also present the 2-letter ISO code of each country (which is directly obtained from the query) annotating each point in the graph, so that the reader can know which countries belong to each cluster more easily.

Fig. 9.

Clusters of countries by growth and life expectancy.

Then, the Iris Dataset in RDF66 is used to run a clustering query on petal length and width. In Fig. 10 the extended SPARQL query that divides the objects into three clusters using the k-medoids algorithm is presented. Figure 11 shows the results of the clustering, where the green cluster is iris setosa, the blue cluster is mostly iris virginica, and the red cluster is mostly iris versicolor. Notice that the iris types can also be retrieved with the query.

Fig. 10.

Extended SPARQL query to obtain three clusters of iris.

Fig. 11.

Clusters obtained with query 10.

Next, we present a Hertzsprung–Russell (HR) diagram, that is used in astronomy to classify stars into main sequence, giants, white dwarfs, etc. HR diagrams have the normalised B–V Colour (a measure of the temperature or “brightness” of the star) on the X-axis, and MV (the absolute magnitude) on the Y-axis. To achieve this, we generate an RDF version of a real-world catalogue of stars.77 In Fig. 12 a sample of the generated data can be found. The full RDF data is available at https://github.com/scferrada/starsrdfdata. Then, we cluster the stars by their absolute magnitude (MV) and their B–V colour using DBSCAN, since the main sequence cluster is better obtained by density-based methods. We also filter in the query the stars that have a high parallax uncertainty (a measure of the chance that the distance of the star, and thus its magnitude, is incorrect), because these stars may have an unreliable magnitude measure and just add noise to the diagram. Since magnitude and colour have very different scales, we also apply min–max normalisation in two BIND clauses, and perform the clustering over the normalised data. The SPARQL query that represents this process can be found in Fig. 13. The plot of the result of the query can be seen in Fig. 14, where the central purple cluster represents stars in the main sequence, the top right blue and sky blue clusters represent the giant and super giant stars, and the bottom-left red cluster contains the white dwarfs.

Fig. 12.

Extract of the RDF data for stars.

Fig. 13.

SPARQL query for clustering star data.

Fig. 14.

Visual representation of the star clusters obtained with query from Fig. 13. Outliers not presented.

Finally, we showcase how the CLUSTER BY solution modifier can interact with GROUP BY in a SPARQL query. To do this, we modify the query from Fig. 8, which obtains the life expectancy and growth rate of the countries in Wikidata, to now GROUP BY cluster identifier and compute the average life expectancy and the minimum growth rate of each cluster. This query is presented in Fig. 15, and the results of its evaluation over Wikidata can be seen in Table 2 where cluster 1 corresponds to the dark blue cluster in Fig. 9, which includes Japan and Italy, and has the highest life expectancy and a minimum growth rate of 0.9%; cluster 2 is the pink cluster, which contains New Zealand and Chile; cluster 3 is the sky blue cluster, which includes Brazil and Bulgaria, and presenting the lowest growth rate at −18%; and cluster 4 is the red cluster, presenting the lowest life expectancy average.

Fig. 15.

Example SPARQL query with the CLUSTER BY solution modifier and GROUP BY.

6.1.Similarity join evaluation

We compare the performance of different physical operators for similarity joins in the context of increasingly complex SPARQL queries, as well as a comparison with the baseline system DBSimJoin. We conduct experiments with respect to two benchmarks: the first is a benchmark we propose for Wikidata, while the second is an existing benchmark used by DBSimJoin based on visual descriptors of images.

6.1.1.Wikidata: k-nn self-similarity queries

Extending the performance experimentation presented in our previous work [9], we now present similar experiments using real SPARQL queries. We use a truthy version of the Wikidata RDF dump.99 We start with SPARQL queries from the Wikidata query logs, and apply several filters: first, at least one numeric attribute must be projected in the SELECT clause; second, these numeric attributes must not be obtained in an OPTIONAL clause; third, they produce at least 8 solution mappings; and fourth, they are executed in less than 3 hours using Jena. We obtain 2,726 SPARQL queries. For each of these base queries, we wrote a k-nn self-similarity join version for our experiments.

We executed self-similarity joins with k∈{2,4,8}, and compare 3 different techniques: Nested Loops (NL), vp-Trees (VPT), and FLANN. We run the queries sequentially, to avoid caching. In Fig. 16 we present our findings, where we provide the execution time of the base query as a baseline for comparison. VPT perform the best in 2,841 out of 8,178 scenarios (34.7%), NL in 2,770 (33.9%), and FLANN in 2,567 (31.4%). NL tend to perform better when the number of solution mappings is relatively smaller, which makes sense, since building indices has an overhead cost. The mean set size of the cases where NL performs the best is 178 elements. FLANN tends to perform better, when the set is comparably larger (mean size of 2,155 elements). As VPT perform better in the majority of the times and provides an exact result it should be preferred for larger result sets, and NL for smaller result sets.

Fig. 16.

Execution time for self-similarity join queries, for different values of k.

6.1.2.Corel colour moments: Range similarity queries

The system proposed in this work is compared with the closest found in literature, DBSimJoin [43], a PostgreSQL extension that supports range-based similarity joins in metric spaces implementing the Quickjoin (QJ) algorithm. As DBSimJoin only supports range queries, it is to be compared with the vp-Tree implementation in Jena (Jena-vp). The DBSimJoin system was originally tested with synthetic datasets and with the Corel Colour Moments (CCM) dataset, which consists of 68,040 records of images, each described with 9 dimensions representing the mean, standard deviation and skewness for the colours (red, green and blue) of the pixels of the image. For CCM, the DBSimJoin paper only reports the effect of the number of QJ pivots on the execution time when r=1% of the maximum possible distance in the space [43]. Here, the comparison between the systems takes into account more general performance metrics, using CCM. The CCM dataset was converted to an RDF graph using a direct mapping.

To find suitable distances, we first compute a 1-nn self-similarity join, where we take the maximum 1-nn distance in the result: 5.9; this distance ensures that each object has at least one neighbour in a range-based query with r=5.9. Therefore, we compare the runtime of both systems with increasing values of r, using r=5.9 as an upper bound.

DBSimJoin is implemented and distributed an extension for PostgreSQL 8. When installed in the current hardware, it crashed with any similarity join query, because of the use of outdated I/O directives, making it impossible to re-run the experiments. Thus, we present the results previously reported [9] where we compare them with Jena-vp using the same dataset, the same queries, and the same hardware reported in [9]. Here, we provide extended discussion over these results, which are presented in Table 3. The execution time of DBSimJoin grows rapidly with r because of the quick growth of the size and number of window partitions in the QJ algorithm. DBSimJoin crashes with r⩾0.4 so results between 0.3 and 0.4 are included to illustrate the growth in runtime closer to the failing point. The runtime of Jena-vp increases slowly with r, where more tree branches need to be visited as the result-set size increases up to almost 400 million records. The implementation of Jena-vp does not crash with massive results because it fetches the bindings lazily: it obtains all pairs within distance r for a single object and returns them one by one, only computing the next batch when it runs out of pairs; on the other hand, QJ starts piling up window partitions that replicate the data at a high rate, thus causing DBSimJoin to crash. In Fig. 17 the execution times of DBSimJoin and vp-Jena are presented visually, along with a polynomial trend of order 2 that predicts the execution times for when DBSimJoin crashes. Notice that both axes are in logarithmic scale.

Considering range-based similarity joins, these results indicate that Jena-vp outperforms DBSimJoin in terms of efficiency (our implementation is faster) and scalability (our implementation can handle larger amounts of results).

Table 3

Execution times in seconds for range similarity joins over the CCM dataset

Distance	# of Results	DBSimJoin (s)	Jena-vp (s)
0.01	68,462	47.22	6.92
0.1	68,498	84.00	7.45
0.3	72,920	775.96	9.63
0.39	92,444	1,341.86	11.17
0.4	121,826	–	11.30
1.0	4,233,806	–	35.01
5.9	395,543,225	–	1,867.86

Fig. 17.

Execution time of range-based self-similarity joins, including polynomial trend line for DBSimJoin times beyond r=0.4.

6.2.Clustering experimental results

To gain insight on the performance of the clustering solution modifier, we measure the overhead produced by the clustering algorithms. To achieve this, we prepared 1,000 synthetic SPARQL queries that draw values from the numeric properties of Wikidata. The queries are composed of only one Basic Graph Pattern (BGP), and we apply clustering over its solutions. To produce these queries, we begin with some data exploration. Specifically, from a Wikidata dump, we compute the ordinal/numeric characteristic sets [28] by: (1) filtering triples with properties that do not take numeric datatype values, or that take non-ordinal numeric datatype values (e.g., Universal Identifiers); (2) extracting the characteristic sets of the graph [28] along with their cardinalities, where, specifically, for each subject in the resulting graph, we extract the set of properties for which it is defined, and for each such set, we compute for how many subjects it is defined. Finally, we generate CLUSTER BY queries from 1,000 ordinal/numeric characteristic sets containing more than 3 properties that were defined for at least 500 subjects.

Then, we execute these queries with different parameters, in order to compare the execution time of the three implemented algorithms under various realistic configurations. These parameters are:

We use as a baseline the execution time of the query that COUNTs the results of the underlying BGP of each benchmark query, so as to measure the overhead produced by the CLUSTER BY operators.

Fig. 18.

Execution time of the CLUSTER BY queries using k-means clustering.

In Fig. 18, we present the results for the queries using the k-means algorithm. We use same-coloured lines for runs with the same value of k, and different dashing for different values of m. The baseline is shown with the light green line. We observe that the execution time increases as the value of k and n increases, and that the value of m does not significantly influence the execution time. This is expected, since k-means has an upper bound time complexity of O(knm) distance computations. However, k-means can terminate before m iterations if the clusters have converged.

The results for the queries using DBSCAN are harder to interpret, as the execution time also depends on the distance distribution of the space defined by the solution mappings obtained from evaluating each BGP. This is because DBSCAN’s cost depends on the cost of performing ε-range searches, and on the number of found neighbours. This can be noticed in Fig. 19, which presents a plot where queries with the same value for ε are shown in the same colour, and queries with the same value for p are shown with the same line dashing. The baseline is shown with the light green line. In Fig. 19, we observe unpredictable changes in the magnitude of the execution time, even for queries with a similar n. This can also be explained by the fact that we use fixed values of ε for this evaluation instead of using distance values depending on the metric space derived from the query evaluation, as it is recommended [39]. Notice that normalisation of the underlying metric space would not guarantee more consistent results, as the cost of DBSCAN depends on the distance distribution of the space. Nevertheless, queries with a larger ε and a smaller p tend to take more time. For these results, we marked queries taking more than 3 hours as timeouts, and thus not reported in the graph. This leads to most queries with ε=1 to not be included.

Fig. 19.

Execution time of the CLUSTER BY queries using DBSCAN clustering.

Fig. 20.

Execution time of the CLUSTER BY queries using k-medoids clustering.

k-medoids is the costliest clustering algorithm of the three, as it minimises intra-cluster distance while maximising inter-cluster distance. Since the implementation requires to compute all pairwise distances first, O(n2) memory is required, with an extra memory of O(k) used by the FASTPAM algorithm [38]. This memory requirement resulted in queries with n larger than 5,584 to fail with out of memory errors. In Fig. 20, we present the execution times for those queries that finished successfully. It can be noticed that k-medoids takes much longer to execute than the underlying query, and around four orders of magnitude more time than k-means. For k=16, queries with n>2908 take longer than 12 hours and were manually cancelled and therefore not reported.

Given these experimental results, we can argue that the preferred way to cluster query results would be to use k-means, which shall have a similar execution time as the underlying query. Moreover, the k-medoids clustering algorithm should be avoided given its intensive memory and time usage. For the case of DBSCAN, it is necessary to be familiar with the vector space that is being generated, and carefully choose the parameters, for which we refer to the recommendations of Schubert et al. [39], of using p=2·d, where d is the dimensionality of the space, and ε as the “elbow” value in a graph of the distance of each object to its 2d−1-nearest neighbour.