1.4.1 Open data

Open data is data that can be accessed equally by people and machines. Its definition is grounded in principles that assert what conditions data must meet to achieve legal and technical openness. Principles of open data are perhaps best embodied in the Open Definition (Open Knowledge 2015) and the Eight principles of open government data (2007). According to the Open Definition’s summary, “open data and content can be freely used, modified, and shared by anyone for any purpose.”² The Eight principles of open government data draw similar requirements as the Open Definition and add demands for completeness, primacy, and timeliness.

Open data is particularly prominent in the public sector, since public sector data is subject to disclosure mandated by law. Open data can be a result of either reactive disclosure, such as upon Freedom of Information requests, or proactive disclosure, such as by publishing open data. In case of the EU, disclosure of public sector data is regulated by the directive 2013/37/EU on the re-use of public sector information (EU 2013).

While releasing open data is frequently framed as a means to improve transparency of the public sector, it can also have a positive effect on its efficiency (Access Info Europe and Open Knowledge Foundation 2011, p. 69), since the public sector itself is often the primary user of open data. Using open data can help streamline public sector processes (Parycek et al. 2014, p. 90) and curb unnecessary expenditures (Prešern and Žejn 2014, p. 4). The publication of public procurement data is claimed to improve “the quality of government investment decision-making” (Kenny and Karver 2012, p. 2), as supervision enabled by access to data puts a pressure on contracting authorities to follow fair and budget-wise contracting procedures. Matchmaking public contracts to relevant suppliers can be considered an application of open data that can contribute to better-informed decisions leading to more economically advantageous contracts.

Open data can help balance information asymmetries between participants of public procurement markets. The asymmetries may be caused by clientelism, siloing data in applications with restricted access, or fragmentation of data across multiple sources. Open access to public procurement data can increase the number of participants in procurement, since more bidders can learn about relevant opportunities if they are advertised openly. Even distribution of open data may eventually lead to better decisions of the market participants, thereby increasing the efficiency of resource allocation in public procurement.

Open data addresses two fundamental problems of recommender systems, which apply to matchmaking as well. These problems comprise the cold start problem and data sparseness, which can be jointly described as the data acquisition problem (Heitmann and Hayes 2010). Cold start problem concerns the lack of data needed to make recommendations. It appears in new recommender systems that have yet to acquire users to amass enough data to make accurate recommendations. Open data ameliorates this problem by allowing to bootstrap a system from openly available datasets. In our case, we use open data from business registers to obtain descriptions of business entities that have not been awarded a contract yet, in order to make them discoverable for matchmaking. Data sparseness refers to the share of missing values in a dataset. If a large share of the matched entities is lacking values of the key properties leveraged by matchmaking, the quality of matchmaking results deteriorates. Complementary open datasets can help fill in the blank values or add extra features (Di Noia and Ostuni 2015, p. 102) that improve the quality of matchmaking.

The hereby presented work was done within the broader context of the OpenData.cz³ initiative. OpenData.cz is an initiative for a transparent data infrastructure of the Czech public sector. It advocates adopting open data and linked data principles for publishing data on the Web. Our contributions described in Section 2 enhance this infrastructure by supplying it with more open datasets and improving the existing ones.

1.4.2 Linked data

Linked data is a set of practices for publishing structured data on the Web. It is a way of structuring data that identifies entities with Internationalized Resource Identifiers (IRIs) and materializes their relationships as a network of machine-processable data (Ayers 2007, p. 94). IRIs are universal, so that any entity can be identified with a IRI, and have global scope, therefore an IRI can only identify one entity (Berners-Lee 1996). A major manifestation of linked data is the Linking Open Data Cloud (Abele et al. 2017), which maps the web of semantically structured data that spans hundreds of datasets from diverse domains, such as health care or linguistics. In this section we provide a basic introduction to the key aspects of linked data that we built on in this dissertation. A more detailed introduction to linked data in available in Heath and Bizer (2011).

Linked data may be seen as a pragmatic implementation of the so-called semantic web vision. It is based on semantic web technologies. This technology stack is largely built upon W3C standards.⁴ The fundamental standards of the semantic web technology stack, which are used throughout our work, are the Resource Description Framework (RDF), RDF Schema (RDFS), and SPARQL.

@prefix contract: <http://linked.opendata.cz/resource/isvz.cz/contract> .
          @prefix dcterms:  <http://purl.org/dc/terms/> .
          @prefix pc:       <http://purl.org/procurement/public-contracts#> .
          
          contract:60019151 a pc:Contract ;
            dcterms:title "Poskytnutí finančního úvěru"@cs,
                          "Financial loan provision"@en ;
            pc:contractingAuthority business-entity:CZ00275492 .

SELECT DISTINCT ?class
          WHERE {
            [] a ?class .
          }
          ORDER BY ?class

1.5.1 Legal context

Public procurement is a domain governed by law. We are focused on the Czech public procurement, for which there are two primary sources of relevant law, including the national law and the EU law. Public procurement in the Czech Republic is governed by the act no. 2016/134 (Czech Republic 2016). Czech Republic, as a member state of the European Union, harmonises its law with EU directives, in particular the directives 2014/24/EU (EU 2014a) and 2014/25/EU (EU 2014b) in case of public procurement. The first directive regulates public procurement of works, supplies, or services, while the latter one regulates public procurement of utilities, including water, energy, transport, and postal services. The act no. 2016/134 transposes these directives into the Czech legislation. Besides legal terms and conditions to harmonize public procurement in the EU member states, these directives also define standard forms for EU public procurement notices,⁵ which constitute a common schema of public notices. The directives design Tenders Electronic Daily (“Supplement to the Official Journal”)⁶ to serve as the central repository of public notices conforming to the standard forms.

In an even broader context, the EU member states adhere to the Agreement on Government Procurement (GPA)⁷ set up by the World Trade Organization. GPA mandates the involved parties to observe rules of fair, transparent, and non-discriminatory public procurement. In this way, the agreement sets basic expectations facilitating international public procurement.

Legal regulation of public procurement has important implications for matchmaking, including explicit formulation of demands, their proactive disclosure, desire for conformity, and standardization. Public procurement law requires explicit formulation of demands in contract notices to ensure a basic level of transparency. In most markets only supply is described explicitly, such as through advertising, while demand is left implicit. Since matchmaking requires demands to be specified, public procurement makes for a suitable market to apply the matchmaking methods.

There is a legal mandate for proactive disclosure of contract notices. Public contracts that meet the prescribed minimum conditions, including thresholds for the amounts of money spent, must be advertised publicly (Graux and Tom 2012, p. 7). Moreover, since public contracts in the EU are classified as public sector information, they fall within the regime of mandatory public disclosure under the terms of the Directive on the re-use of public sector information (EU 2013). In theory, this provides equal access to contract notices for all members of the public without the need to make requests for the notices, which in turn helps to enable fair competition in the public procurement market. In practice, the disclosure of public procurement data is often lagging behind the stipulations of law.

Overall, public procurement is subject to stringent and complex legal regulations. Civil servants responsible for public procurement therefore put a strong emphasis on legal conformance. Moreover, contracting authorities strive at length to make evaluation of contract award criteria incontestable in order to avoid protracted appeals of unsuccessful bidders that delay realization of contracts. Consequently, representatives of contracting authorities may exhibit high risk aversion and desire for conformity at the cost of compromising economical advantageousness. For example, the award criterion of lowest price may be overused because it decreases the probability of an audit three times, even though it often leads to inefficient contracts, as observed for the Czech public procurement by Nedvěd et al. (2017). Desire for conformity can explain why not deviating from defaults or awarding popular bidders may be perceived as a safe choice. In effect, this may imply there is less propensity for diversity in recommendations produced via matchmaking. On the one hand, matchmaking may address this by trading in improved accuracy for decreased diversity in matchmaking results. On the other hand, it may intentionally emphasize diversity to offset the desire for conformity.

Finally, legal regulations standardize the communication in public procurement. Besides prescribing procedures that standardize how participants in public procurement communicate, it standardizes the messages exchanged between the participants. Contracting authorities have to disclose public procurement data following the structure of standard forms for contract notices. The way in which public contracts are described in these forms is standardized to some degree via shared vocabularies and code lists, such as the Common Procurement Vocabulary (CPV) or the Nomenclature of Territorial Units for Statistics (NUTS). Standardization is especially relevant in the public sector, since it is characterized by “a variety of information, of variable granularity and quality created by different institutions and represented in heterogeneous formats” (Euzenat and Shvaiko 2013, p. 12).

Standardization of data contributes to defragmentation of the public procurement market. Defragmentation of the EU member states’ markets is the prime goal of the EU’s common regulatory framework. It aims to create a single public procurement market that enables cross-country procurement among the member states. Standardization simplifies the reuse of public procurement data by third parties, such as businesses or supervisory public bodies. Better reuse of data balances the information asymmetries that fragment the public procurement market.

Nevertheless, public procurement data is subject to imperfect standardization, which introduces variety in it. The imperfect standardization is caused by divergent transpositions of EU directives into the legal regimes of EU member states, lack of adherence to standards, underspecified standards leaving open space for inconsistencies, or meagre incentives and sanctions for abiding by the standards and the prescribed practices. Violations of the prescribed schema, lacking data validation, and absent enforcement of the mandated practices of public disclosure require a large effort from those wanting to make effective use of the data. For example, tasks such as search in aggregated data or establishing the identities of economic operators suffer from data inconsistency. Moreover, public procurement data can be distributed across disparate sources providing varying level of detail and completeness, such as in public profiles of contracting authorities and central registers. Fragmentation of public procurement data thus requires further data integration in order for the consumer to come to a unified view of the procurement domain that is necessary for conducting fruitful data analyses. In fact, one of the reasons why the public procurement market is dominated by large companies may be that they, unlike small and medium-sized enterprises, can afford the friction involved in processing the data.

According to our approach to data preparation, linked data provides a way to compensate the impact of imperfect standardization. While a standard can be defined as “coordination mechanism around non-proprietary knowledge that organizes and directs technological change” (Gosain 2003, p. 18), linked data enables to cope with insufficient standardization by allowing for “cooperation without coordination” (Wood 2011, p. 5) or without centralization. Instead, linked data bridges local heterogeneities via the flexible data model of RDF and explicit links between the decentralized data sources. We describe our use of linked data in detail in Section 2.

1.5.2 Economic context

Public procurement constitutes a large share of the volume of transactions in the economy. The share of expenditures in the EU member states’ public procurement on works, goods, and services (excluding utilities) was estimated to be “13.1 % of the EU GDP in 2015, the highest value for the last 4 years” (European Commission 2016). This estimate amounted to 24.2 billion EUR in 2015 in the Czech Republic, which translated to 14.5 % of the country’s GDP (European Commission 2016). Compared with the EU, the Czech Republic exhibits consistent above-average values of this indicator, as can be seen in Fig. 1.

The large volume of transactions in public procurement gives rise to economies of scale, so that even minor improvements can accrue substantial economic impact, since the scale of operations in this domain provides ample opportunity for cost savings. Publishing open data on public procurement as well as using matchmaking methods can be considered among the examples of such improvements, which can potentially increase the efficiency of resource allocation in the public sector, as mentioned in Section 1.4.1.

Due to the volume of the public funds involved in public procurement, it is prone to waste and political graft. Wasteful spending in public procurement can be classified either as active waste, which entails benefits to the public decision maker, or as passive waste, which does not benefit the decision maker. Whereas active waste may result from corruption or clientelism, passive waste proceeds from inefficiencies caused by the lack of skills or incentives. Although active waste is widely perceived to be the main problem of public procurement, a study of the Italian public sector (Bandiera et al. 2009, p. 1282) observed that 83 % of uneconomic spending in public procurement can be attributed to passive waste. We therefore decided to focus on optimizing public procurement where most impact can be expected. We argue that matchmaking can help improve the public procurement processes cut down passive waste. It can assist civil servants by providing relevant information, thus reducing the decision-making effort related to public procurement processes. We identified several use cases in public procurement where matchmaking can help.

1.5.3 Use cases for matchmaking

Matchmaking covers the information phase of market transaction (Schmid and Lindemann 1998, p. 194) that corresponds to the preparation and tendering stages in public procurement life-cycle (Nečaský et al. 2014, p. 865). During this phase “participants to the market seek potential partners” (Di Noia et al. 2004), so that public bodies learn about relevant bidders and companies learn about relevant open calls. In this sense, demands for products and services correspond to information needs and the aim of matchmaking is to retrieve the information that will satisfy them. Several use cases for matchmaking follow from the public procurement legislation according to the procedure types chosen for public contracts, such as:

1. Matching bidders to suitable contracts to apply for in open procedures
2. Matching relevant bidders that contracting authorities can approach in closed procedures
3. Matching similar contracts to serve as models for a new contract

The following use cases are by no means intended to be comprehensive. They illustrate the typical situations in which matchmaking can be helpful.

Public procurement law defines types of procedures that govern how contracting authorities communicate with bidders. In particular, procedure types determine what data on public contracts is published, along with specifying who has access to it and when it needs to be made available. The procedure types can be classified either as open or as restricted. Open procedures mandate contracting authorities to disclose data on contracts publicly, so that any bidders can respond with offers. In this case, contracting authorities do not negotiate with bidders and contracts are awarded solely based on the received bids. Restricted procedures differ by including an extra screening step. As in open procedures, contracting authorities announce contracts publicly, but bidders respond with expression of interest instead of bids. Contracting authorities then screen the interested bidders and send invitations to tender to the selected bidders.

The chosen procedure type determines for which users is matchmaking relevant. Bidders can use matchmaking both in case of open and restricted procedures to be alerted about the current business opportunities in public procurement that are relevant to them. Contracting authorities can use matchmaking in restricted procedures to get recommendations of suitable bidders. Moreover, in case of the simplified under limit procedure, which is allowed in the Czech Republic for public contracts below a specified financial threshold, contracting authority can approach bidders directly. In such case, at least five bidders must be approached according to the act no. 2016/134 (Czech Republic 2016). In that scenario, matchmaking can help recommend appropriate bidders to interest in the public contract. There are also other procedure types, such as innovation partnership, in which matchmaking is applicable to a lesser extent.

An additional use case for similarity-based retrieval employed by matchmaking may occur during contract specification. The Czech act no. 2016/134 (Czech Republic 2016) suggests contracting authorities to estimate contract price based on similar contracts. In order to address this use case, based on incomplete descriptions of contracts matchmaking can recommend similar contracts, the actual prices of which can help estimate the price of the formulated contract.

1.6.1 Case-based reasoning

