Nihel Kooli
email: nihel.kooli@loria.fr

Abdel Belaïd
email: abdel.belaid@loria.fr

Inexact Graph Matching for Entity Recognition in OCRed Documents

Keywords: entity recognition, local structure, graph matching, mislabeling correction, structure model, graph clustering

This paper proposes an entity recognition system in image documents recognized by OCR. The system is based on a graph matching technique and is guided by a database describing the entities in its records. The input of the system is a document which is labeled by the entity attributes. A first grouping of those labels based on a function score leads to a selected set of candidate entities. The entity labels which are locally close are modeled by a structure graph. This graph is matched with model graphs learned for this purpose. The graph matching technique relies on a specific cost function that integrates the feature dissimilarities. The matching results are exploited to correct the mislabeling errors and then validate the entity recognition task. The system evaluation on three datasets which treat different kind of entities shows a variation between 88.3% and 95% for recall and 94.3% and 95.7% for precision.

I. INTRODUCTION

An entity is a homogeneous group of attributes such as an enterprise in a business form or some meta-data representing the title, the authors and their affiliation in a scientific paper. It is characterized with its attributes. Entity recognition in documents is the task of identifying the entity attributes. It adds a wealth of knowledge to help us understand the document content. Recognizing entities is an important task in enterprises and constitutes an essential component of data integration research community. The task is not easy, especially when dealing with OCRed documents since there are numerous problems to solve. Most prominently, the OCR alters the document structure and introduces errors in the text. Furthermore, attribute locations in the physical structure of documents vary. This requires high-level knowledge to identify them.

In the literature, the entity recognition approaches can be classified into three categories: context oriented approaches, data oriented approaches and structure oriented approaches.

The first ones rely on contextual and linguistic rules for labeling the entity elements in the text. They require predefined rules and are domain and language dependent. An example of these approaches was proposed in [START_REF] Hashemi | Extraction of features with unstructured representation from html documents[END_REF] to extract events in online newspapers.

Secondly, the data oriented approaches are based domainand language-dependent. on an annotated corpus and tend to treat the problem as a classification one, or on a predefined database and try to match the entity definition in the database and its representation in the document by searching for the common terms. An example of the first strategy of approaches is described in [START_REF] Isaac | A data-intensive approach to named entity recognition combining contextual and intrinsic indicators[END_REF] which uses a Bayesian model to classify entity attributes based on contextual and intrinsic features. In second strategy context, authors in [START_REF] Chakaravarthy | Efficiently linking text documents with relevant structured information[END_REF] provide EROCS algorithm to identify entities embedded in document segments (few consecutive sentences). EROCS uses a score, defined for an entity with respect to a segment, which considers the frequency of the common terms in the segment and their importance in the database. This work treats web documents, so it considers the text as a sequence of lines and uses strict comparison between terms. A modified version, called M-EROCS, that treats OCRed documents was proposed in our earlier work in [START_REF] Kooli | Semantic label and structure model based approach for entity recognition in database context[END_REF]. It identifies attributes in contiguous blocks given by the OCR and tolerates content errors in the comparison using the Edit Distance. However, it does not solve the problem of under-segmentation since it assumes that the terms in each block belong to a single entity. Also, it does not assemble non-contiguous parts of the entity.

Finally, the structure oriented approaches propose to benefit from the physical and/or logical structure of the document for the recognition. For example, the authors in [START_REF] Liang | Logical labeling of document images using layout graph matching with adaptive learning[END_REF], [START_REF]Content features for logical document labeling[END_REF] use graphs to model the document layout for logical labeling. This model is proposed at document level and represents spatial relationships between blocks segmented by OCR. However, this approach is dependent on document class. A recent approach, proposed in [START_REF] Santosh | g-dice: graph mining-based document information content exploitation[END_REF], aims to identify table rows content using a set of text field patterns selected by a user. This approach relies on a graph isomorphism technique between a pattern graph and a model graph. The graphs represent the field names and the relative position between them. This approach treats only linear structure and is dependent on the user given patterns.

The proposed entity recognition approach, called G-ELSE (Graph matching for Entity Local Structure Extraction), is a combination of the three types of approaches described previously. It lies in the context of entity recognition guided by a predefined database describing each entity attributes by its records. Entity attributes are labeled in the document using their syntactic information in the database, as detailed in [START_REF] Kooli | Entity matching in ocred documents with redundant databases[END_REF]. The entity labels which are locally close are represented by a structure graph which is then matched with a learned structure model. The matching results are then used to correct the mislabeling and validate the entity recognition.

Our graph matching strategy consists of an inexact graph matching technique which looks for the best match by tolerating noisy representation and errors. Several approaches have been proposed in the literature for graph matching in document analysis as described in [START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF]- [START_REF] Foggia | Graph matching and learning in pattern recognition in the last 10 years[END_REF]. The most commonly used approach is the Graph Edit Distance (GED) as reported in [START_REF] Sanfeliu | A distance measure between attributed relational graphs for pattern recognition[END_REF]. GED is defined as the weighted sum of the edit operation costs needed to transform one graph to the other. However, in the case of labeled graph where the labels are not of nominal type but represent a set of numeral attributes, it is generally not possible to find an exact mapping between those labels. To deal with such problems, label discretization based solution can be used to transform the numerical attributes into nominal labels, but such mapping is very sensitive to discretization errors. Another solution consists of defining the mapping cost as the sum of distances between the label values and using a cost threshold for the label mapping decision but it is not easy to find the proper threshold. This problem was treated in [START_REF] Bodic | An integer linear program for substitution-tolerant subgraph isomorphism and its use for symbol spotting in technical drawings[END_REF] by reformulating the problem in the Integer Linear Program (ILP) formalism and integrating the label mapping cost into the graph matching cost. However, this approach only takes into account the label substitution operation and does not treat the deletion of nodes or arcs. This work is a thorough extension of the work reported in [START_REF] Kooli | Semantic label and structure model based approach for entity recognition in database context[END_REF] which performs substitution tolerant graph matching for the entity structure correction and involves human for the structure model learning. The mislabeling correction proposal was detailed in our previous work [START_REF] Kooli | Entity local structure graph matching for mislabeling correction[END_REF]. In this paper, we add the node and arc insertion and deletion in the graph matching in order to tolerate the noisy representation of our real graphs. We also propose an unsupervised learning of the structure model based on a clustering algorithm. Moreover, we integrate probability estimation of the labels belonging to the entities based on their structure for making the recognition decision. We also extend the experiments by validating the system on two other datasets.

The remainder of this paper is organized as follows. The entity recognition approach is detailed in Section II. Then, experiments on three real world datasets are presented in Section III. Section IV concludes.

