Mireille Ducassé
email: mireille.ducasse@irisa.fr

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

Fair(er) and (almost) serene committee meetings with Logical and Formal Concept Analysis

In academia, many decisions are taken in committee, for example to hire people or to allocate resources. Genuine people often leave such meetings quite frustrated. Indeed, it is intrinsically hard to make multi-criteria decisions, selection criteria are hard to express and the global picture is too large for participants to embrace it fully. In this article, we describe a recruiting process where logical concept analysis and formal concept analysis are used to address the above problems. We do not pretend to totally eliminate the arbitrary side of the decision. We claim, however, that, thanks to concept analysis, genuine people have the possibility to 1) be fair with the candidates, 2) make a decision adapted to the circumstances, 3) smoothly express the rationales of decisions, 4) be consistent in their judgements during the whole meeting, 5) vote (or be arbitrary) only when all possibilities for consensus have been exhausted, and 6) make sure that the result, in general a total order, is consistent with the partial orders resulting from the multiple criteria.

Introduction

There are numerous situations in academic life where decisions are taken in committee, for example to hire people or to allocate resources. The problem is to put a total order in partially ordered sets. For example, the applicants for a job have different qualities that are not necessarily comparable. Assume that a committee has to decide between two persons, if one is systematically better than the other one for all the criteria, the decision is easy to take. In general, however, the candidates are numerous (more than 100 in some cases), and some are the best with respect to some criteria and only average with respect to other criteria.

The final decisions of such committee meetings are necessarily arbitrary, at least partially. While some people may enjoy the opportunity to intrigue, our experience is that most participants have a genuine approach and try to be as honest as possible. This article is dedicated to such honest participants who want the process to be as rational as possible.

We conjecture that the frustrations felt by genuine people come mainly from the fact that the selection criteria are hard to express and that the global picture is too large for participants to embrace it fully.

In this article, we propose a decision process where Logical Concept Analysis (LCA) [START_REF] Ferré | An introduction to logical information systems[END_REF] and Formal Concept Analysis (FCA) [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] are used to address the above two problems. We do not pretend to totally eliminate the arbitrary side of the decision. After all, a committee is in general set up when it has been recognised that there is no obvious best solution. The role of the committee is therefore to make a decision and collectively take the responsibilities for it. We claim, however, that, with our approach, genuine people have the possibility to : 1) be fair with the candidates, 2) make a decision adapted to the circumstances, 3) smoothly express the rationales of a decision, 4) be consistent in their judgements during the whole meeting, 5) vote (or be arbitrary) only when all possibilities for consensus have been exhausted, and 6) make sure that the result, in general a total order, is consistent with the partial orders resulting from the multiple criteria.

In the following we illustrate our approach with an example which reconstitutes a committee meeting which had to choose among 43 job applicants. At the original meeting, the only tool which had been used was a spreadsheet. The actual arguments which had been put forward during the discussions are explicited a posteriori in this article.

Two tools are used, Camelis and Conexp. Camelis3 [START_REF] Ferré | CAMELIS: Organizing and browsing a personal photo collection with a logical information system[END_REF] is a concept-based information system. It relies on concept analysis to support the organizing and browsing of a collection of objects. One specificity w.r.t other (pure) FCA based systems [START_REF] Lindig | Concept-based component retrieval[END_REF][START_REF] Cole | CEM -a conceptual email manager[END_REF][START_REF] Ducrou | FCA-based browsing and searching of a collection of images[END_REF] is the use of logics to represent and reason on object descriptions, queries and navigation links. This allows typed attributes to be used, for instance, date intervals, string patterns, and Boolean connectives and, or, not. Conexp4 , developed by Sergey A. Yevtushenko, enables, among other features, to edit a Formal Concept Analysis context and to display concept lattices.

The example illustrates how two formal concept analysis tools can help alleviate frustrations and explain a decision. We show that the taken decision has a rationale behind it and argue that had the tools been used the discussions would have been much more serene. Regarding FCA and LCA, this case study also shows that both local navigation, such as advocated by Camelis, and global formal concept lattices are needed.

Running example

The example which is used throughout the article reconstitutes a committee meeting which had to produce a sorted list of five candidates in order to fulfil a two-year position 5 . The application was open either to PhD or to PhD students about to defend. There were 43 candidates.

In the French academic system, before hiring people, reports must be written. At the computer science department of the INSA of Rennes, besides a qualitative free style report, referees also fill in a spreadsheet file where a number of objective criteria are assessed. This is somehow a many valued context.

For this article we have straightforwardly used the actual spreadsheet file used in the recollected meeting as a formal context for Camelis. We have only replaced the names of the candidates (resp. the names of the research teams) by three (resp two) letter codes. The attributes are : the number of publications in international and national conferences as well as in journals, the location of the thesis, the expected date of the end of the thesis, whether the candidates have a computer science education, whether they have teaching experience, whether they have practical (programming) experience, whether there is a pedagogical project in the application file, whether they could integrate a research team of the laboratory. Two attributes, "bonus" and "malus", were meant to capture information which had not been anticipated.

Advocated decision process

The decision process that we advocate has three stages : firstly an analysis of the context driven by the attributes/criteria which eliminates obviously out of scope candidates, secondly an analysis of the context driven by the candidates, thirdly a discussion to make partial orders into a total order, this includes votes. Indeed, it is not tractable to examine all the attributes of each candidate in a detailed way. This would require at least 5mn per candidate. With more than 40 candidates, doing this for all candidates means several hours of analysis, people are not ready to do that for candidates who are obviously out of scope. Starting by an analysis driven by the attributes helps to speed up the process in a fair way and to spend time on valuable candidates.

Context analysis driven by the attributes

In the first stage the analysis of the context is driven by the attributes. The attributes are investigated in turn. For each one the committee decides how relevant the attribute is for this particular decision. In particular it is decided whether a given attribute is selective: the committee decides that it is mandatory. The candidates who do not fulfil them are eliminated. selective but counterbalanced: the committee decides that, in the absolute, the attribute would be mandatory, but in this context another attribute exhibited by some candidates could counterbalance the lack of this attribute. The counterbalancing attributes are specified. The candidates who do not fulfil either the selective or the counterbalancing attribute are eliminated. relevant: the committee decides that the attribute is relevant but not mandatory. It is kept to later differentiate the candidates. irrelevant: the committee decides that the attribute is not relevant for this particular decision.

Furthermore, new attributes may be identified, and the context is subsequently updated on the fly. Attributes that contain interesting information but which are not totally accurate can be restated.

In our example, this first stage is done under Camelis. A snapshot taken during the attribute driven stage is given Figure 1. The upper area contains the list of buttons and menus which are not detailed here.

The query area contains the selection criteria that the committee has specified so far. Namely on the figure this can be read as the selected candidates must have a Computer science education AND (they should have an experience abroad OR a teaching experience) AND their integration in the research laboratory should be granted AND they should have at least a publication in an international conference.

The bottom right-hand side window is the "object" window. It contains the name codes of the candidates who fulfil the criteria of the query area. One can see that, out of the initial 43 candidates, only 18 are left with the above query.

The bottom left-hand side window contains the taxonomy of all the attributes. The number on the left tells how many of the selected candidates have the attribute. One can see, for example, that only 11 candidates, out of the remaining 18, have a bonus. Starting from the top of the window, here is the information contained in the attribute window. One can read that the number of publications in journals, international conferences and national conferences are numbers (they can match "O.OOe3").