Case-base reasoning (CBR) is a problem solving methodology that learns from experiences of previously solved problems, which are called cases (Richter and Weber 2013, p. 17). A case consists of a problem specification and a problem solution. Experiences described in cases can be either positive or negative. Positive experiences propose solutions to be reused, whereas the negative ones indicate solutions to avoid. For example, experiences may concern diagnosing a patient and evaluating the outcome of the diagnosis, which may be either successful or unsuccessful. Cases are stored and organized in a case base, such as a database. Case base serves as a memory that retains the experiences to learn from.

The workings of CBR systems can be described in terms of the CBR cycle (Kolodner 1992). The cycle consists of four principal steps a CBR system may iterate through:

1. Retrieve
2. Reuse
3. Revise
4. Retain

In the Retrieve step a CBR system gets cases similar to the query problem. Case bases are thus usually built for efficient similarity-based retrieval. Since descriptions of cases are often complex, computing their similarity may involve determining and weighting similarities of their individual features. For each use case and each feature a different similarity measure may be adopted, which allows to use pairwise similarity metrics tailored for particular kinds of data. This also enables assigning each feature a different weight, so that more relevant features may be emphasized. The employed metrics may be either symmetric or asymmetric. For example, we can use an asymmetric metric to favour lower prices over higher prices, even though their distance to the price in the query is the same. Since the similarity metrics allow fuzzy matches, reasoning in CBR systems is approximate. Consequently, as Richter and Weber argue, the characteristic that distinguishes CBR from deductive reasoning in logic or databases is that “it does not lead from true assumptions to true conclusions” (2013, p. 18).

A key feature of CBR is that similarity computation typically requires background knowledge. While similarity of cardinal features can be determined without it, nominal features call for additional knowledge to assess their degree of similarity. For instance, a taxonomy may be used to compute similarity as the inverse of taxonomic distance between the values of the compared feature. Since hand-coding background knowledge is expensive, and typically requires assistance of domain experts, CBR research considered alternatives for knowledge acquisition, such as using external semantics from linked open data or discovering latent semantics via machine learning.

The retrieved nearest neighbour cases serve as potential sources of a solution to the query problem. Solutions of these cases are copied and adapted in the Reuse step to formulate a solution answering the query. If a solved case matches the problem at hand exactly, we may directly reuse its solution. However, exact matches are rare, so the solutions to matching cases often need to be adapted. For example, solutions may be reused at different levels. We may either reuse the process that generated the solution, reuse the solution itself, or do something in between.

The reused solution is evaluated in the Revise step to assess whether it is applicable to the query problem. Without this step a CBR system cannot learn from its mistakes. It is the step in which CBR may add user feedback.

Finally, in the Retain step, the query problem and its revised and adopted solution may be incorporated in the case base as a new case for future learning. Alternatively, the generated case may be discarded if the CBR system stores only the actual cases.

The CBR cycle may be preceded by preparatory steps described by Richter and Weber (2013). A CBR system can be initialized by the Knowledge representation step, which structures the knowledge contained in cases the system learns from. Cases are explicitly formulated and described in a structured way, so that their similarity can be determined effectively. The simplest representation of a case is a set of feature-value pairs. However, using more sophisticated data structures is common. In order to compute similarity of cases, they must be described using comparable features, or, put differently, the descriptions of cases must adhere to the same schema.

Problem formulation is a preliminary step in which a query problem is formulated. A query can be considered a partially specified case. It may be either underspecified, such that it matches several existing cases, or overspecified, if it has no matches due to being too specific. Underspecified queries may require solutions from the matching cases to be combined, while overspecified queries may need to be relaxed or provided with partial matches.

Overall, the CBR cycle resembles human reasoning, such as problem solving by finding analogies. In fact, the CBR research is rooted in psychology and cognitive science. It is also similar to case law, which reasons from precedents to produce new interpretations of law. Thanks to these similarities, CBR is perceived as natural by its users (Kolodner 1992), which makes its function usually easy to explain.

CBR is commonly employed in recommender systems. Case-based recommenders are classified as a subset of knowledge-based recommenders (Jannach et al. 2010). Similarly to collaborative recommendation approaches, case-based recommenders exploit data about past behaviour. However, unlike collaborative recommenders, “the case-based approach enjoys a level of transparency and flexibility that is not always possible with other forms of recommendation” (Smyth 2007, p. 370), since it is based on reasoning with explicit knowledge. Our adaptation of CBR for matchmaking can be thus considered a case-based recommender.

1.6.2 Statistical relational learning

Statistical relational learning (SRL) is a subfield of machine learning that is concerned with learning from relational data. SRL learns models that “describe probability distributions \(P(\{X\})\) over the random variables in a relational domain” (Tresp and Nickel 2014, p. 1554). Here, \(X\) denotes a random variable and \(\{X\}\) refers to a set of such variables in a relational domain. The learned model reflects the characteristic patterns and global dependencies in relational data. Unlike inference rules, these statistical patterns may not be universally true, but have useful predictive power nonetheless. An example of such pattern is homophily (McPherson et al. 2001), which describes the tendency of similar entities to be related. A model created by SRL is used to predict probabilities of unknown relations in data. In other words, in SRL “the underlying idea is that reasoning can often be reduced to the task of classifying the truth value of potential statements” (Nickel et al. 2012, p. 271).

There are two basic kinds of SRL models: models with observable features and models with latent features. Our work focuses on the latent feature models. Unlike observable features, latent features are not directly observed in data. Instead, they are assumed to be the hidden causes for the observed variables. Consequently, results from machine learning based on latent features are usually difficult to interpret. Latent feature models are used to derive relationships between entities from interactions of their latent features (Nickel et al. 2016, p. 17). Since latent features correspond to global patterns in data, they can be considered products of collective learning.

Collective learning “refers to the effect that an entity’s relationships, attributes, or class membership can be predicted not only from the entity’s attributes but also from information distributed in the network environment of the entity” (Tresp and Nickel 2014, p. 1550). It involves “automatic exploitation of attribute and relationship correlations across multiple interconnections of entities and relations” (Nickel et al. 2012, p. 272). The exploited contextual information propagates through relations in data, so that the inferred dependencies may span across entity boundaries and involve entities that are more distant in a relational graph. Among other things, this feature of collective learning can help cope with modelling artefacts in RDF, such as intermediate resources that decompose n-ary relations into binary predicates.

Collective learning is a distinctive feature of SRL and is particularly manifest in “domains where entities are interconnected by multiple relations” (Nickel et al. 2011). Conversely, traditional machine learning expects data from a single relation, usually provided in a single propositional table. It considers only attributes of the involved entities, which are assumed to be mutually independent. This is one of the reasons that can explain why SRL was demonstrated to be able to produce superior results for relational data when compared to learning methods that do not take relations into account (Tresp and Nickel 2014, p. 1551). These results mark the importance of being able to leverage the relations in data effectively.

Nowadays the relevance of SRL grows as relational data becomes still more prevalent. In fact, many datasets have relational nature. For instance, vast amounts of relational data are produced by social networking sites. Relational data appears in many contexts, including relational databases, ground predicates in first order logic, or RDF.

Using relational datasets is nevertheless challenging, since many of them are incomplete or noisy and contain uncertain or false statements. Fortunately, SRL is relatively robust to inconsistencies, noise, or adversarial input, since it utilizes non-deterministic dependencies in data. Yet it is worth noting that even though SRL usually copes well with faulty data, systemic biases in the data will manifest in biased results produced by this method.

LOD is a prime example of a large-scale source of relational data afflicted with the above-mentioned ills. The open nature of LOD has direct consequences for data inconsistency and noisiness. These consequences make LOD challenging for reasoning and querying. While SRL can overcome these challenges to some extent, they pose a massive hurdle for traditional reasoning using inference based on description logic. Logical inference imposes strict constraints on its input, which are often violated in real-world data (Nickel et al. 2016, p. 28):

“Concerning requirements on the input data, it is quite unrealistic to expect that data from the open Semantic Web will ever be clean enough such that classical reasoning systems will be able to draw useful inferences from them. This would require Semantic Web data to be engineered strongly according to shared principles, which not only contrasts with the bottom-up nature of the Web, but is also unrealistic in terms of conceptual realizability: many statements are not true or false, they rather depend on the perspective taken.” (Hitzler and van Harmelen 2010, p. 42)

To compound matters further, reasoning with ontologies is computationally demanding, which makes it difficult to scale to the larger datasets in LOD. While we cannot guarantee most LOD datasets to be sound enough for reasoning based on logical inference, “it is reasonable to assume that there exist many dependencies in the LOD cloud which are rather statistical in nature than deterministic” (Nickel et al. 2012, p. 271). Approximate reasoning by SRL is well-suited to exploit these dependencies and to address the challenges inherent to LOD. This setup enables logical inference to complement SRL where appropriate. For example, results produced by logical inference can serve as gold standard for evaluation of SRL, such as in case of Nickel et al. (2012), who used rdfs:subClassOf inferences to evaluate a classification task.

We conceived matchmaking via SRL as a link prediction task. Link prediction is “concerned with predicting the existence (or probability of correctness) of (typed) edges in the graph” (Nickel et al. 2016, p. 14). In the context of knowledge graphs, such as LOD, link prediction is also known as knowledge graph completion (Nickel et al. 2016, p. 14). An example application of link prediction is discovery of protein interactions in bioinformatics. Typical cases of link prediction operate on multi-relational and noisy data, which makes the task suitable for SRL. In our case, we predict the link between a public contract and its awarded bidder.

1.7.1 Related applications

Early matchmaking dates back to the 1990s. Matchmakers proposed during that era often adopted reasoning with description logics (DL) and communication between software agents. An example of such approach is the work of Kuokka and Harada (1995), who used Knowledge Query and Manipulation Language (KQML) to describe messages exchanged between agents participating in matchmaking. However, without a common vocabulary the semantics of the messages had to be hardwired in application code.

A new wave of matchmaking based on DL arose with the semantic web initiative in the 2000s. These efforts employed then created ontological languages, such as the DARPA Agent Markup Language plus the Ontology Inference Layer (DAML+OIL) (González-Castillo et al. 2001), or the Web Ontology Language (OWL) (Di Noia et al. 2004, 2007), and approached matchmaking as a task for DL reasoning. Viewed in this way, matchmaking queries can be formulated as classes of matches and matches may thus be tested via subsumption or satisfiability of the class constraints. Such inferences can be produced by standard reasoners, such as RACER (Haarslev and Möller 2001). During this time, typical application domains for matchmaking included web service discovery (Trastour et al. 2011; Ankolekar et al. 2002) or e-commerce (Li and Horrocks 2004).

Using reasoners for matchmaking turned out to be problematic as their performance did not scale well for larger data. In time with the initial release of SPARQL in 2008 (Prud’hommeaux and Seaborne 2008) several efforts appeared that approached matchmaking via production rules implemented as database queries in SPARQL. The turn to SPARQL provided matchmaking with better performance and expressivity. An example of this approach was used in the Market Blended Insight project (Salvadores et al. 2008). While this project was concerned mostly with data preparation and feature extraction, basic matchmaking was included as its part, using SPARQL to discover the matches satisfying owl:onProperty constraints. Matchmaking was used as means of micro-segmentation to target specific agents exhibiting the propensity to buy. An RDF version of the Standard Industry Classification 1992 was used to determine similarity of the matched entities. A similar technique that combined SPARQL with RDFS entailment was explored in BauDataWeb (Radinger et al. 2013).⁸ BauDataWeb applied matchmaking to the European building and construction materials market. Similarity of the matched entities was determined via the FreeClassOWL taxonomy.⁹

Perhaps the first application of matchmaking in public procurement was conceived in the Spanish research project 10ders Information Services.¹⁰ Overall, this project aimed to design an interoperable architecture of a pan-European platform for aggregating and mediating public procurement notices in the EU. A part of the project that explored semantic web technologies in public procurement was called Methods on Linked Data for E-procurement Applying Semantics (MOLDEAS) (Alvarez-Rodríguez et al. 2012). MOLDEAS covered algorithms for enriching data about public procurement notices (Alvarez-Rodríguez et al. 2011c), integration of diverse data sources via linked data (Alvarez-Rodríguez et al. 2011a), and matchmaking via SPARQL enhanced with query expansion (Alvarez-Rodríguez et al. 2011b) or spreading activation (Alvarez-Rodríguez et al. 2013, p. 118). Unfortunately, it is difficult to compare the results matchmaking in MOLDEAS with our approach, because neither implementation details nor evaluation were revealed in the papers describing this work. The project emphasized product classification schemes and devoted extensive efforts to converting such classifications to RDF and linking them. Product Types Ontology (PTO),¹¹ a product ontology derived from Wikipedia, was selected as a linking hub to tie these classifications together.

10ders Information Services also involved Euroalert.net (Marín et al. 2013),¹² a commercial undertaking that alerts small and medium enterprises about relevant public sector information, including current public contracts. Euroalert.net generates alerts by matching the profiles of its subscribers to an incoming stream of published calls for tenders from Tenders Electronic Daily (TED).¹³ TED is an EU-wide register of public procurement that aggregates data about public contracts from the EU member states. According to the public description of Euroalert.net, its matchmaking is based on comparison of keywords and code lists and does not exploit semantics or linked open data.

While SPARQL improves on reasoning-based matchmaking in terms of better expressivity and performance, queries need to be restricted to exact matches for the most part in order to maintain a good runtime. A fundamental feature of matchmaking is ranking matches by the degree to which they satisfy a query. Exact matching, to the contrary, produces only matches and non-matches, without any way to rank the matches. Moreover, exact matches in SPARQL are optimized for structured data, so that performance degrades if SPARQL queries analyse semi-structured or unstructured data, such as literals, which may nevertheless supply valuable data to matchmaking. Concerns such as these led to the development of approaches to matchmaking that involved full-text search or machine learning.

A forerunner of this research direction was iSPARQL (Kiefer et al. 2007). iSPARQL extends SPARQL with similarity measures implemented using Apache Jena¹⁴ with custom property functions. In this way, it allows to combine graph pattern matching with similarity-based retrieval within a single query. While conceived as a general approach, it was also applied to matchmaking of web services (Kiefer and Bernstein 2008). This application coupled iSPARQL with machine learning in order to improve the detection of approximate matches. This use case demonstrated that the hybrid “combination of logical deduction and statistical induction produces superior performance over logical inference only” (Kiefer and Bernstein 2008, p. 473). Moreover, the similarity-based queries “that exploit textual information of the services turned out to be very effective” (Kiefer and Bernstein 2008, p. 475). Both these findings greatly influenced our approaches to matchmaking. For example, we leverage machine learning in the RESCAL-based matchmaking.