II. PROPOSED APPROACH: G-ELSE

A. Entity selection

A label is defined as: l i = (c i , conf i , v i , sim i ), where c i is the corresponding column (field) in the database, conf i is the confidence of labeling l i as a field c i , v i = {t j } is the value of the label represented by a bag of words and sim i is the Levenshtein distance between v i and e.c i where e.c i is the attribute of the entity e corresponding to the field c i . Each input document is represented by a set of labels d = {l i }.

After labeling, labels are grouped into candidate entities. The grouping is made possible using a score defined in [START_REF] Hashemi | Extraction of features with unstructured representation from html documents[END_REF].

score(e, d) = li∈F (e,d)

P (l i ∈ e|e).conf i .sim i ( 1
)
where e is an entity, P (l i ∈ e|e) is the probability that the label l i belongs to a known entity e (initialized to 1 at this phase), F (e, d) is the set of labels that belong to d and contained as well in the entity e, i.e.

l i ∈ F (e, d) ≡ (l i ∈ d and v i e.c i )
where v i e.c i means that v i and e.c i are considered similar according to the string distance of value sim i .

The set of labels d is then matched with an entity e m when: e m = arg max e∈E score(e, d). A rejection threshold T is defined for score(e m , d) to deduce the set of candidate entities for the document. This threshold is empirically fixed.

B. Structure building

An entity local structure is modeled by an attributed graph G = (N, A, µ, ξ) where N is a finite set of nodes corresponding to field labels, A ⊆ N × N is a finite set of arcs representing the geometrical relations between the nodes, µ : N → L N and ξ : A → L A are two functions assigning a label to a node and an arc respectively. L N and L A are discrete sets of labels for the nodes and the arcs respectively. Each arc a ij ∈ A linking the nodes n i and n j is represented by n i n j .

A node n i corresponding to a label l i is defined in [START_REF] Isaac | A data-intensive approach to named entity recognition combining contextual and intrinsic indicators[END_REF].

n i = (c i , conf i , nt i , nl i , p i ) (2)
where nt i is the number of terms, nl i is the number of lines and p i is the normalized font size according to the average font in document (small: 0, medium: 1 2 , large: 1). For an arc a ij , we define a feature vector describing the spatial relationships between the labels in [START_REF] Chakaravarthy | Efficiently linking text documents with relevant structured information[END_REF].

a ij = (vs ij , hs ij , al ij ) (3)
where vs ij (vertical separation) is the number of lines that separate the labels corresponding to n i and n j . hs ij (horizontal separation) is the distance, in number of characters, that separates the bounding boxes of the labels corresponding to n i and n j . vs ij and hs ij are signed values to inform about the relative vertical position ("above" or "below") or the relative direction ("on the right" or "on the left").

al ij = (rJust ij , lJust ij , cent ij )
is a vector of three binary values informing about line alignment ("right aligned" or "left aligned" or "centered"). Slight variation (≤ 20 pixels) between the line boundaries is tolerated for the alignment.

C. Structure matching

The local structure graph is compared with the structure model. This can be formulated as a problem of inexact graph matching between a candidate graph and a model graph in the structure model. For matching, the arc and node label distortions (i.e. variations in their attributes) are considered. Also, extraneous and missed arcs or nodes in the candidate graph are taken into account. In order to solve this problem which is generally NP-hard, we use the branch and bound algorithm, [START_REF] Wong | An algorithm for graph optimal monomorphism[END_REF], which proposes a tree search of the node mapping with backtracking using heuristics. This algorithm is easily adapted to our context since it takes into account the node and arc attributes to provide the matching heuristics. In fact, we employ syntactic/semantic and physical heuristics. Some heuristics are generic, such as:

• a label which corresponds to an alphabetic field (for example, name, city, title, etc.) can not be mapped to the one that corresponds to numeric or alphanumeric field (for example, zip code, phone number, date, etc.);

• paths that match more than N labels of uncommon fields are eliminated, where N is empirically fixed (for example, N = 3 for enterprise entities).

We also employ some dataset specific heuristics, such as :

• paths present on the right of a postal code other than a city are eliminated;

• an author can not be present above a title in a bibliography reference header structure.

Let δ : G → M ∪ { } be a graph mapping function from a candidate graph G = (N G , A G , µ G , ξ G ) to a model graph M = (N M , A M , µ M , ξ M ). To allow the node deletion, it is possible to map a node in G to . The graph matching cost for the mapping δ from G to M is shown in [START_REF] Kooli | Semantic label and structure model based approach for entity recognition in database context[END_REF].

C(G, M, δ) = α |N G | n∈N G C N (n, δ(n)) + 1 -α |A G | n∈N G n ∈N G C A (nn , δ(n)δ(n )) (4)
where α ∈ [0, 1] and

C N : N G × N M → R + and C A : A G × A M → R +
are the mapping cost functions for the nodes and arcs respectively. Let ∆ be the set of the possible mapping functions from G to M . The matching cost is defined in [START_REF] Liang | Logical labeling of document images using layout graph matching with adaptive learning[END_REF].

C(G, M ) = min δ∈∆ C(G, M, δ) (5)
Let F N = {nt, nl , p} and F A = {vs, hs, al } be two sets of node and arc features respectively. The node mapping cost function from

n 1 = (c 1 , conf 1 , nt 1 , nl 1 , p 1 ) ∈ N G to n 2 = (c 2 , conf 2 , nt 2 , nl 2 , p 2 ) ∈ N M is shown in (6). C N (n 1 , n 2 ) = λ n2 (1 -conf 1 .conf 2 ) if c 1 = c 2 ; λ n2 f ∈F N λ f d f (f 1 , f 2 ) else.
(6) The arc mapping cost function from a 1 = (vs 1 , hs 1 , al 1 ) ∈ A G to a 2 = (vs 2 , hs 2 , al 2 ) ∈ A M is defined in [START_REF] Santosh | g-dice: graph mining-based document information content exploitation[END_REF].

C A (a 1 , a 2 ) = λ a2 f ∈F A λ f d f (f 1 , f 2 ) ( 7
)
where λ n2 , λ a2 ∈ [0, 1] are the weight factors for n 2 , a 2 , λ f ∈ [0, 1] depends on the feature relevance and f 1 , f 2 are the values corresponding to the feature f for n 1 , n 2 or a 1 , a 2 . Dissimilarities of scalar features are defined in [START_REF] Kooli | Entity matching in ocred documents with redundant databases[END_REF].