The committee has decided that having a "teaching experience" was a selective but counterbalanced attribute. Indeed, while everybody agreed that it is a very important criterion, somebody pointed out that it would not be fair that one of the candidates was eliminated because he had not enough teaching experience. He was doing a PhD partly in the USA and has not been able to teach. The group decided that having an "experience abroad" is very interesting for the department and that it can counterbalance not enough teaching experience. This is the echo of the second line of the query area. At that moment of the meeting, the context did not yet contain the information about an experience abroad. It had been easily updated on the fly. All candidates with an experience abroad were identified by their respective referee. A new attribute was added and associated to them.

The "date of the end of the thesis" has not been considered yet. The attribute is therefore not yet sorted. This also applies to whether candidates have "practical experience", and to which "research team" the candidates might join. "Other attributes" is folded, it contains attributes that the committee has already assessed as irrelevant for this decision. The committee has decided that "Bonus", "Malus", "other publications" and the presence of a "pedagogical project" in the file were interesting properties but that they should not yet be used for the selection. The four attributes have therefore been put under "Relevant attributes". The "Computer science education" and the "research integration" have been used in the query. The two attributes have therefore been put under "Selective attributes". The snapshot has been taken when the committee had just realized that "date end thesis" and "thesis location" could not be used as such. It had been decided that the candidates should either have submitted their thesis or that their thesis location should be close enough to Rennes to give them a better chance to complete their thesis. Therefore, instead of the precise thesis location, it is more accurate to know whether the thesis is done in a laboratory close enough to Rennes. With Camelis, it is easy to fix that: select all the thesis locations that are close enough to Rennes, then select the candidates associated with these locations and add a new attribute to those candidates. Similarly, instead of the estimated date of the PhD defence, it is better to know whether the thesis is already submitted. The context had therefore been extended on the fly by two new attributes, "Submitted thesis" and "Thesis location close enough", as well as their associations to candidates.

The figure illustrates how the two new attributes will be taken into account in the query. Namely, the committee would like to select only candidates with a "submitted thesis" or a "thesis location close enough" to Rennes. The two attributes have been clicked. Camelis has greyed them. It has also greyed the candidates not fulfilling one or the other. The committee can therefore see who is going to be eliminated if the disjunction of the two attributes is judged selective. "ARI", "DES", "GUX" and two other candidates hidden by the pop-up window might disappear. Each referee has a chance to tell if a candidate that he considers valuable might be lost. At the actual meeting, the committee had decided that the selection was fine. A right-click opens the pop-up window. The user is about to click on "<query> AND <selection>" which will add "AND (Submitted thesis' OR 'Thesis location close enough')" to the query.

Context analysis driven by the objects/candidates

At some point, the number of remaining candidates becomes small enough so that it becomes tractable to examine candidates in a detailed way. The committee analyzes all the attributes of each candidate in turn. In so doing, the committee can, of course, still decide that an attribute should be "selective" or "selective but counterbalanced".

During the first, attribute-driven, stage the committee checks that the candidates who are about to be eliminated indeed miss a required selective attribute. During the second, candidate-driven, stage the committee checks that the remaining candidates indeed have the attributes that their referees associated to them, in particular the selective ones. The committee also checks that no important attribute association is missing. It is most likely that new attributes emerge.

Figure 2 illustrates the investigation of a candidate assessment. The "CAL" candidate has been clicked in the right-hand side "object" window. His attribute values are shown, in two different ways, in the left-hand side attribute window as well as in the query window. The committee has just detected that the research team associated to this candidate is not "ic+tx" but "ic". It is about to select "Paste not" in the pop-up window to remove the attribute from the intent of Fig. 2. Snapshot of Camelis during the candidate driven context analysis "CAL". The next step will then be to "Paste" candidate "CAL" to attribute "Research team is "ic"".

In the actual session, the remaining of the second, candidate-driven, stage went as follows. Fourteen candidates were still in competition at the beginning of the second stage. While examining each candidate in turn, the committee questioned the potential integration into the research laboratory of two candidates. After discussion, it was agreed that the referees may have been a bit overoptimistic. The two candidates were said not to be easily integrated in the lab. The context was therefore updated and there were 12 candidates left.

Investigating the "malus" attribute, the committee decided that one of the candidates, currently working in the laboratory, might never complete his thesis. His long term integration into the research laboratory was therefore questioned and the related attribute negated. Among the remaining candidates, somebody pointed out that one of them was having a "major contribution in teaching". This would be interesting to keep. An attribute was added.

As there were still numerous good candidates in the list, the committee tested whether there would be enough good candidates to reinforce research teams already present at INSA. A new attribute had been introduced and six good candidates fulfil it. The committee decided that the attribute could be selective.

Making partial orders into a total order

At some point, the committee is confident that the context is valid and that the selection query is relevant for the current decision process. Furthermore, no more objective selection can be done with general consensus. We conjecture that, at this point, the formal concept lattice could be useful as it gives a global picture of all the partial orders. The task of the committee is to rank 5 candidates, hence making the partial orders into a total order.

Figure 3 shows the lattice related to the six candidates coming out of the second stage. From Camelis, we exported into Conexp a context containing the remaining 6 candidates and attributes which had been identified "relevant". In order to see the partial orders on numerical attributes, the context had been completed. Namely a candidate exhibiting "#int. confs=3" has also be credited by "#int. confs=2" and by "#int. confs=1". We can see that research teams "ic" and "ps" still have two candidates. From the informal information given by the two teams, the committee decides that, for "ic", "ROU" is better than "CAL", and it, therefore, keeps "ROU" and eliminates "CAL". Similarly, for "ps", "BUN" is kept and "SOZ" is eliminated. These decisions use information not yet in the formal context. At this stage of the process, there are few remaining candidates, the decisions start to become arbitrary, it is not so crucial to update the context. The eliminated candidates are simply removed from the display.

Figure 4 shows the lattice related to the remaining four candidates on the left-hand side. Using, again, informal information, the committee reckoned that "MOC" and "BUN" were stronger with respect to research and that "ROU" and "BOL" were stronger with respect to teaching. Furthermore, it had been decided that "BUN" was stronger than "MOC" considering the number and the quality of the publications. It had also been decided that "BOL" was stronger than "ROU" considering the teaching contribution. This resulted in the lattice shown on the right-hand side of Figure 4. The lattice shows the attributes common to the two candidates at the top. The attributes that neither of them has are displayed at the bottom. The specific attributes are attached to each candidate. At that point, the committee can vote.

Discussion

In this section we discuss the benefits of our method to make decisions. We argue 1) that the process is fair to the candidates, 2) that the decision is adapted to the circumstances, 3) that committee members can be (relatively) serene, 4) that the process requires LCA/FCA tools and 5) that using a fully automatic tools would be unwise.

The process is fair to the candidates

This process is fair to the candidates. Until the last "political" stage, no candidate can be eliminated without an explicit reason and the reason is applied to all candidates. The selection criteria are explicitly specified. All candidates fulfiling a given criterion are treated equally. When the committee thinks that a candidate quality could counterbalance a required criterion, all candidates exhibiting this very quality will be considered equally. In general, every time the context is updated, all candidates are concerned. Reports of eliminated by the current selection are also updated. Indeed, if the committee has second thoughts and relaxes some of the selective attributes, some candidates may no longer be eliminated by the relaxed attributes. They may therefore re-appear in the selection. As their attributes have been updated, they will benefit from all the decisions that have been taken after their initial elimination.

The decision is adapted to the circumstances

