Jérémie Bettinelli

A simple explicit bijection between (n, 2) Gog and Magog trapezoids

Keywords: bijection, Gog, Magog, alternating sign matrix, totally symmetric self-complementary plane partition. AMS classification: 05A19

A sub-problem of the open problem of finding an explicit bijection between alternating sign matrices and totally symmetric self-complementary plane partitions consists in finding an explicit bijection between so-called (n, k) Gog trapezoids and (n, k) Magog trapezoids. A quite involved bijection was found by Biane and Cheballah in the case k = 2. We give here a simpler bijection for this case.

Introduction

One of the most famous open problem in bijective combinatorics is to find an explicit bijection between alternating sign matrices of a given size and totally symmetric self-complementary plane partitions of the same size. These objects of combinatorial interest have been known since the end of the '90s to be equinumerous [START_REF] Andrews | Plane partitions. V. The TSSCPP conjecture[END_REF][START_REF] Zeilberger | Proof of the alternating sign matrix conjecture[END_REF] but, as of today, there is no direct bijective proof of this fact. We refer the reader to [START_REF] David | Proofs and confirmations[END_REF][START_REF] Cheballah | Combinatoire des matrices à signes alternants et des partitions planes[END_REF] for more information on this story.

The previous objects are in known bijections with arrays of integers called respectively Gog and Magog triangles. The triangles of size n consist in Young diagrams of shape (n, n -1, . . . , 2, 1) filled with positive integers satisfying variation conditions along vertical, horizontal and possibly oblique lines. Although they satisfy very similar variation conditions, nobody managed to find a direct bijection between these triangles. Another surprising fact is that, if we only consider the k first rows of the triangles, the objects we obtain are also equinumerous. These objects called (n, k) trapezoids were introduced in [START_REF] Mills | Self-complementary totally symmetric plane partitions[END_REF] where they were conjectured to be equinumerous; this was later proved by Zeilberger [Zei96, Lemma 1].

The supposedly simplest problem of finding an explicit bijection between (n, k) Gog trapezoids and (n, k) Magog trapezoids has been solved only for k ≤ 2. In fact, for k = 1, the objects are exactly the same so there is nothing to prove. There is, however, a refined conjecture by Krattenthaller [Kra] involving the number of entries equal to 1 and the number of entries equal to the maximum possible value in the first and last rows. For this conjecture, even the case k = 1 is nontrivial; it was proven in [Kra].

For k = 2, a bijection was found by Biane & Cheballah [START_REF] Biane | Gog and Magog triangles, and the Sch ützenberger involution[END_REF]. Their bijection is relatively complicated and uses the so-called Sch ützenberger involution; it does not match the statistics of Krattenthaller's refined conjecture. In this work, we give a different bijection for this case. Our bijection is very simple and involves only one operation. It does not match Krattenthaller's statistics either.

Acknowledgements. I thank Jean-Franc ¸ois Marckert for introducing this problem to me.

Magog and Gog trapezoids

In this work, we are solely considering (n, 2) trapezoids and we furthermore impose that n ≥ 3 in order to avoid trivialities. Let us give proper definitions (see Figure 1 for more graphical definitions and examples).

Definition 1. Let n ≥ 3 be an integer. An (n, 2) Magog trapezoid is an array of 2n -1 positive integers m 1,1 , . . . , m 1,n-1 , m 2,1 , . . . , m 2,n such that (i) m i,j ≤ m i,j+1 for all i ∈ {1, 2} and j ∈ {1, . . . , n + i -3} ;

(ii) m 1,j ≤ m 2,j ≤ j for all j ∈ {1, . . . , n -1} and m 2,n ≤ n . Definition 2. Let n ≥ 3 be an integer. An (n, 2) Gog trapezoid is an array of 2n -1 positive integers g 1,1 , . . . , g 1,n , g 2,1 , . . . , g 2,n-1 such that (i) g i,j ≤ g i,j+1 for all i ∈ {1, 2} and j ∈ {1, . . . , n -i} ;

(ii) g 1,j < g 2,j < j + 2 for all j ∈ {1, . . . , n -1} ;

(iii) g 1,j+1 ≤ g 2,j for all j ∈ {1, . . . , n -1} .

We denote respectively by M n and G n the sets of (n, 2) Magog and Gog trapezoids.

1 2 3 3 4 4 5 5 6 6 7 7 8 8 g 1,1 g 1,2 g 1,3 g 1,4 g 1,5 g 1,6 g 1,7 g 1,8 g 2,1 g 2,2 g 2,3 g 2,4 g 2,5 g 2,6 g 2,7 m 1,1 m 1,2 m 1,3 m 1,4 m 1,5 m 1,6 m 1,7 m 2,1 m 2,2 m 2,3 m 2,4 m 2,5 m 2,6 m 2,7 m 2,8 (8, 2) Gog trapezoid (8, 2) Magog trapezoid 1 2 3 3 4 4 5 5 6 6 7 7
8 8 2 2 4 5 6 7 8 1 1 2 4 4 5 7 7 1 2 2 4 4 6 7 7 1 1 2 4 4 5 7

From Magog to Gog

Let us consider an (n, 2) Magog trapezoid M = (m i,j ). We say that an integer j ∈ {1, . . . , n -2} is a bug if m 1,j+1 > m 2,j + 1. For instance, 3 is the only bug of the Magog trapezoid of Figure 1. We set Φ n (M ) := (g ij ), where (g ij ) is constructed as follows (see Figure 2). The three cases of the bijection, from a Magog trapezoid to a Gog trapezoid. On the top line, the first bug is 3: it is symbolized by a small black oblique line. The colored blocks are moved and, whenever there is a tag on a block, it is added to all the elements of the block.

First case: M has at least a bug. In this case, we let k be the smallest bug of M and we set

g 1,j := m 1,j for 1 ≤ j ≤ k ; g 1,k+1 := m 2,k ; g 1,j := m 1,j-1 -2 for k + 2 ≤ j ≤ n ; g 2,j := m 2,j + 1 for 1 ≤ j ≤ k -1 ; g 2,j := m 2,j+1 for k ≤ j ≤ n -1 .
Second case: M does not have bugs and m 2,n-1 < m 2,n . In this case, we set

g 1,j := m 1,j for 1 ≤ j ≤ n -1 ; g 1,n := m 2,n-1 ;
g 2,j := m 2,j + 1 for 1 ≤ j ≤ n -2 ; g 2,n-1 := m 2,n .

Third case: M does not have bugs and m 2,n-1 = m 2,n . In this case, we set

g 1,j := m 1,j for 1 ≤ j ≤ n -1 ; g 1,n := m 2,n + 1 ; g 2,j := m 2,j + 1 for 1 ≤ j ≤ n -1 .
Let us check that Φ n (M ) ∈ G n . First, observe that, if j is not a bug, then by definition, m 1,j+1 ≤ m 2,j + 1, so that the yellow and purple blocks always satisfy the oblique inequalities after the mapping. It is straightforward to verify that the other inequalities are satisfied in the second and third case. In the first case, notice that g 1,k = m 1,k ≤ m 2,k = g 1,k+1 and

g 1,k+1 = m 2,k ≤ m 1,k+1 -2 = g 1,k+2 as k is a bug. Furthermore, g 2,k-1 = m 2,k-1 + 1 ≤ m 2,k + 1 ≤ m 1,k+1 -1 ≤ m 2,k+1 -1 = g 2,k -1 so that the horizontal inequalities are satisfied. Moreover, g 1,k = m 1,k ≤ m 2,k ≤ m 1,k+1 -2 ≤ m 2,k+1 -2 = g 2,k -2, g 1,k+1 = m 2,k ≤ m 2,k+2 -2 = g 2,k+1 -2, g 1,j = m 1,j-1 -2 ≤ m 2,j+1 -2 = g 2,j -2 for k + 2 ≤ j ≤ n -1,
and g 2,j = m 2,j+1 < j + 2 for k ≤ j ≤ n -1, so that the vertical inequalities are also satisfied.

Finally, the oblique inequalities are satisfied since

g 1,k+1 = m 2,k ≤ m 2,k+1 = g 2,k and g 1,j = m 1,j-1 -2 ≤ m 2,j -2 = g 2,j-1 -2 for k + 2 ≤ j ≤ n.

From Gog to Magog