d f (f 1 , f 2 ) = |f N 1 -f N 2 | ∀f ∈ F N ∪ F A \ {al} (8) f N 1 resp. f N 2 is the normalized value of f 1 resp. f 2 . f N 1 (equivalently f N 2 ) is defined in (9). f N 1 = f 1 -max(f 1 ) max(f 1 ) -min(f 1 ) (9)
where max(f 1 ) and min(f 1 ) represent the maximum and the minimum values respectively and are dataset dependent. The alignment dissimilarity is defined in [START_REF] Hancock | Pattern analysis with graphs: Parallel work at bern and york[END_REF].

d al (al 1 , al 2 ) = 0 if al 1 × al 2 = 0; 1 else. ( 10
)
Comparing a candidate graph to all model graphs in the structure model is time consuming. We therefore propose to filter these graphs using semantic and structural heuristics:

• the number of lines in the local structure;

• the number of nodes having a common label field;

• the logical order of the labels in a page line or column.

Given a set of model graphs S M = {M 1 , ..., M n } and one candidate graph G, the matching is equivalent to the selection of the model graph M match , as in [START_REF] Foggia | Graph matching and learning in pattern recognition in the last 10 years[END_REF].

M min = arg min Mi∈S M C(G, M i ) (11)
The selected model graph is retained if its graph matching cost is below an empirically fixed threshold.

D. Mislabeling correction

A matched model graph with a candidate graph is used to correct the following three types of mislabeling in the local structure: missed labels, erroneous label fields and extraneous labels. These errors are corrected using the deletion, substitution and insertion operations as follows:

• The extraneous nodes in the model graph may correspond to missed labels in the local structure. The geometrical relations provided by the arcs related to these nodes are used to localize the missed labels in the document. To validate these label correspondence to the candidate entity in the database, their values are compared to the entity attributes by being less strict in the string distances than in the labeling step.

• The substituted node labels in the model graph are used to correct the label fields in the local structure.

• the labels corresponding to deleted nodes in the candidate graph are pruned in the local structure. Fig. 3 shows an example of mislabeling correction in a structure model. In Fig. 3 (a), the value "3091Z" was labeled as a zip code due to a confusion made by the OCR of the character 'Z' with the character '7'. Furthermore, the mail was not labeled due to OCR errors and the fax number was labeled as a phone number since they have the same syntax. The candidate graph built from this local structure is shown in Fig. 3 (b). The matched model graph with this candidate graph using inexact graph matching is shown in Fig. 3 (c). This model graph is used to extract the missed mail, to correct the erroneous phone number and to prune the extraneous zip code in the local structure as showed in Fig. 3 (d).

E. Recognition validation

Once the entity local structures are corrected, the recognition of such entities is validated similarly to the entity selection module, where the score in ( 1) is redefined to consider the structure matching results. In fact, P (l i ∈ e|e) becomes dependent on the label membership to a local structure of e, denoted S(e), and the graph matching cost between the candidate graph G that represents this local structure and its corresponding model graph M in the structure model. This is expressed by [START_REF] Sanfeliu | A distance measure between attributed relational graphs for pattern recognition[END_REF].

P (l i ∈ e|e) = 1 -C(G, M ) if l i ∈ S(e); 1 -P s (c i ) else. ( 12
)
where P s (c i ) is the probability of any label having a field c i to belong to a local structure. This probability is statistically computed over the corpus.

In the following, we define the process of learning the structure model employed in the structure matching module.

F. Structure model learning

The structure model is learned using the incremental graph clustering algorithm detailed in Algorithm 1. The proposed algorithm is executed on a dataset chosen to be representative of the corpus. It is an improvement of the Leaders algorithm, proposed in [START_REF] Vijaya | Leaders-subleaders: An efficient hierarchical clustering algorithm for large data sets[END_REF], by adding the incremental update of the centroid to be more representative of the cluster members. This algorithm is adapted to our case since it is a simple incremental clustering algorithm that requires one dataset scan. Besides, experiments on our corpus show that the performances are independent of the data stream order.

The distance mentioned in the algorithm is the graph matching cost function. The centroid is the representative graph of the cluster members. The structure of this graph is built using the concept of "Weighted Minimum Common Supergraph (WMCS)" proposed in [START_REF] Bunke | Graph clustering using the weighted minimum common supergraph[END_REF]. The attributes of the representative graph are learned by fusing the attributes of the members. For distances, the sample average is computed. For alignment, the dominant value is used. The weight factors of the representative graph are set up inversely proportional to the deviation of the attributes in the samples. That is to say, the larger the sample variation of an attribute is, the less discriminant it is and so the lower its weight factor is.

During the document stream processing, the structure model is updated similarly to the initial learning. Indeed, if the candidate graph corresponds to an existent model graph, the latter is recomputed by considering this new candidate graph. Otherwise, an embryo model graph is initialized by the candidate graph. It becomes a mature graph when its occurrence exceeds an threshold (empirically fixed to 10).

III. EXPERIMENTS

For experiments, we used three datasets where the two first datasets are provided by the ITESOFT1 company and the third • 252 documents: first pages of journals, conferences, thesis manuscripts, posters; • a database of 415500 records, described by fields: title, authors, affiliations, journal, etc.; • 252 entities: meta-data of scientific papers.

For evaluation, we used ground truth tables that link documents with their contained entity identifiers in the databases. These tables were manually prepared. For the entity attribute labeling in the documents, a company internal tool called FullText was used.

First, we evaluate the proposed approach by focusing on the ultimate goal: the entity recognition. Next, a finer evaluation is made by considering each of the two main modules of the approach: the model learning and the graph matching.

A. Entity recognition evaluation

For evaluation, recall (R), precision (P) and f-measure (F) are computed as in [START_REF] Bodic | An integer linear program for substitution-tolerant subgraph isomorphism and its use for symbol spotting in technical drawings[END_REF]. [START_REF] Bodic | An integer linear program for substitution-tolerant subgraph isomorphism and its use for symbol spotting in technical drawings[END_REF] where RE represent the relevant entities, such as a relevant entity for a document is defined as an entity present in the document and referring to some record in the database, ME represent the matched entities and RME represent the relevant matched entities.

R = # RME # RE P = # RME # ME F = 2.P.R P +R
The entity recognition results are shown in Table I. This table shows that the entity selection process gives low recall, precision and f-measure caused by the association of labels to the entities without considering their structural information in the document page. These percentages are significantly improved by the mislabeling correction processes. The causes of entity recognition errors are enumerated in Tables VI. We compared G-ELSE to two other works in the state of the art. Table I presents the obtained results. It shows a significant increase in precision and recall compared to the evaluation of EROCS and M-EROCS methods on our datasets. Furthermore, we notice an important decrease in the run time due to the labeling and the entity filtering steps.

