O Bedel

-S Ferré

- O Ridoux

-E Quesseveur

GEOLIS : A Logical Information System for Geographical Data

Keywords: Logical Information Systems, geographical data, navigation, querying. MOTS-CLÉS : Systèmes d'information logiques, données géographiques, requêtes, navigation

Today, the thematic layer is still the prevailling structure in geomatics for handling geographical information. However, the layer model is rigid: it implies partitionning geographical data in predefined categories and using the same description schema for all elements of a layer. Recently, Logical Information Systems (LIS) introduced a new paradigm for information management and retrieval. Using LIS, we propose a more flexible organisation of vectorial geographical data at a thiner level since it is centered on the geographical feature. LIS do not rely on a hierarchical organisation of information, and enable to tightly combine querying and navigation. In this article, we present the use of LIS to handle geographical data. In particular, we detail a data model for geographical features and the corresponding querying and navigation model. These models have been implemented in the GEOLIS prototype, which has been used to lead experiments on real data.

RÉSUMÉ. La structuration de l'information géographique en couche thématique est actuellement le modèle d'organisation le plus usité en géomatique. Cependant, ce modèle peut paraître rigide : il impose une partition des données géographiques et un schéma de description fixe par couche. Depuis peu, les Systèmes d'Information Logiques (SIL) offent un nouveau paradigme pour l'organisation et la recherche d'information. Avec les SIL, nous proposons un modèle d'organisation des données géographiques vectorielles plus flexible, centré sur l'entité géographique. Les SIL n'imposent aucune structuration hiérarchique de l'information et permettent de combiner étroitement interrogation et navigation. Dans cet article, nous présentons nos travaux sur l'utilisation des SIL en géographie. Nous détaillons un modèle de données, d'interrogation et de navigation, et nous illustrons son application sur un jeu de données réelles.

Introduction

Currently, layer organisation is the prevailling model for handling information in Geographical Information Systems (GIS). This structure gathers geographical data under a common theme e.g., soils, roads, water [START_REF] Laurini | Fundamentals of Spatial Information Systems[END_REF], and has become a standard for handling data. It enables to link a cartographic representation to a particular theme and to produce new information from layers processing, e.g. map algebra [START_REF] Bruns | User Interfaces for map Algebra[END_REF]. However, this structure is rigid as it implies partitioning geographical information in predefined categories, and usually having the same description schema for all the elements of a layer. As a consequence, data belonging to several themes are often duplicated in corresponding layers. Furthermore, the layer model is not really designed to manage relations between objects. If current GIS tools enable to query and to work on data distributed in several layers, pre-processing or repeated operations are often necessary.

On the opposite, the Logical Information System (LIS) model was proposed to avoid the rigidity of hierarchical data systems, and to merge querying facilities (as in databases) and navigation facilities (as in hierarchical filesystems). Logical Information Systems (LIS) offer a new paradigm for information management and retrieval. This paradigm is characterized by the following principles [START_REF] Ferré | An Introduction to Logical Information Systems[END_REF]:

information is centered on the objects of interest, i.e., on the entities one wishes to classify and retrieve (e.g., files, bibliographical references, geographical features), -querying and navigation are tightly combined, so that users can freely mix them in a same search, -the navigation structure is automatically derived and continuously updated w.r.t. data, -logic is used in all aspects of object description, querying, and navigation, which provides a uniform and expressive language, as well as automated reasoning capabilities.

In this article, we explore how GIS applications can gain in flexibility by using LIS for handling geographical data. We propose an organisation centered on the geographical feature that avoids the rigidity of the layer model. A prototype combining a navigation interface with data stored in a LIS, has been implemented. This prototype, named GEOLIS, is used to illustrate concepts presented in this article. More precisely, we detail how the LIS notions of logics, object-centered information, querying, and navigation are instantiated for the purpose of GIS. In the next section, we introduce the data model used in GEOLIS. Section 3 is devoted to the navigation model. In Section 4, we describe the implementation of the prototype. And in the last two sections, we present results of experiments led on a real data set concerning the distribution of rodents in Sahelo-Sudanian Africa, and we compare our approach to existing works concerning information retrieval and logic applied to geographical data.

Data model

In GEOLIS data model, a geographical feature is represented by an object, and logics are used to describe and query objects. First of all, we introduce a formal definition of what we call a logic, and we show how logics are used to define the description language. Then, we introduce the notion of logical context and we illustrate it with the real dataset that we used in our experiments. Last, we detail the querying of the data model.

Logic and description language

A logic is a formal encapsulation of representation and reasoning. It is mainly composed of a language, whose elements are called formulas; and of a deduction relation, called subsumption, that tells us when a formula is more specific than another formula. Additional operations, such as conjunction, can be used.

Definition 1 (logic)

We define a logic as a partially ordered set L = (L, , ), where L is a set of logical formulas, and is a subsumption relation between formulas, i.e., a partial ordering, and is a conjunction operation.

In GEOLIS data model, each object represents a geographical feature and is described by a logical formula. This formula is a conjunction of logical properties derived from the semantic attributes and the spatial description of the feature (geometry and location). These properties are given a name and may be atomic or valued. They are the main elements of the description language (see Table 1).

Grammar of the description language description

→ description ¢¡ ¤£ description | descrProp descrProp → name ¥ | name ¥ value Grammar of the querying language query → ¦ query § | ¡ © query | query query | query ¡ ¤£ query | ¢ ¤ | queryProp queryProp → name ¥ | name ¥ formula formula → value | pattern
Table 1. Grammars of GEOLIS description and querying languages.

Example: Here is an example of two formulas corresponding to a possible description of the French cities Rennes and Strasbourg in the GEOLIS data model:

-¢¡ ¤£ ¦¥ ¥ § ¥ ¨ © ¢¥ ¢¡ ¤£ ¦ ¡ ¤£ ¦ ¤ © ¦! ¡ " " ¥ $# "% ©& '% ©% ©% ¡ ¤£ ¦ " ¥ ¢¦ $( ) ¦0 21 "& ©3 54 61 ©( 87 $& '9 ©1 "3 @& BA ( 54 63 C0 ¤ § ¢¡ ¤£ ED ¡ " ¡ F G BH ¢ ID ¥ G ¥ QP ¡ ¢R IS ©S ¡ ¤£ D ¥ "T G ¢ ¤ " ¥ § ¡ D £ I G ¡ " IH ¥ UT B¥ ¨ ¥ G V BW BX ¢¥ Y G ¥ I CT ¤X G ¥ "` " Va G ¢ © ¡ ¨ b -¢¡ ¤£ ¦¥ ¥ § R G ¡ ¤c I G ` ¢¡ ¤£ ¦ ¢¡ ¢£ ¦ ¨ " ¦! ¡ " B ¥ $# "& ©( d3 BA e0 ¢¡ ¢£ ¦ " ¥ ¢¦ f0 5% "A 3 g3 ©3 # h4 6) BA 57 $& @1 "A # i% # BA 24 6& "( § ¢¡ ¢£ pD ¡ " ¡ ©F G BH ID ¥ G ¥ QP ¡ ¢R IS ©S ¢¡ ¤£ D ¥ "T G ¢ ¤ " ¥ § ¡ D £ I G ¡ " IH ¥ UT B¥ ¨ ¥ G V BW BX ¢¥ Y G ¥ I CT ¤X G ¥ "` " ! B¡ T B¥
In these descriptions, formulas are composed of logical properties combined with the conjunction operator q er es . More in details, t vu xw "y is an atomic property about the geometric shape of the feature, t vu t e x ¦ ¦ 8w u ¢y is an integer valued property, y © h and e 8w "t e 8w u y are string valued properties and t vu v w © 8w u ¢y is a coordinate valued property expressed in the coordinate system "Lambert 93". Metadata about features such as data source or production date can also be expressed as properties, e.g. ¦ t e u ¢ 8w © ¢ ¤ "r ¢ e . As seen in the example, there are several domains of values depending on the type of properties. They can be simple (string, integer, float) or composite (coordinates), and have their own semantic and syntax. In LIS, each domain is defined as a specialized logic having its own language of formulas. This enables to use specific patterns in formulas, e.g. t vu ¢t e v C ¢ 8w u y ed ¢f hg "h eh ih eh eh which is more general than t u ¢t e x ¦ ¦ 8w u ¢y kj Ch el ih eh eh .

The subsumption relation provides generalisation ordering between formulas: for instance,

- ¦ ¨ © ¦! ¡ " " ¥ $# "% ©& '% ©% ©% ¢ ¨ © ¦! ¡ B " ¥ $# "% ©& '% ©% ©% , - ¦ ¨ © ¦! ¡ " " ¥ $# "& ©( '3 "A e0 ¢ ¨ © ¦! ¡ B " ¥ $m "n # "% ©% '% ©% ©% , - ¦ ¨ © ¦! ¡ " " ¥ $m "n # "% ©% '% ©% ©% ¦ ¤ © ¦! ¡ " " ¥ $m "n C0 ¤% ©% '% ©% ©% ¦ ¨ " ¦! ¡ " B ¥ , - ¦ ¨ © ¦! ¡ " " ¥ $# "% ©& '% ©% ©% ¢¡ ¤£ T ¨ G b ¥ § Y G ¡ I CT B¥ T ¤ G b ¥ § Y G ¡ I CT B¥ .
Left formulas are as precise or more precise than right ones and may describe fewer objects.