We now consider an (n, 2) Gog trapezoid G = (g i,j ) and construct Ψ n (G) = (m ij ) as follows. We define k := max j ∈ {2, . . . , n -1} : g 2,j-1 ≤ g 1,j+1 + 1 .

(1)

This number is well defined as g 2,1 = 2 ≤ g 1,3 + 1.

First case: k ≤ n -2. We set

m 1,j := g 1,j for 1 ≤ j ≤ k ; m 1,j := g 1,j+1 + 2 for k + 1 ≤ j ≤ n -1 ; m 2,j := g 2,j -1 for 1 ≤ j ≤ k -1 ; m 2,k := g 1,k+1 ; m 2,j := g 2,j-1 for k + 1 ≤ j ≤ n .
Second case: k = n -1 and g 1,n < g 2,n-1 . We set Third case: k = n -1 and m 1,n = m 2,n-1 . We set

m 1,j := g 1,j for 1 ≤ j ≤ n -1 ; m 2,j := g 2,j -1 for 1 ≤ j ≤ n -2 ; m 2,n-1 := g 1,n ; m 2,n := g 2,n-1 . → -1 +2 → 1
m 1,j := g 1,j for 1 ≤ j ≤ n -1 ; m 2,j := g 2,j -1 for 1 ≤ j ≤ n -1 m 2,n := g 1,n -1 .
We now show that Ψ n (G) ∈ M n . In the first and second cases, the definition of k entails that m 2,k-1 = g 2,k-1 -1 ≤ g 1,k+1 = m 2,k , so that the horizontal inequalities hold. In the second case, we conclude by noticing that m 2,n-

1 = g 1,n ≤ g 2,n-1 -1 ≤ n -1 and m 2,n = g 2,n-1 ≤ n.
In the first case, by definition of k, m 1,j = g 1,j+1 + 2 ≤ g 2,j-1 = m 2,j for k + 1 ≤ j ≤ n -1 and, by vertical inequalities, m 2,j = g 2,j-1 ≤ j for k + 1 ≤ j ≤ n. Finally, still by definition

of k, m 2,k = g 1,k+1 ≤ g 1,k+2 ≤ g 2,k -2 ≤ k -1.
This concludes in the first case. The third case is straightforward.

The previous mappings are inverse one from another

We now prove that the previous mappings are bijections.

Theorem 1. The mappings Φ n : M n → G n and Ψ n : G n → M n are bijections, which are inverse one from another.

Proof. We have already established that Φ n : M n → G n and Ψ n : G n → M n . It remains to show that Ψ n • Φ n and Φ n • Ψ n are the identity respectively on M n and G n . In fact, we will see that the three cases we distinguished are in correspondence via the bijection.

First case. Let M = (m i,j ) ∈ M n be a Magog trapezoid that has a bug and let k be its smallest bug. As in Section 3, we denote by

(g ij ) := Φ n (M ). We have g 2,k-1 = m 2,k-1 + 1 ≤ m 2,k + 1 = g 1,k+1 +1 and, for k+1 ≤ j ≤ n-1, g 1,j+1 +1 = m 1,j -1 < m 2,j = g 2,j-1 for k+2 ≤ j ≤ n-1, so that max j ∈ {2, . . . , n -1} : g 2,j-1 ≤ g 1,j+1 + 1 = k.
As the box moving procedure of Section 4 is clearly the inverse of that of Section 3, we conclude that

Ψ n • Φ n (M ) = M . Let now G = (g ij ) ∈
G n be such that the integer k defined by (1) is smaller than or equal to n -2. In order to conclude that Φ n • Ψ n (G) = G, it is sufficient to show that k is the smallest bug of (m i,j ) := Ψ n (G). This is indeed the case as

m 1,k+1 = g 1,k+2 + 2 > g 1,k+1 + 1 = m 2,k + 1 and, for 1 ≤ j ≤ k -1, m 1,j+1 = g 1,j+1 ≤ g 2,j = m 2,j + 1.
Second and third cases. Let M = (m i,j ) ∈ M n be a bug-free Magog trapezoid and (g ij ) := Φ n (M ). If we are in the second case, g 2,n-2 = m 2,n-2 + 1 ≤ m 2,n-1 + 1 = g 1,n + 1 and, if we are in the third case, g 2,n-2 = m 2,n-2 + 1 ≤ m 2,n + 1 = g 1,n , so that, in both cases, max j ∈ {2, . . . , n -1} : g 2,j-1 ≤ g 1,j+1 + 1 = n -1 and we conclude as above that Ψ n • Φ n (M ) = M .

Let now G = (g ij ) ∈ G n be such that the integer k defined by (1) is equal to n -1. We see that

Φ n • Ψ n (G) = G by noticing that (m i,j ) := Ψ n (G) is bug-free as, for 1 ≤ j ≤ n -1, m 1,j+1 = g 1,j+1 ≤ g 2,j = m 2,j + 1.

Extension to (ℓ, n, 2) trapezoids and perspectives

Our bijection can trivially be extended to (ℓ, n, 2) trapezoids, where ℓ ≥ 0 is an integer. An (ℓ, n, 2) Magog trapezoid is defined as an (n, 2) Magog trapezoid with the difference that item (ii) of Definition 1 is replaced by (ii') m 1,j ≤ m 2,j ≤ j + ℓ for all j ∈ {1, . . . , n -1} and m 2,n ≤ n + ℓ . See Figure 4. Similarly, an (ℓ, n, 2) Gog trapezoid is defined as an (n, 2) Gog trapezoid with the difference that item (ii) of Definition 2 is replaced by (ii') g 1,j < g 2,j < j + 2 + ℓ for all j ∈ {1, . . . , n -1} ;

g 1,1 g 1,2 g 1,3 g 1,4 g 1,5 g 1,6 g 1,7 g 1,8 g 2,1 g 2,2 g 2,3 g 2,4 g 2,5 g 2,6 g 2,7 m 1,1 m 1,2 m 1,3 m 1,4 m 1,5 m 1,6 m 1,7
m 2,1 m 2,2 m 2,3 m 2,4 m 2,5 m 2,6 m 2,7 m 2,8

(3, 8, 2) Gog trapezoid (3, 8, 2) Magog trapezoid For any ℓ ≥ 1 and n ≥ 3, the mappings Φ n and Ψ n can be extended without any differences in the construction into bijections between the set of (ℓ, n, 2) Magog trapezoids and the set of (ℓ, n, 2) Gog trapezoids. The proofs can be copied almost verbatim, the only thing to do is add ℓ whenever we use one of the bounds changed by these definitions.

Unfortunately, as of today, we did not manage to extend this bijection to (n, 3) trapezoids. The mapping Φ n exchanges the sizes of two consecutive rows so that one could think that, in the case of (n, 3) trapezoids, we would need to apply a similar operation several times in order to pass from a Magog to a Gog. Unfortunately, whenever a third row is present, we cannot slide the boxes of two consecutive rows without breaking the rules. This question remains under investigation.

Figure 1 :

 1 Figure 1: The conditions satisfied by (n, 2) Magog and Gog trapezoids. Every sequence formed by numbers obtained by following the direction of a simple-arrowhead (resp. a double-arrowhead) arrow is non-decreasing (resp. increasing).

Figure 2 :

 2 Figure 2:The three cases of the bijection, from a Magog trapezoid to a Gog trapezoid. On the top line, the first bug is 3: it is symbolized by a small black oblique line. The colored blocks are moved and, whenever there is a tag on a block, it is added to all the elements of the block.

Figure 3 :

 3 Figure 3: The three cases of the bijection, from a Gog trapezoid to a Magog trapezoid. On the top line, k = 3.

Figure 4 :

 4 Figure 4: Definition of (ℓ, n, 2) trapezoids.

† CNRS & Laboratoire d'Informatique de l' École polytechnique; jeremie.bettinelli@normalesup.org; www. normalesup.org/~bettinel.


Mehwish Alam
email: mehwish.alam@loria.fr

Aleksey Buzmakov
email: aleksey.buzmakov@loria.fr

Amedeo Napoli
email: amedeo.napoli@loria.fr

Alibek Sailanbayev
email: alibek.sailanbayev@nu.edu.kz

Revisiting Pattern Structures for Structured Attribute Sets

Keywords: Formal Concept Analysis, Pattern Structures, Structured Attribute Sets, Least Common Ancestor, Range Minimum Query