Another attempt to go beyond SPARQL was the initial matchmaker developed for the PC Filing App (Snoha et al. 2013) in the context of the LOD2 project.¹⁵ PC Filing App was a content management system for administering public contracts by contracting authorities. The matchmaker integrated in this application combined SPARQL, which retrieved the matches satisfying the declared hard constraints, with a custom Java implementation of similarity measures between the pre-filtered matches. While its second step enabled the matchmaker to leverage literals more effectively, the footprint of its in-memory implementation based on Java objects led to its poor performance. Our SPARQL-based matchmaker later replaced this matchmaker in the LOD2 project.

A related research effort that closely matches the objectives pursued by our work is the Web of Needs project (Kleedorfer et al. 2014). Its “overall goal is to create a decentralized infrastructure that allows people to publish documents on the Web which make it possible to contact each other” (Kleedorfer and Busch 2013). Web of Needs thus covers the entire distributed infrastructure for marketplaces on the Web with matchmaking being just one of its components. The infrastructure supports three principal tasks: describing supply or demand, identifying trading partners, and conducting a transaction (Kleedorfer et al. 2014). The proposed process overview involving these tasks, described in detail in Kleedorfer et al. (2016), includes online and offline matchmaking. The online matchmaking, which is capable of serving queries in real time, is implemented via full-text search in semi-structured data using Apache Solr.¹⁶ The offline matchmaking, which delivers results periodically as it processes queries in batches, is implemented using machine learning via RESCAL (Nickel et al. 2011). It thus closely resembles our matchmaker based on the same technology. Detailed evaluation of the offline matchmaker is available in Friedrich (2015). While our approaches to matchmaking mirror the ones in the Web of Needs to a large extent, their fundamental difference is the application to the public procurement domain. Matchmakers in the Web of Needs are generic, since they are not tuned for any specific use case. Instead, they support common matchmaking scenarios shared in many domains, so they are based on a common denominator of data about demands and offers, including features such as title, description, tags, or price (Friedrich et al. 2016). However, the architecture of the Web of Needs allows extensions to particular vertical marketplaces, such as the public procurement, so that more powerful domain-specific features can be leveraged in matchmaking.

An alternative tensor-based approach to matchmaking semantic web services is described in (Szwabe et al. 2015). This proposal combines tuple-based probabilistic tensor modeling with covariance-based multilinear filtering. Extensive evaluation shows the presented approach as superior to other matchmaking methods for the evaluated task.

1.7.2 Related vocabularies

Semantic matchmaking operates on data described by vocabularies and ontologies. Vocabularies enable to bestow data with semantic features that matchmaking can leverage. Support for matchmaking was one of the design goals of the Public Contracts Ontology (PCO), described in Section 2.1.1, which we developed to represent public procurement data. Here we present a review of related vocabularies that too can provide support for matchmaking.

Call for Anything (C4N)¹⁷ is a simple vocabulary for describing demands, such as calls for tenders or calls for papers. C4N can be regarded as one of the first to aim for explicit formulation of demands on the Web. However, the vocabulary features only rudimentary means to express what is sought by demands, as it relies on unstructured literals to specify the objects in demand.

GoodRelations (Hepp 2008) is an ontology for e-commerce on the Web. It focuses on describing offers, which it views as promises, emphasizing the importance of good and explicitly captured relationships between entities in the e-commerce domain. While the ontology is oriented towards supplies, its cookbook remarks that it is possible to “use the very same GoodRelations vocabulary for the buy and the sell side of commerce.”¹⁸ In order to do that, the ontology proposes a conceptual symmetry between demand and supply. It suggests to model demands as ideal offers (i.e. instances of gr:Offering) satisfying what that entities seek (i.e. link via the gr:seeks property). In this way, GoodRelations can take advantage of its comprehensive vocabulary for offers to describe demands, including specifications of the demanded products and services or the payment conditions.

LOTED2 (Distinto et al. 2016) is a legal ontology for public procurement notices. As a legal ontology, it closely follows the EU directives governing public procurement, which we described in Section 1.5.1. As such, the ontology enables to describe the tendering process for public contracts in legal terms. It pays a special attention to qualification criteria, which matchmaking may interpret as hard constraints for filtering bidders who are allowed to compete for public contracts. As the name indicates, LOTED2 evolved from Linked Open Tenders Electronic Daily (LOTED) (Valle et al. 2010), an effort to convert TED to RDF using a simple vocabulary that mirrored the structure of the source data. The account on LOTED2 (Distinto et al. 2016, p. 21) proposes matchmaking as future work and suggests matching TED to OpenCorporates,¹⁹ an open database of companies, using reasoning and matching classifications.

Public Procurement Ontology (PPROC) (Muñoz-Soro et al. 2016) is an ontology that covers the complete life-cycle of public contracts, ranging from their issue to termination. As such, it supports both publication of public contracts as open data and management of public procurement processes in a transparent and accountable way. Its stated underlying goal is to enable open access to procurement data to the public (Muñoz-Soro and Esteban 2015). Although the publications about the ontology are agnostic of its intended use in applications, the ontology was already used in practice for integration of public procurement data from Spanish administrative bodies. It was adopted for public contracts of several authorities from the autonomous community of Aragón.

1.7.3 Related technologies

We conclude this section with a brief overview of related technologies. To the best of our knowledge, these technologies have not yet found use in matchmaking, although they were adopted for related tasks, such as in recommender systems.

LOD-enabled recommender systems (Di Noia et al. 2012b, 2012a, 2016; Thalhammer 2012) constitute a source from which many technologies applicable to semantic matchmaking can be drawn. These systems typically employ established techniques for producing recommendations, such as matrix factorization (Koren et al. 2009), but enhance them with semantic features extracted from LOD. Since the graph data model of LOD is conducive to the use of graph algorithms, some of the LOD-enabled recommender systems found uses for such algorithms or proposed novel algorithms operating on graph data. Examples of this sort include personalized PageRank (Nguyen et al. 2015), spreading activation (Heitmann and Hayes 2014, 2016), or WeightedNIPaths (Ristoski et al. 2015).

Matchmaking can also derive inspiration from technologies in two broader research areas. Instance matching (Christen 2012; Bryl et al. 2014) is usually limited to discovering identity links, although its similarity measures and combination functions to aggregate similarity scores are also applicable to discovering matches between demands and supplies. Semantic search (Davies et al. 2009) can be considered a research area to which semantic matchmaking belongs. Matchmaking can borrow many techniques from this parent, such as query expansion or retrieval from semi-structured data. A notable example of a semantic search engine for RDF is SIREn (Delbru et al. 2012), which extends Apache Lucene²⁰ with capabilities to search deeply nested data without a fixed schema.

2.1.1 Public Contracts Ontology

Public Contracts Ontology²³ (PCO) is a lightweight RDF vocabulary for describing data about public contracts. The vocabulary has been developed by the Czech OpenData.cz initiative since 2011, while this dissertation’s author has been one of its editors. Its design is driven by what public procurement data is available, mostly in the Czech Republic and at the EU level. The data-driven approach “implies that vocabularies should not use conceptualizations that do not match well to common database schemas in their target domains” (Mynarz 2014b).

PCO establishes a reusable conceptual vocabulary to provide a consistent way of describing public contracts. This aim for reusability corresponds with the established principle of minimal ontological commitment (Gruber 1993). The vocabulary exhibits a simple snowflake structure oriented around contract as the central concept. It extensively reuses and links other vocabularies, such as Dublin Core Terms²⁴ or GoodRelations.²⁵ While direct reuse of linked data vocabularies is discouraged by Presutti et al. (2016), because it introduces a dependency on external vocabulary maintainers and the consequences of the ontological constraints of the reused terms are rarely considered, we argue that these vocabularies are often maintained by organizations more stable than the organization of the vocabulary’s creator and that the mentioned ontological constraints are typically non-existent in lightweight linked data vocabularies, such as Dublin Core Terms. Several properties in PCO have their range restricted to values enumerated in code lists. For example, there is a code list for procedure types, including open or restricted procedures. These core code lists are represented using the Simple Knowledge Organization System (SKOS) (Miles and Bechhofer 2009) and are a part of the vocabulary. The design of PCO is described in more detail in Klímek et al. (2012) and Nečaský et al. (2014). The class diagram in Fig. 3 shows the Public Contracts Ontology.

The vocabulary was used to a large extent in the LOD2 project.²⁶ For example, it was applied to Czech, British, EU, or Polish public procurement data. In this way, we validated the portability of the vocabulary across various legal environments and ways of publishing public procurement data.

2.1.2 Concrete data model

The concrete data model of the Czech public procurement data uses the PCO mixed with terms cherry-picked from other linked open vocabularies, such as Public Procurement Ontology (PPROC) (Muñoz-Soro et al. 2016), which directly builds upon PCO. The data model’s class diagram is shown in Fig. 4.

The data model of the extracted data departs from PCO in several ways. There are ad hoc terms in the <http://linked.opendata.cz/ontology/isvz.cz/> namespace to represent dataset-specific features of the Czech public procurement register. Some of these terms are intermediate and are subsequently replaced during data transformation.

Contract objects expressed via pc:mainObject and pc:additionalObject are qualified instead of linking CPV directly. A proxy concept that links a CPV concept via skos:closeMatch is created for each contract object to allow qualification by concepts from the CPV’s supplementary vocabulary. The proxy concepts link their qualifier via skos:related. For example, a contract may have Electrical machinery, apparatus, equipment and consumables; lighting (code 31600000) assigned as the main object, which can be qualified by the supplementary concept For the energy industry (code KA16). This custom modelling pattern was adopted, since SKOS does not recommend any way to represent pre-coordination of concepts.²⁷

Data in the Czech public procurement register is represented using notices, such as prior information notices or contract award notices. Notices are documents that inform about changes in the life-cycle of public contracts. Using the terminology of Jacobs and Walsh (2004), notices can be considered information resources describing contracts as non-information resources. Information resource is “a resource which has the property that all of its essential characteristics can be conveyed in a message” (Jacobs and Walsh 2004), so that it can be transferred via HTTP. On the contrary, non-information resources, such as physical objects or abstract notions, cannot be transferred via HTTP.

We represent contract notices as instances of the subclasses of pproc:Notice from PPROC, since PCO does not include the concept of a contract notice. PCO treats notices as mere artefacts of the document-based communication in public procurement. Each notice pertains to a single contract, while a contract may link several notices informing about its life-cycle. Notices thus provide a way to represent the temporal dimension of contracts. They serve as time-indexed snapshots tracking the evolution of contracts, based on the notice type and its timestamp. To a large extent, we treat notices as intermediate resources, the data of which are combined to form a unified view of contracts during data fusion. Nevertheless, in focusing on the central concept of the public contract, this modelling approach glances over the temporal dimension of other data. For example, it does not accommodate expressing that a contracting authority was renamed. Neither is it supported by PCO, which was designed as atemporal, since modelling temporal data remains an open research topic.

Apart from reusing the code lists incorporated in PCO, we employed a few others. We extracted the code list standardizing categories of procured services as defined in the EU directive 2004/18/EC (EU 2004). This code list links CPV to the Central Product Classification (CPC).²⁸ We also extracted several code lists enumerating the types of contract notices. The EU-wide standard types of notices, including the prior information notice or the design contest notice, were published in 2004 and updated in 2014, with a few types removed, such as the public works concession, or added, such as the modification notice.²⁹ All these code lists were represented in RDF using SKOS.

The diagram of the concrete data model in Fig. 4 shows the Czech public procurement register data after the steps described in this chapter were applied. As is apparent from the cardinalities of many properties, the dataset’s quality is hardly optimal. Maximum cardinalities of several properties are higher than expected due to several reasons. Some entities were inadvertently merged due to their unreliable identifiers. For example, there are few public contracts that share the placeholder identifier 1. We adopted several heuristic counter-measures to avoid fusing distinct entities, such as in case of the previous example, but we could not ensure the reliability of all identifiers in general. Another cause of the high cardinalities is the incomplete data fusion due to insufficient information needed to decide on which values to drop and which ones to keep. Once the hints for data fusion, such as the semantics or temporal order of contract notices, had been used up, there was no more guidance for preferring particular values. When this happened, we either resorted to random sampling or left the data as it was. Ultimately, further improvements in data quality can be made in line with the pay-as-you-go approach if the invested effort is offset by the gains obtained in matchmaking.

2.3.1 Challenges

The key challenges of the data transformation were dealing with high heterogeneity of the data and achieving a workable performance of complex transformations affecting large subsets of data. Due to the volume of processed data and the complexity of the applied transformations, we have not used LP-ETL to orchestrate the transformations. LP-ETL materializes the output of each processing step and, in case of RDF, loads data into an in-memory RDF store, which leads to performance problems when working with higher volumes of data. Nonetheless, LP-ETL allows to execute SPARQL Update operations on data partitioned into chunks of smaller size, which can significantly speed up processing of larger datasets. However, this technique can be used only for transformations that require solely the data present in the chunk, which prevents it from being used in cases the whole dataset is needed by a transformation; e.g., for joins across many resources. An example where this technique is applicable is sequential processing of tabular data, in which data from each row can be processed separately in most cases. Because of its relational nature, our dataset cannot be effectively split to allow executing many kinds of transformations on smaller chunks of data.

Instead of partitioning data, we partitioned the intermediate query bindings in SPARQL Update operations. Transformations using this technique follow the same structure. They contain a sub-query that selects the unprocessed bindings; either by requiring the bindings to match a pattern that is present only in the unprocessed data, e.g., using FILTER NOT EXISTS to eliminate bindings that feature data added by the transformation, or by selecting subsequent subsets from the sorted bindings. For instance, a transformation of instances of schema:PostalAddress can be divided into transformations of non-overlapping subsets of these instances. The latter option for filtering the unprocessed bindings cannot be used when the set of sorted bindings is modified during the transformation. For example, when a transformation deletes some bindings, the offsets of subsets in the ordered set cease to be valid. Additionally, since sorting a large set is a computationally expensive operation, this option may require the sub-query projecting the ordered bindings to be wrapped in another sub-query to be able to cache the sorted set, such as with the Virtuoso’s scrollable cursors.³⁵ The selected unprocessed bindings from the sub-query are split into subsets by setting a limit. The outer update operation then works on this subset and transforms it.

We developed sparql-unlimited³⁶ that allows to run SPARQL update operations following the described structure using Virtuoso. This tool executes transformations rendered from Mustache³⁷ templates that feature placeholders for LIMIT, and optionally OFFSET. Limit determines the size of a subset to be transformed in one update operation. In this way, the processed subset’s size can be adjusted based on the complexity of the transformation. Updates are executed repeatedly, the offset being incremented by the limit in each iteration, until their response reports zero modifications. This stopping condition is Virtuoso-specific, since the SPARQL 1.1 Update standard (Gearon et al. 2013) leaves it unspecified, so that SPARQL engines differ in how they indicate zero modifications. Additionally, sparql-unlimited provides a few conveniences, including configurable retries of failed updates or the ability to restart transformations from a specified offset.