B. Model learning evaluation

For the clustering, we used: 1) Enterprise: 290 graphs taken from 87 documents. 2) Material: 210 graphs taken from 45 documents.

3) Scientific paper: 200 graphs taken from 70 documents.

To evaluate the clustering algorithm, the Dunn index D was used. It is defined in [START_REF] Kooli | Entity local structure graph matching for mislabeling correction[END_REF].

D = min 1≤i<j≤n d(i, j) max 1≤k≤n d (k) (14)
where d(i, j) is the inter-cluster distance between the clusters i and j (the distance between the centroids) and d(k) is the intra-cluster distance of the cluster k (the maximal distance between any element pair in the cluster k).

Table II presents a comparison of the clustering results between the proposed algorithm and the Leaders one. Its shows that the proposed algorithm outperforms the Leaders one for all datasets. This is due to our choice which consists of using the incremental update technique for each cluster centroid.

C. Graph matching evaluation

For the graph matching experiments, we used: A relevant model graph for a candidate graph is defined as a graph that corresponds to this candidate graph. The recall (R), precision (P) and f-measure (F) are then defined in [START_REF] Wong | An algorithm for graph optimal monomorphism[END_REF]. R = # RMG # RG P = # RMG # MG F = 2.P.R P +R [START_REF] Wong | An algorithm for graph optimal monomorphism[END_REF] where RG, MG and RMG represent the relevant graphs, the matched graphs and the relevant matched graphs respectively.

For evaluation, we used ground truth tables that link each candidate graph with its model graph. These tables were manually prepared. The results on the three datasets are illustrated in Table III, Table IV and Table V. They show that the proposed method performs well for all structure types. This is explained by the employed heuristics, in the branch and bound algorithm, which guides the matching solutions retrieval.

IV. CONCLUSION AND FUTURE WORK

This paper proposes an entity recognition approach in documents recognized by OCR driven by a structure model. The inexact graph matching technique between the candidate graphs (built for local entity labels) and the model graphs (in the structure model) has proved to be effective in improving the recognition process. The results on three datasets treating different kinds of entities are promising. Our future work is to study the local structure position in the physical or/and logical document structure to guide the search. Moreover, we plan to investigate several string matching combinations for the attribute matching in order to enhance the recognition.

Fig. 1

 1 Fig. 1 presents the global schema of G-ELSE. Firstly, the document labels are grouped to select candidate entities from the database. Secondly, the labels of the same entity which are physically close are used to build a local structure. The latter is modeled by an attributed graph, called local structure graph. This graph is matched to a structure model. The structure model is itself composed of a set of local structures called model graphs. The geometrical relations in the matched model graph are then used to correct the eventual mislabeling in the local structure. The structure model is initially learned from a chosen examples of the studied dataset based on a graph clustering algorithm. It is then progressively updated during the recognition process. Finally the entity candidates are validated or excluded.

Fig. 1 .

 1 Fig. 1. Global schema of G-ELSE

Fig. 2 Fig. 2 .

 22 Fig. 2 shows examples of local structures extracted from real world document images. Fig. 2 (a) shows a local structure of an enterprise entity with its representation by an attributed

Fig. 3 .

 3 Fig. 3. An example showing mislabeling correction in an enterprise local structure, (a) the erroneous structure, (b) the corresponding candidate graph, (c) the matched model graph, (d) the corrected structure

1 )

 1 Enterprise: 41 model graphs, 525 candidate graphs. 2) Material: 11 model graphs, 320 candidate graphs. 3) Scientific paper: 28 model graphs, 200 candidate graphs.

TABLE I .

 I

						ENTITY RECOGNITION COMPARISON RESULTS
	Method	Enterprise dataset R (%) P (%)	F (%)	Runtime (s/doc)	Material dataset R (%) P (%)	F (%)	Runtime (s/doc)	Scientific paper dataset R (%) P (%) F (%)	Runtime (s/doc)
	EROCS [3]	67.68	54.10	60.14	69	76.19	77.42	76.80	37	67.46	77.27	72.03	42
	M-EROCS [8]	73.38	69.68	71.48	4.4	79.37	78.74	79.05	3.5	71.42	90.00	79.64	3
	Entity selection	86.69	56.86	68.67	0.84	77.62	74.31	75.93	0.85	80.51	70.41	75.13	0.90
	G-ELSE	95.06	94.70	94.88	1.4	92.06	94.30	93.17	1.2	88.49	95.30	91.77	1.2

  CL = {c 1 } where c 1 .centoid = g 1 4: for each g i ∈ G; i = 2 → |G| do 5: c min = arg min c∈CL C(g i , c.centroid) C(g i , c.centroid) is the graph matching cost between g i and c.centroid CL = CL ∪ {c} where c.centoid = g i

					TABLE II.	CLUSTERING COMPARISON RESULTS
			Method	Enterprise dataset Best threshold	# Cluster	Dunn	Material dataset Best threshold	# Cluster	Dunn	Scientific paper dataset Best threshold # Cluster	Dunn
			Leaders [16]	0.1	42	0.71	0.15	10	0.74	0.11	31	0.78
			Our method	0.1	41	0.74	0.15	11	0.77	0.12	28	0.80
	Algorithm 1 Graph dataset clustering
	Require: graph dataset : G, threshold : T
	Ensure: cluster set: CL
	1: CL = ∅	a cluster c ∈ CL is defined by its centroid
		c.centoid
	2: select a graph g 1 ∈ G
	3: 6:	if C(g i , c min .centroid) < T then
	7:	recompute c min .centroid
	8:	else
	9:
	10:	end if
	11: end for

TABLE V

 V

					• 630 entities: materials.
					3) Scientific paper dataset:
	.	GRAPH MATCHING RESULTS IN SCIENTIFIC PAPER DATASET
	Structure	R (%)	P (%)	F (%)
	Reference information (50 graphs)	96.00	90.56	93.20
	Edition information (40 graphs)	90.00	90.00	90.00
	Author information(40 graphs)	82.50	82.93	82.71
	Mixed (70 graphs)	85.71	92.3	88.88
	Total (200 graphs)	88.50	89.53	89.01
	one is extracted from public sites 2 :
	1) Enterprise dataset:
		• 278 documents: invoices and purchase orders;
		• a database of 230000 records, described by
		fields: name, address, phone, mail, tva, etc.;
		• 526 entities: enterprises (clients + suppliers).
	2) Material dataset:
		• 200 documents: invoices;
		• a database of 86600 records, described by
		fields: description, serial, amount, price, etc.;
	2 https://hal.archives-ouvertes.fr/;http://www.istex.fr/;http://dblp.uni-trier.de/