In this paper, we revisit an original proposition on pattern structures for structured sets of attributes. There are several reasons for carrying out this kind of research work. The original proposition does not give many details on the whole framework, and especially on the possible ways of implementing the similarity operation. There exists an alternative definition without any reference to pattern structures, and we would like to make a parallel between two points of view. Moreover we discuss an efficient implementation of the intersection operation in the corresponding pattern structure. Finally, we discovered that pattern structures for structured attribute sets are very well adapted to the classification and the analysis of RDF data. We terminate the paper by an experimental section where it is shown that the provided implementation of pattern structures for structured attribute sets is quite efficient.

Introduction

In this paper, we want to make precise and develop a section of [START_REF] Ganter | Pattern structures and their projections[END_REF] related to pattern structures and structured sets of attributes. There are several reasons for carrying out this kind of research work. Firstly, the the pattern structures, the similarity operator and the associated subsumption operator for structured sets of attributes are based on antichains and rather briefly sketched in the original paper. Secondly, there is an alternative and a more "qualitative" point of view on the same subject in [START_REF] Carpineto | A lattice conceptual clustering system and its application to browsing retrieval[END_REF][START_REF] Carpineto | Concept Data Analysis: Theory and Applications[END_REF] without any reference to pattern structures, and we would like to make a parallel between these two points of view. Finally, for classifying RDF triples in the analysis of the content of Linked Open Data (LOD), we discovered that actually pattern structures for structured sets of attributes are very well adapted to solve this problem [START_REF] Alam | Interactive exploration over RDF data using Formal Concept Analysis[END_REF]. Moreover, the classification of RDF triples provides a very good and practical example for illustrating the use of such a pattern structure and helps to reconcile the two above points of view.

Accordingly, in this paper, we will go back to the two original definitions and show how they are related. For completing the history, it is worth mentioning that antichains, whose intersection is the basis of the similarity operation in the pattern structure for structured attribute sets, our paper, are studied in the book [START_REF] Caspard | Finite Ordered Sets[END_REF]. Moreover, this book cites as an application of antichain intersection an older paper from 1994 [START_REF] Pichon | Un algorithme de partition d'un produit direct d'ordres totaux en un nombre fini de chaînes[END_REF], written in French, about the decomposition of total orderings and its application to knowledge discovery.

Then, we proceed to present a way of efficiently working with antichains and intersection of antichains, which can be very useful, especially in case of large sets of data. The last section details a series of experiments where it is shown that pattern structures can be implemented with an efficient intersection operation and that they have a generally better behavior than scaled contexts.

Pattern Structures for Structured Attributes

Pattern Structures

Formal Concept Analysis [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] can process only binary contexts. Pattern structures are an extension of FCA which allow a direct processing of such kind of data. The formalism of pattern structures was introduced in [START_REF] Ganter | Pattern structures and their projections[END_REF].

A pattern structure is a triple (G, (D, ), δ), where G is the set of objects, (D, ) is a meet-semilattice of descriptions, and δ : G → D maps an object to its description. In other words, a pattern structure composed of a set of objects, a set of descriptions equipped with a similarity operation denoted by . This similarity operation is idempotent, commutative and associative. If (G, (D, ), δ) is a pattern structures then the derivation operators (Galois connection) are defined as: A pattern extent corresponds to the maximal set of objects A whose descriptions subsume the description d, where d is the maximal common description for objects in A. The set of all pattern concepts is partially ordered w.r.t. inclusion on extents, i.e., (A 1 , d 1 ) ≤ (A 2 , d 2 ) iff A 1 ⊆ A 2 (or, equivalently, d 2 d 1 ), making a lattice, called pattern lattice.

A := g∈A δ(g) for A ⊆ G d := {g ∈ G|d δ(g)} for d ∈ D Each element in D is

Two original propositions on structured attribute sets

We briefly recall two original propositions supporting the present study. The first work is firstly published by Carpineto & Romano in [START_REF] Carpineto | A lattice conceptual clustering system and its application to browsing retrieval[END_REF] and then developed in [START_REF] Carpineto | Concept Data Analysis: Theory and Applications[END_REF]. The second work is related to the definition of pattern structures by Ganter & Kuznetsov in [START_REF] Ganter | Pattern structures and their projections[END_REF].

In [START_REF] Carpineto | A lattice conceptual clustering system and its application to browsing retrieval[END_REF][START_REF] Carpineto | Concept Data Analysis: Theory and Applications[END_REF], the authors consider a formal context (G, M, I) and an extended set of attributes M * ⊃ M where attributes are organized within a subsumption hierarchy according to a partial ordering denoted by ≤ M * . The following condition should be satisfied:

∀g ∈ G, m 1 ∈ M, m 2 ∈ M * : [(g, m 1 ) ∈ I, m 1 ≤ M * m 2 ] =⇒ (g, m 2 ) ∈ I
The subsumption hierarchy can be either a tree or an acyclic graph with a unique maximal element, as this is the case of attributes lying in a thesaurus for example. Then the building of a concept lattice from such a context can be done in two main ways. A first is to use a scaling and to complete the description of an object with all attributes implied by the original attributes. We discuss this scaling operation in detail later. The problem would be the space necessary to store the scaled context, especially in case of big data. A second way is to use an "extended intersection operation" between sets of attributes which is defined as follows. The intersection of two sets of attributes Y 1 and Y 2 is obtained by finding for each pair (m 1 , m 2 ), m 1 ∈ Y 1 , m 2 ∈ Y 2 , the most specific attributes in M * that are more general than m 1 and m 2 , and then retaining only the most specific elements of the set of attributes generated in this way. Then if (X 1 , Y 1 ) and (X 2 , Y 2 ) are two concepts, we have:

(X 1 , Y 1 ) ≤ (X 2 , Y 2 ) ⇐⇒ ∀m 2 ∈ Y 2 , ∃m 1 ∈ Y 1 , m 1 ≤ M * m 2
In other words, this intersection operation corresponds to the intersection of two antichains as this is explained in [START_REF] Ganter | Pattern structures and their projections[END_REF], where the authors define the formalism of pattern structures and take as an instantiation structured attribute sets. More formally, it is assumed that the attribute set (M, ≤ M ) is finite and partially ordered, and that all attribute combinations that can occur must be order ideals (downsets) of this order. Then, any order ideal O can be described by the set of its maximal elements; O = {x|∃y ∈ M, x ≤ y}. It should be noticed that the order considered on the attribute sets in [START_REF] Ganter | Pattern structures and their projections[END_REF] is reversed with respect to the order considered in [START_REF] Carpineto | A lattice conceptual clustering system and its application to browsing retrieval[END_REF][START_REF] Carpineto | Concept Data Analysis: Theory and Applications[END_REF]. However, we keep the original definitions used in [START_REF] Ganter | Pattern structures and their projections[END_REF] in the present paragraph. These maximal elements form an antichain, and conversely, each antichain is the set of maximal elements of some order ideal. Thus, the semilattice (D, ) of patterns in the pattern structure consists of all antichains of the ordered attribute set. In addition, it is isomorphic to the lattice of all order ideals of the ordered set, and thus isomorphic to the concept lattice of the context (P, P, ≥). For two antichains AC 1 and AC 2 , the infimum AC 1 AC 2 consists of all maximal elements of the order ideal:

{m ∈ P | ∃ac 1 ∈ AC 1 , ∃ac 2 ∈ AC 2 , m ≤ ac 1 and m ≤ ac 2 }.
There is a "canonical representation context" (or an associated scaling operator) for the pattern structure (G, (D, ), δ) related to structured attribute sets, which is defined by the set of "principal ideals ↓ p" as follows: (G, P, I) with (g, p) ∈ I ⇐⇒ p ≤ δ(g).

In the next section, we make precise and discuss the pattern structure for structured attribute sets by taking the point of view of filters and not of ideals in agreement with the order from [START_REF] Carpineto | A lattice conceptual clustering system and its application to browsing retrieval[END_REF][START_REF] Carpineto | Concept Data Analysis: Theory and Applications[END_REF], with the most general attributes above.

From Structured Attributes to Tree-shaped Attributes

An important case of structured attributes is "tree-shaped attributes", i.e., when the attributes are organized within a partial order corresponding to a rooted tree. If it is the case, then the root of the tree, denoted by , can be matched against the description of any object, while the leaves of this tree are the most detailed descriptions. For example, the root can correspond to the attribute 'Animal' and a leaf can correspond to the attribute 'Cat'; somewhere in between there could be attribute 'Mammal'.