While sparql-unlimited was used to automate parts of individual transformations, each transformation was launched manually. Virtuoso, the RDF store in which we executed the transformations, has an unpredictable runtime, which may be due to unresolved previous transactions or generally faulty implementation. Therefore, we started each transformation manually to allow to fine-tune the configuration for each run depending on the received response from Virtuoso.

A good practice in ETL is to make checkpoints continuously during data processing. Checkpoints consist of persisting the intermediate data output from the individual processing steps, usually to disk. However, due to the large numbers of transformations in our case large disk space would be required if checkpoints were done for every transformation. To reduce disk consumption we persisted only the outputs of the major sub-parts of the data processing pipeline.

2.3.2 Transformation tasks

Overall, we developed tens of SPARQL Update operations for the data transformation. One of the principles we followed was to reduce data early in order to avoid needless processing in the subsequent transformation steps. For example, we deleted empty contract lots and the resources orphaned³⁸ in other transformations. Several transformations were used to clean malformed literals; for example to regularize the common abbreviations for organizations types or convert \/ into V. We removed award dates from the future. We added default values into the data. Since the dataset is of Czech origin, we used Czech koruna (CZK) as the default value in case currency was missing. The addresses without an explicitly stated country were assumed to be located in the Czech Republic. Nonetheless, it is important to acknowledge that adding default values was a trade-off favouring coverage over accuracy.

We paid particular attention to structuring postal addresses in order to improve the results of the subsequent geocoding, described in Section 2.4.5. The primary aim of the transformation of postal addresses was to minimize their variety to increase their chance for match with the reference postal addresses. We managed to extract postal codes, house numbers, and street names from otherwise unstructured data. Accidental variations in postal addresses, such as punctuation, were normalized where possible. Unfortunately, this effort was hindered by a Virtuoso’s bug in support for non-ASCII characters,³⁹ which prevented us from using SPARQL Update operations with diacritical characters, for example when expanding Czech abbreviations in street names.

We made several transformations to move data of select properties, which was difficult to achieve in XSLT during the data extraction. Since RDF/XML lacks a way to express inverse properties, we minted provisional properties in the data extraction, which were reversed as part of the data transformation. For example, a temporary property :isLotOf linking lots to contracts was reversed to pc:lot from PCO. We also corrected domains of some properties, because moving them in XSLT would require joins based on extra key indices.

Some data transformations required additional data. A subset of these transformations leveraged background knowledge from vocabularies. For example, we used rdfs:subClassOf axioms from PPROC to distinguish subclasses of pproc:Notice, when we merged data from notices to contracts. We loaded the required vocabularies into separate named graphs via the SPARQL Update LOAD operation.

In order to make prices comparable, we converted non-CZK currencies to CZK via exchange rates data from the European Central Bank (ECB).⁴⁰ This dataset contains daily exchange rates of several currencies to EUR. We used an RDF version of the dataset⁴¹ prepared for the OpenBudgets.eu⁴² project. This derivative covers the rates from November 30, 1999 to April 7, 2016, so it allowed to convert most prices in our dataset. Prices in non-CZK currencies were converted using the exchange rates valid at their notice’s publication date. This was done as a two-step process, first converting the prices to EUR followed by the conversion to CZK. In order to automate the execution of this task we employed sparql-to-csv,⁴³ a tool that we developed, which allows to pipe query results into another query or update operation.

The normalized prices were winsorized⁴⁴ at 99.5^th percentile to remove the likely incorrect extreme prices. Due to the limited expressivity of SPARQL this task needed to be split into two SPARQL queries followed by a SPARQL Update operation. The first query retrieved the count of 0.5 % prices, the second query chose the minimum price in the highest 0.5 % prices using the count as a limit, and the final update capped the 0.5 % of highest prices at this minimum. As in the case of currency conversion, we automated the steps of this task using piped queries in sparql-to-csv.

Finally, some estimated prices are expressed as ranges from minimum to maximum price. These prices were converted to arithmetic averages to simplify further processing.

2.4.1 Content-based addressing

In the absence of agreed-upon identifiers, entities are referred to by their description. Moreover, unlike RDF, some data formats, such as CSV, do not have a mechanism for linking. The lack of shared identifiers established by a reliable authority leads to proliferation of aliases for equivalent entities. Missing consensual identifiers are one of the key challenges in integration of public procurement data (Alvarez-Rodríguez et al. 2014).

If the descriptions with which entities are referred to are reliable and complete, we can use content-based addressing to discover which descriptions refer to the same entity. Content-based addressing is a general approach for identifying entities by using the content of their representations. In case of RDF entities, we assume that triples containing an entity’s identifier as subject or object to make up the entity’s description, also known as the concise bounded description (Stickler 2005). We typically restrict such triples to those in which an entity’s identifier is in the subject role. Various content signatures may be derived from such descriptions of entities.

Simple keys of entities can be derived from values of specific properties. In case of subjects, their keys can be objects of outbound properties that may be interpreted as inverse functional properties; i.e. instances of owl:InverseFunctionalProperty. For example, the property foaf:homepage, which describes an entity’s home page, is defined as an inverse functional property and as such it is usable as a simple key of an entity. In case of objects, their keys can be subjects of inbound properties that may be interpreted as functional object properties; i.e. instances of both owl:FunctionalProperty and owl:ObjectProperty. For example, the property pc:contractingAuthority, which links a contract to its contracting authority, is defined as a functional object property, so that its subject can function as a simple key of the contracting authority. Both kinds of simple key properties may be chained in property paths and followed to obtain keys that do not directly describe the entities they identify. For example, the property path pc:awardedTender/pc:bidder can be treated as a functional object property, the subject of which may be used as a bidder’s key if we accept the assumption that a contract can be awarded to a single organization only. Simple keys are typically used directly as part of entity IRIs, which prevents creating multiple aliases for the entities in the first place. A caution must be given if schema axioms related to functional and inverse functional properties are unreliable or if instance data is diverging from them. In such case, it is better to skip inferring equivalence links via the described methods in order to avoid false results.

Compound keys are more complex content signatures that can be derived from combinations of values of specific properties. In order to be eligible as keys, these combinations must be unique. For example, a contract and a lot number can serve as a compound key for a contract lot. Similarly to simple keys, such compound keys are commonly used as parts of IRIs of the entities they identify. We also employed this approach to merge the bidders sharing the same name and awarded with the same contract. Nevertheless, compound keys are perhaps used more often in a probabilistic setting, in which the degree of their match implies a probability of equivalence of the keyed entities. Fuzzy matches of combinations of values can approximate exact matches of simple keys. However, unlike identifying simple keys, identification of suitable compound keys and approaches for their matching usually requires an expert insight into the domain in question. A common scenario for probabilistic matching of compound keys uses combinations of simple keys that are unreliable identifiers on their own. In the context of our dataset, even when registered identification numbers (RNs) are available, they may be misleading as identifiers. For example, there are several public contracts each year that a contracting authority awards to itself according to the supplied RNs of the authority and the awarded bidder. Moreover, many RNs in the data are syntactically invalid and cannot be automatically coerced to the correct syntax. So, for example, an organization’s name may be combined with its syntactically invalid RN to produce an approximate compound key.

Further extending the size of keys, we can use the complete descriptions of the keyed entities. Since such keys may be unwieldy, they can be substituted by their hashes to make them more manageable. Using hashes as keys is standard in content-based addressing. Hash functions, such as MD5, map variable length descriptions to a fixed length, while preserving their uniqueness. Unlike the previously described approaches for deriving keys, hashes do not require background knowledge to select the key properties, so their production can be fully automated. However, on the one hand, hash keys tend to be more brittle, since any change in the hashed descriptions produces a different hash, which may lead to many false negatives when comparing hashes. On the other hand, hashes can also produce false positives if they are used for underspecified entities. For example, postal addresses for which we know only that they are located in the Czech Republic are unlikely to be the same. The risk of false positives can be reduced by requiring a minimum description, similar to a compound key, to be present. For instance, we can hash only the postal addresses that feature at least a street address and an address locality.

We also experimented with linking entities by discovering entities that are described with a subset of another entity’s description. Given some minimum description of entities to avoid false positives, we assumed that if a set of property-object pairs of a subject is a subset of such set of another subject, the subjects are co-referent. However, detecting subsets in SPARQL is problematic because defining subsets requires universal quantification. Since SPARQL is based on existential quantification instead, universally qualified predicates need to be reimplemented as double negation via nested FILTER NOT EXISTS clauses. Ultimately, we abandoned this linking method because of its poor performance, which makes it unusable for larger data.

In case of entities for which no key can be used to construct IRIs directly during data extraction via XSLT, we employed blank nodes as identifiers. Subsequently, we converted these blank nodes to hash-based IRIs via SPARQL Update operations. The hashes were computed by concatenating the properties and objects of the identified subject and deriving an SHA1 hash from the concatenated string. We used this approach primarily for entities that can be interpreted as structured values, such as price specifications. The entities identified by blank nodes were processed in their inverse topological order. If a blank node linked another blank node, the linked blank node was rewritten first. This was done to ensure that the hashed descriptions of blank nodes do not contain blank nodes, which would cause different hashes to be computed from otherwise equivalent descriptions. Since no two blank nodes are the same, this procedure led to a significant reduction of aliases.

2.4.2 Linking technologies

We employed four kinds of linking technologies. Simple keys and some compound keys were used directly to construct IRIs in XSLT. Linking based on hashes was done using SPARQL Update operations (Gearon et al. 2013). Update operations were also used when creating links required a join via a key, for example when reconciling code list values. Most linking tasks based on fuzzy matches of compound keys were done using the Silk link discovery framework (Bryl et al. 2014). Silk was used when links could not be established via exact matches. For example, we used it to compare syntactically invalid RNs via string distance metrics. We used Silk Workbench, a graphical user interface for Silk, for iterative development of the linkage rules. Silk Workbench displays the results of linking in a way the interlinked entities can be compared manually. This enables to examine a sample of links for false positives and negatives and adjust the linkage rules accordingly, tuning weights and thresholds to avoid the undesired results. An example linkage rule in Silk Workbench is shown in Fig. 5. Elasticsearch⁴⁵ was employed for matching postal addresses to reference addresses from the Czech addresses dataset.

In general, linking was done iteratively, interposed with data fusion. Fusion reduced the size of the data, in turn reducing the search space for linking. Additionally, linking that followed fusion could build on the previously created links.

2.4.3 Linking tasks

We worked on three main linking tasks. We reconciled the values in our dataset with standard code lists. Code lists provide common reference concepts with which values from our source data can be linked. For instance, we mapped different wordings of procedure types to the PCO’s code list for the procedures recognized by the Czech public procurement law.

We linked organizations in the Czech public procurement register to ARES. Instead of deduplicating organizations directly in the public procurement dataset, we decided to reconcile them with ARES, which provided reference identities for organizations. We developed Silk linkage rules using combinations of several properties as compound keys. Syntactically invalid RNs were matched with valid RNs using the Levenshtein string distance metric to find the RNs containing typos. Normalized legal names of organizations were compared via the Jaro-Winkler distance metric with a high required similarity threshold. This metric was selected because it penalizes mismatches near the start of the name more than mismatches at the end. It also takes the lengths of the compared names into account, so that more mismatches are tolerated in longer names. Thanks to these features this distance metric is widely used when comparing names. Legal names were first normalized by converting to lowercase and removing both non-alphanumeric characters and stop-words (e.g., “Czech”), which were generated from the most frequent words appearing in the legal names. Exact matches via postal codes or normalized URLs of organizations were used to disambiguate homonymous organization names. Unfortunately, URLs were discovered to be unreliable as simple keys, because they can be assigned incorrectly, so that we used them as keys only in combination with other data. Geo-coordinates of organizations obtained by geocoding postal addresses were used to filter matches by maximum allowed geographic distance. The resulting equivalence links generated by Silk were serialized using the owl:sameAs property, loaded in a separate named graph, and resolved during data fusion. In total, we generated 6842 links for the 14177 business entities unlinked to reference entities from ARES. Resolution of these links thus reduced the share of the unlinked business entities from 33.38 % to 15.9 %.

We geocoded postal addresses in ARES and in the Czech public procurement register by linking them to the Czech addresses dataset. Geocoding is the described in greater detail further in a separate section.

2.4.4 Evaluation of linking

Evaluation of the quality of linking typically involves a clerical review of a sample of the resulting equivalence links (Christen 2012, p. 174). By using manual assessment, a randomly selected sample of links can be split into correct and incorrect matches. This allows to compute quality metrics, such as precision, which is defined as the ratio of correct links (true positives) to all links (positives). Results of the metrics computed on a sample may be then extrapolated to approximate the quality of the complete output of linking.

We manually evaluated a randomly selected sample of 200 links to ARES generated by approximate matching in Silk. To a limited extent, the evaluation of this subset of links can substitute the evaluation of all links, which was unfeasible due to the manual effort involved in assessing link validity. Validity of each link was confirmed or rejected based on the data published in the PR, also taking into account its changes over time, or based on the web sites of the linked organizations. 9 links were determined to be false positives, while the rest was confirmed to be valid. This ratio of false positives produces the precision of 0.955. We consider such precision to be reasonable, given the low quality of the linked data. Some of the false positives were caused by ambiguous descriptions of business entities. For example, there are two distinct entities named COMIMPEX spol. s r.o. that also share the same organization type.

Apart from the clerical review, there are also few automated measures that may indicate the quality of links. An example of such measure is the reduction ratio, defined as the number of generated equivalence links compared to all possible equivalence links. Effectiveness of linking measured in its total runtime compared to the number of the processed entities can also be determined without human input. A more detailed review of the evaluation methods for linking is presented by Christen (2012, pp. 163–184).

2.4.5 Geocoding

Geocoding is the process of linking postal addresses to geographic locations. The locations are represented as coordinates corresponding to a place on the Earth’s surface. Geocoding can be considered a case of instance matching (Christen 2012, sec. 9.1) that matches addresses from a dataset to reference addresses equipped with geo-coordinates. We geocoded the postal addresses of business entities in the Czech public procurement register, the Public Register (PR), and the Trade Licensing Register (TLR). In case of PR we geocoded only the addresses that were missing links to the Czech addresses dataset. Unlinked addresses in PR amounted for 12.42 % of all its addresses. No addresses in TLR were linked. In total, we geocoded over 180 thousand postal addresses from these registers. In case of the Czech public procurement register we geocoded the addresses of business entities that were not linked to the above-mentioned registers. The overall goal of this effort was to be able to locate the business entities for the purposes of linking, analyses, and matchmaking.