The process allows the decision to be adapted to the circumstances. Indeed, even if a committee uses more or less the same criteria for different meetings, the context is every time different, even if only slightly. For example, for a given recruitment there may be very few candidates, the committee can decide either not to fulfil a position or to adapt the selective criteria. It can also happen that the set of candidates is especially strong and that for a given recruitment the selective criteria can be tightened. It can also happen that some candidates exhibit special qualities not yet identified. For all the cases, the formal context can be easily updated, the selection query can be easily refined, constraints can be easily relaxed. The approach has all the required flexibility to adapt to the situation.

Committee members can be (relatively) serene

It is always hard to take multi-criteria decisions. The discussion below takes the point of view of honest committee members who sincerely want that the decision benefits to the institution.

The process is consistent, flexible and backtrackable. The underlying concept lattice ensures that the process is consistent through out the meeting and that the result, in general a total order, is consistent with the, easy to express, partial orders. Flexibility and consistency are the basis of the fairness discussed in the above section. For example, with our approach, it cannot happen that a candidate is eliminated whereas he has an attribute that enabled another candidate to be given a second chance. Furthermore, without support it is easy to be inconsistent even genuinely. With our approach, if a criterion is said crucial at the beginning of the discussion and if the chosen candidates do not fulfil it, then at the very least it will be visible and the committee can discuss whether this is acceptable on the spot. Last but not least the result of the selection is independent of the order in which the atomic decisions are taken. As a result, every partial decision can always be questioned, the process is backtrackable. There is no need to be always on edge, no fatal decision is taken until the last minute.

The process is transparent and traceable. Some committee meetings sometimes feel like a "Three card trick" game. Our process is transparent and traceable.

The context can be easily extended on fly with new attributes and their associations to candidates. Every member of the committee can follow the updates and can raise an objection at any time. The new context is easy to check. The selection decisions are visible in the query area. It expresses the rationale of the final decision.

The end result comes from many small and (relatively) easy decisions. Anybody can propose a new attribute or a new association, or suggest that an attribute should be selective. If the committee agrees by consensus, it is fine. If no consensus emerges the committee can vote to decide whether a new attribute is relevant or selective. It can also vote to decide whether a given candidate has an attribute. Those are small decisions, relatively easy to take. Furthermore, if the committee decides that the attribute is not selective but only relevant, it is fine that the context is anyway updated. It will be taken into account later when people will vote. It is also fine that a criterion is labeled relevant even if only one person in the committee judges it so. Consensus is only mandatory for selective criteria. This can save a lot of fruitless discussions.

Intriguing is not so easy. At such meetings, there are often people who are only there to "push" their own candidate regardless of the means. For example, we have seen situations where a candidate who had never been discussed comes out of the votes because a sub-part of the committee had plotted beforehand. With our approach the candidates who are voted upon must have been examined in depth, their attributes must have been validated. They must satisfy a number of required properties. It is not so easy to manipulate a group on small concrete decisions. It is therefore most likely that candidates who do not fulfil the required properties will have been eliminated. Sometimes it also happens that a new criterion comes out at the end of the meeting and that it gives a decisive advantage to the very candidate who is supported by the referee who expresses the criterion. As this is bad practice, genuine referees can refrain from specifying an important criterion only because it is somehow too late. With our approach if somebody wants to defend a candidate, it is fine at any time because all candidates with the same attributes will be treated equally. Last but not least, voting occurs only when all possibilities for consensus have been exhausted. At that moment, any result is fair as the whole rational is fulfilled.

LCA/FCA tools are relevant

The overall process is very hard to achieve without appropriate tools. When we started using a spreadsheet it was already a big improvement over oral or written reports even if structured. However, selecting criteria and candidates in the spreadsheet is very error prone. It is hard to be 100% sure that the process is consistent. Furthermore adding attributes and stating in the table who has them is very tedious and again error prone. Even worse, keeping track of the selection process is almost impossible, especially when it is a combination of a logical AND, OR and NOT connectors. In Camelis, everything that was so hard to do with a spreadsheet can be done naturally. the global consistency is guaranteed and the query keeps the history of decisions.

At the actual meeting, neither Camelis nor the lattices were available. The decisions were, nevertheless, taken mostly with respect to the criteria displayed in the previous section. People had to keep the picture in their mind and it took a lot of time. The same arguments had to be repeated again and again, every time we needed them somebody had forgotten them.

It is not straightforward to get the initial context, especially when no formal reports are required. However, our experience shows that people are more keen to write them once they understand the potential gain. We are actually considering to use Camelis to fill in the initial reports, skipping the spreadsheet altogether. Indeed, updating the associations attributes-candidates is very easy. If the attributes already exist it is just a matter of drag and drop. Adding a new attribute is also straightforward. A verbose report would be easy to generate automatically from the final context. Furthermore, the criteria resulting from a meeting could be used to initialize the next recruitment.

Using a fully automatic tools would be unwise

The context must be updated and validated. It is important to note that even with a large experience of committee sessions there is no way the formal context can be filled and not been questioned. The formal context has to be updated and validated. Firstly, it is impossible to guarantee that all the important criteria have been foreseen and anticipated. Secondly, the context depends of the set of candidates: it is possible that not enough candidates fulfil the selection criteria that have been used in previous meetings. Thirdly, some of the candidates can show interesting features that had not been previously identified. Fourthly, referees may make mistake while filling in the context. Lastly, referees make judgements that the remaining of the committee may want to question. Some people are too kind and other are too strict, it is also easy to miss an important feature in a CV. As a consequence, it is out of question that the decision is taken automatically using the context as it is at the beginning of the meeting. One of the objectives of the process described so far is, on the contrary, that the members of committee collectively agree both on a set of attributes/criteria and on who satisfy them. Namely the context is revised and updated during the process and is as much a result of the meeting as the resulting ranked list of candidates.

No magical number. Once the context is agreed upon by the committee, we still do not advocate to build a program that would compute magical numbers. Numbers have the nice feature to be naturally ordered. However, the committee has to take full responsibility for the final decision. With our process, all the attributes are identified. All the selective attributes have been agreed upon. The weights and priority among the attributes which have been labelled relevant depend of each committee member who takes them into account while voting. This makes it easier for committee members to shoulder the final decision. Concept analysis has been applied to numerous social contexts, such as social networks [START_REF] Roth | Binding social and semantic networks[END_REF] and computer-mediated communication [START_REF] Hara | Analysis of computer-mediated communication: Using formal concept analysis as a visualizing methodology[END_REF]. Most of those applications are intended to be applied a posteriori, in order to get some understanding of the studied social phenomena. On the contrary, we propose to use LCA and FCA in the course and as a support of the phenomena itself. In our case, the purpose is to support a social/committee decision process. Our approach is to other social applications, what information retrieval is to data-mining. Whereas data-mining automatically computes a global and static view on a posteriori data, information retrieval (i.e. navigation in the concept lattice) presents the user with a local and dynamic view on live data, and only guides users in their choice.

A reason for not showing the global concept lattice is that it is too large to be managed by hand. Figure 5 shows the resulting concept lattice. Even in the case of our small context reduced to the 43 candidates and 40 attributes (out of 62), the number of concepts is 1239. Indeed, that formal context is dense. All candidates have many attributes, hence the large number of concepts. Local views such as proposed by Camelis or other FCA-based tools in the domain of information retrieval [START_REF] Ducrou | FCA-based browsing and searching of a collection of images[END_REF] are better suited for the first two stages described in this article than global lattices.