An example of such kind of data naturally appears in the domain of semantic web data. For example, Figure 1 gives a small part of ACCS1 . This attribute tree will be used as a running example and should be read as follows. If an object belongs to class C 1 (and probably to some other classes), then it necessarily belongs to classes C 10 , C 12 , and , e.g., if an object is a cat, then it is a mammal and an animal. Accordingly, the description of an object can include several classes, e.g., classes C 1 , C 5 and C 8 . Thus, some of the tree-shaped attributes can be omitted from the description of an object. However, they should be always taken into account when computing the intersection between descriptions. Thus, in order to avoid redundancy in the descriptions, we can allow only antichains of the tree as possible elements in the set D of descriptions, and then, accordingly compute the intersection of antichains.

An efficient way of computing intersection of antichains is explained in the next section. Here it is important to notice that although it is a hard task to efficiently compute intersection of antichains in an arbitrary partial order of attributes, the intersection of antichains in a tree can help in computing this more general intersection. Indeed, in a partial order of attributes, we can add an artificial attribute that can be matched against any description. Then, instead of considering an intersection of antichains in an arbitrary poset we can take a spanning tree of it with taken as the root. Although we have lost some relations between attributes, and, thus, the size of the antichains is probably larger, we can apply the efficient intersection of antichains of tree discussed below.

On Computing Intersection of Antichains in a Tree

In this subsection we show how to efficiently solve the problem of intersection of antichains in a tree. The problem is formalized as follows. A partial order is

C12 C10 C1 C2 C11 C4 C5 C6 C13 C7 C8 C9
Fig. 1: A small part from ACM Computing Classification System (ACCS).

described by the Hasse diagram corresponding to the tree. The root is denoted by and it is larger w.r.t. the partial order than any other element in the tree. Given a rooted tree T and two antichains X and Y , we should find an antichain Z such that (1) for all x ∈ X ∪ Y there is z ∈ Z such that x ≤ z and (2) no z ∈ Z can be removed or changed to z < z without violating requirement [START_REF] Ganter | Pattern structures and their projections[END_REF].

If the cardinality of antichains X and Y is 1 then this task is reduced to the well-known problem of a Least Common Ancestor (LCA). In 1984 it was already shown that the LCA problem can be reduced to Range Minimum Query (RMQ) problem [START_REF] Gabow | Scaling and Related Techniques for Geometry Problems[END_REF]. Later several simpler approaches were introduced for solving the LCA problem. Here we briefly introduce the reduction of LCA to RMQ in accordance with [START_REF] Bender | Lowest common ancestors in trees and DAGs[END_REF].

Reduction of LCA to RMQ. Given an array of numbers, the RMQ problem consists in efficient answering queries on the position of the minimal value in a given range (interval) of positions for this array. For example, given an array

Array [ 2 1 0 3 2 ] Positions 1 2 3 4 5
where the first value is in position 1 and the last value is in position 5, the answer to the query on the position of the minimal number in the range 2-4, i.e., the corresponding part of array is [1;0;3], is 3 (the value of the 3rd element in the array is 0 and it is the minimal value in this range). Accordingly, the position of the minimal number in the range 1-2 (the part of the array is [2;1]) is 2. The good point about this problem is that it can be solved in O(n) preprocessing computational time and in O(1) computational time per one query [START_REF] Bender | Lowest common ancestors in trees and DAGs[END_REF], where n is the number of elements in the array.

In order to introduce the reduction of LCA to RMQ we need to know what is the depth of a tree vertex. The depth of a vertex in a rooted tree is the number of edges in the shortest path from that vertex to the root of the tree.

We create the array of depths of the vertices in the tree that is used as an input array for RMQ. We build this array in the following way. We traverse the tree in depth first order (see Figure 2). Every time the algorithm considers a Now for any value in D we know the corresponding vertex of the tree and any vertex of the tree is associated with several positions in D. For example, in Figure 2 the value in the first position of D, i.e., D [START_REF] Ganter | Pattern structures and their projections[END_REF], is 0, corresponding to the root of the tree. If we take vertex 3, then the associated values of D are on positions 5, 7, and 9.

Given two vertices A, B ∈ T , let a be one of the positions in D corresponding to vertex A, let b be one of the positions in D corresponding to B. Then it can be shown that the vertex corresponding to the minimal value in D in the range a-b is the least common ancestor of A and B. For example, to find LCA between vertices 3 and 6 in Figure 2, one should first take two positions in D corresponding to vertices 3 and 6. Positions 5,7, and 9 in array D correspond to vertex 3, positions 12 and 14 correspond to vertex 6. Thus, we can query RMQ for ranges 5-14, 7-14, 7-12, etc. The minimal value in D for all these ranges is 0 located at position 11 in D, i.e., RMQ(5, 14) = 11. Thus, the vertex corresponding to position 11, i.e., vertex 0, is the least common ancestor for vertices 3 and 6.

Let us notice that if Let us reformulate this naive approach in terms of RMQ. Given a depth array D and two sets of indices A, B ⊆ N |D| forming an antichain, we should compute the set Z = {RMQ(a, b) | ∀a ∈ A and ∀b ∈ B} and then remove all elements z ∈ Z such that there is x ∈ Z \ {z} with the position RMQ(z, x) corresponding to the same vertex as z, i.e., elements z corresponding to an ancestor of another element from Z. Let us consider for example the tree T given in Figure 1. Let us discuss two points that help us to reduce the complexity of the naive approach. Consider the positions i ≤ l ≤ m ≤ j and k = RMQ(i, j), n = RMQ(l, m). Then the depth in the position k is not larger than the depth in the position n, D[k] ≤ D[n]. Hence the position RMQ(k, n) corresponds to the same vertex as position k. For example, in Figure 3 However, the set Z of RMQs of consecutive elements does not not necessarily correspond to an antichain in T . Thus we should filter this set, in order to remove all ancestors of another elements form Z. Accordingly, it is clear that to filter the set Z it is enough to check only consecutive elements of Z. For example, the intersection of A = {4, 12, 20} and B = {4, 18, 22} gives us the following set Z = {4, 8, 15, 19, 21}. Let us now check the RMQs of consecutive elements. RMQ(4, 8) = 8, thus, 8 is an ancestor of 4 and 8 can be removed. Since 8 is removed, we compare RMQ(4, 15) = 15, thus, 15 should be also removed. Then we compute RMQ(4, 19) = 15, i.e., the indices 4 and 19 are not ancestors and both are kept. Now we compute RMQ(19, 21) = 19 and, thus, 19 should be removed (actually positions 19 and 21 correspond to the same vertex C 13 and one of them should be removed). Thus, the result of intersecting A and B is {4, 21} corresponding to the antichain {C 1 , C 13 }.

A ∈ T is
Since the number of elements in the set Z is O(|A| + |B|), then overall complexity of computing intersection for two antichains A, B ⊂ T of a tree T is O(|A| + |B|) or, taking into account that the cardinality of an antichain in a tree is less then the number of leaves (vertices having no descendants) in this tree, the complexity of computing intersection of two antichains is O(|Leaves(T )|).

Antichain intersection by scaling. An equivalent approach for computing intersection of antichains is to scale the antichains to the corresponding filters. A filter corresponding to an antichain in a poset is the set of all elements of the poset that are larger then at least one element from the antichain. For example, let us consider a tree-shaped poset in Figure 1. A filter corresponding to the antichain {C 1 , C 5 , C 8 } is the set of all ancestors of all elements from the antichain, i.e., it is equal to {C 1 , C 10 , C 12 , , C 5 , C 11 , C 8 , C 13 , C 6 }.

The set-intersection of filters corresponding to the given antichains is a filter corresponding to the antichain resulting from intersection of the antichains. However this approach has a higher complexity. Indeed, the size of a filter is O(|T |) and, thus, the computational complexity of intersecting two antichains by means of a scaling is O(|T |) which is harder then O(|Leaves(T )|) for intersecting antichains directly. Indeed, the number of leaves in a tree can be dramatically smaller than the number of vertices in this tree. For example, the number of vertices in Figure 1 is 13, while the number of leaves is only 7. Thus, the direct intersection of antichains is more efficient than the intersection by means of a scaling procedure.