In fact reasoning on descriptions combines at the same time reasoning on the conjunction of logical properties and reasoning on the values of logical properties. More examples will be given in Section 2.3.

Logical context and dataset for experimentation

Once we have the logics to describe geographical objects, we need a structure to link each object to its description. This structure is called a logical context. A logical context is the encapsulation of a logic (which may be different from a context to another), and a set of objects accompanied with their logical description. This definition is from Logical Concept Analysis (LCA) on which LIS is based [START_REF] Ferré | An Introduction to Logical Information Systems[END_REF]. A context is not static, but evolves through the addition, update, and removal of objects.

Definition 2 (context) A logical context (or simply a context) is a triple (O, L, d),
where O is a finite set of objects, L is a logic, and d is a mapping from objects to logical formulas, i.e., denotes the logical description of objects.

To illustrate the GEOLIS data model, we now indroduce the data set we used to make our experiments. It deals with the distribution of several species of rodents in Sahelo-Sudanian Africa. It is composed of one table where rows identify rodents and columns give descriptive information about these animals. This base, quite large (more than 20 000 individuals, potentialy described by 92 attributes), comes from the merging of several databases, the oldest data of which date back to 1903. Since 1980 the base is maintened by the French Institute for Research and Developpement (IRD) (L. Granjon, 2007). As rodent data come from local observations, this base is an imperfect sampling of the whole Sahelo-Sudanian stripe. It has been mainly designed to study the actual distribution of rodents, and to determine possible causes affecting this distribution.

In the rodents context, each object corresponds to a trapped rodent which is described by a conjunction of logical properties. These properties, expressed in French, inform about biometry (size aka v t x h ¢ ¢¡ , weight aka £ u xw x , sexe, age), phylogeny (family aka ¤ © gw e ¦ , genus aka ¥ ¢y , species aka 8 ©t v ¢ ), localisa- tion (habitat, position where the animal was captured), and period of capture (aka y ey v e e t ¦ e ). The semantic diversity, the various domains of values available (string, integer, float, coordinates) and the simple geometry (point) of the features make this context an interesting candidate for first experiments of the GEOLIS data model. Table 2 shows a toy context representing a small part of the original rodent context.

Logic and querying language

Given a context, an important task is to compute the answers to a query. The answers are defined as the objects of the context whose description is subsumed by this query. The set of all answers to the query is called the extent of the query, which comes from LCA terminology.

Definition 3 (extent) Let K = (O, L, d) be some context, and q ∈ L be a logical formula representing a query. The extent of q in K, denoting the answers of the query q in the context K, is defined by

ext(q) = {o ∈ O | d(o) q}.
In order to avoid false negatives (missed answers), and false positives (wrong answers), it is important to ensure that the subsumption relation is consistent and complete w.r.t. the semantics of formulas. For instance, 3 0..5 is correct, but 7 0..5 is incorrect because 7 does not belong to the interval 0..5. GEOLIS querying language extends the description language (see Table 1). It allows the use of disjunction and negation operators (resp. and r ¢ ), parentheses in formulas, patterns from specialized logics allowing for building formulas subsuming a group of values, and the keyword q corresponding to the most general query, i.e. the query subsuming all object descriptions. Specialized logics improve querying capabilities of GEOLIS. For instance a string logic enables to build patterns like ¢u ¢y vw By h "! v C © gw "y hw ¦ C ¦ 8w " ¢y ¢ $# which will cover the two cities of our previous example. In the toy context, an interval logic on the property ¢y ey v e e t e C e enables to define periods with patterns like w "y g ¡% % % '& £& j Ch Ch eh . In the same way, if attached to the weight property, it pro- vides comparison operators like in the formula £ u xw © x ' d ¢f 5g "h Ch '& kh . The empty pattern, like in query £ u xw x @ is the most general pattern of a logic. For instance, we have