A specificity of Camelis is the use of logics. This has consequences both on the queries that can be expressed, i.e. on the set of candidates that can be selected, and on the attribute taxonomy, i.e. on the presentation of the criteria occurring in the selected candidates. The use of logics allows to express inequalities on numerical attributes (e.g., number of publications), disjunctions and negations in queries. In pure FCA, only conjunctions of Boolean attributes can be expressed. Previous sections have shown how disjunction is important to take into account counterbalanced selection criteria. In the taxonomy, criteria are organized according to the logical subsumption relation between them (e.g., "nb. papers = 2" is placed under "nb. 1.."). In pure FCA, criteria would be presented as a long flat list. Logics helps to make the taxonomy more concise and readable by grouping and hierarchizing together similar criteria. The taxonomy can be updated dynamically, making it possible to group together all irrelevant attributes. In this way, irrelevant attributes are displayed in one line, instead of many, but they are still accessible, and can be moved back as relevant attributes.

Conclusion

There are numerous situations similar to the one recollected in this article. Every time a scarce resource has to be assigned by a group which wants to put rationale into its decision, our approach could be used. We have illustrated that with our approach genuine people have the possibility to smoothly express the rationales of a decision. The resulting query gives an explanation of the selection. The committee can take the responsibility of its decision. The committee can be consistent in their judgements during the whole meeting and can be fair with the candidates. It can make a decision adapted to the circumstances. Voting can be postponed to the moment when all possibilities for consensus have been exhausted. The result, in general a total order, is consistent with the expressed partial orders.

Fig. 1 .

 1 Fig. 1. Snapshot of Camelis during the attribute driven context analysis

Fig. 3 .

 3 Fig. 3. The concept lattice with six remaining candidates and relevant attributes

Fig. 4 .

 4 Fig. 4. The concept lattices with four remaining candidates and with the two finalists

Fig. 5 .

 5 Fig. 5. Concept lattice for the 43 and 40 attributes out of 62

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

http://conexp.sourceforge.net/

called "Attaché Temporaire d'Enseignement et de Recherche"

Acknowledgements The authors thank Daniel Herman for fruitful comments.


Olivier Bedel

Sébastien Ferré

Olivier Ridoux

Handling Spatial Relations in Logical Concept Analysis to Explore Geographical Data

Because of the expansion of geo-positioning tools and the democratization of geographical information, the amount of geo-localized data that is available around the world keeps increasing. So, the ability to efficiently retrieve informations in function of their geographical facet is an important issue. In addition to individual properties such as position and shape, spatial relations between objects are an important criteria for selecting and reaching objects of interest: e.g., given a set of touristic points, selecting those having a nearby hotel or reaching the nearby hotels. In this paper, we propose Logical Concept Analysis (LCA) and its handling of relations for representing and reasoning on various kinds of spatial relations: e.g., Euclidean distance, topological relations. Furthermore, we present an original way of navigating in geolocalized data, and compare the benefits of our approach with traditional Geographical Information Systems (GIS).

Introduction

In previous work [START_REF] Bedel | Exploring a geographical dataset with GEOLIS[END_REF], we have applied Logical Information Systems (LIS) to explore of geographical data. LIS allow to query and browse a collection of geographical objects using spatial properties, such as position and shape, and non spatial ones, such as description and date. The geographical objects were described in isolation, not taking into account their mutual organization. However, relations, and particularly spatial relations, play an important role when describing and exploring geographical data. Indeed, geographical information is tradionnaly split in thematic layers, and localization is often the only common property between these different layers. Quantitative and qualitative spatial relations between geographical objects may be easily derived from objects localization. Spatial relations enhance the description of geographical data, improve the expressivity of spatial querying and facilitate the combination of data dealing with several thematics. For instance, one may want to find all bus stops under some distance from some place; or to find appartments that are close to a public garden that contains a lake.

LIS are founded on Logical Concept Analysis (LCA) [START_REF] Ferré | An introduction to logical information systems[END_REF]. Like FCA, LCA allows to group objects into concepts on the basis of individual properties, but moreover LCA also enables to consider arbitrary relations between concepts [START_REF] Ferré | Arbitrary relations in formal concept analysis and logical information systems[END_REF]. FCA does not natively support relations, however several extensions have been proposed in this sense: Power Context Families [START_REF] Wille | Conceptual graphs and formal concept analysis[END_REF] and Relational Concept Analysis (RCA) [START_REF] Rouane | A proposal for combining formal concept analysis and description logics for mining relational data[END_REF]. These extensions are discussed in Section 2, and the choice of LCA is motivated within the scope of describing spatial relations and exploring geographical data. Section 3 recalls the useful definitions of LCA.

There are various formalisms to represent and reason on spatial relations, from purely numeric relations [START_REF] Michael | Geospatial Analysis: A Comprehensive Guide to Principles, Techniques and Software Tools[END_REF] to purely symbolic relations [START_REF] Cohn | Qualitative spatial representation and reasoning techniques[END_REF]. We show LCA covers a wide range of spatial relations by applying it to two different kinds of spatial relations (Section 4). The first kind is a numeric spatial relation, the distance between objects, where relations are described by a precise value, and intervals of distance can be used in queries. The second kind is a symbolic spatial relation, topological relations such as "contains", "overlaps", or "touches". Furthermore, we show that these relations can be automatically derived from the position and shape of objects. So, having such relations costs nothing more to the application designer than the individual description of objects.

A prototype has been implemented, and is used to demonstrate the benefits of our approach for exploring geographical data (Section 5). The navigation facilities are especially emphasized as they prevent users from having to write complex queries. Finally, we compare our work with state of the art in Geographical Information Systems (GIS) (Section 6), and conclude with further works (Section 7).

Relations in Concept Analysis

To our knowledge, three main approaches have been proposed to take into account arbitrary relations between objects in FCA: Power Context Families, Relational Concept Analysis, and relations in Logical Concept Analysis. Each of them has its advantages and its drawbacks regarding the intended use. In this section, we discuss the oportunity of considering a formalism rather than another for the purpose of geographical data exploration in the FCA framework. In fact, we want to represent spatial relations between geographical objects and use them as a key for navigation and querying.

Power Context Families (PCF) extend standard FCA and enable to represent arbitrary n-ary relations between objects of a formal context. A PCF is a vector of formal contexts (K

1 , K 2 , ..., K n ), n ≥ 2 with K i = (O i , A i , I i ), s.t. O i ⊆ (O 1 ) i .
K 1 is the formal context that stores the description of objects and K n describes the n-ary relations linking n of those objects. Dealing with n-ary relations may be interesting when representing complex interactions between objects, as it is the case in software engineering for instance. But, in the geographical domain, most of spatial relations that are used in GIS are expressed in terms of binary relations. Moreover, a drawback of PCF is that a different lattice is generated for each context. This means that one cannot use relational properties to navigate in the traditional concept lattice, i.e. the lattice derived from K 1 . Yet, mixing object properties and relational properties in a navigation search is one goal we want to achieve.

Contrary to PCF, Relational Concept Analysis (RCA) and LCA enables to describe objects and their relations to each other in the same context, and so in the same lattice. RCA introduces into FCA abstractions of binary relations between formal concepts similar to role description (∀r.C,∃r.C) in Description Logics [START_REF] Rouane | A proposal for combining formal concept analysis and description logics for mining relational data[END_REF]. These abstractions result from a relational scaling on the object context, and appear in the corresponding concept lattice. However, RCA only deals with a flat set of relation names, and does not allow a priori to express valued relations or to represent a generalization ordering between relations. When dealing with spatial relations, this is a drawback as distance relations are valued relations, and topological relations can be organized in a taxonomy. LCA uses logic to describe objects and relations, as well as to express queries over those objects. Navigation between concepts is enabled by navigation links that take the form of ∃r.f , where r denotes the relation and f a description of the image through r. They can be nested or combined with Boolean operators to define complex queries. As shown in Section 4, logic enables to express and reason with valued properties, and also to consider a partial ordering over relational properties. This provides facilities to represent distance or topological relations. LCA has first been introduced to generalize FCA for the purpose of information retrieval [START_REF] Ferré | An introduction to logical information systems[END_REF]. In the same way as RCA extends FCA to support relations in concept analysis, the addition of relations in LCA [START_REF] Ferré | Arbitrary relations in formal concept analysis and logical information systems[END_REF] brings arbitrary relations in information retrieval with LCA. If RCA and LCA do not share a common goal, the same motivation in handling relations appears in both approaches.