Relation to intersection of antichains in partially ordered sets of attributes. As it was mentioned in the previous section, the intersection of antichains in arbitrary posets can be reduced to the intersection of antichains in a tree. However, the size of the antichain representing a description of an object can increase. Indeed, since we have reduced a poset to a tree, some relations have been lost, and thus the attributes that are subsumed in the poset for a given antichain A are no more subsumed in the tree for A, and hence should be added to A. However, the reduction is still more computationally efficient than Table 1: Results of the experiments with different kind of data.

#objects is the number of objects in the corresponding dataset. #attributes is the number of numerical attributes before scaling. |G| is the number of objects used for building the lattice. |T | is the size of the attribute tree and the number of attributes in the scaled context |M |. Leaves(T ) is the number of leaves in the attribute tree. |L| is the size of the concept lattice for the corresponding data. t T is the computational time for data represented as a set of antichains in the attribute tree.

tK is the computational time represented by a scaled context, i.e., by a set of filters in the attribute tree; '*' shows that the we are not able to build the whole lattice. tnum is the computational time for numerical data represented by an interval pattern structure.

(a) Real data experiments. computing the intersection of antichains in a poset by means of a scaling as it is discussed in the previous paragraph. However, for the reduction it could be interesting to find the spanning tree with the minimal number of leaves. Unfortunately, this is an NP-complete task and it thus cannot be applied for increasing the computational efficiency [START_REF] Salamon | On finding spanning trees with few leaves[END_REF]. We should notice here that there is some work that solves the LCA problem for more general cases, e.g., lattices [START_REF] Aït-Kaci | Efficient Implementation of Lattice Operations[END_REF] or partially ordered sets [START_REF] Bender | Lowest common ancestors in trees and DAGs[END_REF]. However, it is an open question whether these works can help to efficiently compute intersection of antichains in the corresponding structures.

Dataset

Experiments and Discussion

Several experiments are conducted using publicly available data on a MacBook with a 1.3GHz Intel Core i5, 4GB of RAM running OS X Yosemite 10.3. We have used FCAPS2 software developed in C++ for dealing with different kinds of pattern structures. It can build a concept lattice starting from a standard formal context or from object descriptions given as antichains of a given tree. The last one is based on the similarity operation that is discussed above. We performed our experiments on two datasets from different domains namely DBLP and biomedical data. In these datasets, object descriptions are given as subsets of attributes. A taxonomy of the attributes is already known based on domain knowledge. We compute a concept lattice in two different ways. In the first one, we directly compute the concept lattice from the antichains in a taxonomy. In the second one we scale every description to the corresponding filter of the taxonomy. After this we do not rely on the taxonomy and process the scaled context with standard FCA.

The first data set is DBLP, from which we extracted a subset of papers with their keywords published in conferences in Machine Learning domain. The taxonomy used for classifying such kind of triples is ACM Computing Classification System (ACCS) 3 .

The second data set belongs to the domain of life sciences. It contains information about drugs, their side effects (SIDER4 ), and their categories (Drug-Bank 5 ). The taxonomies related to this dataset are MedDRA6 for side effects and MeSH7 for drug categories.

The parameters of the datasets and the computational results are shown in Table 1a. It can be noticed that for DBLP the context consists of 5293 objects and 33207 attributes, in the taxonomy of the attributes we have 33198 leaves meaning that most of attributes are mutually incomparable. It took 45 seconds to produce a lattice having 10134 concepts directly from the descriptions given by antichains of the taxonomy. To produce the same lattice starting from a scaled context the program only takes 21 seconds. However, if we consider the biomedical data, the approach based on antichains is better. Indeed, it takes 145 seconds, while the computation starting from the scaled contexts takes 162 seconds. In this case, the dataset contains 1490 attributes with 933 leaves. Thus, the direct approach works faster if the number of leaves is significantly smaller than the number of vertices. It is worth noticing that the size of antichains is significantly smaller than the size of the filters, and thus our approach is more efficient. However, when the number of leaves is comparable to the number of vertices, our approach is slower. Although in this case our approach has the same computational complexity as the scaling approach, the antichain intersection problem requires more efforts than the set intersection.

Since the efficiency of the antichain approach is high for the trees with a low number of leaves, we can use this method to increase efficiency of standard FCA for special kind of contexts. In a context (G, M, I) an attribute m 1 can be considered as an ancestor of another attribute m 2 if any object containing the attribute m 2 also contains the attribute m 1 . Accordingly we can construct an attribute tree T and rely on it for computing intersection operation. In this case the set of attributes M and the set of vertices of T are the same and |M | = |. The second part of the experiment was based on this observation.

We used numerical data from Bilkent University in the second part of the experiments 8 . It was converted to formal contexts by the standard interodinal scaling. The scaled attributes are closely connected, i.e., there are a lot of pairs of attributes (m 1 , m 2 ) such that the set of objects described by m 1 is a subset of objects described by m 2 , i.e., (m 1 ) ⊆ (m 2 ) . Thus, we can say that m 1 ≤ m 2 . Using this property we built attribute trees from the scaled contexts. These trees have many more vertices than leaves, thus, the approach introduced in this paper should be efficient. We compare our approach with the scaling approach. Moreover, recently, it was shown that interval pattern structures (IPS) can be efficiently used to process such kind of data [START_REF] Kaytoue | Mining gene expression data with pattern structures in formal concept analysis[END_REF]. Accordingly we also compared our approach with IPS.

The results are shown in Table 1b. Compared to Table 1a it has several additional columns. First of all, since for numerical data we typically got large lattices, in most of the cases we considered only part of the objects. The actual number of used objects is given in the column |G|, while the total size of the dataset is given in the column '#objects', e.g., BK dataset contained 96 objects, while we have used only 35. In addition for every dataset we also provide the number of the numerical attributes, e.g., BK has 5 numerical attributes. We should notice that when we built the lattice from some datasets by standard FCA, the lattice was so large that the memory was swapping and we stopped the computation. It was not the case for our approach since antichains requires less memory to store than the corresponding filters. The fact of swapping is shown by '*' next to computational time in column t K . In addition we also show the time for IPS to process the same dataset. For example, the processing of BK dataset took 37 seconds by our approach, took more than 42 seconds by standard FCA and memory had started swapping, and took 19 seconds by IPS.

This experiment shows that our approach takes not only less time to compute concept lattice, but also requires less memory, since there is no memory swapping. We can also see that the computation time for IPS is smaller than for our approach. However, IPS is only applicable for numerical data, while our approach can be applied for all cases when attributes of a context are structured. For example, we can deal with graph data scaled to the set of frequent subgraphs where many such attributes are subgraphs of other attributes.

In this paper we recalled two approaches for dealing with structured attributes and explained how we can compute intersection of antichains in tree-shaped posets of attributes, an essential operation for working with structured attributes. Our experiments showed the computational efficiency of the proposed approach. Accordingly, we are interested in applying our approach to other kinds of data such as graph data. Moreover, the generalization of our approach to other kinds of posets is also of high interest.

  referred to as a pattern. The natural order on (D, ), given by c d ⇔ c d = c is called the subsumption order. Now a pattern concept can be defined as follows: Definition 1 (Pattern Concept). A pattern concept of a pattern structure (G, (D, ), δ) is a pair (A, d) where A ⊆ G and d ∈ D such that A = d and A = d , where A is called the concept extent and d is called the concept intent.

2 3 2 3 2 1 0 1 2 Fig. 2 :

 22 Fig. 2: Reducing RMQ task to LCA. Arrows show the depth first order traversal. The depth array D is accompanied by the corresponding vertices and positions.

Fig. 3 :

 3 Fig. 3: Depth array, the corresponding vertices, and indices for the tree in Figure 1.