TABLE VI

 VI

		.	CAUSES OF ENTITY RECOGNITION ERRORS
	```````C auses	Corpus		Enterprises	Materials	Scientific papers
	Structure segmentation errors (%)	1.52	0.95	2.78
	Structure matching errors (%)	0.38	0.48	0.79
	Unrecoverable OCR errors (%)	1.90	1.90	2.38
	Non-standardization (%)		0.19	4.29	3.57
	Incomplete entities (%)		0.95	0.32	1.98

http://www.itesoft.com

V. ACKNOWLEDGMENT

The authors would like to thank their collaborator ITE-SOFT for providing real word data for tests.


Gianluca Demartini

Iliya Enchev

Marcin Wylot

Joël Gapany

Philippe Cudré-Mauroux

Exascale Infolab

BowlognaBench-Benchmarking RDF Analytics

Introduction

The amount of semantic data available on the Web is rapidly increasing due to successful initiatives such as the Linked Open Data movement 1 . At the same time, semantic knowledge bases are being developed and improved in order to face the pressing demand of storing and querying large scale datasets. As examples, the semantic search engine Sindice2 indexes up to 200M RDF documents, while very large datasets containing billions of RDF triples3 are increasingly common. The bigger the datasets grow in size, the more interesting it becomes to perform complex analysis on RDF data, in order for example to identify patterns or discover data correlations. This is somehow similar to OLAP (On-Line Analytical Processing) transactions on large databases where complex read-mostly queries are run over big datasets.

Modern business processes generate much data which is often stored for further analysis or even for legal purposes. Such data can be seen an important asset for a company willing to improve their processes by means of data analysis. One of the current open challenges that limits such analysis is the poor performance of data management platforms. Specifically, for the case of graph data (of which business process data is a good example) much improvement can be obtained.

In order to foster such efficiency and scalability advances that address the need for business process analysis, in this paper 4 , we propose a benchmark for evaluating and comparing the efficiency of knowledge management systems focusing in particular on analytic queries over RDF data. Other benchmarks for RDF storage systems have been proposed already-the most popular one being LUBM [START_REF] Guo | LUBM: A benchmark for OWL knowledge base systems[END_REF], which provides an ontology describing universities together with an automatic instance generator and a set of 14 simple queries. Extensions of such benchmarks have also been proposed. For example, Minack et al. [11] created a benchmark for full-text search over semantic repositories. Further RDF benchmarks include a benchmark over full-text data (see, for instance, [START_REF] Bizer | Benchmarking the performance of storage systems that expose SPARQL endpoints[END_REF]13]), a benchmark based on scientific publications (that is, DBLP) [START_REF] Schmidt | SPˆ2Bench: A SPARQL Performance Benchmark[END_REF], and a benchmark based on a Web data exploration application [START_REF] Daniel | Scalable semantic web data management using vertical partitioning[END_REF]. Recently, the DBpedia SPARQL Benchmark [START_REF] Morsey | DBpedia SPARQL Benchmark -Performance Assessment with Real Queries on Real Data[END_REF] has also been proposed: it consists of a RDF store benchmark which focuses on evaluating system performance over real queries and real data. It contains queries mined from real logs of the DBPedia system 5and resembles original DBPedia data.

Why is there a need for a new RDF benchmark? The simple answer is that none of the aforementioned benchmarks focuses on complex analytic queries. Analytic operations have become a major concern of any modern company, as they are used to measure and improve the performance of many complex operations (from data warehousing to reporting or data mining). Traditional relational systems were designed and optimized for transactional queries mostly, and cannot handle analytic queries efficiently. This recently led to many advances in data management technologies with the emergence of companies like Teradata6 or, more recently, Vertica7 , and the definition of new benchmarks, such as TPC-H8 (which is the standard benchmark for data analytics today) or the recent benchmark we suggested for mixed OLAP/OLTP settings [8]. In the university context we can expect relatively low volumes of insert and update queries (as compared, for example, to an e-commerce scenario). For this reason, we thought that it would be interesting to focus on analytic and trend queries rather than supporting high volume of transactions. To the best of our knowledge, BowlognaBench is the first RDF benchmark focusing on this topic.

Beyond its focus on data analytics, we feel that BowlognaBench is based on a more realistic ontology than previous attempts. Duan et al. [START_REF] Duan | Apples and Oranges: A Comparison of RDF Benchmarks and Real RDF Datasets[END_REF] recently proposed a comparison between available RDF benchmarks and real datasets such as DBpedia [START_REF] Auer | Dbpedia: a nucleus for a web of open data[END_REF] and YAGO [START_REF] Suchanek | Yago: a core of semantic knowledge[END_REF]. Their study showed that existing benchmarks have little in common with real world datasets. This finding confirms our motivation for creating a novel benchmark for RDF that better reflects user information needs. LUBM, the most popular RDF storage benchmark, does not directly reflect a real university setting, while the ontology we propose models an academic setting as prescribed by the Bologna process. The second drawback of LUBM is that its set of queries tries to cover possible failures in knowledge management systems and advanced (but rather rare) inference cases, rather than model real user information needs. We develop a set of queries of real interest to the academic domain (e.g., "what is the percentage of students who continue their university studies after the Bachelor?"). Third, the LUBM benchmark does not involve the temporal dimension, which is a very important aspect of analytic queries; in our benchmark, we propose to evaluate queries asking for specific time or time intervals over the data (e.g., "how did student performance evolve over the last 5 years"?), which is a popular type of query that need to be supported by current systems (see for example [START_REF] Hoffart | YAGO2: exploring and querying world knowledge in time, space, context, and many languages[END_REF]).

In summary, BowlognaBench provides a framework for evaluating the performance of RDF systems on a real-world context derived from the Bologna process; it strains systems using both analytic and temporal queries; and it models real academic information needs.

The rest of the paper is structured as follows. In Section 2 we briefly describe the Bologna reform of the European university studies. Then, in Section 3 we present the lexicon of terms relevant to the Bologna process that has been defined in order to avoid ambiguities and misunderstandings. Next, in Section 4 we introduce the Bowlogna Ontology that has been developed to model the university setting after the Bologna reform. Together with the set of queries defined on top of the Bowlogna Ontology in Section 5, we propose the Bowlogna Benchmark to evaluate and compare efficiency of knowledge bases for analytic queries. In Section 6 we present an experimental comparison of different systems over the proposed benchmark. Finally, we conclude the paper in Section 7.

Information Systems in The Bologna Process

The Bologna Process is the set of reforms into which European higher education institutions entered from June 1999 onward, after the ministries of education of 29 European countries convened in Bologna and laid new foundations for the future European higher education. The Bologna Declaration defines a general framework in which signatory countries commit themselves to develop their higher education system. As such, it also leaves a certain margin for interpretation, which has allowed local appreciation and various implementations of the process. As a consequence, during the last decade, a specific form a relationship between universities has unquestionably developed, according to which both cooperation and competition in teaching and research are equally fostered.

In this context, the need to make available (for example, in RDF form) comprehensive and transferable datasets about current students and course offerings is increasing dramatically, as a key dimension of quality processes. In this competitive environment also, the capacity to attract new students, especially at the master level, is generally regarded as a factor of success. It is therefore not surprising that universities invest considerable efforts into the development of new information infrastructures, and into increasingly sophisticated analytic tool to help them monitor and assess their performance.

The Bologna Linguistic Lexicon

The Bologna Process initiated a radical change within higher education institutions. This change encompasses the creation of new administrative procedures, inclusive quality procedures, in the every day life of the universities. It also gave rise to the emergence of new concepts for the description of curricula. In this respect, we recently published [START_REF] Gapany | Curricular design and computerisation: are information systems useful in curricular reorganisation? European University Association: the Bologna Handbook[END_REF] in the Bologna Handbook the basic set of entities that correspond to the new system of studies and that seem to be rather stable across time and institutions. In this paper, we described how the compilation of a lexicon of about 60 definitions contributed to the implementation of the Bologna Process in our institution. This booklet has been spread among academic and administrative staff, in order to create a common understanding of Bologna. It is worth noting that the defined entities are concepts, rather than single words, and that they were selected and defined by professional terminologist who adopted a rigorous, text-based approach to study the Bologna Process.

The Bowlogna Ontology

The formal lexicon described above paved the way for an ontology-based computerization of the Bologna process. Based on our understanding of the Bologna and on the Bologna lexicon, we developed an OWL ontology describing all the relevant concepts and their relations 9 . Figure 1 shows some of the classes in the Bowlogna ontology together with their relations. The ontology contains 29 top level classes (67 in total) describing concepts like students, professors, student evaluations (i.e., exams where students get a grade from a lecturer in the context of a teaching unit), teaching units (i.e., courses given by lecturers and attended by students), ECTS credits, as well as formal documents such as, for instance, study programs, certificates, or grade transcripts. Additionally, all definitions from the lexicon, both in German and French, are included in the ontology.

One of the key classes in this ontology is "Evaluation" in which a Student, a Professor and a Teaching Unit are involved. This class models the event when a student, after attending a course given by a professor (i.e., a teaching unit) is evaluated and given a grade. Properties of teaching units include the semester and the language in which the units are given, as well as the number of corresponding ECTS credits earned by students who successfully follow the course. The class Student also has a number of properties including the name of the student, his enrollment or graduation date for Bachelor and Maser degrees. The same student instance can be, over time, registered for different academic degrees (e.g., first a Bachelor and then a Master). The class "ECTS credit" is linked to all classes directly or indirectly related to the measurement of students advancement: for example, teaching units and study programs. The class Semester, with start and end dates, enables queries on the temporal dimensions (e.g., the number of students enrolled at the university during a certain semester).

Public and Private Ontology Parts

The Bowlogna ontology can be divided in two important parts according to the type of information stored. Some information are public and can be shared with other universities as well as with the general public. Examples of such public information include the departments, the teaching units together with information about their ECTS credits and teaching language. The second part of the ontology consists of information which should not be publicly available, such as grades given to students. In real instantiations of the ontology, the private part will contain many more instances as compared to the public part. It is also clear that aggregations over private information might often be of general interest (e.g., the number of students currently enrolled at the university), and can be safely shared.

Additional Testing for Scalability: Multiple Universities

The ontology we described so far is suitable to describe a single university setting. As the benchmark we are proposing aims at testing system performance as the amount of stored data increases, we can imagine, for example, to test systems on different repositories containing an increasing number of students or departments. Additionally, we can imagine that different universities may adopt the same ontology for describing their data. In such settings, we can even imagine exchange students following teaching units in different universities. In this case, we can scale the size of the dataset and evaluate system performance on the private part of a single a university as well as on the public part of several universities.

Queries

In this section, we describe the various queries we defined in order to evaluate the performance of RDF data management systems systems in an analytic setting. The proposed set of queries aims at covering a broad range of requests, including Average, Max, Min, GroupBy, Top-K, Rank, and Path queries. In the following we describe the queries using natural language. The complete set of SPARQL queries is available in the Appendix as well as on the benchmark website.

Count Queries

This subset of queries requires systems to count the number of instances having specific characteristics. Some of them only need to access the public information, and thus can be scaled to multiple universities, while others access private information such as the result of student evaluations.

Query 1. What is the percentage of master theses that received a mention? For this query the system has to select the successful master theses and to check how many of them are related to a Mention object. In general, such information is publicly available, thus systems only need to access the public part of the ontology.

Query 2. What is the percentage of students who continue their university studies beyond the Bachelor? This query needs to check, for every student who obtained a Bachelor degree, whether he/she is registered to any Master program, count the number of such students, and finally divide it by the total number of students who registered for a Bachelor degree. In order to run this query the system only has to access the public part of the ontology (provided that registration information is increasingly shared across universities).

Query 3. What is the current number of ECTS credits Student0

has acquired? This is a more transactional query focusing on a specific instance (i.e., Student0 ), which requires to check for each evaluation taken by this student whether it was successful or not. For all such cases, the system must then sum the number of ECTS credits assigned to the related teaching unit. For this query, systems have to access the private part of the ontology (i.e., grades of evaluations).

Selection Queries

This group aims at retrieving a large set of instances from the knowledge base. The queries may be simple in terms of operators but it requires knowledge bases to handle large amount of data.

Query 4. Return all students whose surname starts with 'A'. This query returns a portion of all the student instances stored in the knowledge base. This type of queries may be useful when creating catalogs of students where, for each letter of the alphabet, there is a page containing all students whose surname starts with the same letter. As student names should not be released to the general public, in order to run this query systems needs to be able to access the private part of the dataset.

Molecule Queries

This type of queries aims at retrieving all the information surrounding a specific instance in the graph. To answer such queries, systems have to be efficient in retrieving all triples in the vicinity of a given node in the RDF graph, which represents a complex operation (with series of joins) for many transactional systems.

Query 5. Return all information about Student0 within a scope of two. This query returns all triples connected directly or indirectly to Student0, that is, a subgraph centered on Student0 and containing all the triples directly attached to the student, plus the triples attached to those triples. As private student information are also requested, this query needs to access the private as well as the public part of the ontology.

Max and Min Queries

These queries require to find some specific instances which, among others of the same type, have the highest/lowest value for the requested characteristic. Query 6. Which teaching unit has the lowest success rate? This query requires to compute the success rate, that is, the number of successful student evaluations divided by the total number of student evaluations done for that teaching unit, and find the minimum. It needs to access private information of the ontology. Query 7. Who is the professor who supervised most theses? This query requires, after counting the number of theses grouped by professors, to compute the maximum and return the professor. For this query, the functionality of subclass inference needs to be additionally supported by systems. This is the case as matching instances are of type Thesis Supervisor which is a subclass of Professor. Thus, systems have to infer that such instances are of type Professor to correctly answer the query. The information required to answer this query is typically publicly available.

Ranking and TopK Queries

For such queries, the systems have to either rank all instances of a certain class or to find the top k elements of a ranked list. Query 8. Who are the top 5 performing students in StudyTrack0 and semester Semester0 ? This is a top-k query that asks the system to rank students for a specific Study Track and Semester after computing the average grade obtained in all the evaluations they have performed so far. This requires to access student grades, which is private information.

Temporal Queries

This set of queries aims at checking system support and efficiency of temporal queries, that is, requests that involve a filter of instances based on a specific date or time interval.

Query 9. What is the average completion time of Bachelor studies for each Study Track?

This query requires the repository to compute the completion time for each student of the university, average them and group the results by study track. Information about registration and graduation date may be private or public depending on the university. Query 10. How did university student performance evolve over the last 3 semesters? This query requires the system to compute the average grade of all student evaluations grouped by semester. Evaluation results required to answer this query are private information.

Path Queries

This type of query wants to test the ability of systems to exploit several nodes in the ontology joined through RDF predicates.

Query 11. What are the names of students who took an exam with a professor of Department0 ? This is a path query in the sense that it requires to join triples over several different predicates (namely, Student:hasFamilyName, Student:hasFirstName, Evaluation:performedByStudent, Evaluation:evaluatedByProfessor, Professor:isAffiliatedWithDepartment, Department:hasName). As student names should not be released to the general public, in order to run this query systems needs to be able to access the private part of the dataset.

Multiple University Queries

As the goal of building an RDF benchmark is to test for scalability of systems as the size of the dataset grows, we can imagine to run certain queries over several university repositories and aggregate the results to provide a final answer to the user. In this setting, the amount of data that has to be managed can increase a lot as compared to a single university, but, on the other hand, initial queries may be run in parallel and results aggregated later on.

Query 12. In which university can I attend Teaching Unit0 in English?

In case different universities share their ontology, it is possible to run queries over different instances of the same schema. In this case, the system has to check the language of the instance Teaching Unit0 in all accessible universities. Information about teaching units is assumed to be public for all universities. Query 13. How did the number of newly registered students to each University evolve over the last 5 years? For this query, systems need to find the number of students enrolled at each university for each semester. This computation requires to check the registration and the possible graduation dates for each student and compare them with the semester start and end dates. We consider that information about registration and graduation date are shared across collaborating universities.

Query Classification

Table 1 presents a classification of the proposed queries based on several dimensions. First, we classify queries accordingly to the fact that they need to access the public or the private part of the ontology (see Section 4.1). Then, we use the dimensions that were introduced in [START_REF] Guo | LUBM: A benchmark for OWL knowledge base systems[END_REF], that is, Input Size, Selectivity, and Complexity. Input size measures the number of instances involved in the query: we classify a query as having a large input size if it involves more than 5% of instances, and small otherwise. Selectivity measures the amount of instances that match the query: we classify a query as having high selectivity if less than 10% of instances match the query, and low otherwise. Complexity measures the amount of classes and properties involved in the query: queries are classified as having high or low complexity accordingly to the RDF schema we have defined. As we can see the majority of queries have a low selectivity which reflects our intent of performing analytic queries, that is, queries for which a lot of data is retrieved and aggregated. For the same reason, most of the queries have a large input. Finally, queries are equally divided in high and low complexities.

Comparing RDF systems using BowlognaBench

In this section we report the results of an experiment which aims at comparing the performance of different knowledge base platforms on the analytic queries of BowlognaBench. First, we describe all the additional elements composing the proposed benchmark, namely the instance generator and the BowlognaBench website.

BowlognaBench Instance Generator. The artificial instance generator provided with BowlognaBench is a Java program that takes as input the number of departments, the number of fields per department, and the number of semesters to scale over the time dimension as well. It generates a populated Bowlogna ontology by producing RDF files (one per department) in NTriple format. In order to generate large datasets, it is recommended that at least 2G of memory are assigned to the Java process.

Artificial data may not well reflect real data distribution [START_REF] Duan | Apples and Oranges: A Comparison of RDF Benchmarks and Real RDF Datasets[END_REF]. For this reason, we analyzed a sample of real academic data provided by the University of Fribourg administration. The observed properties are used to add additional parameters to the BowlognaBench artificial instance generator. In the following we report some observations made over the real data we had access to.

The data describes professors, departments, teaching units, and fields of study over 34 semesters at the University of Fribourg. Figure 2 shows the distribution of professors with respect to the number of teaching units related to them. As expected this follows a power law distribution where we can see that many professors teach only one teaching unit while few professors teach many units. We manually inspected special cases such as, for example, the professor with most teaching units and observed that she is an University administration employee assigned to 643 foreign language courses. Strictly speaking, this is not an error in the data but rather an imprecise link as the relation between that person and the language courses is not of the same type as for the others. Such cases are typical in real data but not so easy to find in artificially generated data.

Number of Professor Instances

Professor in--degree Fig. 2. In-degree of Professor instances (i.e., Teaching Units related to a Professor).

Another aspect of real data is incompleteness. While it is easy to generate complete artificial data, systems running over real data need to face the problem of missing values. In the available real data we observed that 0.8% of the teaching units have a 'null' value for the 'number of ECTS credits' field which is not supposed to be left empty. Another example of data incompleteness is shown in Figure 3 where the out-degree of the Teaching Unit class is displayed. We can see that 17 teaching units have out-degree of 1 which is wrong as at least 'bb:belongsToFieldOfStudies' and 'bb:isForSemester' should be defined for a teaching unit. Otherwise, the data distribution looks as expected.

BowlognaBench Website. The benchmark we produced and used for the following experiments-that is, the Bowlogna ontology together with the set of queries and the Bowlogna artificial instance generator-is available for download at: http://diuf.unifr.ch/xi/bowlognabench/. The instance generator includes various options to scale and change the statistical distribution of the data. On the BowlognaBench website we also allow third-parties to publish their own test configurations and performance results.

Experimental Setting

We compared the following RDF systems: 4Store 4s-query revision v1.1.3, RDF-3X 0.3.5, Virtuoso Open-Source Edition 6.1.3, and our own dipLODocus[RDF] system [START_REF] Wylot | dip-LODocus[RDF] -Short and Long-Tail RDF Analytics for Massive Webs of Data[END_REF]. In order to run such comparison we use two different datasets generated with the BowlognaBench Instance Generator for 1 and 10 departments, 4 fields per department and 15 semesters. The datasets contain 1.2 and 12 million RDF triples for 273MB and 2.7GB respectively. We run the 13 queries of BowlognaBench to compare the query execution time for four different RDF systems. Reported execution times are obtain by averaging over 10 executions of the same query over a warm-cache system. Aggregation (COUNT, SUM, AVG, etc.) and operations such as percentage or ratio have not been performed as not supported by all system: instead, all data needed to compute such aggregates is retrieved. We also compare the load time and the size of the created indexes.

Experiments were run on a machine with Intel Core i7-2600 CPU @ 3.40GHz, 8GB RAM, Ubuntu 11.10.

RDF systems.

In the following we provide some details about the different systems we compared over BowlognaBench: RDF 3X 10 creates various heavily compressed indices starting from a huge triple-table . Compression is done by means of dictionary encoding and bytewise compression. Indices are based on the six possible permutations of RDF triple elements, and aggregate indices storing only two out of the three elements. The RDF-3X query executor optimizes join orderings and determine the cheapest query plan by means of a dedicated cost-model. 4Store 11 from Garlik is a recent parallel RDF database distributing triples using a round-robin approach. It stores data in quadruple-tables. Virtuoso 12 is an object-relational database system using bitmap indices to optimize the storage and processing of RDF data. dipLODocus[RDF] 13 is a hybrid RDF system combining subgraph storage (where joins are materialized) and column-store technologies (where values are compactly stored in vectors) to answer both triple pattern queries and analytic queries very efficiently.

Experimental Results

Table 2 shows the index size and the load time for the two datasets and four RDF systems. We can see that Virtuoso takes more time to load and index the dataset but the size of the indices scales better than for other systems. The faster system is 4Store which also has the biggest indices. RDF 3X, Virtuoso, and dipLODocus achieve good compression with Virtuoso showing the best scaling. As we can see, query execution time for the BowlognaBench analytic queries strongly vary for different systems (note that Figure 4 for a single department) the dipLODocus system is faster than others for 9 out of 13 queries. Specifically, shortest query executions can be observed for queries 12 and 13. The slowest is the path query which involves several joins. The RDF 3X system obtained the best performance on 3 queries (i.e., query 1, 7, and 9). We can see that query 8 (i.e., top K) is not easy to be efficiently answered for all systems. Query 3 and 11 are also challenging for most systems because of the several joins involved. For the bigger dataset (i.e., data for 10 departments) we can observe the slower performances of 4Store for 7 out of 13 queries as compared with the other three systems: for some queries (e.g., 11) the execution times took up to 8 seconds. One difference that we can observe as compared with the smaller dataset is the good result of Virtuoso: it performed faster than other systems on 4 out of 13 queries. The dipLODocus system performed best on 6 queries with dramatic improvements for some queries (e.g., 5 the molecule query) showing execution times orders of magnitude smaller than other systems. In general, we can again observe that query 8 and 11 are difficult to answer efficiently because of several joins.

Conclusions

As RDF continues to grow in popularity, being able to efficiently execute analytic, data-intensive operations over large RDF graphs is becoming increasingly important in the business process analysis field as well as in others. In this paper, we proposed a benchmark for evaluating and comparing the performance and scalability of knowledge base systems on complex analytic queries. After describing the European academic landscape as outlined by the Bologna reform, we introduced BowlognaBench, a benchmark for RDF systems consisting of an ontology derived from a systematic study of the official Bologna documents, a set of complex queries derived from concrete user information needs, and an automatic instance generator that allows to populate the ontology with a given number of instances and relations. Finally, we compared the query execution time of different RDF systems over the proposed benchmark showing common limitations and bottlenecks of such systems as, for example, queries involving several joins. As for former benchmarks, we hope that this project will stimulate a healthy competition among RDF data management systems as well as foster the emergence of new RDF back-ends geared towards complex, data-intensive Semantic Web applications.

Acknowledgment

This work is supported (in part) by the Swiss National Science Foundation under grant number PP00P2 128459.

Fig. 1 .

 1 Fig. 1. The Bowlogna ontology: key classes and relations.

3 .

 3 Out-degree of Teaching Unit instances (i.e., relations with other entities).

Figure 4 Fig. 4 .

 44 Fig. 4. Query execution time for BowlognaBench queries over the single department dataset.

Fig. 5 .

 5 Fig. 5. Query execution time for BowlognaBench queries over the 10 departments dataset.

Table 1 .

 1 Classification of queries according to their need to access private and public data, input size, selectivity, and complexity.

			Count		Selection Molecule MaxMin TopK	Temp	Path MultiUniv
	Query	1	2	3	4	5	6	7	8	9	10	11	12	13
	Public	x	x					x	x	x		x	x	x
	Private			x	x	x	x		x	x	x	x		x
	Input Size Small Large Small Large	Small Large Small Large Large Large Large Large Large
	Selectivity High Low Low	High	Low	Low Low High Low Low Low Low Low
	Complexity Low Low Low	Low	High High Low High Low High High Low High

Table 2 .

 2 Load time and index size for four RDF systems and two datasets.

		RDF 3X 4Store Virtuoso dipLODocus
	Load Time 1 dept. (s)	11.94	6.25	31.71	18.35
	Load Time 10 dept. (s)	139.55 69.65 363.24	526.65
	Indices size 1 dept. (MB)	60	192	108	92
	Indices size 10 dept. (MB) 618	1752	616	920

http://linkeddata.org/

http://sindice.com/

http://km.aifb.kit.edu/projects/btc-2010/

This paper is an extended version of[START_REF] Demartini | BowlognaBench-Benchmarking RDF Analytics[END_REF].

http://dbpedia.org/

http://www.teradata.com/

http://www.vertica.com/

http://www.tpc.org/tpch/

Query 4 could not be run on RDF 3X and dipLODocus as they do not provide full SPARQL support (i.e., for this query no support for pattern matching is provided).