An advantage of RCA is its ability to effectively build the concept lattice, which is useful for data-mining tasks. LCA supports the exploration of the concept lattice, where the focus is on the concept and its neighborhood. This is valuable when exploring large and dense concept lattices. And precisely, our aim is here information retrieval and among the previous approaches, LCA appears to be the most appropriate to deal with spatial relations for the purpose of exploring geographical objects with querying and navigation.

Relations in Logical Concept Analysis

In this section, we recall how LCA enables to take into account arbitrary binary relations between objects. We here limit our presentation to the parts that are relevant to querying and navigation mechanisms, i.e. we focus on the computation of extents and navigation links between concepts, and let out the computation of intents. For readers interested in the details of our approach, a complete introduction to relations in LCA can be found in [START_REF] Ferré | Arbitrary relations in formal concept analysis and logical information systems[END_REF].

Describing Objects and Relations

In LCA, the object context contains the description proper to each object individually, whereas the relation context describes the binary relations between objects of the object context. Definition 1 (object context). An object context is a triple K 1 = (O, L 1 , d 1 ), where:

-O is a set of objects.

-L 1 = (L 1 , 1 ) is called a logic. L 1 is a language of formulas used to describe objects, i.e., L 1 is composed of all words that can be used to build a formula, e.g. atoms or connectors. 1 is a partial ordering, called subsumption. d 1 : O → L 1 is a mapping from objects to their description.

The extent of an L 1 -formula q 1 is defined as the set of objects whose description is subsumed by q 1 . Definition 2 (object extent). Let K 1 = (O, L 1 , d 1 ) be an object context and q 1 ∈ L 1 be a query. The object extent of q 1 in K 1 is defined by

ext 1 (q 1 ) = def {o ∈ O | d 1 (o) 1 q 1 }.
Example 1 (The film and artist context). Here we consider the context of Figure 1 about films and artists. The first row is to be read:

d 1 (f 1 ) = {title : P ulp F iction , year : 1994 , style : detective} In this example, L 1 = P(A×L V 1 ) is a composite logic, where a 1 :v 1 ∈ A×L V
1 is called a valued logical property and represents an attribute followed by its value. A and L V 1 are logics about attributes and values, × enables to define the product of two logics, and P enables to reason on sets of formulas of a logic. A composite logic L includes a composite language L and a composite subsumption relation . In this example, 1 correponds to a variant of set-theoretic inclusion where subsumption of values of the same attributes are taken into account. When querying, this enables to use patterns over values of properties. For instance, {year : 1994 , style : Detective} 1 {year : >= 1990}. Other examples will be given in Section 4, but for a detailed explanation of the mechanism of logic composition, the reader should refer to [START_REF] Ferré | Logic functors: A toolbox of components for building customized and embeddable logics[END_REF].

The relation context is a kind of logical context, whose objects are pairs of objects of an object context, and there is an inverse operation for both objects and formulas.

Definition 3 (relation context). Let K 1 = (O, L 1 , d 1 ) be an object context. A relation context is a triple K 2 = (R, L 2 , d 2 ), where: -R is a set of pairs (o 1 , o 2 ) ∈ O × O. Each pair (o 1 , o 2 )
(p1, f1) x (p1, f2) x (p1, f3) x (p2, f2) x x (p3, f1) x (p3, f2) x (p3, f4) x x
Fig. 1. An object context about artists and films, and the corresponding relation context. Relations plays -1 and directs -1 are not explicitly described, but can be automatically infered from the relation context.

-

L 2 = (L 2 , 2 , . -1
) is a logic of relations. L 2 is a language of formulas used to described relations. 2 is a subsumption relation, and (. -1 ) denotes an inverse operation over formulas, considering the inverse of relations s.t. for every f 2 , g 2 ∈ L 2 , the following axioms are satisfied:

• (f -1 2 ) -1 ≡ 2 f 2 (where f 2 ≡ 2 g 2 = def f 2 2 g 2 ∧ g 2 2 f 2 ), • f 2 2 g 2 ⇔ g -1 2 2 f -1 2 . -d 2 : R → L 2 is
a mapping from pairs of objects to their description expressed as a logical formula. d 2 is compatible with the inverse relation, i.e. ∀r ∈ R,

d 2 (r -1 ) ≡ 2 d 2 (r) -1 .
The extent of an L 2 -formula q 2 over a relation context is the set of pairs of objects that are related by a relation subsumed by q 2 . Definition 4 (relation extent). Let K 2 = (R, L 2 , d 2 ) be a relation context, and q 2 ∈ L 2 be a query. The relation extent of the query q 2 is defined by

ext 2 (q 2 ) = def {r ∈ R | d 2 (r) 2 q 2 }.
Example 2 (The playing and directing relation context). We now consider the relation context of Figure 1 indicating who plays in a film and who directs it. For instance, from this context, we can read:

d 2 ((p 3 , f 1 )) = {directs} and d 2 ((f 1 , p 3 )) = {directs -1 } d 2 ((p 2 , f 2 )) = {plays, directs} and so d 2 ((f 2 , p 2 )) = {plays -1 , directs -1 }
In this case, L 2 = P(Ro) where Ro = {plays, plays -1 , directs, directs -1 } is a logic of roles. Ro corresponds to the different roles an artist can have in a film, and vice versa. The subsumption relation 2 =⊇. (. -1 ) maps a set of roles to the set of its inverse roles. For instance, {plays, directs} 2 {directs} and {plays} -1 = {plays -1 }.

Querying

In LCA, queries include criteria on both objects and relations. So, for the purpose of querying and navigation, a new context K = (K 1 , K 2 ), combining the object and relation contexts, is considered. In the same way, a combined query language L is defined for representing expressive queries.

Definition 5 (combined context and language). Let K 1 be an object context, and K 2 be a relation context. K = (K 1 , K 2 ) is the combined context, that gathers the individual descriptions of objects and their relationships to each others. The combined language L is defined as follows:

L → | ⊥ | L 1 | ∃L 2 .L | ∀L 2 .L | ¬L | L L | L L.
This language is the language of the description logic ALC [START_REF] Donini | The complexity of concept languages[END_REF], except atomic concepts are replaced by object formulas (coming from L 1 ), and atomic roles are replaced by relation formulas (coming from L 2 ). The previous definitions of object and relation extents are used as the basis for a combined extent that computes the extent of a combined query. The semantics behind its definition is the same as in description logics, except the closed world assumption is used instead of the open world assumption (e.g., the extent of the negation of a formula is always the complement of the extent of this formula).

Definition 6 (combined extent). Let K = (K 1 , K 2 ) be a combined context, and q ∈ L be a combined query. The combined extent of q is defined by the recursive set of definitions:

-ext( ) = def O -ext(¬q) = def O \ ext(q) -ext(⊥) = def ∅ -ext(q q ) = def ext(q) ∩ ext(q ) -ext(q 1 ) = def ext 1 (q 1 ), where q 1 ∈ L 1 -ext(q q ) = def ext(q) ∪ ext(q ) -ext(∃q 2 .q) = def {o | ∃r ∈ ext 2 (q 2 ).(start(r) = o ∧ end (r ) ∈ ext(q))} -ext(∀q 2 .q) = def {o | ∀r ∈ ext 2 (q 2 ).(start(r) = o ⇒ end (r ) ∈ ext(q))}
The formula ∃q 2 .q can be understood as having at least one image through relation q 2 that satisfies the formula q. Whereas ∀q 2 .q can be understood as having all images through relation q 2 that satisfy q. Definition 7 (query reversal). The query reversal is a query transformation defined as follows: rev(q ∃q 2 .q , ∃q 2 .q ) = q ∃q -1 2 .q with q , q ∈ L, q 2 ∈ L 2 .

Query reversal allows to traverse backward relations already mentioned in a query. This allows to change the point of view by considering either one side of a relation or the other. This is useful because the query ∃q -1 2 (∃q 2 .q ) is not always equivalent to the query q .

Navigating

As seen before, query reversal already enables to navigate between queries. Moreover, in order to help users in building queries, a subset of navigation links can be computed for any query in order to refine it. These navigation links are taken in a finite vocabulary, whose elements are called features. We assume that the set of features for an object context K 1 (resp. relation context K 2 ) is given by a user-defined function, called f eat 1 (K 1 ) (resp. f eat 2 (K 2 )). In most cases, f eat 1 (K 1 ) (resp. f eat 2 (K 2 )) contains at least the subset of L 1 (resp. L 2 ) that is used to describe objects, and the subset of patterns of L 1 (resp. L 2 ) that users have already entered in queries. Those two vocabularies need to be combined in order to provide a navigation vocabulary over a combined context. It has been proved [START_REF] Ferré | Arbitrary relations in formal concept analysis and logical information systems[END_REF] that the subset of the combined language useful to build navigation links can be restricted to: Definition 8 (combined vocabulary). Let K = (K 1 , K 2 ) be a combined context. The combined vocabulary is recursively defined as the set of features

feat(K) = def feat 1 (K 1 ) ∪ {∃x 2 .x | x 2 ∈ feat 2 (K 2 ), x ∈ feat(K)}.
Features coming from K 1 are called object features, whereas those coming from K 2 are called relation features. As a query ∀q 2 .q can be rewritten as ¬∃q 2 .¬q, there is no need for ∀ quantifier in relation features. Given a current query q ∈ L, only features occuring in the extent of q are presented to users as further query increments.

Definition 9 (query increments). Let K = (K 1 , K 2 ) be a combined context, and a query q ∈ L. A feature x ∈ feat(K) is a query increment if it has a common instance with the query q, i.e. ext(q) ∩ ext(x) = ∅.

Object features and relation features can both be used as query refinements, but relation features can also serve as paths to go through. A relation feature ∃q 2 .q and may be used go from a query q to q ∃q 2 .q (refinement) or q ∃q -1 2 .q (relation traversal). In order to facilitate the browsing of query increments, these navigation links are partially ordered according to subsumption. This requires to define subsumption between features by combining object and relation subsumptions.

Definition 10 (combined subsumption). Let K = (K 1 , K 2 ) be a combined context. The combined subsumption between features in feat(K) is defined by

x y = def    x 1 y if x, y ∈ L 1 x 2 2 y 2 ∧ x y if x = ∃x 2 .
x , y = ∃y 2 .y (f or some x , y ∈ L) f alse otherwise Example 3 (Query refinement, relation traversal and query reversal). We consider the film and artist context, and using the different ways of navigation, we progressively build a query. We start from the most general query q t0 = .

1. We start by refining q t0 with the object feature Style:Action to select action films: q t1 = style:Action = style:Action. 2. Then, we use the relation feature ∃plays -1 .(name:"Quentin Tarantino") to refine the query: q t2 = style:Action ∃plays -1 .(name:"Quentin Tarantino"). 3. We choose then to traverse the relation directs -1 using the relation feature ∃directs -1 .( ). Now q t3 = ∃directs -1 .(q t2 ) denotes the artists who direct an action film in which Quentin Tarantino plays.

4. We are then able to restrict to artists that are men: q t4 = q t3 sex:M . 5. Last, we decide to come back to the selected films using the query reversal on relation direct -1 traversed in q t3 . The new query q t5 is equal to: style:Action plays -1 .(name:"Quentin Tarantino") ∃directs -1 .(sex:M ).

LCA applied to the Geographical Domain

In the sequel, we first present a logic L g 1 over geometries that enables to describe and reason about the spatial properties of geographical objects. Then, we give two examples of spatial relations defined as logical relations using LCA: a Euclidean distance relation defined as

L [m] 2
and a set of topological relations defined as L T opo

2

. Especially, we describe the logical reasoning over these kinds of spatial relations.

Spatial Properties

As introduced in Section 3, the object context contains the description of objects expressed as a conjunction of logical properties. To describe the spatial characteristics of a geographical object, we use a particular logical property, called the geometry property. The geometry property is a valued property whose name is geometry and whose value represents the shape of the geographical object. This value corresponds to a textual description of the geometry, expressed in the Well Known Text (WKT) format [START_REF] Herring | OpenGIS Implementation Specification for Geographic information (06-103r3)[END_REF] defined by the Open Geospatial Consortium. Like most other geographical data formats, WKT encompasses the location in the shape description. In fact, the shape is defined as a sequence of absolute coordinates determining the spatial border of the geographical object. Examples of geometry properties are presented in Table 1. The domain of values of the geometry property is defined by a specialized logic over geometries: L g 1 = (L g 1 , g 1 ). Table 1. Three simple spatial descriptions illustrating point-wise, linear and area representation of geographical objects.

L g 1 is equal to the WKT language, and g 1 corresponds to the inclusion of geometries. According to L g 1 , the value g =POLYGON((110.6 ... 20.3)) represents all geometries that are entirely inside g. For instance, POINT(0.0 0.0) g 1 POLYGON((-1.0 -1.0,-1.0 1.0,1.0 1.0,1.0 -1.0,-1.0 -1.0)).

When querying for geographical objects, a user has thus the ability to draw an area of interest on a map, and L g 1 can be used to retrieve all objects located inside the polygon corresponding to the drawn area. A more detailed explanation of the use of L g 1 can be found in [START_REF] Bedel | Exploring a geographical dataset with GEOLIS[END_REF].

Spatial Relations

Spatial relations are implicitly derived from to the geographical description of objects. The distance relation and the topological relations are function of the location and the shape of objects.

Distance Relation

Our first example of a spatial relation is the distance between objects. In the following, we consider only the case where coordinates of geographical objects are expressed in the same projected coordinate system, which corresponds to the common practice in GIS. We define the distance dist between two points as the Euclidean distance. The distance dist g between two geometries g 1 and g 2 corresponds to the minimun distance between a point of g 1 and a point of g 2 :

∀g 1 , g 2 , dist g (g 1 , g 2 ) = min{dist(p 1 , p 2 ) | p 1 ∈ g 1 , p 2 ∈ g 2 }
With LCA, dist g can be represented with a logic of relations L

[m]

2 . Formulas take the form of valued attributes. The attribute name is distance and its values correpond to a distance expressed as a real number in the metric system. Intervals and several metric symbols, e.g. m, cm or km can be used as patterns. As a distance relation is symmetric,

f -1 2 = f 2 for all f 2 ∈ L [m]
2 . We give some examples of formulas from L (being distant of 100m is being distant) dist:1km

[m] 2 distance:1000m (1km is the same as 1000m) distance:1km [m] 2 distance:in [10m,1km] [m] 2 distance:>=100m (distance:1km) -1 ≡ [m] 2 distance:1km
The logic L