The main challenge to address in geocoding was the lack of structure in the geocoded data. As described in Section 2.3, we attempted to parse the unstructured addresses to recover their structure. Nevertheless, many addresses contained just a name of a region or a municipality. This is why we started with simple geocoding based on matching region or municipality names.

We used LP-ETL to extract the names of regions and municipalities along with their corresponding geo-coordinates from the RÚIAN SPARQL endpoint.⁴⁶ The data provides geo-coordinates of centroids of each region and municipality. The geo-coordinates were reprojected from EPSG:5514 coordinate reference system (CRS) to EPSG:4326 to improve their interoperability, since the latter one is a de facto standard CRS on the Web. We loaded the data into our RDF store and ran a SPARQL Update operation to match the geo-coordinates to postal addresses via the names of regions and municipalities.

In order to geocode other postal addresses, we built an Elasticsearch-based geocoder using the Czech addresses data, covered in Section 2.4.6.3. We decided not to use an existing solution for several reasons. Some existing services for geocoding have restrictive licenses. For instance, the results of the Google Maps Geocoding API can be used only in conjunction with displaying the obtained geo-coordinates on a map from Google Maps.⁴⁷ More liberal geocoding services often provide poor accuracy. For example, this is the case of OpenStreetMap’s Nominatim,⁴⁸ both for its structured and unstructured search. Finally, we wanted to assess whether open data can help build a geocoder on par with the commercial offerings. This is why we based the developed geocoder on the gazetteer built from the Czech address data.

During the development of the geocoder we leveraged the tooling we built for data preparation, described in the Appendix 6. sparql-to-jsonld⁴⁹ was used to retrieve the Czech addresses data from a SPARQL endpoint, construct descriptions of the individual postal addresses, and frame them into JSON-LD documents. We used jsonld-to-elasticsearch⁵⁰ to index the addresses in Elasticsearch. In the index phase we applied a basic normalization and employed a synonym filter to expand the abbreviations commonly found in postal addresses.

The geocoder elasticsearch-geocoding⁵¹ was implemented as a command-line tool that loads the addresses to geocode from a SPARQL endpoint using a paged SPARQL SELECT query provided by the user, and queries an Elasticsearch index with the Czech addresses data for each address. We adopted Elasticsearch for the geocoder because, unlike SPARQL, it allows to perform fuzzy searches, in which results are ranked by the degree to which they fulfil the search query. This is useful since the geocoded addresses may be incomplete, poorly structured, or contain misspellings. In case we obtained multiple results from the geocoder, we selected the first one, which ranked the best.

Since we practice separation of concerns, the geocoder expects a reasonably clean input. It is the responsibility of data preparation to structure and normalize the geocoded postal addresses. This effort has benefits for many tasks, not geocoding only. Instead of ad hoc cleaning during geocoding we thus prepared the postal addresses as part of the ETL pre-processing, as described in Section 2.3.

The geocoder generates the queries to Elasticsearch from its input addresses. Since every property of the addresses is optional, the queries can be generated in several ways, depending on the semantics associated with the properties. If schema:description is the only available property, we search for it across all fields. A more complex query matching combinations of subqueries is generated if more properties are present. The objects of postal code (schema:postalCode) and address locality (schema:addressLocality) are treated as co-referent, so that it suffices if one matches if both are available.

The design of the geocoding queries was guided by the level of accuracy required to support the envisioned use cases. For us errors in the range of tens to hundreds of meters are tolerable, so that we could trade in accuracy for increased recall. We made adjustments to the geocoding queries to better serve this objective. As house numbers and orientational numbers are often mixed up, we enabled the geocoding queries to match either number. We boosted the weight of postal codes because the match on their level is more important than the match on more specific levels, such as the house number. Prior to introducing the boost for postal codes, in some cases distant addresses sharing the same street address and house number were mixed in their geolocation. Moreover, unlike address localities, postal codes are usually regular, which makes them more reliable in retrieval. Further optimization of the geocoding queries was guided by the results of evaluation.

2.4.6 Linked datasets

We linked several datasets with the Czech public procurement register. In this section we describe how these datasets were prepared. Fig. 6 shows how these datasets are linked. In this diagram, dataset size corresponds to the number of RDF triples in the dataset, while the thickness of lines between the datasets corresponds to the number of links connecting them. Both proportions are logarithmically scaled for display purposes.

In the following we review these linked datasets and explain how they were obtained and prepared.

2.5.1 Conflict resolution strategies

The conflict resolution strategies we implemented can be classified according to Bleiholder and Naumann (2006). We used Trust your friends (Bleiholder and Naumann 2006, p. 3) strategy to prefer values from ARES, since we consider it a trustworthy reference dataset. Leveraging the semantics of notice types, we preferred data from correction notices. A similar reason led us to remove syntactically invalid RNs in case valid RNs were present too. We used Keep up to date (Bleiholder and Naumann 2006, p. 3) metadata-based conflict resolution strategy to prefer values from the most recent public notices. We determined the temporal order of notices from their submission dates and the semantics of their types, which represent an implicit order. For example, prior information notice comes before contract notice, which in turn precedes contract award notice. The order of notice types can be learnt from the most common order of notices with immediately following submission dates. We combined such distribution of subsequent notice types with manual assessment to rule out erroneous pairs. The order of notice types was provided as an inline table to the SPARQL Update operation resolving the conflicts. In line with this strategy, we also preferred the most recent values of pc:awardDate. We used Most specific concept (Bleiholder and Naumann 2006, p. 4) strategy for resolution of conflicts in values from hierarchical concept schemes. In case a single functional property linked multiple concepts that were in a hierarchical relation, the most specific concepts were retained. For instance, we removed procedure types that can be transitively inferred by following skos:broaderTransitive links. We used No gossiping (Bleiholder and Naumann 2006, p. 3) strategy for conflicting boolean values. If a boolean property has both true and false value, and there is no way to prioritize a value, we conclude the true value of the property is unknown, and therefore delete both conflicting values. Once the conflicts were resolved by the above-described strategies, we moved the remaining notice data to the associated contracts, which corresponds to the strategy Take the information (Bleiholder and Naumann 2006, p. 3). We excluded notice’s proper data, such as submission date or notice type, from this step. If all previous conflict resolution strategies failed, in select cases we followed Roll the dice (Bleiholder and Naumann 2006, p. 5) strategy and picked a random value via the SAMPLE aggregate function in SPARQL. We did this for procedure types (values of pc:procedureType), contracting authorities (values of pc:contractingAuthority) without valid RNs, and actual prices (values of pc:actualPrice).

As the final polishing touch we excised the resources orphaned during data fusion. Since removing orphans may create more orphans, we deleted orphans in the topological order based on their links. In this way we first removed orphans, followed by deleting their dependent resources that were orphaned next.

2.5.2 Evaluation of fusion

If we decide to evaluate the quality of data fusion, there are several measures available. One of the broadest measures for assessing data fusion is data reduction ratio, which represents the decrease of the number of fused entities. This figure corresponds to the measure of extensional conciseness defined by Bleiholder and Naumann (2008, pp. 1:5–1:6) as the “percentage of real-world objects covered by that dataset.” Many evaluation measures used for data fusion reflect the impact of this task on data quality. An example of those measures is completeness, which represents the ratio of instances having value for a specified property before and after fusion, and is sometimes rephrased as coverage and density (Akoka et al. 2007).

Compared with the raw extracted datasets, fusion decreased the number of distinct entities by 61.68 % to 2 million. Overall, fusion reduced the data by 52.14 % from 20.5 million triples to 9.8 million.

2.6.1 SPARQL-based matchmakers

The SPARQL-based matchmakers require data to be available via the SPARQL protocol (Feigenbaum et al. 2013). The SPARQL protocol describes the communication between clients and SPARQL endpoints, which provide query interfaces to RDF stores. Exposing data via the SPARQL protocol thus requires simply to load the data into an RDF store equipped with a SPARQL endpoint. We chose to use the open source version of Virtuoso⁸⁷ from OpenLink as our RDF store. Even though Virtuoso lacks in stability and adherence to the SPARQL standard, it redeems that by offering a performance unparalleled by other open source RDF stores. We used Virtuoso’s bulk loader⁸⁸ to ingest RDF data into the store.

2.6.2 RESCAL-based matchmakers

The RESCAL-based matchmakers operate on tensors. Tensors are multidimensional arrays typically used to represent multi-relational data. The number of dimensions of a tensor, also known as ways or modes (Kolda and Bader 2009), is referred to as its order. Tensors usually denote the higher-order arrays: first-order tensors are vectors and second-order tensors are matrices.

Higher-order tensors provide a simple way to model multi-relational data, such as RDF. Since RDF predicates are binary relations, RDF data can be represented as a third-order tensor, in which two modes represent RDF resources in a domain and the third mode represents relation types; i.e. RDF predicates (Tresp and Nickel 2014). The two modes are formed by concatenating the subjects and objects in RDF data. The mode-3 slices of such tensors, also referred to as frontal slices, are square adjacency matrices that encode the existence of relation \(R_{k}\) between RDF resources \(E_{i}\) and \(E_{j}\), as depicted in Fig. 7. Consequently, RDF can be modelled as \(n \times n \times m\) tensor \(\mathcal{X}\), where \(n\) is the number of entities and \(m\) is the number of relations. If the \(i\)^th entity is related by the \(k\)^th predicate to the \(j\)^th entity, then the tensor entry \(\mathcal{X}_{ijk} = 1\). Otherwise, if such relation is missing or unknown, the tensor entry is zero.

There are a couple of things to note about tensors representing RDF data. Entities in these tensors are not assumed to be homogeneous. Instead, they may instantiate different classes. Moreover, no distinction between ontological and instance relations is maintained, so that both classes and instances are modelled as entities. In this way, “ontologies are handled like soft constraints, meaning that the additional information present in an ontology guides the factorization to semantically more reasonable results” (Nickel et al. 2012, p. 273). Tensors representing RDF are usually very sparse due to high dimensionality and incompleteness, calling in for algorithms that leverage their sparseness for efficient execution, in particular for large data. Scalable processing of large RDF datasets in the tensor form is thus a challenge for optimization techniques. Interestingly, unlike RDF, tensors can represent n-ary relations without decomposing them into binary relations. What would in RDF require reification or named graphs can be captured with greater tensor order. This presents an opportunity for more expressive modelling outside of the boundaries of RDF.

We developed sparql-to-tensor, described in Section 6.2.9, to export RDF data from a SPARQL endpoint to the tensor form. The transformation is defined by SPARQL SELECT queries given to this export tool. Each query retrieves data for one or more RDF properties that constitute the relations in the output tensor. During the evaluation, we created and tested many tensors, each combining different properties and ways of pre-processing.

In most cases the retrieved relations corresponded to explicit RDF properties found in the source data. However, in a few select cases we constructed new relations. This was done either to avoid intermediate resources, such as tenders relating awarded bidders or proxy concepts relating unqualified CPV concepts, or to relate numeric values discretized to intervals. Since the original RESCAL algorithm does not support continuous variables, we discretized such variables via discretize-sparql, which is covered in Section 6.2.1.

Apart from binary numbers as tensor entries we used float numbers \(\mathcal{X}_{ijk} \in \mathbb{R} \colon 0 \leq \mathcal{X}_{ijk} \leq 1\) to distinguish the degrees of importance of relations. Float entries were used to de-emphasize less descriptive RDF properties, such as pc:additionalObject, or to model information loss from ageing, so that older contract awards bear less relevance than newer ones. We reused the ageing function from (Kuchař et al. 2016, p. 212) to compute the tensor entries:

\[\mathcal{A}(t_{0}) = \mathcal{A}(t_{x}) \cdot e^{-\lambda t}; t_{0} > t_{x}, t = t_{0} - t_{x}\]

In this function “\(\mathcal{A}(t_{0})\) is the amount of information at the time \(t_{0}\). \(\mathcal{A}(t_{x})\) is the amount of information at the time \(t_{x}\) when the information was created, \(\lambda\) is ageing/retention factor and \(t\) is the age of the information.” We assume \(\mathcal{A}(t_{x})\) to be equal to 1, the same value used for relations encoded without ageing. Since our dataset covers a period of 10 years, we use \(\lambda = 0.005\) that provides a distribution of values spanning approximately over this period. We used contract awards dates as values of \(t_{x}\) and the latest award date as \(t_{0}\). Award dates were unknown for the 2.3 % of contracts, for which we used the median value of the known award dates. The ageing function was implemented in a SPARQL SELECT query. Since the required natural exponential function is not natively supported in SPARQL, we used the extension function exp()⁸⁹ built in the Virtuoso RDF store to compute it.

Instead of exporting all RDF data to the tensor format, we selected few features from it that we deemed to be the most informative. There are 76 different relations in the Czech public procurement dataset in total. Even more relations are available if we add the linked data. We experimented with selecting individual relations as well as their combinations to find out which ones produce the best results. We guided this search by the assumption that the contributions of the individual relations do not cancel one another out. Moreover, we ignore the possibility that features that do not bring improvement separately can produce improvement if used in combination, having synergic effect. Our heuristic for manual feature selection thus resembles simple hill-climbing.

3.2.1 Benefits and drawbacks

This matchmaker explores the use of SPARQL (Harris and Seaborne 2013) for matchmaking. We introduced SPARQL in Section 1.4.2. The choice of this technology for matchmaking has both benefits and drawbacks.

3.2.2 Ranking matches

SPARQL queries retrieve exact matches satisfying the query conditions. Since SPARQL can tell only matches from non-matches, matches that satisfy the query partially are left out. Ranking of matches by the degree to which they satisfy the query thus needs to be implemented on top of SPARQL. Hence, we need to relax the match conditions to avoid filtering partial matches and then compute scores to rank the matches.

The matchmakers operate with a given query contract \(c_{q}\), which is matched to contracts from the set \(C\). They retrieve contract objects that overlap with the object of the query contract, which are optionally expanded to include related CPV concepts. Components of contract objects are weighted and these weights are combined into partial similarity scores. Partial similarities are then aggregated per bidder to produce the bidder’s match score.

3.2.2.2 Query expansion