Figure 3

 3 shows the depth array, the corresponding vertices, and indices of this array. Let us show how to compute the intersection of A = {C 1 , C 5 , C 8 } and B = {C 1 , C 7 , C 9 }. The expected result is {C 1 , C 13 }. First we translate the sets A and B to the indices in array D for RMQ, i.e., A = {4, 12, 20} and B = {4, 18, 22}. Then we compute RMQ for all pairs from A and B: {RMQ(4, 4) = 4, RMQ(4, 18) = 15, RMQ(4, 22) = 15, • • • , RMQ(20, 18) = 19, • • • }. Now we should remove positions corresponding to ancestors in the tree, e.g., RMQ(4, 15) = 15 and, hence, 15 should be removed. The result is {4, 13} representing exactly {C 1 , C 13 }.

  RMQ(4, 6) = 5 and RMQ(2, 7) = 2. The value in position 5 in the array D is D[5] = 2. It is larger than the value in position 2, D[2] = 1. Thus, the value in position returned by RMQ for the larger range is smaller than the value in position returned by RMQ for the smaller range. Thus, given two sets of indices A, B ⊆ N |D| corresponding to antichains, we can modify the naive algorithm by ordering the set A ∪ B and computing RMQ only for consecutive elements from different sets, rather then for all pairs from different sets. For example, for intersecting A = {4, 12, 20} and B = {4, 18, 22}, we join them to the set Z = {4 A , 4 B , 12 A , 18 B , 20 A , 22 B }. Then, we compute RMQ only for consecutive elements from different sets, i.e., RMQ(4, 4) = 4, RMQ(4, 12) = 8, RMQ(12, 18) = 15, RMQ(18, 20) = 19, and RMQ(20, 22) = 21. The cardinality of A ∪ B is less then |A| + |B|, hence, the number of the consecutive elements is O(|A|+|B|), and, thus, the number of RMQs of consecutive elements is O(|A| + |B|).

This work was done during the stay of Alibek Sailanbayev at LORIA, France.

https://www.acm.org/about/class/2012

https://github.com/AlekseyBuzmakov/FCAPS

https://www.acm.org/about/class/2012

http://sideeffects.embl.de/

http://www.drugbank.ca/

http://meddra.org/

http://www.ncbi.nlm.nih.gov/mesh/

http://funapp.cs.bilkent.edu.tr/DataSets/


Mehwish Alam
email: mehwish.alam@loria.fr

Amedeo Napoli
email: amedeo.napoli@loria.fr

Matthieu Osmuk
email: matthieu.osmuk@loria.fr

RV-Xplorer: A Way to Navigate Lattice-Based Views over RDF Graphs

Keywords: RV-Xplorer, Lattice Navigation, SPARQL Query Views, Formal Concept Analysis

More and more data are being published in the form of machine readable RDF graphs over Linked Open Data (LOD) Cloud accessible through SPARQL queries. This study provides interactive navigation of RDF graphs obtained by SPARQL queries using Formal Concept Analysis. With the help of this View By clause a concept lattice is created as an answer to the SPARQL query which can then be visualized and navigated using RV-Xplorer (Rdf View eXplorer). Accordingly, this paper discusses the support provided to the expert for answering certain questions through the navigation strategies provided by RV-Xplorer. Moreover, the paper also provides a comparison of existing state of the art approaches.

Introduction

Recently, Web Data is turning into "Web of Data" which contains the meta data about the web documents present in HTML and textual format. The goal behind this "Web of Data" is to make already existing data to be usable by not only human agents but also by machine agents. With the effort of Semantic Web community, an emerging source of meta data is published on-line called as Linked Open Data (LOD) in the form of RDF data graphs. There has been a huge explosion in LOD in recent past and is still growing. Up until 2014, LOD contains billions of triples. SPARQL1 is the standard query language for accessing RDF graphs. It integrates several resources to generate the required answers For instance, queries such as What are the movements of the artists displayed in Musee du Louvre? can not be answered by standard search engines. Nowadays, Google has introduced a way of answering questions directly such as currency conversion, calculator etc. but such queries are answered based on most frequent queries posed by the experts.

When an expert poses a query to a search engine too many results are retrieved for the expert to navigate through, which may be cumbersome when a expert has to go through a number of links to find the interesting ones, hence leading to the problem of information overload [START_REF] Carpineto | A survey of web clustering engines[END_REF]. Same is the case with the answers obtained by SPARQL query with the SELECT [START_REF] Claudia D'amato | Categorize by: Deductive aggregation of semantic web query results[END_REF]. Even if there are hundreds of answers, it becomes harder for the expert to find the interesting patterns. The current study is a continuation of Lattice-Based View Access (LBVA) [START_REF] Alam | Defining views with formal concept analysis for understanding SPARQL query results[END_REF] which provides a view over RDF graphs through SPARQL queries to give complete understanding of a part of RDF graph that expert wants to analyze with the help of Formal Concept Analysis. LBVA takes the SPARQL query and returns a concept lattice called as view instead of the results of the SPARQL query. These views created by LBVA are machine as well as human processable. Accordingly, RV-Xplorer (Rdf View eXplorer) exploits the powerful mathematical structure of these concept lattices thus making it interpretable by human. It also allows human agents to interact with the concept lattice and perform navigation. The expert can answer various questions while navigating the concept lattice. RV-Xplorer provides several ways to guide the expert during this navigation process.

This paper is structured as follows: section 2 gives the motivating example, section 3 introduces the required background knowledge to understand the rest of the paper. Section 4 details the elements of Graphical User Interface while section 5 and section 6 details the navigation operations as well as other functionalities supported by RV-Xplorer. Section 7 briefly discusses the related work. Finally, section 8 concludes the paper and discusses the future work.

Motivating Example

Consider a scenario where an expert wants to pose following questions based on articles published in conferences or journals from a team working on data mining. In the current study, we extract the papers published in "Orpailleur Team" in LORIA, Nancy, France. Following are the questions in which an expert may be interested in:

-What are the main research topics in the team and the key researchers w.r.t. these topics, for example, researchers involved in most of the papers in a prominent topic? -What is the major area of the research of the leader of the team and various key persons? -Can the diversity of the team leader and key persons be detected? -Given a paper is it possible to retrieve similar papers published in the team? -Who are the groups of persons working together? -What are the research tendencies and possibly the forthcoming and new research topics (for example, single and recent topics which are not in the continuation of the present topics)?

Such kind of questions can not be answered by Google. In this paper we want to answer such kind of questions through lattice navigation supported by RV-Xplorer which is built from an initial query and then is explored by the expert according to her preferences.

Linked Open Data: Linked Open Data (LOD) [START_REF] Bizer | Linked data -the story so far[END_REF] is the way of publishing structured data in the form of RDF graphs. Given a set of URIs U, blank nodes B and literals L, an RDF triple is represented as t

= (s, p, o) ∈ (U ∪ B) × U × (U ∪ B ∪ L)
, where s is a subject, p is a predicate and o is an object. A finite set of RDF triples is called as RDF Graph G such that G = (V, E), where V is a set of vertices and E is a set of labeled edges. Each pair of vertices connected through a labeled edge keeps the information of a statement. Each statement is represented as subject, predicate, object referred to as an RDF Triple. V includes subject and object while E includes the predicate. SPARQL: A standard query language for RDF graphs is SPARQL2 which mainly focuses on graph matching. A SPARQL query is composed of two parts the head and the body. The body of the query contains the Basic Graph Patterns (present in the WHERE clause of the query). These graph patterns are matched against the RDF graph and the matched graph is retrieved and manipulated according to the conditions given in the query. The head of the query is an expression which indicates how the answers of the query should be constructed.

Let us consider a query from the scenario in section 2, Q = Who is the team leader of the data mining team in loria. For answering such questions consider an RDF resource containing all the papers ever published in the data mining team. With the help of SPARQL query the papers published in the last 5 years in English language can be extracted. The SPARQL representation of the query Q is shown in listing 1.1. Lines 1, 2 keep the information about the prefixes used in the rest of the query. Line 5, 6 and 7 retrieve all the papers with their authors and keywords. Line 8 and 9 retrieve the publication year of the paper and filter according to the condition. Lattice-Based View Access: Lattice-Based View Access [START_REF] Alam | Defining views with formal concept analysis for understanding SPARQL query results[END_REF], allows the classification of SPARQL query results into a concept lattice, referred to as a view, for data analysis, navigation, knowledge discovery and information retrieval purposes. It introduces a new clause VIEW BY which enhances the functionality of already existing GROUP BY clause in SPARQL query by adding sophisticated classification and Knowledge Discovery aspects.

The variable appearing in the VIEW BY clause of the SPARQL query is referred to as object variable 3 The rest of the variables are the attribute variables. Then the answer tuples obtained by the query are processed based on object and the attribute variables. The values obtained for the object variable are mapped to the objects in the formal context K = (G, M, I) and the answers obtained for attribute variables are mapped to the attributes in the context. Consider the query given in listing 1.1 with classification capabilities i.e., containing the clause VIEW BY ?title then the set of variables in the SELECT clause can be given as V = {?title, ?keyword, ?author}. The object variable will be ?title and attribute variable will be ?keyword and ?author. After applying LBVA, the objects contain the titles of the paper and the attributes are the set of keywords and authors in the context. From this context, the concept lattice is built which is referred to as a Lattice-Based View.