[m] 2 enables queries in the form ∃(distance:<=d) . f 1 , which selects all objects within a distance less or equal to d of objects described by f 1 . This kind of queries corresponds to a fundamental functionality of GIS. This is a common way to define a buffered area, i.e. an area determined by both: a set of objects of interest (f 1 ) and a distance relation (distance:<=d). For instance, the following query q 1 selects fields close to a river: q1 = type:field ∃(distance:<=20m) . type:river Furthermore, distance formulas can be combined and even nested to build complex queries. For instance consider the query q 2 dealing with apartments: q2 = (apType:T3 apType:T4) ∃(distance:<=500m ). type:garden ∃(distance:<=200m ). (type:busStop ∃(travel time:<=10min ). (type:busStop ∃(distance:<=200m ). place:'IRISA'))

Query q 2 selects 3-or 4-rooms apartments that are close (less than 500m) to a public garden, and that are near (less than 200m) a bus stop from where it takes less than 10min by bus to reach another bus stop that is close to IRISA (less than 20m).

Topological Relations Topological relations are binary relations describing the spatial position of an object w.r.t another object. These relations are qualitative, they give information about the spatial organisation of objects independently from their size, shape or distance. The expression of topological relations is a domain that has already been widely investigated [START_REF] Cohn | Qualitative spatial representation and reasoning techniques[END_REF]. Several classifications have been proposed, some of which based on Galois lattices [START_REF] Napoli | The galois lattice as a hierarchical structure for topological relations[END_REF]. In the following, we consider a taxonomy of topological relations over regions [START_REF] Wessel | Visual spatial query languages: A semantics using description logic[END_REF], including the 8 base relations of the RCC8 model [START_REF] Randell | A Spatial Logic Based on Regions and Connection[END_REF] and 7 intermediate relations (see Figure 2). Each organisation of 2 polygonal geometries in a 2-dimension space can be expressed as one of the 8 base relations. For the purpose of information retrieval, this classification has the advantage of being quite simple with only few relations [START_REF] Cox | Geography Markup Language (GML) Encoding Spec. Open Geospatial Consortium[END_REF] and understandable intermediate relations. The stands for the general relation being spatially related, which we consider always true between two geographical objects. Notice also the symmetric properties between relations: inside -1 = contains, inside t -1 = contains t, inside s -1 = contains s, and r -1 = r for all other relations. We now suppose that for each couple of area objects (o 1 , o 2 ) of the object context, the 2 RCC-8 relations describing the position of o The query q 1 selects all non-terraced houses, q 2 , residential areas, and q 3 , roads next to my home and leading to a public garden having a lake.

One asset of LCA is to combine querying and navigation in order to make information retrieval easier and faster. From any query, navigation is enabled through a set of navigation links that update the query, and eventually through query reversal. To facilitate the navigation, query increments are ordered in a navigation tree, according to the subsumption relation ( ). In previous works [START_REF] Bedel | Exploring a geographical dataset with GEOLIS[END_REF], we have already introduced a graphical interface that enables navigation inside geographical data, however it was not dealing with relational properties. This interface is composed of a query box, a map area, and a navigation tree. The query box recalls the current query, i.e. the navigation context and is manually editable by the user. By analogy with file systems, the current query is called the working query (wq). The map area is a cartographic representation of the explored context and enables to graphically select regions of interest as graphical query increments. The navigation tree is a visual representation of the partially ordered set of query increments, which are computed on demand and always relevant w.r.t. wq. In the following, we present a navigation tree allowing relational navigation through spatial relations. The query box has also been enhanced with the query reversal transformation. Non nested relation features appearing in wq are in fact hyperlinks that enable to traverse backward those relations.

To illustrate the use of navigation, we consider the following situation, where a traveller arrives in an unknown (fictive) city and looks for information about several points of interest, including lodging, lunch, recreation or transport offers. To help himself, he relies on a LIS device that let him query and navigate the city map context using a navigation tree and a query box. The set of objects O of the context corresponds to the points of interest, the streets and the position of our traveller. The individual spatial and non-spatial properties of the objects are described with a logic L city

1 = P(A × (L V 1 ∪ L g 1 )
). The distance relations and the topological relations the objects share are expressed with the logic L city . The description of the city map is presented in Figure 3a. Topological relations between all pairs of objects have been computed beforehand using a GIS. The disjoint relations, not relevant for this case of navigation, have not been expressed. However, objects disjoint from others can be accessed through the ¬∃connected . increment. Distance relations have also been computed beforehand between each point of interest and its neighbour streets. For instance, the "Bus stop 1" touches the "Street A", and the "Bar 2" is within a distance of 10 meters of "Street A".

The Navigation Tree

The navigation tree related to the citymap context is presented in Figure 3b. It displays information about the type of geographical objects (type), their name (place name), and about the spatial relations they share (distance and spatially related for topological relations). Query increments, also called features, may be of two kinds (see Section 3.3). Object features are properties shared by at least one object of wq. For instance, in the citymap navigation tree, there is one lodging object. Relation features denote a relation between some objects of the current query, with at least one other object of the context. Relation features correspond to ∃x 2 .x navigation links, but are expressed in the navigation tree with direction symbols > and <. For instance, in the citymap navigation tree, 6 objects are spatially related to another object. The feature spatially related>ALL corresponds to ∃spatially related. , and spatially related<ALL corresponds to ∃spatially related -1 . . In the tree of Figure 4, both features distance:>ALL and distance:<ALL are represented, altougth they are redundant because the distance relation is symmetric. This is also true for some topological relations. In the future, a special handling of symmetric relations is planed.

Each node of the tree represents a feature which can be used to change wq. When a node is expanded, this entails dynamically the computation of features that are specializations of the feature of this node. Then, the new features appear as its children in the tree. For instance, in Figure 3b, the taxonomy of points of interest is visible under the feature type, and distance intervals are visible under the distance:<ALL feature. The root of the tree is ALL, i.e., the most general formula. Each node of the tree is rendered with an icon, a label, two numbers, and possibly an arrow. The label is the formula representing the feature. The style of the label is informative: underlined labels correspond to formulas shared by all the objects in wq, whereas blue labels indicate properties that discriminate them. The two numbers indicate a proportion: the count of objects in wq that the feature leads to, i.e. the support, out of the count total of objects sharing the feature. In Figure 3b, the counts next to the feature distance:[0.0,50.0]<ALL are both equal to 16, i.e. all geographical objects of the citymap context are within 50 meters of another object. Three actions are possible in the tree: (1) displaying more (resp. less) navigation links, i.e. expanding (resp. collapsing) a node by acting on its icon; (2) refining wq by selecting a label; (3) traversing a relation by selecting the arrow next to the node.

Example of Navigation

Just suppose that our traveller has left his luggage at the hotel and wants to have some recreation before having lunch. He looks at his LIS device, provides it with a new geographical object corresponding to its position (which we denote here). This entails the addition of distance relations (already displayed in the tree of Figure 3b) between the object here and the other points of interest of the context; the distances are computed on the basis of the shortest path, following streets. He then queries the system with:

wq = recreation
The LIS system provides him with the updated navigation tree of Figure 4a. The taxonomy of geographical objects (under feature type) has been reduced and now only contains the recreation feature. By expanding this feature, he can see 2 sub-features indicating 2 types of available recreation: cinema and public garden. The first count of the feature recreation indicates that only 3 geographical objects correspond to recreational areas. The other features of the tree have also been updated. For instance, we can see that 2 recreation places are connected to "Street A".