Controlled vocabularies that describe contract objects can be semantically structured, such as via hierarchical or associative relations. Since relevance of a concept may entail relevance of concepts in its neighbourhood, we can leverage the structure of these vocabularies and perform expansion to include the related concepts in the query. In particular, we expand CPV concepts by following transitive hierarchical relations in this vocabulary. We follow either links to narrower concepts via skos:narrowerTransitive, links to broader concepts via skos:broaderTransitive, or links in both directions. Query expansion can be parameterized by the maximum number of hops followed to obtain a graph neighbourhood of the expanded concept. When a concept is expanded, its inferred concepts include those that are one to the maximum hops away from the expanded concept. Note that it is possible to infer a concept already included in the explicitly assigned concepts when these are hierarchically related. In such case, the concept appears twice in the contract object, distinguished by its concept assignment. Similarly, the same inferred concept can be reached more times by expanding different concepts. Such concept is present once in the results of query expansion since the results form a set. The figures 8 and 9 illustrate the query expansion, showing expansions to two-hop neighbourhoods.

The arguments of the query expansion function \(exp\) are a set of contract objects, a direction of expansion, and a distance of the expansion. The direction of expansion \(Dir\) is the set \(\{\texttt{skos:broaderTransitive}, \texttt{skos:narrowerTransitive}\}\) indicating either the expansion to broader or narrower concepts. The distance is the maximum number of hops followed in the expansion. Consequently, the query expansion function can be defined as \(exp \colon \mathbb{P}(Cobj) \times Dir \times \mathbb{N}_{> 0} \to \mathbb{P}(Cobj)\). Bidirectional expansion of the set of contract objects \(\{cobj\} \subset Cobj\) to the distance \(dis\) can thus be computed as \(exp(\{cobj\}, \texttt{skos:broaderTransitive}, dis) \cup exp(\{cobj\}, \texttt{skos:narrowerTransitive}, dis)\). We only require \(exp\) to be monotonous, so that for every contract object \(cobj \in Cobj\) holds that \(((con, p), cona) \in cobj \;\; \Rightarrow \;\; ((con, p), cona) \in exp(cobj, dir, dis)\), and hence the function \(exp\) returns a union of its provided contract objects with the inferred contract objects. Concrete instantiations of \(exp\) can limit which input contract objects are expanded. In our case, either no contract objects are expanded or we only expand the explicitly assigned contract objects where \(p = \texttt{pc:mainObject}\) and \(con \in Con_{CPV}\).

3.2.2.3 Matching

The matchmakers examine only the exact matches between concepts of contract objects. Instead of matching complete contract descriptions or sets of concepts, matching on the finer level of individual concepts allows to capture partial overlaps between contracts. The predicate \(matches \colon Cobj \times Cobj \to \{T, F\}\) returns the boolean value true, denoted as \(T\), if concepts in the compared contract objects are the same, otherwise returning the boolean value false, denoted as \(F\).

\[matches(cobj_{a}, cobj_{b}) = \begin{cases} T & \text{if}\ ccobj(cobj_{a}) = ccobj(cobj_{b}) \\ F & \textrm{otherwise} \\ \end{cases}\]

Here, \(ccobj(cobj_{a})\) accesses the concept in the contract object \(cobj_{a}\). As is evident, in order to achieve a match, the ranges of the properties in the compared contract objects must be the same.

Matching considers its input as the query contract, while the other contracts are treated as potential matches. The function \(match \colon \left\{c_{q}\right\} \times Dir \times \mathbb{N}_{> 0} \to \mathbb{P}(CMA)\) retrieves concept-mediated associations matching a given query contract \(c_{q}\).

\[match(c_{q}, dir, dis) = \bigcup \left\{ \begin{split} & (ccobj(o_{q}), pcobj(o_{q}), pcobj(o_{m}), c_{m}) \colon \\ & o_{q} \in exp(obj(c_{q}), dir, dis), \\ & c_{m} \in C, \\ & o_{m} \in obj(c_{m}), \\ & matches(o_{q}, o_{m}) \end{split}\right\}\]

The direction of expansion \(dir\) and the distance \(dis\) are passed as arguments to the query expansion function \(exp\). The function \(match\) produces a set of concept-mediated associations \(CMA\) that are defined as 4-tuples \((con, p_{q}, p_{m}, c_{m}) \colon con \in Con, p_{q} \in P, p_{m} \in P, c_{m} \in C\). We call them concept-mediated associations since they connect the query contract with the matched contracts via concepts. In each association \(p_{q}\) is a property associating a concept \(con\) to the query contract and \(p_{m}\) is a property associating \(con\) to a matched contract \(c_{m}\).

Fig. 10 shows an overall diagram of concept-mediated associations. The query contract \(c_{q}\) is associated to the matched contracts \(c_{1}, c_{2}, c_{3} \in C\) via concepts that are assigned to the query contract via \(p_{q_{i}}\) and to the matched contracts via \(p_{m_{i}}\). As shown in Fig. 11, contracts may be associated through different kinds of concepts. The matched contracts in turn lead to bidders \(b_{1}, b_{2} \in B\). Here, \(B\) is the set of known bidders. Contracting authority of \(c_{q}\) is marked as \(a_{q}\), while the contracting authority of \(c_{3}\) is denoted as \(a_{3}\). For \(a_{3}\) a zIndex score \(z_{3}\) is available.

3.2.3 Blind matchmakers

Apart from the above-described matchmakers, we also implemented three blind approaches for matchmaking, none of which considers the query contract. The most basic is the random matchmaker that recommends bidders at random. While it is hardly going to deliver a competitive accuracy, it produces diverse results. An approach contrary to random matchmaking is the recommendation of the top-most popular bidders. For each contract this matchmaker recommends the same bidders that were awarded the most contracts. A similar approach is employed in the matchmaker that recommends bidders with the highest score computed by the PageRank-like algorithm implemented by the Virtuoso-specific IRI_RANK (OpenLink Software 2017). Since this score uses a proprietary extension of SPARQL, it is an exception from our constraint to standard SPARQL. These conceptually and computationally simpler approaches are used as baselines to which we can contrast the more sophisticated approaches in evaluation.

3.2.4 Implementation of SPARQL-based matchmakers

The matchmakers are implemented by SPARQL query templates. Each template receives a configuration and produces a SPARQL query. The generated queries are executed on the configured SPARQL endpoint and return ordered sets of matches. Each kind of matchmaker corresponds to a particular query template. It may also expose specific parameters that can be provided via the configuration.

The basic graph pattern considered in most matchmakers is illustrated in Listing 3 using the SPARQL 1.1 Property Path syntax. The path is complicated by intermediate resources proxying CPV concepts connected via skos:closeMatch, as described in Section 2.1.2.

?queryContract ^pc:lot/pc:mainObject/skos:closeMatch/
                         ^skos:closeMatch/^pc:mainObject/pc:lot/
                         pc:awardedTender/pc:bidder ?matchedBidder .

Apart from our baseline matchmaker, which uses the property path in Listing 3, the implementation of the matchmakers is based on nested sub-queries and VALUES clauses used to associate the considered properties with weights.

We implemented query expansion via SPARQL 1.1 property paths. Property paths allow us to retrieve concepts reachable within a given maximum number of hops transitively following the hierarchical relations in CPV. We use the short-hand notation {1, max} for these property paths. It defines a graph neighbourhood at most max hops away. This notation is not a part of the SPARQL standard, but it is formally defined by Seaborne (2014), and several RDF stores, including Virtuoso, support it. However, it can be rewritten to the more verbose standard SPARQL notation if full standards-compliance is required.

Score aggregation via aggregation functions is done using SPARQL 1.1 aggregates. However, probabilistic sum requires aggregation by multiplication, which cannot be implemented directly in SPARQL since it lacks an operator to multiply grouped bindings. Therefore, we implemented this aggregation function via post-processing of SPARQL results. Eventually, since the difference on the evaluated metrics between probabilistic sum and summation (\(a + b\)) turned out to be statistically insignificant, we opted for summation, which can be computed directly in SPARQL and is marginally faster. A side effect of this implementation is that the match scores in the matchmakers using this aggregation function are not normalized.

The execution time of the matchmakers can be improved by common optimization techniques for SPARQL. We reordered triple patterns in the matchmaking queries in order to minimize the cardinalities of the intermediate results. We reduced unnecessary intermediate bindings via blank nodes and property paths. Performance can be also enhanced by storing pre-computed data. While there is no need for data pre-processing specific for the matchmakers, derived data that changes infrequently can be materialized and stored in RDF. Doing so can improve the performance of matchmakers by avoiding the need to recompute the derived data at query time. This benefit is offset by increased use of storage space and an additional overhead with updates, since materialized data has to be recomputed when the data it is derived from changes. We used materialization for pre-computing IDF of CPV concepts. While IDF can be computed on the fly, we decided to pre-compute it and store it as RDF. Computation of IDF is implemented via two declarative SPARQL Update operations, the first of which uses a Virtuoso-specific extension function for logarithm (bif:log10()), and the second normalizes the IDFs using the maximum IDF.

The implementation of the matchmakers, described in Section 6.2.4, is built as a wrapper over the Virtuoso RDF store. Example SPARQL queries used by the matchmakers can be found at https://github.com/opendatacz/matchmaker/wiki/SPARQL-query-examples.

3.3.1 RESCAL

RESCAL is a machine learning algorithm for factorization of third-order tensors. It factorizes a tensor \(\mathcal{X}\) with \(n\) entities to a rank-\(r\) representation, so that each frontal slice \(\mathcal{X}_{k}\) of the tensor can be approximately reconstructed via matrix product from the decomposition to latent components, as shown in Fig. 12, using this formula:

\[X_{k} \approx AR_{k}A^{T}\qquad(1)\]

In this formula, \(A\) is an \(n \times r\) matrix containing the latent component representation of entities in \(\mathcal{X}\), \(A^{T}\) is its transposition, and \(R_{k}\) is a square \(r \times r\) matrix that models the interactions of the latent components in the \(k\)^th predicate (Nickel et al. 2011). Using this decomposition, RESCAL “explains triples via pairwise interactions of latent features” (Nickel et al. 2016, p. 17). Unlike in other latent feature models, the latent variables in RESCAL do not describe entity classes but latent entity factors instead (Tresp and Nickel 2014). The rank \(r\) is a “central parameter of factorization methods that determines generalization ability as well as scalability” (Nickel et al. 2014). While higher \(r\) increases the expressiveness of the latent features, it also increases the runtime of tensor factorization as well as its propensity for overfitting. Consequently, setting \(r\) to an appropriate value is a key trade-off to be made when tuning RESCAL.

RESCAL uses distinct latent representations of entities as subjects and objects, which enables efficient information propagation to capture correlations over long-range relational chains (Nickel and Tresp 2013b, p. 619) that may span heterogeneous relations. In this way, RESCAL is able to leverage contextual data that is more distant in the relational graph for collective learning, which we described in Section 1.6.2. Unlike other factorization methods that cannot model collective learning sufficiently, “the main advantage of RESCAL, […] is that it can exploit a collective learning effect when applied to relational data” (Nickel et al. 2012, p. 272).

RESCAL achieves a leading performance for link prediction tasks. It was shown to be superior for link prediction tasks on several datasets. Moreover, it scales better to large data than many traditional methods for statistical relational learning, such as Markov logic networks. Nickel et al. (2012) demonstrated how the execution of RESCAL can be parallelized and distributed across multiple computing nodes. RESCAL is also fundamentally simpler than other tensor factorization methods. Unlike similar algorithms, RESCAL stands out by a low Kolmogorov complexity. It is implemented only in 120 lines of code in Python (Nickel et al. 2011) using solely the NumPy⁹⁰ library.

Many extensions of RESCAL were proposed. Its state-of-the-art results and conceptual simplicity invite improvements. The aspects that the extensions deal with include negative training examples, handling literals, or type constraints.

RESCAL adopts the local closed world assumption (LCWA), which is used often for training relational models (Nickel et al. 2016, p. 13). It “approaches the problem of learning from positive examples only, by assuming that missing triples are very likely not true, an approach that makes sense in a high-dimensional but sparse domain” (Nickel et al. 2012, p. 273). However, “training on all-positive data is tricky, because the model might easily over generalize” (Nickel et al. 2016, p. 24). In order to avoid underfitting, negative examples can be generated via type constraints for predicates or valid ranges of literals. Nickel et al. (2016) propose generating negative examples by perturbing true triples. For instance, switching subjects in triples sharing the same functional property produces false, but type-consistent triples.

The original version of RESCAL (Nickel et al. 2011) uses only object properties as relations. Datatype properties with literal objects can only be used if the literals are treated as entities. When literals are included as entities in a tensor, although they never appear as subjects, the tensor’s sparseness grows. Moreover, since the number of distinct literals may significantly surpass the number of entities, this naïve treatment will greatly expand the dimensionality of the input tensor. Both high dimensionality and sparseness thereby increase the complexity of computing the factorization. Minor improvements can be attained by pre-processing literals, such as by discretizing numeric values, tokenizing plain texts, and stemming the generated tokens. Nevertheless, treatment of literals warrants a more sophisticated approach. To address this issue, Nickel et al. (2012) introduced an extension of RESCAL to handle literals via an attribute matrix that is factorized conjointly with the tensor with relations between entities. In a similar vein, Zhiltsov and Agichtein (2013) proposed Ext-RESCAL, an approach using term-based entity descriptions that include names, other datatype properties as attributes, and outgoing links.

Several researchers (Chang et al. (2014), Krompaß et al. (2014), Krompaß et al. (2015)) investigated adding type constraints to RESCAL. These constraints improve RESCAL by preventing type-incompatible predictions. The type compatibility can be determined by interpreting the rdfs:domain and rdfs:range axioms under LCWA or by evaluating custom restrictions, such as requiring the subject entity to be older than the object entity when predicting parents. These type constraints can be represented as binary matrices (Krompaß et al. 2014) indicating compatibility of entities. The original RESCAL considers all entities for possible relations, notwithstanding their type, which increases its model complexity and leads to “an avoidable high runtime and memory consumption” (Krompaß et al. 2014). Even though RESCAL is faster than the type-constrained approach with the same rank, using type constraints typically requires a lower rank to produce results that RESCAL is able of achieving only at higher ranks.

Other notable extensions of RESCAL add time awareness or tensor slice similarities. Kuchař et al. (2016) enhanced link prediction via RESCAL to be time-aware. We used this approach in data pre-processing, as described in Section 2.6.2, to model decaying relevance of older contract awards. Padia et al. (2016) obtained better results from RESCAL by considering the similarities of tensor slices.

3.3.2 Ranking matches

We applied link prediction via RESCAL to matchmaking, assuming that the tensor decomposition produced by RESCAL can accurately model the affinities between contracts and bidders. Probabilities of links predicted in the tensor slice representing contract awards can be obtained by reconstructing the slice from the tensor decomposition. Given the slice \(R_{award}\) for contract awards from the latent factor tensor \(\mathcal{R}\) produced by RESCAL, we can obtain predictions of entities awarded with the contract \(c\) by following Eq. 1 and computing the predictions vector \(p = A_{c}R_{award}A^{T}\). Entries in \(p\) can be interpreted as probabilities of the contract \(c\) being awarded to entities at corresponding indices in \(p\). Using the indices of bidders we can filter the entries in \(p\) and then rank them in descending order to obtain the best matches for \(c\).