LBVA is oriented towards the classification of SPARQL queries, but we can interpret the present research activity at a more general level, the classification of LOD. Accordingly, what is proposed in the paper is a tool for navigating a classification of LOD.

The RV-Xplorer

RV-Xplorer (Rdf View eXplorer) is a tool for navigating concept lattices generated by the answers of SPARQL queries over part of RDF graphs using Lattice-Based View Access. Accordingly, this tool provides navigation to the expert over the classification of SPARQL query answers for analyzing the data, finding hidden regularities and answering several questions. On each navigation step it guides the expert in decision making and performing selection to avoid unnecessary selections. It also allows the user to change her point of view while navigating i.e., navigation by extent. Moreover, it also allows the expert to only focus on the specific and interesting part of the concept lattice by allowing her to hide the part of lattice which is not interesting for her.

RV-Xplorer is a web-based tool for building concept lattices. On the client side it uses D3.js which stands for Data-Driven Documents and is based on Javascript for developing interactive data visualizations in modern web browsers. It also uses model-view-controller (MVC) which separates presentation, data and logical components. On the server side we use PHP and MySQL for computing and storing the data. Generally, data can be a graph or pattern generated by pattern mining algorithms etc. Currently, this tool is not publicly available.

Figure 1 shows the overall interface of RV-Xplorer (Rdf View eXplorer) which consists of three parts: (1) the middle part is called local view which shows detailed description of the selected concept allowing interaction, navigation and level-wise navigation, (2) the left panel is referred to as Spy showing the global view of the concept lattice and (3) the lower left is the summarization index for guiding the expert in making decision about which node to choose in the next level by showing the statistics of the next level. For the running scenario, the concept lattice is also available on-line4 .

Local View

Each selected node in the concept lattice is shown in the middle part of the interface displaying complete information. Let c be the selected concept such that c ∈ C where C is the set of concepts in the complete lattice L = (C, ≤) then a local view shows the complete information about this concept i.e., the extent, intent and the links to the super-concept and the sub-concepts. The set of super and sub-concepts are linked to the selected node where each link represents the partially ordered relation ≤. By default, the top node is the selected node and is shown in local view.

Figure 1 (below) shows the selected concept, the orange part defines the label of the selected node which is the entry point for the concept, the pink and yellow parts give the labels of the super-concepts and sub-concepts connected to the selected concept respectively. The green and blue part give the information about the intent and the extent respectively.

Spy

A global view in left panel shows the map of the complete lattice L = (C, ≤) for a particular SPARQL query over an RDF Graph. It tracks the position of the expert in the concept lattice and the path followed by the expert to reach the current concept. It also helps in several navigation tasks such as direct navigation, changing navigation space and navigation between point-of-views. All of these navigation modes are discussed in section 5.

Statistics about the next level

The statistics about the next level are computed with the help of a summarization index which depicts the information about the distribution of the objects in the extent of the selected concept in the linked sub-concepts i.e., concepts in the next level of the concept lattice. Let c i be a concept in the next level where i ∈ {1, . . . , n} and n is the number of concepts in the next level. ext(c i ) is the extent of the concept then |ext(c i )| is the size of the extent. Finally, the statistics about the next level are computed with the help of summarization index.

summarization index = |ext(c i )| j={1,...,n} |ext(c j )| × 100 (1)
Here, j={1,...,n} |ext(c j )| is the sum of extent size of all the concepts in the next level. The sum of summarization index for all the sub-concept adds to 100%. In Figure 1, the percentages are represented in the form of a pie-chart which shows the distribution. The sub-concept containing the most elements in the extent has the highest percentage and hence has the biggest part in the pie chart.

Navigation Operations

In this section we detail some of the classical [START_REF] Carpineto | A lattice conceptual clustering system and its application to browsing retrieval[END_REF] as well as advanced navigation operations that are implemented in RV-Xplorer. Navigation can be done locally with a parallel operation which is shown globally through local and global views. Navigation operations allow the expert to locate particular pieces of information which helps in obtaining several answers of the expert questions as well as analysis of the data at hand. Initially, the selected concept is the top concept which contains all the objects.

Guided Downward (Drill down)/ Upward Navigation (Roll-up):

The local view provides expert with the drilling down operation which is achieved by selecting the sub-concepts given in yellow part of local view. RV-Xplorer guides the expert in drilling down the concept lattice by showing contents of the sub-concept to the expert before selecting the node on mouse over. Another added guidance provided to the expert is with the help of the summarization index which gives the statistics about the next level. This way the expert can avoid the attributes or the navigation path which may lead to uninteresting results. The local view also allows the expert to roll-up from the specific concept to the general concept. A super-concept can be selected following the link given in the view.

Consider the running scenario discussed in section 2 where the expert wants to know who are researchers having main influences in the team? by analyzing the publications of this particular team. Initially, the selected concept in the local view is the top concept (see Figure 1 (above)). Now it can be seen from the summarization index that most of the papers are contained in K#52. On mouse over on K#52 it shows that this concept keeps all the papers published by Amedeo Napoli. From here it can be safely concluded that Amedeo Napoli is the leader of the team. Similarly, several key team members can be identified on the same level such as supervisors etc. If the expert wants to view the papers published by Amedeo Napoli, a downward navigation is performed by selecting concept K#52. With the help of the summarization index another question can be answered i.e., what are the main research topics of these researchers?. Again by consulting the index it can be seen that K#4 keeps the largest percentage of papers published by Amedeo Napoli (see Figure 1 (below)) and the keyword in this concept is Formal Concept Analysis meaning that the main area of research of Amedeo Napoli is Formal Concept Analysis. However, there are many other areas of research on which he has worked, which shows the diversity of authors based on the area of research he has published in. Moreover, the sub-lattice connected to this concept keeps information about the community of authors with who she publishes the most and about which topic and what variants of formal concept analysis. Now, if the expert wants to retrieve all the papers published by Amedeo Napoli then she can go back to K#52.

Direct Navigation

The spy on the left part of the RV-Xplorer (see Figure 1) allows the expert for direct navigation. If an expert has navigated too deep in the view while performing multiple drill-down operations then the spy, which keeps track of the current position of the expert, shows all the paths from the selected concept to the top concept and allows the expert to directly jump from one concept to another linked concept without performing level-wise navigation. Unlike drilldown and roll-up, direct navigation allows the expert to skip two or more hops and select the more general or specific concept.

These three navigation modes are very common and are repeatedly discussed in many of the navigational tools built for concept lattice such as Camelis [START_REF] Ferré | Camelis: a logical information system to organise and browse a collection of documents[END_REF] and CREDO [START_REF] Carpineto | Exploiting the potential of concept lattices for information retrieval with CREDO[END_REF] which may or not may not be for a specific purpose. The main difference between RV-Xplorer and the two approaches and most of the navigational tools is that they use folder-tree display. As a contrast we manage to keep the original structure of a concept lattice. An added advantage of RV-Xplorer is that these navigation modes are guided at each step meaning that the interface shows the expert with what is contained in the next node as well as the statistics about the next level. This way the interface guides the expert in choosing the nodes interesting for her by reducing the chance of performing unnecessary navigation and backtracking to see the details unnecessarily.

Navigating Across Point-of-Views

The current interface allows the expert to toggle between points-of-view, i.e., at any point an expert can start exploring the lattice with respect to the objects (extent) in the concept lattice. Let c be the selected concept and the expert is interested in g 1 ∈ ext(c) where ext(c) is the extent of the selected concept. Then if the expert hovers her mouse over this extent in the local view, the Spy highlights all the concepts where this object is present along with the object concept of g 1 which is highlighted in red.

For instance, the selected concept contains keyword data dependencies in the intent and she is interested in the paper Computing Similarity Dependencies with Pattern Structures and she wants to retrieve all the related or similar papers then on mouse hover it highlights all the concepts containing this paper. Then she selects the concept highlighted in red i.e., the object concept of this paper. The right side of Figure 2 shows the highlighted object concept of Computing Similarity Dependencies with Pattern Structures in RV-Xplorer. After this concept is selected. The spy highlights all the paths from this concept until bottom and the top which actually is the sub-lattice associated to this paper. All the objects contained in the extent of the concepts in this sub-lattice are similar to the paper at hand i.e., papers sharing some properties with the paper Computing Similarity Dependencies with Pattern Structures.