Prefering being outside, our traveller decides to restrict his choice to public gardens not too close to his actual position. So, in the tree, he selects the feature public garden, and manually modify wq so as to select public gardens located at more than 350 meters: wq = public garden ∃(distance :>= 350.0m).here

The navigation tree has been updated anew, and indicates him that two public gardens satisfy the query. By looking at the navigation tree, he can see the query increment connected>ALL denoting that some information about the topological organization of these gardens is available. Wanting more details about the environnement of the gardens, he traverses the connected relation by selecting the arrow next to the feature. This updates wq to: wq = ∃connected -1 .(public garden ∃(distance :>= 350.0m).here)

The navigation tree now displays information concerning 3 geographical objects topologically linked with a public garden (see Figure 4b). By looking at the feature type, he can see that two of these objects are streets leading to a garden, and that the other one belongs to the miscellaneous category. Just by selecting the misc feature and looking at the feature place name, our traveller can see that it corresponds to a lake which is in fact inside a public garden. To retrieve the corresponding garden, he then just has to follow backward the connected relation (query reversal) by clicking on connected -1 in the query box. Then wq becomes: 6 Benefits of using LCA to Query Geographical Data Regarding data organisation and retrieval, GIS have been widely influenced by Relational Database Management Systems (RDBMS) [START_REF] Laurini | Fundamentals of Spatial Information Systems[END_REF]. Most of the time, geographical information is structured into thematic layers, i.e., a layer for the streets, another for the points of interest, etc. Recently, XML-based formats for geographical data [START_REF] Cox | Geography Markup Language (GML) Encoding Spec. Open Geospatial Consortium[END_REF] allow to consider collections of heterogeneous geographical objects. But in every instance, retrieving data is done using querying interfaces and querying languages (XQuery-like or SQL-like) that integrate spatial predicates.

Our proposal of using LCA to manage geographical data not only enables to build queries similar to traditional GIS queries, it also offers a flexible organization of the data. Our data model is centered on the geographical object and enables to consider each collection of objects that share a common description expressed by a query q as a kind of flexible layer that can serve as a basis for further processing. In GIS, traditionally, querying for data disseminated into several collections implies making as many sub-queries as collections and merging the results. This service is automatically provided by LCA but requires the descriptions of similar objects to be comparable. Concerning the querying capabilities, firstly, the querying language available in LCA (see Section 4), combined with the spatial logics of distance relation and topological relations, already enables to express most of the queries traditionally used in a GIS, as shown in Section 4.2.

For instance, concerning spatial queries, the formula ∃(distance:<=d).q enables to consider buffered areas of radius d around geographical objects described by q . Moreover, like with GIS traditional languages, these buffered areas can be combined using Boolean operators and nested in other spatial predicates. Secondly, the expressivity of LCA relies for one part on the sub-logics used to reason on object descriptions. But once a new logic has been designed for a particular purpose, e.g. comparing areas derived from geometrical descriptions, it can be added to the system without reconsidering the whole theory. This makes the LCA querying language powerful as it can be easily extended, and customized to handle particular data. Currently, compared to SQL or XQuery, LCA lacks the ability to express agregates, although this is an interesting field we plan to investigate.

An advantage of LCA compared to traditional GIS is the navigation tree. Even in dedicated map search tools such as the proximity business search of Google Maps , the results are always delivered as a flat textual list with bullets on a map, where no indication is given on the structure of the answer and on how to refine it. In comparison, the navigation tree offers at least three assets. First, the navigation links give at a glance a summarized description of the currently selected dataset. Then, these navigation links provide a querying vocabulary which allows to build a query from scratch even with no knowledge about the data. Last but not least, the navigation links enable to refine the current query in a relevant way, i.e., ensuring the answer will be reduced but not empty. Giving aid in the building of queries is also a contribition of the VISCO system [START_REF] Wessel | Visual spatial query languages: A semantics using description logic[END_REF]. In VISCO, description logics are used to query a spatial database in a visual way. Like our prototype, VISCO enables to represent and to reason about spatial properties, e.g. area or perimeter, and topoligical relations of geographical objects. In addition to querying capabities, VISCO also assists the user with query completion based on terminological default reasoning. However, contrary to our proposal, augmented queries may lead to empty answers because it does not take into account the content, but only the logic.

LCA also brings a new kind of navigation, the relational navigation. Considering a set of objects O that are instances of a query q and in relation r with other objects O described by f , i.e. the link ∃r.f is visible in the tree, one can directly jump to the related objects O . In the geographical domain, this provides facilities when querying data organized in several thematic collections. Compared to traditional GIS practices, this kind of navigation prevents the user from building sub-queries corresponding to search criteria depending on several layers and then combining or nesting these sub-queries in the right way. With the relational navigation, the search process can be fully incremental, and does not impose any order on the building of a query.

Conclusion

In this paper, we first show that LCA is a framework that enables to easily model spatial relations between geographical objects. Valued spatial relations such as distance can be expressed in an intuitive manner thanks to the expressivity of logics. Furthermore, thanks to the partial ordering between logical relations, LCA naturally integrates taxonomies of relations, such as topological relations. Then, we present an original way to explore geographical data, using a navigation based on spatial and non-spatial properties of objects, as well as on the spatial relations between geographical objects. Especially, we illustrate the benefits of this paradigm of geographical data exploration provided by LCA, compared to traditonal GIS querying capabilities.

In the future, we plan to make the update of relations automatic and incremental when the description of geographical objects changes, e.g. their position. We also plan to work on a graphical representation of relation features in order to enhance the readibility of the navigation tree and to assist the user in the building of queries involving spatial relations.

2 ,

 2 their inverse and their ordering w.r.t.

Fig. 2 .

 2 Fig.2. A taxonomy of spatial relations over 2 regions proposed in[START_REF] Wessel | Visual spatial query languages: A semantics using description logic[END_REF]. Leafs of the taxonomy correspond to the 8 base relations of the RCC-8 model.

  1 w.r.t. o 2 , and reciprocally, have been added in the relation context. At the moment, the computation of the relevant relation is done by an external GIS module. The logic L T opo 2 allows to build queries such as: q1 = type:building ¬ ∃touching . (type:building) q2 = type:cityBlock ∀contains . (type:lodging) q3 = type:road ∃touching . (place:'my home') ∃connected . (type:garden ∃contains . (type:lake))

2 = 2 )

 22 , allowing that descriptions of relations can include formulas from either L [m] 2 or L T opo 2

Fig. 3 .

 3 Fig. 3. Map of a city unfamiliar to our traveller (on the left), and the corresponding navigation tree (on the right).

Fig. 4 .

 4 Fig. 4. The citymap navigation tree at two different steps. In tree a, wq = recreation, in tree b, wq = ∃connected -1 .(public garden ∃(distance:>=350.0m).here)

  represents an ordered binary relation from o 1 to o 2 . Two mappings start and end are defined over

			Object context			Relation context
	type	title	year	style	name	age sex	plays directs
	f1 Film Pulp Fiction 1994 detective
	f2 Film Planet Terror 2007 Action
	f3 Film Die Hard 4 2007 Action
	f4 Film Death Proof 2007 Action
	p1 Artist				Bruce Willis	52 M
	p2 Artist			Robert Rodriguez 39 M
	p3 Artist			Quentin Tarantino 44 M
	R s.t. start((o, o )) = def o and end((o, o )) = def o . Furthermore, R is closed
	with an inverse operation -1 , i.e. for every pair r ∈ R, start(r -1 ) = end(r)
	and end(r -1 ) = start(r).

This work is funded by a scholarship from Région Bretagne.