object description o d(o) G 1 R ¥ ¡ ©¥ ¥ § Y ¡ ¤£ ©¥ ¥ § £¢ H ¢¡ ¤£ ¥¤ ¢ © ID ¥ 6( "1 54 6% ¢¡ ¤£ ¡ ¨ © ¢¥ ©¥ F ©T B¡ G ¥ ¥ $# "% ©% ©% ¢¡ ¤£ Y ¡ ¤£ B! ©! ¥ ¥ § §¦ G ¢ ID ¡ ©¥ ¢¡ ¤£ ©¨¥ I G ¥ ¥ § ¡ " ¥ G ¡ ¡ ¤£ ¦ " ¥ ¢¦ ¨1 54 6% ) 87 f0 ¨# h4 $) "& § G 2 R ¥ ¡ ©¥ ¥ § ¦ © ¡ ¤£ ©¥ ¥ § ©D ¢¡ ¤£ ¥¤ ID ¥ 0 ¨) "% 54 6% ¢¡ ¤£ ¡ ¨ © ¢¥ ©¥ F ©T B¡ G ¥ ¥ $# "% ©% C0 ¢¡ ¤£ Y ¡ ¤£ B! ©! ¥ ¥ § §¦ G ¢ ID ¡ ©¥ ¢¡ ¤£ ©¨¥ I G ¥ ¥ § ©G ©H ¢ T B¡ I BX ¢¡ ¢£ ¦ " ¥ ¢¦ ¨1 54 $) h7 f0 ¨# h4 $) © § G 3 R ¥ ¡ ©¥ ¥ § Y ¡ ¤£ ©¥ ¥ § P ¤ D ¢¡ ¤£ ¥¤ ¢ © ID ¥ e0 fA 1 54 6% ¢¡ ¤£ ¡ I " ¢¥ ©¥ F T I¡ G ¥ ¥ e0 ¤3 ©3 ©3 ¢¡ ¤£ Y ¡ ¤£ B! ©! ¥ ¥ § R T ¤ G ¢ ID ¡ ©¥ ¡ ¤£ ©¨¥ ¨ G ¥ ¥ § ¥ G B ¡ ¤£ ¦ " ¥ ¢¦ ¨1 54 A 0 7 f0 ©0 4 63 ©& § G 4 R ¥ ¡ ©¥ ¥ § ¦ ¨ ¢¡ ¢£ ©¥ ¥ § P ¤ D ¡ ¤£ ¥¤ ¢ © ID ¥ 6( h4 6& ¢¡ ¤£ ¡ ¨ © ¢¥ ©¥ F ©T B¡ G ¥ ¥ $# "% ©% C0 ¢¡ ¤£ Y ¡ ¤£ B! ©! ¥ ¥ § §¦ G ¢ ID ¡ ©¥ ¢¡ ¤£ ©¨¥ I G ¥ ¥ § ¦ ¢¡ ¤£ ¢ B ¥ ¢¦ ¨1 54 e0 ¨# 87 f0 ¨# © § ¢¡ ¤£ X ¢¡ Ic ¡ " ¥ § ¡ G T B¥ ! ©! ¥ D ¥ X ¡ G ¢ T ¢ G 5 R ¥ ¡ ©¥ ¥ § Y ¡ ¤£ ©¥ ¥ § ©D ¢¡ ¤£ ¥¤ ID ¥ 0 ¤1 "A 24 6% ¢¡ ¤£ ¡ ¨ © ¢¥ ©¥ F ©T B¡ G ¥ ¥ e0 ¤3 ©3 ©1 ¢¡ ¤£ Y ¡ ¤£ B! ©! ¥ ¥ § §¦ G ¢ ID ¡ ©¥ ¢¡ ¤£ ©¨¥ I G ¥ ¥ § ©G ©H ¢ T B¡ I BX ¢¡ ¢£ ¦ " ¥ ¢¦ I# h4 63 57 f0 ¨) h4 6% C0 ¢ § ¢¡ ¤£ X ¡ Ic ¡ B ¥ § c G ¨ © B¥
£ u xw x @ Ig )( $0 '& kh £ u xw x @ ed ¢f hg "h eh 1& kh £ u xw v ' .
String logics and numeric logics enable to deal with semantic attributes. But semantic querying is a first step that has to be completed with spatial querying in order to retrieve the most information of geographical data. Spatial querying involves spatial logics. At the moment, GEOLIS supports a bounding box logic. In GIS, a bounding box corresponds to an axis-aligned rectangular envelope containing one or more features (see Figure 1). The most common way to define a bounding box is with the position of its lower left and upper right corner (resp. noted (x1,y1) and(x2,y2)). But as it is a rectangular area, it can also be considered as the product of two of its adjacent sides (resp. written (x1..x2) and (y1..y2)). So a bounding box logic can be formed as the product of two interval logics on x and y coordinate values (see Section 4 for a description of the technology used to design this logic). This logic can be used to test if a ponctual feature belongs to a rectangular region on a map. For instance, in the rodent context, the trapping position of r 5 is subsumed by the query t vu v ew © hw u y w By ¢¡ g §0 eh 1& h 1& £& Ig ¡0 Ch 1& h ¤£ Bg ¦¥ 1& kh 1& & ¨g "l '& kh ¨ § , which represents the stripe delimited by latitude 15˚N and 16˚N. As we will see in next section, this is very useful when using a graphical interface, as rectangular zoom operations can be translated into bounding boxes. In the future, we plan to develop other logics to handle basic shapes including lines, polygons or disks. ((x1..x2),(y1..y2)) represents the bounding box of all points of the region. It includes envelope ((x3..x4),(y3..y4)), which itself contains envelope (x3,y3) corresponding to the bouding box of only one point.

When combining formulas in a query, the operator NOT is useful to exclude unwanted values like in ¤ © gw e ¦ ! © ¦ 8w © C # q er es r ¢ ¥ y ! eq C e 8w ¦ ¢ y e 5w ¦ # . Naturally, the operator offers the disjunction of formulas like in the query q = q ! eq £# q i ! h By £# q er es £ u xw x @ d ¦f hg "h eh 1& kh ¨ § (See Table 3 for more ex- amples of queries with their extents).

Navigation model

GEOLIS navigation model aims at suggesting to the user navigation links that lead him from a current place to a target place containing objects of interest. It is derived from the LIS navigation model and relies on the notion of query increments which is just introduced in the following. As GEOLIS deals with geographical features, we want it to render on a map the results of querying and navigation. That is why GEOLIS has to integrate a graphical interface. This interface and the corresponding navigation q ext(q) e ¡ ! ¤ $# {r 1 , r 3 , r 5 } e ¡ f u ¢y e xw By 8 "! © $# q Cr es q ! q e £# {r 2 } ¢y ey v e e ¢ t e C e w By g §% % ¥ '& £& kj eh Ch ¥ q Cr es r ¢ ¢y ey v e e t ¦ e kj Ch eh 8g

{r 1 , r 3 , r 5 } ¤ © gw ¢ C ¦ ! © C e 8w e C # q Cr es r
¥ ¢y e ! eq e C 8w ¦ ¢ y e hw ¦ # {r 1 , r 4 } q ! eq e # q ! h By £# q er es £ u xw x @ d ¦f hg "h Ch

'& kh ¨ § {r 2 , r 3 , r 5 } ¤ © gw ¢ C ¦ ! © C e 8w e C # q Cr es ¢ w © ¢ u y vw By h "! et v ¦ x ¢ e C C # t vu v w © 8w u ¢y w "y ¢¡ 0 '& ( h 1& £& ¡ 0 1& l Ch ¨ § £ g Cg & ¤£ 1& £& Ig "j 1& ¥£ ¨ § § § {r 3 , r 4 }
Table 3. Examples of queries with their extents about the toy context of Table 2.

process are detailled in Section 3.2. Last, we discuss on the benefits of using GEOLIS for geographical information retrieval in comparison to traditionnal GIS.

LIS navigation model

The key contribution of LIS is to combine querying with a navigation that is automatically derived from the context. Querying is directly reaching a navigation place by giving a full query (possibly modified by hand from a previous query). As with file systems, we call working query the query that designates the current place. Navigating is following links from a working navigation place to other navigation places. Each link is represented by a query increment, i.e. a logical formula, and is automatically suggested by the system. These increments are defined as conjunctive refinements of the working query. If q t denotes the working query at time t, q t+1 = q t x t , where x t denotes a query increment of q t . LIS guaranty the relevance of the suggested query increments: when following a query increment, LIS ensure at the same time that the extent of the reached place has been reduced (w.r.t. the extent of the previous query), and that this extent is not empty. The need for this querying/navigation combination has already been recognized in other works (see Section 6). In LIS, every query reaches a navigation place that is characterized by a set of objects, the extent of the query. Reciprocally, every navigation place can be reached by one or several queries. For instance, the 2 queries (q 1 x 1 ) x 2 and (q 1 x 2 ) x 1 lead to the same navigation place, unlike in file systems (and other hierarchies), where 2 different paths lead to different directories.

Definition 4 (increments) Let K = (O, L, d) be a context, X ⊆ L be a finite subset of formulas, and wq ∈ L be a formula representing the working query, and denoting the working navigation place. The query increments from wq in K, denoting the way the query wq can be refined to reach relevant navigation places, are defined by

incrs(wq) = {x ∈ X | ∅ ⊂ ext(wq x) ⊂ ext(wq)}.
To each increment is associated a number, called support, that is equal to the cardinal of the extent ext(wq x), i.e. the number of objects that have this property. The subset X of formulas is the vocabulary used for increments. It is dependent on the chosen logic, and may be customized by users.

For instance, in the toy context, consider wq = £ u xw © x ' d ¢f 5g "h Ch 1& h . Avail- able query increments are all properties discriminating ext(wq) = {r 2 , r 3 , r 5 }.

They include £ u xw x @ Ig ¥ Ch , £ u xw x @ Ig )( $0 , £ u xw x @ Ig ¡0 ( , v ¢ w © ¢ ! ¢ u ¢ 8 C £# ,
q ! h "y £# , q ! eq e # but not q ! ¡ # because ext(wq q ! ¡ # ) = ∅.

If we choose to refine wq with the increment ¥ ¢y i ! q C C 8w C y hw C # , then wq = £ u xw x @ d ¦f hg "h eh 1& kh q er es ¥ e ¢y i ! eq C e 8w ¦ ¢y e 5w ¦ # and new query increments are generated. e ¡ ! © # , e ¡ i ! ¤ # , £ u xw x @ Ig ¥ Ch , £ u xw x @ Ig ¡0 ( are still available, but not £ u xw © x ' ¨g )( 0 . No increments concerning the age, nor the family of rodents are proposed because they do not discriminate ext(wq). Indeed, rodents of genus "Arvicanthis" always belong to family "Muridae", this entailment is due to the phylogeny classification. The fact that all considered Arvicanthis rodents are adult depends on the context. This is called contextual entailment and may change when the context is updated.

Navigation interface

GEOLIS interface, which is shown in Figure 2, is composed of three main parts: the navigation tree placed on the left, the map area filling the center and the right, and the working query box at the bottom.

-The working query box displays the current query in the navigation. It indicates the query subsuming objects rendered in the map. The query box is editable, so that it is possible to enter manually a new query or to modify the current one.

-The map area is a composed component. A main map including fixed background layers (administrative boundaries, hydrography, isohyetal lines and satellite image) indicates by red points the position of rodents satisfying the current query. A legend details symbology of the main map and enables to specify which layers are visible. A keymap locates the boundaries of the main map on the Sahelian band. Last, standard map tools are also available: pan, zoom in/out and to full extent. The map area component comes almost unchanged from an existing interface (Mapserver community, 2007). It has been enhanced with a logical zoom tool, which enables to select rodents directly on the map by drawing a rectangle, i.e. a bounding box, enclosing them. This functionnality will be detailled in Section 3.3.

-The navigation tree is a visual representation of the partially ordered set of query increments. Query increments are properties shared by at least one rodent of wq. Each node of the tree represents a query increment which can be used to change wq (see Figure 2). A node can be expanded (resp. collapsed) to show (resp. to hide) its children, which represent more specific increments. The root of the tree is q , i.e., the most general formula. Nodes under the root correspond to general properties of the taxonomy built over the dataset, e.g.

¢ w u " h ¦ C 8w whose children are q , £ u xw v '

Navigation process

During the navigation process, the interface is always maintained consistent. Each action on the working query box, the navigation tree, or the map area entails the update of all the components. This is illustrated by the transition from Figure 2 to Figure 3. In Figure 2, no navigation is engaged, all objects are rendered on the map, wq is equal to the top formula q $ , and all navigation increments are available in the navigation tree. Let us suppose we are interested in the distribution of two families of rodents ! © C e hw "y C £# and ! v v w B 8w © C # . By editing the working query box and using the operator, we can restrict navigation to families of interest. In the same way, we can limit investigation to rodents captured since 2000, using the pattern y ey v e e t ¦ e d ¢f j Ch Ch Ch . The selection of young rodents can be done by selecting the correponding increment q ! e $# in the navigation tree, or by manually updat- ing the working query. The result of these navigation and querying steps appear in Figure 3: the map has been redrawn showing fewer points gathered mostly near water ressources in southern Malia or in the north of Burkina Faso border. At the same time, the new current query has been set, and the navigation tree updated: counts have been updated, increments that are no more relevant to the current query (e.g. q ! q e £# , q ! h "y £# ) have disappeared, and the formula ¢y ey v e e ¢ t e C e i ed ¢f ej eh Ch Ch has been inserted in the tree. Since a formula with a new pattern has been used in the working query, it appears in the navigation tree and can then serve as a query increment for the rest of the navigation.

We want now to focus on the set of rodents in southern Malia. With the logical zoom tool, we can draw on the map a rectangular shape enclosing the desired region (see Figure 3). This graphical selection entails the update of the current query, and consequently of the navigation tree and the map. The rectangular shape is translated into a formula based on t vu w © hw u y property, which is automatically added to the cur- rent query:

wq= ¦ 6Y ¡ ¤£ B! ©! ¥ ¥ ¡ ¦ G ¢ ID ¡ ©¥ ¢ Y ¡ £ "! ©! ¥ ¥ ¡ R T ¤ G ¢ ID ¡ ©¥ £ § ¢¡ ¤£ ¡ I © ¢¥ "¥ F T B¡ G ¥ ¥ $m "n # "% ©% ©% ¢¡ ¤£
¥ ¥ ¡ ¢ H ¢¡ ¤£ ¦ " ¥ ¦ 0 ¤A 24 6% ) "& 54 ©4 6% 54 $) BA % h7 f0 ¤% 54 $% ) "1 ) h4 ©4 e0 ¤( 54 6( ©3 ©( § The navigation tree is reduced, and now shows only properties and increments concerning rodents of the selected area.Furthermore, as expected, rodents in the north of the Burkina Faso border have disappeared from the map.

Notice that the logical zoom tool also plays the role of the information tool of standard GIS, which is used to query for the description of objects pointed on the map. In fact, when enclosing one feature with a logical zoom, its complete description can be read in the navigation tree, i.e. all, and no more, of the logical properties that qualify this feature are visible in the tree. When enclosing several features, orange underlined labels in the tree correspond to properties shared by all the selected features, whereas blue labels indicates discrimant properties, proper to fewer individuals. The common description of all selected rodents, which is not computed by traditionnal information tools, is here automatically provided by the navigation tree.

Once a logical zoom has been performed, it appears in the tree as an increment under the property t vu v w © 8w u ¢y . Actually, a logical zoom is a graphical increment and relies on the same navigation mechanism than other query increments of the tree. The equivalent of the graphical selection can be obtained by entering the formula of the rectangle area in the working query box, or by simply selecting it in the navigation tree, if it has already been defined. However, directly acting with the map is faster, enables to visually take into account the position of other geographical features, and, most of all, is more intuitive to users.

As logical zoom formulas are explicitly written in the query, they can be combined like other formulas using logical operators q er es , and r ¢ . This way, complex areas can be defined from the combination of intersection, union and exclusion of rectangular regions. For instance, as shown in Figure 4, rodents trapped between the Niger River and the Black Volta river can be selected by combining enclosing and excluding logical zoom areas. After having drawn the 3 regions R1, R2 and R3 on the map, the desired area can be expressed by reorganizing the corresponding formulas in the working query : wq = (t u v w © 8w u y R1 t vu v ew © hw u y R2) q er Cs r ¢ t vu v w " hw u y R3 .

Discussion about GEOLIS navigation functionnalities

GEOLIS provides at the same time data navigation and querying functionnalites whereas traditionnal GIS, like databases, are rather designed for data querying. However, we can wonder how far it is possible to go with existing systems in order to provide similar navigation services. When working on data stored in an attribute table, several GIS, e.g. ArcGIS Desktop, SavGIS or GvSIG (ESRI, 2004;[START_REF] Iver | Conselleria Valenciana d'Infraestructures i Transport, GvSIG Official web site[END_REF], or Relationnal Database Management Systems (RDBMS), e.g. Microsoft Access [START_REF] Macdonald | Access 2007 for starters: The Missing Manual[END_REF], already assist the user in the building of queries. For instance, they list all the available fields and their corresponding values for filling the SELECT and WHERE clauses. But this information does not take into account the extent of the queries and so does not always provide relevant increments for this query. Enhancing this kind of interface to help refining the query is totally conceivable. In the absence of patterns in value domains, an approximation of LIS operation incrs(wq) would be in SQL language:

Foreach field prop of the table context

¦ $ C ¡ prop £ ¨ ¢u ¢ ey e ¡ § pq ¤ £ © context ¢ ¤£ e wq ¥ £ ¦¥ £ ¨ § ¤© prop £ q h "r ¥ ¦d Ch ¢y c wq
where c wq corresponds to ¦ $ C ¡ ¢u ¢ ey e § ¤ © wq and is computed once. This implies n + 1 SQL queries at each navigation steps, with n denoting the number of fields of the table. However, such mechanism is artificial because it cannot be easily applied by GIS or RDBMS end-users. Moreover it cannot suggest pattern increments during the navigation, whereas GEOLIS does.

As already seen in previous examples, new patterns used with valued properties are introduced gradually in the tree, and enable to define classes of values just by navigation, when desired. This may be useful to specify weight groups or trapping pe-riods. In the same way, each logical zoom introduces a new increment under property t u v w © 8w u y . For instance, by defining horizontal stripes, we can look if the lattitude impacts the presence of high sized rodents of ! ¥ ¦ ¢ w e 8 # genus. Classes of val- ues are not limited to numeric properties as it is the case in most desktop GIS. On the contrary, users can define patterns on string values, coordinates, and even dates. Moreover, thanks to the logics and the subsumption relation, classification is dynamic, i.e. when inserting new objects in the context, they automatically appear under suitable labels. This also allows for ranges of different sizes to be automatically ordered in the tree (e.g., for weight groups,

g & & Ig "h § g & £& ¥ eh ¨ § g & & ¨g "h Ch § ).
The insertion of classes of value can also be automated using a script that navigates in each class at the first launch of GEOLIS.

GEOLIS navigation tree offers a synthetic vision puting together query increments. Supports of query increments provide a first intuition on the corresponding answer. Under each property node (e.g. q ), the supports of child nodes (e.g. q # Cq e £# ) provide the histogram of the distribution of values (see Figure 2). Furthermore, this representation is automatically derived from the LIS data organisation.

Implementation

The GEOLIS prototype results from the coupling of several technologies from LISFS, web mapping and web domains. First, we introduce LISFS, the implementation of LIS used in GEOLIS, and a way to build specialized logics. Then, we detail the components of the graphical interface and their interaction with LISFS.

LISFS and specialized logics

LISFS is a generic implementation of LIS, and is at the same time a genuine Linux file system [START_REF] Padioleau | A Logic File System[END_REF]. In LISFS, files and file parts (lines) are objects, paths are queries, directories are navigation places, and subdirectories are the automatically computed query increments. Two kinds of plugins can be used in LISFS: logics and transducers. Logics define the kind of formulas that can be used in object description, and queries. Transducers allow to partially automate the description of objects, depending on the file format. For instance an MP3 transducer produces logical properties about the artist, title, etc., from the MP3 tags.

In LISFS, each property belongs to a logic that provides syntactic analysis for values and patterns comparison through deduction and pretty printing. However, designing a logic and ensuring its metalogic properties, i.e. the consistency and the completeness of its subsumption relation, requires logic expertise. This is why, in GEOLIS, we rely on LogFun, a toolbox of logic components which can be composed at a very high level [START_REF] Ferré | A Framework for Developing Embeddable Customized Logics[END_REF]. These components are called logic functors, and their composition results in a program defining a parser, a printer of formulas, and a subsumption tester. Futhermore, the consistency and the completeness of the subsumption relation are checked during the composition; this automatically guarantees the good behaviour of the composed logic. Examples of logic functors are By (integer values), ¤ v ¦u e ¦ (real values), ¦ e 8w "y (string values and patterns such as "contains", "begins with"), "y ¢ e § (intervals over values in ), £ e u C hg £ j ¨ § (product of 2 logics, so that formulas are couples of formulas). The bounding box logic, attached to the property t vu v w © 8w u ¢y , has been formed as the product of two in- terval logics on real values: £ C u C "y e ¦ C e ¤ Cu C ¢ § £ ¨ By ¢ e e ¤ ¦u e ¢ § § . In this case, the subsumption relation expresses inclusion of rectangular regions.

GEOLIS architecture

LISFS constitutes the kernel of GEOLIS, where the geographical data to be explored is stored, i.e. the rodent base in our experimentations. The GEOLIS graphical interface is a web interface. The navigation tree and the working query box have been designed using the server side language PHP. The map area is built with the widely used map generator UMN MapServer. Among the several geographical formats supported by MapServer, we chose to use the Geographical Markup Language (GML) proposed by the OpenGeospatial Consortium [START_REF] Cox | Geography Markup Language (GML) Encoding Specification[END_REF]. GML is an XML based format with public specifications. For our purpose, it has the advantages to gather all information in one file whose XML based structure may be rearranged w.r.t. to GML specifications. Furthermore, GML is supposed to become a standard for geographical data sharing.

We now detail the data flow of rodent information in GEOLIS (see Figure 5). Two phases can be distinguished: data integration in LISFS, which is made once, and data navigation, which occurs at each step of logical navigation. In the data integration phase, the original rodent base, in MS Access format, is first translated in GML format using standard GIS conversion tools. Then, the GML file is reindented so that each geographical feature holds in one line. In the transdution process, i.e. when the GML file is parsed to extract descriptions of rodents, this reorganised structure enables to attach a LISFS object to each feature, as in LISFS objects are files or lines of files.

Once the GML file is mounted on LISFS, the navigation phase can start. At each navigation step, logical subsumption is used to determine which lines correspond to rodents satisfying the working query. In fact, this set of lines constitute a view over the whole GML file. This view, combined with complementary layers (hydrography, administrative limits, isohyetal lines and satellite image), is used by MapServer for the map generation. MapServer produces the general map, the keymap and the legend as images. At the same time, new query increments are computed by LISFS and transmitted to the web interface. Then, GEOLIS web interface generates the navigation tree and integrates the maps and the legend.

The GEOLIS prototype combines LISFS and logic functors, geographical data format and cartographic tools. These technologies were not designed to work together. However, their combination in GEOLIS did not require any modification. Much of the work have been to interface them, i.e. to determine the geographical format the most appropriate to LISFS integration, writting the corresponding transducer, building logics devoted to geographical data using LogFun, and designing the navigation tree interface.

Experimentations

During the development of the prototype, in order to validate navigation functionnalities, tests were first led on a subset of 1 000 rodents. However, for the experimentation phase, the whole base (20 585 rodents with an average of 39 properties in each description) have been loaded in GEOLIS. Response times of navigation commands increased with the size of the context, but still allow human interaction (less than 10s on an experimentation machine, i.e. an Intel Pentium M 2Ghz with 1Go of RAM). That aspect mainly depends on LISFS, which is still under development and improvement.

First experiments in the rodent base highlighted several occurences of anomalous entries. These entries appear as properties with values out of the expected domain, e.g. e ! ( $% # instead of ! ¤ $# or ! © $# , uncertain values, e.g. e ¡ ! ¡ # or even C ¡ ! © ¢ # , or synonymous values, e.g. e ¡ ! # and e ¡ ! © # . These anomalies result from errors in data collecting and merging.

Initialy, spatial information in the rodent base was limited to the trapping position. So, to take into account the impact of other spatial factors on the distribution of rodents, some spatial relations, e.g. minimum distance from natural barriers (large rivers) or closest upper and lower isohyetal lines, have been processed for each rodent using external GIS tools. Then they have been translated into semantic properties. This enables to provide spatial increments in data search. Furthermore, as the main map gives a visual representation of the location and concentration of rodents it rapidly suggested relevant spatial query increments during navigation.

As mentioned previously, the rodent base comes from an imperfect sampling. This has been observed in the navigation. For instance, by just expanding the node t v ¡ x (aka country) in the navigation tree and observing the count of rodents associated with each value, we noticed that half of information in the base comes from Senegal which clearly appears on the map to represent a small part of the studied area.

Then, when expanding node ¢y ey v e e t e C e (trapping year), we could see jointly, in two branchs of the tree, the distribution of rodents by year or place of trapping. Refining the working query with query increments under property t v ¡ 8 showed in one navigation step the evolution of this distribution per year when restricted to a particular country. This way, we noticed that in Chad, recent data have only been collected in year 2000, whereas in Mali and Senegal, data are available at least every two years.

Having knowledge about data origin could enable to balance future results concerning rodents distribution. So we decided, as a first step, to study the sampling strategies in the database. For instance, we looked for connections between rodents trapped states (alive, dead), places and periods of capture. As explained previously, we can restrict navigation to rodents trapped alive, and visualize, at the same time, properties y ey v e e t ¦ e and v ¢ w © ¢ . Selecting a particular habitat, e.g. ¢ ¦ ¢y (savanna), and looking at property ¢y ey v e e ¢ t e C e show for each year, how many rodents were trapped alive in the savane. On the opposite, distribution of trapping places concerning a particular year could be observed by looking at v ¢ w © ¦ and se- lecting ¢y ey e ¢t e ¦ e . This shows that GEOLIS is appropriate to quickly check distribution hypotheses implying several criteria. In this sense, LIS play a similar role to OLAP processing (Chaudhuri et al., 1997, On-Line Analytical Process).

Related works

The need for combining navigation and querying in information retrieval has already been underlined in other works [START_REF] Godin | Experimental Comparison of Navigation in a Galois Lattice with Conventional Information Retrieval Methods[END_REF][START_REF] Chiaramella | Browsing and Querying: Two Complementary Approaches for Multimedia Information Retrieval[END_REF]. Advanced file systems coupling hierarchical navigation and boolean querying have also been proposed. For instance, Semantic File System (Gifford et al., 1991, SFS) enables, in addition to traditionnal directories organisation, to define virtual directories as queries built from intrinsic properties of files, e.g. file type or date of last modification. But in SFS, navigation cannot be used after a querying step. In Hierarchy and Content (Gopal et al., 1999, HAC), another attempt to mix navigation and querying at the file system level, each directory is expressed as a query that defines its content. However, the navigation is limited to the sub-directories that have been manually cre-ated in a directory/query. Futhermore, the user can freely move files into directories, even if they do not satisfy the corresponding query. So nothing guaranties that the navigation structure is kept consistent. On the contrary, LIS allow to freely alternate navigation and querying, and rely on a navigation structure automatically derived from the data, which therefore guaranties its consistency.

The use of logical formalisms in spatial representation has been widely explored in the last two decades. Especially, several approaches have been proposed to model topological relations [START_REF] Asher | Toward a Geometry for Common Sense: A Semantics and a Complete Axiomatization for Mereotopology[END_REF][START_REF] Cohn | Qualitative Spatial Representation and Reasoning Techniques[END_REF]. Modal logics have also been used to define spatial logics, including for instance the notion of proximity [START_REF] Lemon | Semantical Foundations of Spatial Logics[END_REF]. However these approaches are rather qualitative and often not directly useable with real world data. Description logics also allow to represent domain knowledge, and have led to some encouraging attempts to describe the geographical domain. For instance, they have inspired spatial representations used in the LOLA system, wich is devoted to the recognition and the classification of spatial structures from satellite images (Le [START_REF] Ber | Object-based Representation and Classification of Spatial Structures and Relations[END_REF]. The VISCO system [START_REF] Wessel | Visual Spatial Query Languages: A Semantics Using Description Logic[END_REF] can be more closely compared to GEOLIS as the main aim of the two systems is geographical information retrieval. In the VISCO system description logics are used to query a spatial database in a visual way. VISCO enables to represent and to reason on topoligical relations between geographical features. This lacks GEOLIS at the present time, since relations and especially spatial relations cannot be expressed in the current version of the system. VISCO integrates querying capabities, and can also assist the user with query completion. Completion represent a form of navigation, however in VISCO, the proposed completion comes from terminological default reasoning [START_REF] Wessel | Visual Spatial Query Languages: A Semantics Using Description Logic[END_REF], and may produce queries with an empty answer. Whereas in GEOLIS, query increments are always relevant w.r.t. the objects satisfying the current query.

GEOLIS, and more generally LIS, combine a quantitative approach as data are described by expressive logics on concrete domains, and a qualitative approach, derived from the former, through conceptual structures and logical reasoning. Furthermore, GEOLIS provides a geovisualization synchronized with a navigation accross the different dimensions (properties) of a geographical dataset and the possibility to rapidly group and visualize data values. These functionnalities, proper to SOLAP tools (Rivest et al., 2005, Spatial OLAP), offer an iterative and interactive exploration of a geographical dataset.

Conclusion and Prospects

GEOLIS is a framework where Logical Information System principles have been applied to geographical data. It is important to note that the proposed method for managing GIS data is compatible with existing data, and with existing cartographic interfaces. Thanks to the transducers it handles data as it is, and thanks to LISFS being a file system, it is easy to make a standard interface operate on a logical context. The interface needs only be extended to handle LISFS navigation and querying.

The GEOLIS experiments have been conducted with real data, accumulated over years by different teams that were completely unrelated with the GEOLIS group. So, the dataset was not formatted at all to fit the GEOLIS data model. But LISFS naturally offers functionnalities that facilitate the data analysis process: the transducers and the taxonomy made possible to quickly integrate data and organize properties and the navigation links having low support enabled to identify anomalous entries. A main contribution of GEOLIS is to facilitate the exploration of data, and to quickly check experts hypotheses.

In the future, we plan to work on spatial logics to improve expressiveness and querying capabilities of GEOLIS. Data representation should include derived geometrical properties, such as area and length. Navigation should integrate graphical query increments, and the possibility of automatic zooming on the region of interest. GEOLIS querying language is not yet as expressive as traditionnal GIS SQL-based languages (for instance, aggregates are not possible yet). However, we believe our logics of values and patterns for representing various kinds of properties (e.g., coordinates or geometries) are more intuitive to users. This idea follows principles of naive geography, which aims at designing GIS "that follows human intuition" [START_REF] Egenhofer | Naive Geography[END_REF]. Furthermore, LISFS is in permament evolution. In particular, relations [START_REF] Ferré | Arbitrary Relations in Formal Concept Analysis and Logical Information Systems[END_REF] will be soon implemented, including spatial relations in the future. This will enable to express spatial relations between features, such as distances, topological relations and to look for spatial organisation patterns. LISFS should also integrate data-mining operations for finding association rules. This will offer these data-mining operations to the GIS domain almost immediately, and will make emergent relationships between properties visible. In the rodent experiments, these improvements would enable, for instance, to look for spatial barriers in the distribution of rodents.

ANNEXE POUR LE SERVICE FABRICATION

  Figure 1. Envelope((x1..x2),(y1..y2)) represents the bounding box of all points of the region. It includes envelope((x3..x4),(y3..y4)), which itself contains envelope (x3,y3) corresponding to the bouding box of only one point.

  or C ¡ . Then nodes represent pattern properties, e.g. £ u xw © x ' ¡ ¢f 5g "h Ch . Finally, value properties are the leaves of the tree, e.g. £ u xw © x ' £¢ Ch . Each node of the tree is ren- dered with an icon, a label, and two numbers. The label is the formula representing the increment. The style of the label is also informative. Underlined orange labels correspond to formulas shared by all the rodents of wq, whereas blue labels indicate properties that discriminate them. The two numbers indicate a proportion: the count of rodents in wq that the increment leads to, i.e. the support, out of the count total of rodents sharing the formula. Two actions are possible in the tree: (1) collapsing or expanding a node by acting on the icon, (2) updating wq by selecting a label, as detailled in Section 3.3.

Figure 2 .

 2 Figure 2. The GEOLIS interface.

Figure 3 .

 3 Figure 3. Interaction between components. The white rectangle represents the area just selected by the logical zoom tool.

Figure 4 .

 4 Figure 4. Combining logical zoom rectangular areas (dashed outline) to define a complex query area (plain outline).

Figure 5 .

 5 Figure 5. Data flow of rodent information in GEOLIS. Dashed boxes correspond to functionalities specially designed for GEOLIS purpose.

Table 2

 2

. A toy context. Descriptions are incomplete as they only include a part of the available properties. The age of rodents is declined in 3 classes: "Juv" for juveniles, "Ad" for adults, and "Ind" for unknown. Their position is expressed as (longitude, latitude) in decimal degrees.

  A FOURNIR PAR LES AUTEURS AVEC UN EXEMPLAIRE PAPIER DE LEUR ARTICLE ET LE COPYRIGHT SIGNE PAR COURRIER LE FICHIER PDF CORRESPONDANT SERA ENVOYE PAR E-MAIL 1. ARTICLE POUR LA REVUE : Revue internationale de Géomatique. Volume X -n˚x/200X 2. AUTEURS : O. Bedel * 1 -S. Ferré * -O. Ridoux * -E. Quesseveur ** 3. TITRE DE L'ARTICLE : GEOLIS : A Logical Information System for Geographical Data 4. TITRE ABRÉGÉ POUR LE HAUT DE PAGE MOINS DE 40 SIGNES : Retourner le formulaire de copyright signé par les auteurs, téléchargé sur : e Ct ¡ ¢ ¤£ ¥£ ¥£ & $ ¦ ¦ ¢u y v vw By 1& u "

	GEOLIS
	5. DATE DE CETTE VERSION :
	June 23, 2007
	6. COORDONNÉES DES AUTEURS :
	-adresse postale :
	* Univ. Rennes 1/IRISA, Equipe LIS	** RESO, UMR CNRS ESO 6590
	Campus de Beaulieu	Univ. Rennes 2, Campus Villejean
	35042 Rennes Cedex FRANCE	35 043 Rennes Cedex FRANCE
	{prénom.nom}@irisa.fr	{prénom.nom}@uhb.fr
	-téléphone : 02 99 84 73 29
	-télécopie : 02 99 84 71 71
	-e-mail : olivier.bedel@irisa.fr
	7. LOGICIEL UTILISÉ POUR LA PRÉPARATION DE CET ARTICLE :
	L A T E X, avec le fichier de style ¢ e hw C ¢ C	¡	¦ 8 v & f ¦ ,
	version 1.23 du 17/11/2005.
	8. FORMULAIRE DE COPYRIGHT :

SERVICE ÉDITORIAL -HERMES-LAVOISIER

14 rue de Provigny, F-94236 Cachan cedex Tél. : 01-47-40-67-67 E-mail : revues@lavoisier.fr Serveur web : http://www.revuesonline.com

Revue internationale de Géomatique. Volume X -n˚x/200X

Revue internationale de Géomatique. Volume X -n˚x/200X

Acknowledgements

The authors would like to thank M.Laurent Granjon and M. Jean Marc Duplantier from IRD (CBGP UR 22 Montpellier) for their active contribution in the building of the rodent database.

1. Olivier Bedel benefits from a doctoral grant from Region Bretagne.


Sébastien Ferré
email: ferre@irisa.fr

Camelis: Organizing and Browsing a Personal Photo Collection with a Logical Information System

Since the arrival of digital cameras, many people are faced to the challenge of organizing and retrieving the overwhelming flow of photos their life produces. Most people put no metadata on their photos, and we believe this is because existing tools make a very limited use of them. We present a tool, Camelis, that offers users with an organization of photos that is dynamically computed from the metadata, making worthwhile the effort to produce it. Camelis is designed along the lines of Logical Information Systems (LIS), which are founded on logical concept analysis. Hence, (1) an expressive language can be used to describe photos and query the collection, (2) manual and automatic metadata can be smoothly integrated, and (3) expressive querying and flexible navigation can be mixed in a same search and in any order. This presentation is illustrated by experiences on a real collection of more than 5000 photos.

Introduction

Formal Concept Analysis (FCA) has been recognized as a good paradigm for information retrieval [START_REF] Godin | Experimental comparison of navigation in a Galois lattice with conventional information retrieval methods[END_REF][START_REF] Martinez | Browsing image databases with Galois' lattices[END_REF] because it makes it possible to tightly combine querying and navigation in a same search. Querying alone is not satisfying because it requires from users to know the query language, and to have a precise idea of what they search for. Navigation, by leading users to the result step by step, is more interactive, but the navigation structure is most often very rigid so that only one or a few paths exist to each object (e.g., file hierarchy, hyperlink graph). In FCA, the concept lattice plays the role of the navigation structure. Each concept combines a query as a set of attributes (the intent), and a navigation place as a set of objects (the extent). Attributes can be added to the query in any order, so that a concept can be reached through several paths.

Logical Information Systems (LIS) [START_REF] Ferré | An introduction to logical information systems[END_REF] have been introduced (1) to combine querying and navigation, (2) to be reasonably efficient on large collections of objects, (3) to make use of an expressive language for object descriptions and queries, and (4) to be generic w.r.t. the kind of objects and the language. Because of (3) it becomes necessary to do complex reasoning to see whether an object description match a query (e.g., the object description is a string, and the query is a regular expression). Logics are the right things to encapsulate representation and reasoning facilities. So we defined a generalization of FCA, Logical Concept Analysis (LCA) [START_REF] Ferré | A logical generalization of formal concept analysis[END_REF], where logical formulas can be used instead of sets of attributes. This makes FCA an instance of LCA, where object descriptions and queries are sets of attributes.

Camelis1 is a complete implementation of a logical information system. It is generic in that a logic module can be plugged in so as to cover different application needs. It uses specific data structures and algorithms so that it is efficient up to 10,000 objects. It has a graphical interface that displays at all time the query that led to the current concept, its extent, and properties to be added or removed from the current query in order to reach neighbour concepts. Both browsing and defining the context are possible through this interface.

Among the various existing applications of Camelis, the most convincing is the management of a photo collection. Indeed, photos can be described along many facets like date, location, event, visible persons, visible objects, etc. A file hierarchy enforces a strict order between these facets, making some search hardly possible. Tag-based systems like Flickr are limited because a photo tagged with 'Sydney' as location will not be answer to a query containing 'Australia'; and a photo tagged with 'formal concept analysis' will not be answer to '...concept analysis'. These limitations are easily solved by dedicated logics: here, a taxonomy of locations, and a logic of string patterns. In this paper, we illustrate the capabilities of Camelis and LIS on a real context, the personal photo collection of the author. It contains more than 5,000 photos, and has been incrementally defined since 2003, along the arrival of new photos.

Section 2 assumes an existing context, and presents all the facilities provided by Camelis to browse and retrieve photos, from querying by formulas and querying by objects, to different kinds of navigation: i.e., downward and upward, backward and forward, and sideward. Section 3 illustrates the incremental definition of the context with the arrival of a new pack of photos. Section 4 compares Camelis with related tools.

Retrieving Photos

In this section, we assume the existence of a logical context representing a collection of photos and their metadata. The process of building such a context is developed in Section 3. We recall the basics of Logical Concept Analysis (LCA) [START_REF] Ferré | A logical generalization of formal concept analysis[END_REF][START_REF] Ferré | An introduction to logical information systems[END_REF], whose principles are the same as in FCA, except that logical properties partially ordered by a subsumption relation are manipulated instead of unrelated attributes.

Definition 1 (logical context). Let L = (L, ⊑) be a logic, i.e. a set of properties L partially ordered by a subsumption relation ⊑. A logical context is a triple K = (O, L, D), where O is a set of object identifiers, and D is a mapping from objects to their description as a set of logical properties.

In our application, object identifiers are file paths or URLs to photos, and their logical description is a set of properties such as location, date, event, etc. These properties are either taxonomic terms or valued attributes over various concrete domains such as date intervals or string patterns. The subsumption ordering is fixed for concrete domains, and designed by hand for taxonomies.

-location: Montpellier ⊑ France ⊑ 'European Union' -date: date = 24 oct 2007 ⊑ date in sep 2007 .. jun 2008 -event: event is "conference CLA" ⊑ event contains "conference" An object can be in the extent of a property without having it explicitely in its description, through subsumption.

Definition 2 (extent). Let K = (O, L, D) be a logical context, and p ∈ L a property. The extent of property p is defined by the set of objects whose description entails p:

extent(p) = {o ∈ O | ∃d ∈ D(o) : d ⊑ p}.
Hence, object descriptions can be kept small and precise at the same time. For instance, an object described with some date d will be in the extent of any date interval containing d. Here lies the main benefit of logics w.r.t. attributes. A similar benefit can be obtained with conceptual scaling [START_REF] Ganter | Formal Concept Analysis -Mathematical Foundations[END_REF], but only for finite domains (e.g., locations), and with redundancy in the scaled context [START_REF] Cellier | An algorithm to find frequent concepts of a formal context with taxonomy[END_REF].

Logical properties can be combined by boolean operators and , or , not so as to form more complex queries. Their extent is defined inductively as follows for every queries q1, q2: extent(q1 and q2) = extent(q1) ∩ extent(q2) extent(q1 or q2) = extent(q1) ∪ extent(q2) extent(not q1)

= O \ extent(q1)
This definition makes every pair (q, extent(q)) an inf-semiconcept of a logical context whose logic is extended with boolean operators. These semi-concepts play the role of both query and navigation place in the following, founding the combination of querying and navigation presented in the introduction.

In the next sections we present the many different ways information can be retrieved in Camelis. This is illustrated on a logical context made of 5,480 photos described by an average of 10 properties each, taken among a set of 28,143. This later figure is not the number of available properties, which is infinite, but the number of properties used so far.

The Graphical Interface

The graphical interface of Camelis can be seen in Figure 1. At every time, the current query and its extent are displayed respectively as a text field at the top and as a thumbnail list at the right. The query is editable, and the extent can be scrolled page by page (the page size can be customized). At the left is displayed a set of property trees, where the hierarchical relations match the subsumption relations between logical properties. As a logic can be any partial ordering, not necessarily a tree, the same property can appear several times. This is not a problem as tree nodes are expanded on demand.

These trees provide a feedback about the current extent, and a support for navigation. Each visible property has a count (numbers at the left), and a color that depends on the context and the current query. Let K be a logical context, q be the current query, and p be a property. The count of p is the number of objects in the current extent that have p as a property:

count(p) = |extent(q) ∩ extent(p)|.
A property is not shown if its count is 0, because it tells nothing about the current extent. In order to get fewer properties in the property trees it is possible to set a minimum count on each property to control the way it is expanded. A property is red-or orange-colored if it is shared by all objects in the extent, i.e. if its count is equal to the size of the extent. This means the set of orange/red properties is the intent associated to the current extent, and red properties are those properties also occuring in the query. Because the count of properties depends on the current extent, property trees need to be recomputed each time the query changes. This makes the navigation trees very dynamic and informative. Specific data structures are used to make their computation efficient, i.e. linear in the size of the context (see [START_REF] Ferré | An introduction to logical information systems[END_REF][START_REF] Padioleau | A parts-of-file file system[END_REF] for data structures and algorithms). The following sections show how these informations can be used to navigate among photos along various directions, and to get feedback about selected extents.

Navigating Downward in the Concept Lattice

Firstly, suppose I2 want to find some photos from a trip in Australia for ICFCA'04. I first expand the property Location, and find I have photos from Europe (4859), Africa (162), and Australia (148). After selecting the property Australia3 :

-the query becomes Australia, -the property Australia becomes red because it is now part of the query, and it is automatically expanded to show sub-locations of Australia, -the properties Europe and Africa are no more visible, because no more relevant (count = 0), -the extent displays the first page of the 148 selected photos.

The sub-location 'New South Wales' becomes orange, which means this is the only region of Australia where I have taken photos. More precisely I find that I have been mainly in Sydney (105), and in the Blue Mountains (18). Now I expand the property Type and see there are different types of photos: e.g., buildings (29), animals (34), plants (6). I get interested in Australian living things, so I select both Animal and Plant, which leads me to the refined query Australia and (Animal or Plant), whose extent contains 40 photos. One of these photos is a portrait, which I do not want, so I select the negation of Portrait with the help of a contextual menu. This leads me to the new query Australia and (Animal or Plant) and not Portrait (39 photos). By expanding more properties, I discover that these photos were taken in February and March 2004 in New South Wales, that 5 photos of 3 different species of marsupials are present: e.g., kangooroo, koala, wallabi.

These 3 navigation steps led to semi-concepts with more and more precise queries, and hence smaller and smaller extents. This is called downward navigation, and its principle is to combine with a and the current query and a refinement. A refinement can be a single property, a disjunction of properties, or the negation of a property. When a refinement uses only properties that are relevant and not colored, the new semi-concept is always strictly smaller but not empty. This is a big advantage compared to purely querying systems, where it is common to get empty results.

Figure 1 shows the interface obtained after the previous navigation operations. At this stage, I can either browse the 39 photos in Camelis, or launch a diaporama in an external application.

Navigating Backward and Forward in the Query History

Like in web browsers, it is possible to navigate backward and forward in the query history. This is mainly useful for opening parentheses on the path of a navigation. Imagine that, while browsing the extent at the end of previous section, I find a photo of a koala, and want to look at all other photos of koala. I first select the property 'koala', which leads me to a new semi-concept with 2 photos, and then I can move back to the previous semi-concept. When moving back, scrolling positions are remembered, so that I can go on easily in my browsing of Australian animals and plants.

Navigating Upward in the Concept Lattice

During downward navigation, I sometimes want to remove or generalize some properties in the query so as to get larger extents: this is upward navigation. For instance, I realise I have not enough photos of animals and plants. If I want to remove the last refinement, the back button is a simple way to achieve this. But if I want to remove the first refinement Australia, I would need to move 3 steps backward, and re-select the last 2 refinements. I could also edit the query by hand, but users usually prefer to navigate rather than editing queries.

Besides, orange and red properties are shared by all extent objects, and so cannot be used for downward navigation. This makes them available for upward navigation. When a red property is selected, it is removed from the query. For instance, if I select Australia, the new query is (Animal or Plant) and not Portrait (282 photos from many locations). When an orange property is selected, it replaces more specific properties in the query. For instance, if I select Pacific, the new query is (Animal or Plant) and not Portrait and Pacific. In this latter case, the property Pacific becomes red because it is in the new query, and the property Australia becomes orange because this generalization gives no additional photo.

Navigating Sideward

We show in this section that downward and upward navigation can be combined in 2 forms of sideward navigation. From the previous query Australia and (Animal or Plant) and not Portrait, we first select the property Plant to reach the query Australia and not Portrait and Plant (6 photos). This is our starting point for sideward navigation.

At this point, I see that 1 photo has also the type Landscape, which interests me. So I select this property (downward navigation), and as the result has only 1 photo, I generalize it by removing the property Plant from the query (upward navigation). We have done a sidestep from Australian plants (6 photos) to Australian landscapes (80 photos), replacing in the query the property Plant by the property Landscape. From there, I perform a new sidestep from the property Landscape to the property Building, now watching 28 photos of Australian buildings. These steps are suggested and supported by photos sharing two properties. This illustrates the relevance of assigning several types to photos, which is very common in this photo context. The same would apply to persons visible on photos, as a photo often shows several persons.

The same does not apply to locations, as a photo cannot be taken in 2 incomparable locations (e.g., in Australia and Europe). However it is still possible to navigate sideward among locations, through the taxonomy of locations. Suppose I want to find building photos from other locations. I first generalize Australia by Location in the query (upward navigation), and then browse suggested locations before selecting Spain (downward navigation). I thus have done a sidestep from Australia to Spain, and find 18 photos, which appear to be mainly churches taken in the north-west of Spain in 2003.

The latter form of sideward navigation is a downward-upward combination, and can be qualified as contextual because it relies on objects sharing some properties. The former form of sideward navigation is an upward-downward combination, and can be qualified as logical because it relies on subsumption relations between properties.

Querying by Formulas

Most useful queries can be reached by a succession of navigation steps, but not all. Indeed the logic allows the expression of string patterns (e.g., on events) and arbitrary intervals (e.g., on dates), and the navigation trees cannot display them all. However it is always possible to use these patterns and intervals by directly editing the query. For instance, suppose I want to find ICFCA-related photos, I enter event contains "ICFCA" in the query field, and find myself in the same situation as if I had selected the corresponding property in the navigation trees. I find that the 68 photos in the extent are scattered in 3 different years (2004,2006,2007) and in 3 different locations (Dresden, Clermont-Ferrand, Sydney), and they show people from the FCA community. I can further refine my search to photos taken since 2006 by modifying the query into event contains "ICFCA" and date in 2006... I now find that both year 2004, and location Sydney have disappeared from the navigation trees as they are no more relevant to the new query. The result can be seen in Figure 2.

It can be observed in Figure 2 that the 2 properties used in the query are now visible. Each time a new property is given by a user, it is inserted in the property trees for future use. Indeed, if a user has found this property useful, she or another user may well find it useful on another occasion. Now, if a user is not satisfied by this behaviour, she can still hide it, as well as any other property by the way. Conversely it is possible to directly insert a new property, without having to use it in a query. This possibility for users to show and hide properties at will help them customizing navigation trees to their taste.

Querying by Examples

In all previous sections the query is modified either by selection of features, or by direct edition. In this section we present how a query can be determined by the selection of a subset of photos, thus supporting querying by examples. The principle is to make the query be the intent of the subset of photos.

Definition 3 (intent). Let K = (O, L, d) be a context, and O ⊆ O be a subset of objects. The intent of O is the set of most specific properties that are shared by all objects in O:

intent(O) = Min ⊑ {p ∈ X | ∀o ∈ O : ∃d ∈ D(o) : d ⊑ p},
where X is the set of visible properties in the property trees.

Suppose I start with the query Australia and not Portrait. While browsing photos in the result, I see interesting photos of buildings (e.g. 2 photos of the Opera, and 1 photo of the Harbour Bridge), and I would like to find more. By selecting them I move to a new query that is the conjunction of the properties of the intent of those 3 photos. As usual with this form of navigation, the intent query is very specific so that I get no more photos. The properties making the intent query are red in the trees, and I find some of them are very specific: e.g., a precise date (22 feb 2004), a precise location (Sydney). At this stage, I can use upward navigation to generalize the query. By removing in the query properties related to date and event, the query becomes Sydney and Building, and I find 29 photos. I further generalize the query by replacing the property Sydney by Australia, but find no more photos. One more generalization by removing the location, and I now find 933 photos of buildings around the world, mostly in Europe. I can also navigate downward to find photos of modern buildings, or sideward to find buildings in different countries.

A special case of querying by examples is when selecting only one photo. Then there is only one object in the extent, because there is enough properties to uniquely characterize each photo, and the query contains all the object properties, which are more easily read as red properties in the navigation trees. So this is an easy way to access the full description of any object.

Describing Photos

This section shows how the context that is used in Section 2 can be built in a reasonably efficient way. An important practical need is that this building can be done incrementally upon the arrival of new photos, and that everything that is done can be undone. The parts of a logical context that can be updated are (1) the set of objects (i.e., adding and removing photos), (2) the description of objects (i.e., adding and removing properties to objects), and (3) the taxonomic parts of the logic (i.e., moving a property downward and upward in a taxonomy).

Importing Photos along with Intrinsic Properties

Suppose after I took part to CLA'07, I get a new folder of photos taken during this event. In order to add these new photos to my photo context, I apply the command Import files to this folder so that each photo it contains becomes a new object in the context. These new objects comes with an initial description that is automatically computed from the file location and contents. The properties making this initial description are called intrinsic. The intrinsic properties of photos are the file location as a string, and the date. From there it is easy to select the newly imported photos by setting the query to the appropriate file location property (e.g., file contains "My Photos/CLA2007/").

Adding Extrinsic Properties to Photos

The state of the art in image analysis [START_REF] Datta | Content-based image retrieval: approaches and trends of the new age[END_REF] makes it possible to make intrinsic low-level properties of photos, such as orientation, intensity, dominant colors or textures [START_REF] Martinez | Browsing image databases with Galois' lattices[END_REF]. However, most high-level properties such as event or visible persons, which are the most useful, cannot be determined automatically from their contents, and have to be given manually by users [START_REF] Hyvönen | Ontology-based image retrieval[END_REF]. Those properties are called extrinsic. In fact there is no strict borderline between intrinsic and extrinsic properties. For instance, the location could be made instrinsic with the help of a GPS-equiped camera and a geographical information system, but these features are rarely available. Some properties (e.g., sunset) could be made instrinsic, but probably not all. The borderline is fixed as a trade-off between the cost of manually giving properties, and the cost of developping property extraction algorithms. The advantage of extrinsic properties is that they can be customized at will to the needs of users, and the design of the interface make it efficient enough as I experienced with the rich description of more than 5,000 photos.

The principle for efficiently giving new properties to photos is based on copy and paste. A set of photo thumbnails is first selected, and is then pasted on a set of properties, which can be either selected in the navigation trees, or directly entered in a text field. Removing properties is simply done by pasting on the negation of these properties. All my new photos of CLA'07 have the same event and location, so I paste all of them into event is "conference CLA'07" and Montpellier. Both properties are new, and are then inserted in the property trees: event is "conference CLA'07" is placed under event contains "conference", but Montpellier is placed at the highest level because it is a new location. The taxonomy of locations is updated with Montpellier by the drag-and-drop of Montpellier under France, which enforces a subsumption relation between the 2 locations.

Other properties, e.g. types, persons, objects, are added in the same way. When a property already exists, it is enough to find and select it in the property trees. Otherwise it is enough to write it. In the latter case, either it is a valued attribute and it is automatically inserted, or it is a taxonomic term and it can be moved once and for all in a taxonomy. I have observed that after some number of photos I less and less often need to write new properties, and that I can rely on the property trees to maintain consistency in the use of properties. Of course the fact that I am the single user helps a lot to have a consistent vocabulary, but we could imagine a collaborative system under the principles of Wikipedia or Flickr to incrementally develop shared taxonomies.

Related Tools

Among applications for organizing and retrieving photos, Flickr and Picasa are among the most famous. In Picasa, the organization of photos is limited to making albums as collections of photos. So each album can be seen as a property, and because a photo can be put in several albums, a photo can be given several properties. However there is no hierarchy between those properties, and they cannot be combined in queries: e.g., it is not possible to get the intersection, union or difference between 2 albums. Navigation is limited to the usual file system hierarchy. In Flickr, any set of properties, called tags or sets, can be given to photos, and each photo can also have a date, a geolocation, and an owner. The basic queries are conjunctions of tags, but advanced search allows for negation of tags, and an interval of dates. However, the different properties cannot all be mixed in a same query: e.g., "all photos from this author taken in this area about some subject". The navigation is limited to a cloud of tags, where the size of each tag is related to its global frequency. This would correspond to our initial navigation trees, where each tree would be limited to its root, i.e., a flat list of tags.

There also exists tools in the FCA community. Bibsonomy [START_REF] Hotho | BibSonomy: A social bookmark and publication sharing system[END_REF] is similar in its working and appearance to Flickr, except it applies to bookmarks and bibliographical references instead of photos. It formalizes the metadata as a triadic context that links together resources, tags, and users. Im-ageSleuth [START_REF] Ducrou | FCA-based browsing and searching of a collection of images[END_REF] is certainly the tool the most similar to Camelis w.r.t. presentation and navigation. It displays the current semi-concept, the extent as a set of thumbnails and the intent; it provides downward and upward navigation, querying by attributes, and querying by examples. It also uses perspectives (sets of attributes), which are in fact simple cases of 2-levels taxonomies: the 1st level is made of perspectives like Location or Person for photos, and the 2nd level is made of attributes such as concrete locations or persons. It also provides a way to reach similar concepts according to some distance. According to the definition of this distance, we can say that our sideward navigation are a way to reach such similar concepts.

The main advantages we have compared to these tools are brought by the use of logic. Logic enables to express different kinds of properties (e.g., dates, string patterns), and to organize them according to a well-defined subsumption relation. Logic enables users to create and customize several taxonomies. Logic enables to express complex queries where all kinds of properties can be freely combined with all boolean operators. This expressiveness is nevertheless accessible through navigation as illustrated in Section 2. Another major advantage of Camelis is to provide very informative navigation trees from any query, and to support all forms of navigation and querying : navigation downward, upward, sideward, backward and forward, querying by formulas and by examples. Finally, we successfully manage a collection of photos 10 times larger than the example given for ImageSleuth, and we think this is because we do not need to compute the concept lattice. The navigation trees supporting navigation and reflecting the concept lattice are computed on the fly. Systems (LIS), and solves the problem of organizing and retrieving photos in a rich and flexible way. Camelis has also deeply changed the way I take and share photos with friends. I can quickly build customized diaporamas. For instance, to present my region Brittany to a group of foreigners, I selected all buildings and landscapes of this region, except those showing relatives. I am not reluctant to take photos that are irrelevant to the current event because I know I can easily find them afterwards: e.g., the photo of an animal during a conference event. This allows me to progressively gather collections of photos on various themes: e.g., I have got photos for 51 different species of animals, 17 different music instruments, and 255 named persons.

Besides photos, Camelis is also applied to music files (whose tags are automatically extracted as intrinsic properties), and to sets of bibliographical references (imported from BibT E X files and DBLP search results).

Figure1.

  Figure1. A screenshot of the graphical interface of Camelis.

Figure2.

  Figure2. Another screenshot of the graphical interface of Camelis.

See http://www.irisa.fr/LIS/ferre/camelis/.

The pronoun I is used to emphasize a personal experience in the use of Camelis.

French words can be seen in screenshots because it is my real photo collection, but english translations are used in the text for better understanding.

ConclusionCamelis has greatly benefited from several years of application on my collection of photos. This makes it a mature implementation of Logical Information