We used no minimal threshold to filter out irrelevant matches. As reported in (Nickel et al. 2012), determining a reasonable threshold is difficult, because the high sparseness of the input tensors causes a strong bias towards zero (Nickel et al. 2012, p. 274). Consequently, instead of setting an arbitrary threshold, we ranked the predictions by their probability and projected the top-ranking predictions as the matches. This decision is a trade-off erring on the side of delivering less relevant results instead of producing fewer or no results.

Unlike SPARQL, RESCAL is a batch approach that cannot produce results in real time. First, it needs to factorize the input tensor to a decomposition that models the tensor. Once this model is built, predictions for individual contracts can be computed on demand. RESCAL is hence slow to cope with changing data. Matchmaking via RESCAL is thus more appropriate if the matches are delivered via periodic subscriptions instead of on-demand queries.

3.3.3 Implementation of RESCAL-based matchmakers

We implemented matchmaker-rescal, described in Section 6.2.5, a thin wrapper of RESCAL that runs our evaluation protocol, explained in Section 4.2. Instead of extending RESCAL, our contribution lies in the data preparation and pre-processing described in Section 2.6.2.

When developing the RESCAL wrapper, we needed to take several aspects of performance into consideration. Due to the size of the processed data it is important to leverage its sparseness, which is why we employ efficient data structures for sparse matrices from the SciPy⁹¹ library. Due to its size in memory, reconstructing the whole predictions slice is unfeasible for larger datasets. In order to reduce the memory footprint of the RESCAL-based matchmakers, we avoided reconstructing the whole predictions slice from the RESCAL factorization, but computed only the top-\(k\) results instead. Predictions were computed for each row separately, so that the rows could be garbage-collected to free memory. In order to enable parallelization, it was important to compile the underlying NumPy library with the OpenBLAS⁹² back-end, which allows to leverage multi-core machines for parallel computation of low-level array operations, such as the matrix product that is central to RESCAL.

4.4.1 Blind matchmakers

As a starting point, we evaluated the blind matchmakers described in Section 3.2.3. The results of their evaluation are summarized in Table 2. Since these matchmakers ignore the query contract, they are able to produce matches for any contract, and thus score the maximum PC. They cover the extremes of the diversity spectrum. On the one hand, the random matchmaker can recommend practically any bidder, most of whom come from the long tail. On the other hand, recommending the top winning bidders yields the lowest possible catalog coverage, the intersection of which with the long tail is empty by the definition of this matchmaker. Since 7 % of contracts is awarded to the top 10 most winning bidders, recommending them produces the same HR@10. Recommending the bidders that score the highest page rank is not as successful as simply recommending the top winning bidders, achieving an HR@10 of 0.03.

4.4.2 Aggregation functions

We evaluated the aggregation functions from Section 3.2.2.5. In each case, we used the t-norm and t-conorm from the same family; e.g., the Gödel’s t-norm was used with the Gödel t-conorm. The functions were applied to matchmaking via the pc:mainObject property with the weight of 0.6. This weight was chosen in order to allow the differences between the functions to manifest. For instance, if we used the weight of 1, Łukasiewicz’s aggregation would not distinguish between bidders who won one matching contract and those who won more. The results of this comparison are shown in Table 3. Product aggregation clearly outperforms the other functions in terms of accuracy. Both Gödel’s and Łukasiewicz’s aggregation functions do not learn sufficiently from the extent of the matched data. Similar findings were obtained in our previous work in Mynarz et al. (2015). This outcome led us to use the product aggregation in all other matchmakers we evaluated.

4.4.3 Individual features

As we described in Section 3.2.2.1, we used several properties that describe contract objects. We evaluated these properties separately, without weighting, to determine their predictive power. Evaluation results of the matchmakers based on the four considered properties are given in Table 4. The best-performing property is the pc:mainObject. As Fig. 13 illustrates, its HR@\(k\) grows logarithmically with \(k\), starting at 7 % chance of finding the contact’s winner as the first hit. We chose this property as our baseline that we tried to improve further on. The other properties achieved worse results. While the pc:additionalObject covers the long tail better, its prediction coverage is low because it is able to produce matches only for the few contracts that are described with this property. The pc:kind fails in the diversity metrics, covering only a minute fraction of bidders. Since there are only few distinct kinds of contracts in our dataset, this property is unable to sufficiently distinguish the bidders and thus concentrates only on recommending the most popular ones. The weak performance of the isvz:serviceCategory may be attributed to its limit to contracts for services.

4.4.4 Combined features

Having evaluated the properties individually we examined whether their combinations could perform better. We combined the properties with the baseline property pc:mainObject, using a reduced weight of 0.1 for the added properties. Besides the properties evaluated above, we also experimented with including the qualifiers of CPV concepts we described in Section 2.4.6.1. The evaluation results of the matchmakers based on the combinations of properties are presented in Table 5. None of the properties produced a significant synergistic effect with pc:mainObject. If there was an improvement, its scale was not practically meaningful. We also experimented with a larger range of weights for the combination with pc:additionalProperty, however, none of the weights led to a significant difference in the evaluation results. Our conclusion in this respect is in line with Maidel et al., who found in similar circumstances that “the inclusion of item concept weights does not improve the performance of the algorithm” (2008, p. 97).

4.4.5 Query expansion

Apart from using combinations of properties, we can also extend the baseline matchmaker via query expansion, as documented in Section 3.2.2.2. We evaluated the expansion to the related CPV concepts connected via hierarchical relations, both in the direction to broader concepts, to narrower concepts, or in both directions. The query expansion followed a given maximum number of hops in these directions. Since following too many hops to related concepts can introduce noise (Di Noia et al. 2012b), we weighted the concepts inferred by query expansion either by a fixed inhibition or by a weight derived from their IDF. The results of the experiments with query expansion are gathered in Table 6. Here, ↑ denotes the number of hops expanded to the broader concepts and ↓ indicates the hops to the narrower concepts. Expansion by one hop to broader and narrower concepts was able to improve on the accuracy metrics slightly. Overall, we found that introducing query expansion led only to minuscule changes in the performance of the baseline matchmaker. For instance, the expansion to broader concepts weighted by IDF produced results that differed only in higher decimal precision for the different numbers of hops followed.

4.4.6 Data reduction

We evaluated the impact of data reduction on HR@10 for the baseline matchmaker and the blind matchmaker that constantly recommends the top winning bidders. Prior to running the evaluation we reduced the number of links between contracts and bidders to a given fraction. For example, if the level of data reduction was set to 0.4, 60 % of the links were removed. Links to remove were selected randomly. Fig. 14 shows the HR@10 per level of data reduction for the two compared matchmakers. In general, we decreased the data reduction level by 0.1 for each evaluation run, but a smaller step was used for the lower levels to better distinguish the impact of data reduction at smaller data sizes. The evaluation showed that HR@10 grows logarithmically with the size of the data for the baseline, while the blind matchmaker performs the same no matter the data size. As can be expected, the baseline matchmaker improves its performance as the data it learns from accrues. Both approaches suffer from the cold start problem, although the baseline matchmaker improves rapidly with the initial data growth and demonstrates diminishing returns as data becomes larger.

4.4.7 Data refinement

Of the data refinement steps undertaken, as described in Section 2.3, we evaluated what impact better deduplication and mapping CPV 2003 to CPV 2008 had on the baseline matchmaker. Both steps improved the evaluation results of the matchmaker, as can be seen in Table 7. Better deduplication and fusion of bidders reduces the search space of possible matches, so that the probability of finding the correct match increases. Mapping CPV 2003 to CPV 2008 enlarges the dataset the matchmaker can learn from by 15.31 %, accounting for older contracts described by CPV 2003. However, while HR@10 improves after this mapping, CC@10 decreases, which may be explained by more data affirming the few established bidders. Better deduplication improves the accuracy metrics only slightly, which may be due to the original data already being free of most duplicates. Nevertheless, in our prior work (Mynarz et al. 2015), deduplication produced the greatest improvement in the evaluation of the baseline matchmaker.

4.4.8 Counter-measures to limits of ground truth

We evaluated two approaches devised as counter-measures to address the limits of our ground truth we described in Section 3.1. One of them weighted contract awards by the zIndex fairness score of the contracting authority, the other limited the training dataset to the contracts awarded in open procedures. The proposed counter-measures were not successful. Both approaches fared worse than our baseline, as documented in Table 8. While the impact of weighting by zIndex is barely noticeable, the restriction to open procedures decreased most of the observed metrics. The decrease may be attributed to the smaller size of training data, even though the majority of contracts in our dataset were awarded via an open procedure.

In conclusion, rather than improving on the baseline matchmaker, we managed to analyze what makes it perform well. It benefits mostly from refining and extending the training data and from using the product aggregation function. Other extensions of the baseline matchmaker were found to have little practical benefits. A slightly better results were achieved when query expansion by one hop to broader and narrower concepts was used, although this improvement was counterweighed by an increased response time. Simply put, the evaluation indicated that “simple models and a lot of data trump more elaborate models based on less data” (Halevy et al. 2009, p. 9).

4.5.1 Hyper-parameters

The central hyper-parameter of RESCAL is the rank of its decomposition. As reported in existing research, RESCAL’s accuracy improves with increasing rank of the factorization. With higher ranks we observe diminishing returns and, eventually, HR@10 ceases to improve at around rank 500, as Fig. 15 displays. An analogous impact can be observed for CC@10, although its growth is much more subtle. We tested ranks ranging from 10 to 1000, using smaller intervals for greater resolution in low ranks. Runtime of tensor factorization with RESCAL increases approximately linearly with the rank, so there is a need to balance the quality of RESCAL’s results with the available time to compute them.

We observed that performance improves with rank only for more selective properties, e.g., pc:mainObject. Properties that have fewer distinct values, such as pc:kind, reach their peak performance already at lower ranks.

RESCAL allows to tune its generalization ability via the regularization parameters \(\lambda_{A}\) for the latent factor matrix \(A\) and \(\lambda_{R}\) for the tensor \(R\) that captures the interactions of the latent components. Increasing the amount of regularization helps avoid overfitting. Optimal values of the regularization parameters are dataset-specific. While Padia et al. (2016) achieved the best results with \(\lambda_{A} = 10\) and \(\lambda_{R} = 0.2\), Kuchař et al. (2016) obtained the peak performance by setting both to 0.01. In our case, we found that relatively high values of the regularization parameters tend to achieve the best results. We set both \(\lambda_{A}\) and \(\lambda_{R}\) to be 10. A comparison of a few selected values of the regularization parameters is shown in Table 9 for pc:mainObject at rank 50.

The remaining hyper-parameters exposed by RESCAL include initialization methods and convergence criteria. RESCAL can initialize the latent matrices either randomly or by eigenvalues of the input tensor, the latter method being clearly superior, as shown in Table 10 for pc:mainObject at rank 50. RESCAL stops when it reaches the given convergence criteria, which can be specified either as the maximum number of iterations or as the maximum residual. We used the default values for these hyper-parameters.

In the further experiments, we use rank 500 and both \(\lambda_{A}\) and \(\lambda_{R}\) set to 10, unless specified otherwise.

4.5.2 Feature selection

We evaluated the predictive power of the descriptive features that can be obtained from our dataset. While most features correspond to RDF properties, some are derived from property paths, such as pc:location/schema:address or pc:awardCriteriaCombination/pc:awardCriterion/pc:weightedCriterion, which we shorten as pc:weightedCriterion. We started by assessing the results of matchmakers based on the individual features. We combined each feature with the ground truth comprising contract awards and observed how well the feature can help predict the awarded bidders. We evaluated the HR@10 of selected features at ranks 50 and 500, as shown in Fig. 16.

Out of the features pc:mainObject obtained the best results. Higher rank improves the results of most features, such as pc:mainObject, pc:contractingAuthority, or isvz:serviceCategory. However, increasing rank has the inverse effect on other features, including pc:procedureType, pc:actualPrice, or isvz:mainCriterion. We observed that features for which higher rank improves the evaluation results have higher cardinality, while the converse is usually true for features with low cardinality. Here, cardinality is the number of distinct values a feature has in a dataset. For instance, the cardinalities of the mentioned features for which results improve with the increased rank are 4588, 16982, and 43; whereas the cardinalities of the respective features that exhibit the inverse are 10, 15, and 4. These observations suggest that higher rank can reach better resolution if provided with a feature having a higher cardinality. Conversely, RESCAL cannot leverage a higher rank if given a feature with low cardinality, in which case its latent components capture noise instead of informative distinctions. Nevertheless, high cardinality does not imply good results, such as in case of pc:weightedCriterion that has 27793 distinct values in our dataset, yet achieves poor results.

Results of all evaluation metrics for the individual features as listed in Table 11. The pc:mainObject property clearly stands out with the best results of the accuracy metrics. Although the properties of bidders, i.e. ares:zivnost and rov:orgActivity, achieve the best results for the diversity metrics, their poor accuracy is comparable to the results of random matchmaking.

As in the evaluation of the SPARQL-based matchmakers, we adopted pc:mainObject as our pivot feature that we combined with additional features. After we evaluated the features separately, our next step was to see how they perform in combination with pc:mainObject. The evaluation results of these feature pairs are shown in Table 12. In case of rdf:type we included the links to classes of public contracts and bidders. The skos:broaderTransitive property adds the hierarchical relations in CPV, thus emulating the query expansion we described in Section 3.2.2.2. The skos:related property brings in the qualifying concepts from the supplementary vocabulary of CPV.⁹⁴ We achieved the best improvement in all evaluated metrics with the rov:orgActivity property that associates bidders with concepts from the NACE classification in the Business Register we covered in Section 2.4.6.2.

Ultimately, we examined a larger set of features that improved the results of pc:mainObject when combined with it one by one. We tested separately a subset of the improving features that involved only the links to subject classifications via pc:mainObject, pc:additionalObject and rov:orgActivity, together with the hierarchical relations in both CPV and NACE represented by the skos:broaderTransitive property. The evaluation results for both combinations of additional features are presented in Table 13.

The subset of subject classifications fared better than indiscriminate inclusion of all improving features. Yet still, this combination of features did not surpass the evaluation results of pc:mainObject combined just with rov:orgActivity. The worse results scored by the combinations of features individually improving the pc:mainObject baseline invalidate our assumption that the contributions of features do not cancel themselves out. To the contrary, this interplay illustrates that their contributions are not cumulative, and, in fact, some features diminish the contribution of other features.