If we consider the folder-tree display as discussed in most of the navigational tools such as Camelis [START_REF] Ferré | Camelis: a logical information system to organise and browse a collection of documents[END_REF], CREDO [START_REF] Carpineto | Exploiting the potential of concept lattices for information retrieval with CREDO[END_REF] and CEM [START_REF] Cole | CEM -A conceptual email manager[END_REF], such kind of navigation is not possible because it only allows navigation w.r.t. intent and extent is considered as the answers of the navigations. In case of RV-Xplorer, it is possible to obtain the sub-lattice related to a certain interesting object and this way the whole sub-lattice connected to the object concept of the object of interest can be navigated to retrieve similar objects i.e., sharing at least one attribute with the object of interest.

Altering Navigation Space

The navigation space can be changed when the selected concept is deep-down in the concept lattice without the effort to start the navigation all over again from the top concept. Let c be the selected concept such that m 1 and m 2 ∈ int(c) (int(c) is the intent of the selected concept) and the expert has navigated downwards from the concept whose intent only contains m 1 . Now the expert wants to navigate the lattice w.r.t. m 2 , on mouse hover the interface highlights all the concepts where the given attribute exists and further highlights the attribute concept in red. The attribute concept of m 2 can be selected. In the running example, if the expert has navigated the lattice w.r.t. the author Amedeo Napoli and she finds some papers on FCA authored by Amedeo Napoli. Now she wants to navigate the concept lattice w.r.t. the keyword FCA then she can easily locate the attribute concept of the keyword FCA and navigate to get specific information. The left side of Figure 2 shows the highlighted attribute concept of FCA in RV-Xplorer.

In tree-folder display altering navigation space w.r.t. intent needs the expert to locate the attribute concept by herself by manually checking each of the branches because it represents the concept lattice as a tree. The problem with such a display is that it is not easy to alter the browsing space quickly or change the navigation point of view. Moreover, the sub-lattice connected to a selected concept can not be seen because of the restrictions posed by tree display.

Area Expansion

Area expansion allows the expert to select several concepts at one time scattered over the concept lattice and gives the overall view of what these concepts contains. These concepts are not necessarily a part of navigation path that the expert is following. It allows the expert to have an overall view of other concepts without starting the navigation process again.

This idea was first put-forth in [START_REF] Messai | Using domain knowledge to guide lattice-based complex data exploration[END_REF], where they allow the expert to move from one concept lattice to another concept lattice based on the granularity level w.r.t. a taxonomy and a similarity threshold. The concepts in the concept lattice with higher threshold contains more detailed information as compared to the concept lattice built using lesser threshold. One drawback of such kind of zooming operation is that it requires the computation of several concept lattices. In case of RV-Xplorer, we are dealing with simple concept lattice instead of the one created after using hierarchies meaning that all such kind of information needs to be scaled to obtain a binary context. As we are dealing with concept lattices built from binary contexts, we bend this functionality to suit the needs. It does not require computation of many concept lattices as well as no re-computation is required.

Hiding Non-Interesting Parts of the View

One of the most interesting characteristic of RV-Xplorer is that it allows the expert to hide the non-interesting part of the lattice. Let us consider that expert selects a concept c and it contains an attribute which is not interesting for her. She can at any point right click on the concept and select hide sub-lattice. One of the most interesting characteristic of a concept lattice is that if one concept contains some attribute in an intent then all the sub-concepts inherit this attribute. This way if the expert considers one concept as un-interesting then the whole sub-lattice will be considered as uninteresting and hence will be hidden from the expert while navigation. Such kind of functionality enables expert to reduce her navigational space and at the end the concept lattice contains only those concepts which are interesting for the expert.

Similar functionality was first introduced in CreChainDo system [START_REF] Nauer | Dynamical modification of context for an iterative and interactive information retrieval process on the web[END_REF]. Similar to CREDO [START_REF] Carpineto | Exploiting the potential of concept lattices for information retrieval with CREDO[END_REF], CreChainDo allows the expert to pose a query against the standard search engine which returns some results. These results are then organized in the form of a concept lattice and displayed to the expert in the form of folder-tree display. An added advantage of CreChainDo over CREDO is that the former allows expert interaction i.e., the expert can mark the concepts as relevant or irrelevant based on her priorities. After the expert has marked the concept irrelevant the sub-lattice linked to that concept is deleted. Meaning that, it reduces the context based on this feedback and the concept lattice is computed again using the reduced context. In case of RV-Xplorer, the concept lattice is built on top of RDF graphs. Moreover, we do not recompute the lattice or remove anything from the concept lattice. We only hide the non-interesting part of the lattice to reduce the navigation space of the expert. This way a reduction in the navigation space is performed without re-computing a concept lattice.

Related Tools

There have already been many efforts for providing expert the facilities to interact with the concept lattice applied to different domains. In [START_REF] Ferré | Reconciling faceted search and query languages for the semantic web[END_REF], the authors discuss a query-based faceted search for Semantic Web, as a contrast we are mostly dealing with navigational capabilities that can be provided by utilizing the powerful structure introduced by Hasse Diagram. [START_REF] Eklund | Concept lattices for information visualization: Can novices read line-diagrams?[END_REF] proposes another interesting way of navigating the concept lattice which allows the novice user to navigate through the concept lattice without having to know the structure of the concept lattice. Same is the case with SPARKLIS [START_REF] Ferré | Expressive and scalable query-based faceted search over SPARQL endpoints[END_REF], where user can perform selections and the tool acts as a query builder. As a contrast, RV-Xplorer provides exploration/navigational capabilities over SPARQL query answers with the help of view i.e., a concept lattice for data analysis and information retrieval purposes. Conexp5 is another tool for visualizing small lattices. As a contrast, RV-Xplorer allows area expansion and also provides guided navigation. [START_REF] Alam | Defining views with formal concept analysis for understanding SPARQL query results[END_REF] discusses that the views generated are easily navigable by machine as well as human agents. Machine agents may access the datasets through SPARQL queries for application development purposes through generic SPARQL queries generating huge number of answers and consequently large number of concepts are provided by View By clause. However, when human agents want to access the information through SPARQL query they run specialized queries which do not generate huge number of answers. In the current study we are focusing on manageable number of answers to be visualized by human agents using our visualization software.

An added advantage over these approaches is that RV-Xplorer provides guidance to the expert at each step for making the decision about concept selection. This guidance is provided by showing the user at each step, the contents of the intent of next level, by showing the distribution of the extent with the help of summarization index and finally with the help of global view many other ways of guidance are provided.

Discussion

In this study we introduce a new navigational tool for concept lattices called as RV-Xplorer which provides exploration over SPARQL query answers. With the help of guided navigation implemented in RV-Xplorer we were able to answer all the questions posed initially in the scenario. However, this tool is not designed for only specific purpose any kind of concept lattice can be visualized and data from any domain can be analyzed using this tool. The RV-Xplorer tool is still in development and other functionalities should be added such as incremental visualization (w.r.t. a set of given objects and attributes), iceberg visualization (given a set of attributes and objects, and a frequency threshold), integration of quality measures, visualization of implications and Duquenne-Guigues basis... We believe that visualization tools, as many other researchers do (see the tools discussed in [START_REF] Codocedo | Formal concept analysis and information retrieval -A survey[END_REF]) are of main importance, not only for FCA but for data mining in general. Accordingly, a new generation of visualization tools should be studied and designed, and RV-Xplorer is an example of this new tools and what can be imagined for supporting the analyst in the mining activity. We also want to perform human evaluation of the tool as discussed in [START_REF] Eklund | Concept lattices for information visualization: Can novices read line-diagrams?[END_REF] and [START_REF] Ferré | Reconciling faceted search and query languages for the semantic web[END_REF].

Fig. 1 :

 1 Fig. 1: Figure above shows the basic interface of RV-Xplorer displaying the top concept. The Figure below shows the local view of K#52, the concept containing all the papers authored by Amedeo Napoli.

Fig. 2 :

 2 Fig. 2: Left Figure shows the Attribute Concept of FCA and Right Figure shows the Object Concept of Computing Similarity Dependencies with Pattern Structures.

http://www.w3.org/TR/rdf-sparql-query/

http://www.w3.org/TR/rdf-sparql-query/

http://rv-xplorer.loria.fr/#/graph/orpailleur_paper/1/

http://conexp.sourceforge.net/