The directionality of relations in the input tensor matters for RESCAL. We examined this characteristic using the rov:orgActivity property. In the source data, rov:orgActivity is a property of bidders associating them with NACE concepts. We found out that the evaluation results differ widely if the domain of this property changes. Apart from its directionality in the source data, we evaluated the cases in which the property is directly attached to contracts and when it is symmetric. As can be seen in Table 14, the symmetric option decidedly outperforms the others. Nevertheless, treating relations as symmetric does not always lead to an improvement, as in the case of pc:mainObject when the symmetric interpretation in fact worsens the evaluation results.

4.5.3 Ageing relations

Evaluation of ageing was done by time series cross-validation, as described in Section 4.2. Ageing, which we covered in Section 2.6.2, was applied to the tensor slice containing the links between public contracts and awarded bidders. We compared how ageing affects matchmaking with the pc:mainObject property. As shown in Table 15, applying the ageing worsens the results of the accuracy metrics. When compared to pc:mainObject evaluated using the n-fold cross-validation, the results in time series cross-validation are notably worse, which can be attributed to the lower volume of data available in this evaluation protocol.

4.5.4 Use of literals

We experimented with a limited use of literals, namely via discretization of the actual prices of contracts, represented by the pc:actualPrice property, which we split into 15 equifrequent intervals having approximately the same number of members. Actual prices were known for 91.5 % of contracts in the evaluated dataset. We combined the discretized actual prices with pc:mainObject. A comparison of the combination with pc:mainObject only is shown in Table 16. Adding actual prices mostly worsens the evaluation results. We surmise that the decrease can be explained by noisy data about prices. Upon manual inspection, we found that prices may be reported as coefficients to be multiplied by an implicit factor that is not part of the structured data.

In summary, the best results in RESCAL-based matchmakers were achieved for pc:mainObject combined with rov:orgActivity. These relations linking subject classifications, i.e. CPV and NACE, turned out to be the most informative for the prediction of awarded bidders. We found that rank 500 tends to deliver the best accuracy, especially if combined with relatively high regularization parameters that prevent overfitting.

6.1.1 Elasticsearch

Elasticsearch (ES)⁹⁵ is an open source full-text search engine based on Apache Lucene.⁹⁶ ES indexes JSON documents that can be searched via ES query DSL exposed through an HTTP API. The query DSL is an expressive query language based on JSON. The DSL allows to search for terms in full texts and match patterns in the indexed data structures. Simple queries can be combined into complex ones using boolean operators. Besides the basic search operations, ES features high-level query types, such as the More Like This query, which supports similarity-based retrieval. Since ES queries are represented as structured data in JSON, they can be generated easily, lending itself to integration in other tools.

6.1.2 GeoTools

GeoTools⁹⁷ is an open source Java library for working with geospatial data. Its implementation complies with standards of the Open Geospatial Consortium (OGC). For example, it supports reprojection of coordinate data between standard coordinate reference systems.

6.1.3 LinkedPipes-ETL

LinkedPipes-ETL (LP-ETL) (Klímek et al. 2016)⁹⁸ is an open source data processing tool for converting diverse data sources to RDF and performing various transformations of RDF data. LP-ETL follows the Extract-Transform-Load (ETL) workflow. For each ETL phase it offers components dedicated to specific data processing tasks. For example, an extraction component can download data from a given URL, a transformation component can decompress a ZIP archive, and a load component can write data to a file. The components can be composed into pipelines that automate potentially complex data processing workflows. The design of LP-ETL evolved from UnifiedViews and in many respects it can be considered a successor to this project.

6.1.4 OpenLink Virtuoso

OpenLink Virtuoso⁹⁹ is an RDF store that implements SPARQL and a plethora of additional functionality for working with RDF data. A notable characteristic of Virtuoso is its column-wise storage enabling vectored query execution (Erling 2012), which gives Virtuoso a good query performance that scales well to large RDF datasets. Virtuoso offers an open source version that lacks some of the features available in the commercial version.

6.1.5 RESCAL

RESCAL (Nickel et al. 2011) is a tensor factorization technique for relational data modelled as three-way tensors. It has an open source implementation written in Python using the NumPy¹⁰⁰ and SciPy¹⁰¹ modules for low-level array operations. RESCAL achieves superior performance on factorization of large sparse tensors, while having a fundamentally simpler implementation than other tensor factorization techniques.

6.1.6 Saxon XSLT and XQuery Processor

Saxon XSLT and XQuery Processor¹⁰² is an implementation of several W3C standards for processing XML data, including XSLT, XQuery, and XPath. Saxon can transform XML data via XSLT stylesheets or query it via XQuery and XPath. The limited Saxon-HE version is available as open source.

6.1.7 Silk Link Discovery Framework

Silk (Bryl et al. 2014)¹⁰³ is an open source link discovery framework for instance matching. It offers an extensive arsenal of similarity measures and combination functions for aggregating similarity scores. Silk generates links by executing declarative linkage specifications that describe how to compare resources in the source and target datasets to discover matches. As an alternative to explicit linkage specifications, Silk supports active learning from examples of valid links (Isele and Bizer 2013). Data to be interlinked can be retrieved from SPARQL endpoints and RDF or CSV files. Silk thus supports integration of heterogeneous data by materializing explicit links across the integrated data sources.

6.1.8 Tarql

Tarql¹⁰⁴ is an open source CLI tool for converting CSV to RDF via SPARQL CONSTRUCT queries. It extends the query engine of Apache Jena¹⁰⁵ such that values in each CSV row are made available as inline data to the SPARQL query provided by the user. Queries can thus refer to tabular data via query variables based on column names from the source CSV. Instead of resorting to custom-coded conversion scripts, such setup enables to harness the expressivity of SPARQL as a native RDF data manipulation language.

6.1.9 UnifiedViews

UnifiedViews (Knap et al. 2017)¹⁰⁶ is an open source ETL framework with native support for RDF. It allows to execute data processing tasks, monitor progress of their execution, debug failed executions, and schedule periodic tasks. Concrete data processing workflows can be implemented as pipelines that combine pre-made data processing units. Each unit is responsible for a data processing step, such as applying an XSL transformation or loading metadata into a data catalogue. UnifiedViews has been in development since 2013 and it can be considered relatively stable, as it has been already deployed to address many use cases.

6.2.1 discretize-sparql

discretize-sparql¹⁰⁷ allows to discretize numeric literals in RDF data exposed via a SPARQL Update (Gearon et al. 2013) endpoint. Discretization groups continuous numeric values into discrete intervals. It is typically used for pre-processing continuous data for machine learning tools that support only categorical variables. A discretization task in discretize-sparql is formulated as a SPARQL Update operation that uses pre-defined variable names endowed with specific interpretation. The WHERE clause of the operation must contain the variable ?value that selects the values to discretize. The variable ?interval will be bound to the intervals generated by the tool. Consequently, the update operation can be formulated as if it contained a mapping from the values to discretize to intervals in which they belong. For instance, ?interval can be used in the INSERT clause and ?value in the DELETE clause in order to replace the values to discretize with intervals. The tools first rewrites the provided update operation to a SELECT query to retrieve the values to discretize and then it is rewritten to an update operation including the actual mapping from numeric literals to intervals.

6.2.2 elasticsearch-geocoding

elasticsearch-geocoding¹⁰⁸ is a tool for geocoding postal addresses by ES. It uses an ES index seeded with reference addresses to which it matches the addresses to geocode. Such an index can be prepared by using sparql-to-jsonld to convert RDF data into JSON, followed by jsonld-to-elasticsearch to upload the JSON data into ES. The tool loads the addresses to geocode from a SPARQL endpoint using a given SPARQL SELECT query that produces tabular data with specific column names recognized for components of addresses, such as postal codes or house numbers. For each address an ES query is generated to find matching reference addresses. Geo-coordinates of the best ranking result for each query are output as RDF serialized in the N-Triples syntax.

6.2.3 jsonld-to-elasticsearch

jsonld-to-elasticsearch¹⁰⁹ indexes Newline Delimited JSON (NDJSON) in ES. Each input line represents a JSON document that is analysed and bulk-indexed in ES using a provided mapping. The mapping specifies a schema that instructs ES how to store and index the individual attributes in the input documents. If the input JSON-LD contains the @context attribute, it is removed due to being redundant. Each JSON-LD document must contain the @id attribute, which used as the document identifier in ES. RDF data can be prepared into this expected format using sparql-to-jsonld.

6.2.4 matchmaker-sparql

matchmaker-sparql¹¹⁰ is a CLI application for evaluation of matchmaking based on SPARQL. The evaluation setup is guided by a configuration file provided to the application. The configuration describes the data to use, connection to a SPARQL endpoint to query and update the data, parameters of the matchmaker, and the evaluation protocol for the n-fold cross-validation.

6.2.5 matchmaker-rescal

matchmaker-rescal¹¹¹ is a command-line application that wraps the original implementation of RESCAL in Python. It serves as an exploratory tool for experimentation with RESCAL-based matchmaking. The sole purpose of the tool is to evaluate link prediction for a given relation using cross-validation and the metrics defined in Section 4.3. Its input consists of the ground truth matrix encoding the relation to predict, additional matrices encoding other relations, and configuration with hyper-parameters for RESCAL. The matrices required as input by this tool can be prepared by sparql-to-tensor.

6.2.6 sparql-to-csv

sparql-to-csv¹¹² allows to save results of SPARQL queries into CSV. It is primarily intended to support data preparation for analyses that require tabular input. It has two main modes of operation: paged queries and piped queries. In both cases it generates SPARQL queries from Mustache¹¹³ templates, which enable to input parameters into the queries. The mode of paged queries splits the provided SELECT query into queries that retrieve partial results delimited by LIMIT and OFFSET, so that demanding queries that produce many results can be executed without running into the load restrictions imposed by the queried RDF stores, such as timeouts or maximum result sizes. The mode of piped queries allows using Unix pipes to chain the execution of several dependent SPARQL queries. In this mode, each solution from results of the piped query is bound as variables for the template that generates the subsequent query. Such approach facilitates the decomposition of complex queries into a chain of simpler queries that do not strain the queried RDF store. It also enables to query a SPARQL endpoint using data from another SPARQL endpoint, in a similar manner to federated queries (Prud’hommeaux and Buil-Aranda 2013). Alternatively, the query results can be piped to a template producing SPARQL Update operations, so that complex data transformations can be divided into simpler subtasks.

6.2.7 sparql-to-graphviz

sparql-to-graphviz¹¹⁴ generates a class diagram representing an empirical schema of RDF data exposed via a SPARQL endpoint. The empirical schema reflects the structure of instance data in terms of its vocabularies. Instead of representing the structures prescribed by the vocabularies (e.g., rdfs:domain and rdfs:range), it mirrors the way vocabularies are used in instance data, such as in the actual links between resources. In this way, it supports the exploration of unknown data that may not necessarily conform to the expectations set by its vocabularies. In order to separate concerns, in place of producing a visualization, the tool generates a description of the schema in the DOT language.¹¹⁵ The description can be then turned into an image using Graphviz,¹¹⁶ an established visualization tool that offers several algorithms for constructing graph layouts. Instead of producing a bitmap image, a vector image in SVG can be generated, which lends itself to further manual post-production to perfect the visualization.

6.2.8 sparql-to-jsonld

sparql-to-jsonld¹¹⁷ retrieves RDF data from a SPARQL endpoint and serializes it to JSON-LD documents. It starts by fetching a list of IRIs of resources selected by a provided SPARQL SELECT query. The query allows to filter the resources of interest, such as instances of a given class. For each resource a user-defined SPARQL CONSTRUCT or DESCRIBE query is executed. This query selects or constructs the features that describe the resource. Both SPARQL queries are provided as Mustache¹¹⁸ templates to allow parametrization. Each retrieved description in RDF is converted to JSON-LD and transformed via a provided JSON-LD frame that coerces the input RDF graph into a predictable JSON tree. The output is appended to a file serialized as NDJSON.

6.2.9 sparql-to-tensor

sparql-to-tensor¹¹⁹ exports RDF data from SPARQL endpoints to tensors. The tensors are represented as a collection of frontal slices serialized as sparse matrices in the MatrixMarket coordinate format.¹²⁰ IRIs of the tensor entities are written to a headers.txt file. Each IRI is written on a separate line, so that line numbers can be used as indices of the entities in the matrices. The headers file can thus be used to translate the indices in matrices to IRIs of RDF resources. This output complies with the format used by the Web of Needs’ RESCAL matchmaker (Friedrich 2015).

Tensors are constructed from results of SPARQL SELECT queries provided to the tool. Each query must project several variables with pre-defined interpretation. The ?feature variable determines the tensor slice. It typically corresponds to an RDF property, but it can also represent a feature constructed from the source RDF data. The ?s variable is an entity that is the subject of the feature, and the ?o variable is its object. An optional variable ?weight can indicate the weight of the relation between the entities. It is a decimal number from the interval \(\left[0, 1\right]\), with the default value being 1. The SELECT queries must be provided as Mustache¹²¹ templates that allow to retrieve the query results via pages delimited by LIMIT and OFFSET. Support of multiple queries enable to separate concerns and write simpler queries for the individual features.

6.2.10 sparql-unlimited

sparql-unlimited¹²² can execute SPARQL Update operations that affect many resources by running multiple updates that affect successive subsets of these resources. The input SPARQL Update operation must be provided as a Mustache¹²³ template containing a variable for the LIMIT to indicate the size of the subset to process. Operations rendered from this template are executed repeatedly until the requested SPARQL endpoint responds with a message reporting that no data was modified. In order to avoid repeating processing of the same subsets of data, either an OFFSET variable can be provided, which is incremented by the limit in each step, or the update operation itself can directly filter out the already processed bindings. The latter approach is preferable since it avoids sorting a potentially large list of resources affected by the update operation. Due to its stopping condition, the tool can be used only for update operations that eventually converge to a state when there is no more data to modify. Since there is no standard way for SPARQL endpoints to respond that no data was modified by a received update operation, the tool relies on the way Virtuoso responds, which makes it usable only with this RDF store.

6.2.11 vocab-to-graphviz

vocab-to-graphviz¹²⁴ visualizes RDF vocabularies via Graphviz.¹²⁵ It converts an input vocabulary from an RDF file to a description of a class diagram in the DOT language.¹²⁶ The description can be subsequently rendered to an image via Graphviz. The generated class diagram captures the relations between the vocabulary’s terms as defined by its schema axioms, such as rdfs:domain or rdfs:range. It thus functions in a way similar to sparql-to-graphviz.