Marie Le Guilly

Jean-Marc Petit
email: jean-marc.petit@insa-lyon.fr

Vasile-Marian Scuturici

Marie Le Guilly
email: marie.le-guilly@insa-lyon.fr

Marian Scuturici
email: marian.scuturici@insa-lyon.fr

SQL Query Completion for Data Exploration

come

Within the big data tsunami, relational databases and SQL are still there and remain mandatory in most of cases for accessing data. On the one hand, SQL is easy-to-use by non specialists and allows to identify pertinent initial data at the very beginning of the data exploration process. On the other hand, it is not always so easy to formulate SQL queries: nowadays, it is more and more frequent to have several databases available for one application domain, some of them with hundreds of tables and/or attributes. Identifying the pertinent conditions to select the desired data, or even identifying relevant attributes is far from trivial. To make it easier to write SQL queries, we propose the notion of SQL query completion: given a query, it suggests additional conditions to be added to its WHERE clause. This completion is semantic, as it relies on the data from the database, unlike current completion tools that are mostly syntactic. Since the process can be repeated over and over again -until the data analyst reaches her data of interest -, SQL query completion facilitates the exploration of databases. SQL query completion has been implemented in a SQL editor on top of a database management system. For the evaluation, two questions need to be studied: first, does the completion speed up the writing of SQL queries? Second, is the completion easily adopted by users? A thorough experiment has been conducted on a group of 70 computer science students divided in two groups (one with the completion and the other one without) to answer those questions. The results are positive and very promising.

INTRODUCTION

In the last few years, the database world has not escaped the Big Data phenomenon, that contributed to increase tremendously the volume of stored data: it is doubling in size every two years, and should reach 44 zetabyttes (10 21 ) by 2020 [START_REF] Rushby | The Wiley Handbook of Learning Technology[END_REF]. This has thus directly impacted the size of databases, at different levels. Nowadays, it is not unusual to see databases with several hundred of tables, some of them having several hundreds of attributes. For instance, the database used by the LSST 1 (Large Synoptic Survey Telescope) contains tables with hundreds of attributes (table Objects has 229 attributes for example), and a look at it is convincing to see that writing queries on such schemas are not trivial. Moreover, names of tables and attributes might not carry meaningful information, rending data accessing particularly difficult. Therefore, it is sometimes hard to find 1 http://lsst-web.ncsa.illinois.edu/schema/index.php the required information.

In addition to the increase of data volume and databases schema complexity, more and more people are in contact with databases. As the data is stored in order to be used and to get value out of it, those users are confronted to SQL queries in order to fetch data of interest. Both the data's volume and complexity, combined with the use by non-specialized users, make the query formulation process laborious: as a result, [START_REF] Nandi | Guided interaction: Rethinking the query-result paradigm[END_REF] found that data analysts spend more time on writing a query that the DBMS on processing it.

If more and more people are in contact with data and databases, and are therefore confronted to SQL query formulation, it is also because data they are trying to access have a potential value actionnable in their business. Analysts explore data in order to understand it, and to gain additional knowledge through this process. Data exploration tools are therefore crucial as they help users to go to interesting regions of their dataspace, and to identify relevant information or patterns in the data.

In databases, the first step of an exploration consists or is equivalent to the formulation of a SQL query, as it is a way to reach a specific set of data. Moreover, the conditions specified in such a query are already a way to characterize the data. This process is somehow related to web search engines that are used daily to reach specific websites, documents, etc, through keywords to describe what to look for. In this context, the task is easier than with databases from a user point of view: the language to express the query is not constrained, the syntax can be a bit loose . . . and more importantly, some help is provided to them: once the beginning of the search is typed in, the search engines suggests completions to the beginning of an input. These completions guide the search, by refining the idea, or by indicating keywords a user had not thought about. Such completions are based on the data indexed by the search engine, and also on user's history (previous researches, similar queries by other users..

.).

Problem statement To make it easier to write SQL queries, we propose the notion of SQL query completion:

Given an initial SQL query Q against a database d, suggest additional conditions to be added to the WHERE clause of Q such that the new query identifies a meaningful subset of the data identified by Q.

This semantic SQL query completion allows the exploration of databases, since the process can be iteratively repeated over and over again until the data analyst reaches In databases, some help is provided for query formulation, but it is mostly syntactic: SQL editors of leading database management systems propose auto-completion of keywords from the SQL Language, as well as dedicated SQL editors like SQL Complete2 or SQL Prompt3 . Basically, they fetch information for the database's schema to provide auto completion of tables and attributes names, which are a very simple form of semantic completion. However, this completion is only based on the schema, and surprisingly, does not look at all at the data contained in the database. Therefore the help offered by those completion systems is limited, as it does not contain any additional intelligence regarding the content of the database on which the query is evaluated. They only accelerate the process by suggesting information that an analyst would have to search in the schema or in a SQL handbook otherwise, and spare the user some manual writing.

There are also some works that have been done using user's history to suggests new queries. Such a solution is exposed in [START_REF] Çetintemel | Query steering for interactive data exploration[END_REF], to suggest queries based on previous queries asked by similar users. However, this is limited to presenting an already existing query.

Example 1.1. Let us assume that Alice, a data analyst, has access to the database of a company, containing data about employees, presented in table 1. She is asked to find information that can be valuable for the company in terms of discriminatory behaviour for female employees. After looking at some data samples, her first idea is to look for a correlation between the gender and salary of employees. Without any other intuition, she can start with the following simple query Q:

Select Gender , Salary From Employees

Although useful, it does not reveal anything to Alice. With the semantic completion proposed in this paper, Alice would have the choice to get help -without any new interaction with the system -from the three following completions of her initial query: These completions are relevant for Alice: the first one selects employees with a high commission. The two others select employees with a lower commission, among which they discriminate between male and female employees. And it seems that they are more women with low commission than men, which could indicate a discrimination in term of commission based on the gender of employees.

Therefore, those completions are a way to highlight an information and patterns which could be pertinent for Alice, but that would have been hard, or even impossible to find by just looking at the data.

Moreover, the commission attribute appears in completions, even though it was not considered pertinent enough by Alice in her initial query. It helps her to see that the discrimination might not be done on the salary as expected, but on the commission of female employees.

The above example is also useful to explain what a semantic query completion could be, and how it could be useful. Indeed, the following observations can be made:

• Q is contained in each of its completions, but they have additional conditions in their WHERE clause;

• They all lead to different result sets, exploring a different subspace of the initial query's result set. There is no new tuple that did not appear in the evaluation of Q, the completion is here a way to narrow down the initial result set;

• Each completion captures a different pattern in SQL, potentially meaningful;

• The completion is a way to draw attention on new attributes that might have been unnoticed.

This example gives the intuition of the type of SQL query completion proposed in this paper.

Paper contribution To the best of our knowledge, we study for the first time the problem of SQL query completion based on the semantic of the query to be completed. We have made the following contributions:

• A definition of a class of SQL query completion ;

• Given a database, a query and the number of desired completions, an algorithm to compute such completions that does not require any boring user input. The idea is to identify groups of similar tuples in the answer set of an initial query, and based on those groups, to build decision clauses to discriminate between them.

These decision clauses are then injected into the initial query in order to build new queries, that we call completions;

• An implementation of this algorithm in a SQL editor prototype;

• An experiment on a sample group of 70 computer science students, measuring the usefulness and the acceptability of such completions.

Paper organization Section 2 introduces the preliminaries and the definitions of SQL query completion. Section 3 exposes a solution to compute such completions. Then section 4 presents an implementation, and experimentations that were conducted to evaluate the completion in SQL. Finally section 5 summarises the related work, before concluding in section 6.

SQL QUERIES AND THEIR COMPLE-TIONS 2.1 Preliminaries

Let us start by introducing the basic notations to be used throughout this paper. We assume the reader is familiar with databases notations (see [START_REF] Levene | A Guided Tour of Relational Databases and Beyond[END_REF] for details). Let D be a set of constant and U a set of attributes. We consider a database d = {r1, r2, ..., rn} over a database schema R = {R1, R2, ...Rn}, where ri is a relation over a relation schema Ri and Ri ⊆ U, i ∈ 1..n. We consider the SQL and the relational algebra query languages without any restriction. We will switch between both languages when clear from context. A query Q is defined on a database schema R and ans(Q, d) is the result of the evaluation of Q against d. In the sequel, to define the completion of any query Q, we will use two operators: πX the projection defined as usual with X ⊆ U, and σF the selection, where F is a conjunction of atomic formulas of the form AθB or Aθv, with A, B ∈ U, v ∈ D and θ a binary operator in operation in the set {<, >, ≤, ≥, =, =}

Query completion

The simple question we have to answer is: How to define a completion of a query Q ?

Different kinds of completions can be imagined, and many different ways to compute them. However, as well as for search engine, a query's completion should help to narrow down the results. Therefore, the intuition is that if Qcmp is a completion of a query Q then ans(Qcmp, d) ⊆ ans(Q, d). However, many queries could comply with this property , some that might not be considered as completions of Q.

Example 2.1. Let Q1 and Q2 be the two queries over database presented in table 1.

Q 1 : Select EmpNo From Employees Where sex = 'F ' Q 2 : Select EmpNo From Employees Where Commission = 1300
The result of Q2 is contained in the result set of Q1 but Q2 is not a completion of Q1

To define query completion, additional conditions should be given at the syntactic level. This requires to formalize this relationship between a query and its completions.

Definition 1. The completion Qcmp of Q is defined by:

Qcmp = σc 1 ∧...∧cn (Q)
where ci is an atomic formula, for every i ∈ 1..n Specified like this, the number of queries that could be considered as completions is still infinite and it seems difficult, if not impossible, to give a meaningful definition of a single completion.

For this reason, we do not consider a single completion of a given query, but a set of k completions such that global properties can be defined, especially:

• The union of completions set of size k is equal to the initial data set represented by the initial query ; and

• Each completion is as much as possible dissimilar to each other.

We come up with the following definition.

Definition 2. A k-set completion of Q, denoted by CQ, is defined as: Cq = {Q1, Q2, ..., Q k } such that: • Qi is a completion of Q, for all i ∈ 1..k • ans(Qi, d) ∩ ans(Qj, d) = ∅, , for all i, j ∈ 1..k, i = j • k i=1 ans(Qi, d) = ans(Q, d)
Clearly, a k-set completion forms a partition of ans(Q, d).

Those restrictions provide a nice setting to see every completion as a good candidate to start a data exploration process.

COMPUTATION OF K-SET COMPLETION USING MACHINE LEARNING

We argue that computing k-set completions is a new problem, even if many subproblems have been studied for years in different communities, for example clustering in machine learning, query reverse engineering in database [START_REF] Tran | Query reverse engineering[END_REF] or redesciption mining in data mining [START_REF] Parida | Redescription mining: Structure theory and algorithms[END_REF]. In the sequel, we explain the solution based on a two-steps process.

Division of tuples via clustering

Taking into account definition 2 and the need for non similar answer sets for each completion, it is obvious that the division of the tuples in ans(Q, d) should not be random. The k sets obtained through this division have to be pairwise disjunct, and cover ans(Q, d) entirely. Moreover, they should be as different as possible. Clustering algorithms (see [START_REF] Han | Data Mining: Concepts and Techniques[END_REF] for an overview) offer a nice setting to provide effective approximate solutions.

In this paper, we focus ourselves on the k-means algorithm [START_REF] Lloyd | Least squares quantization in pcm[END_REF] since the parameter k is part of the input. This algorithm requires to be able to compute a distance between a given pair of tuples, which is feasible but sometimes tricky. More elaborated techniques is left for future work.

After the clustering, each tuple can be assigned to a single cluster, providing an unique opportunity to simplify drastically the role of the user in the boring task of tuple labelling. However, this label is only here for background completion computation, and is therefore not shown to the user.

Technically, a new attribute, called cluster, is added to the schema of the query to keep track of the cluster corresponding to each tuple. 1, with the additional attribute cluster that is the cluster tuples have been assigned to.

Construction of completions with a binary decision tree

The clustering addresses the first step of the solution. The second step is now to find at least one query to describe each of the clusters, if possible. It should be noted that in our approach, the clustering is done to offer an automatic labelling of tuples, based on a guided division of data, to avoid a manual labelling, and to reveal underlying groups of data. The decision tree will therefore try to discriminate between clusters, and even though the use of a clustering algorithm should facilitate the finding of meaningful discriminating clauses, the purpose is not do describe perfectly each cluster. We rather propose to use the clusters as "clever" labels.

Using decision trees to generate SQL queries is a technique that has already been exploited [START_REF] Cumin | Data exploration with sql using machine learning techniques[END_REF]. To be able to reach the objectives defined for our SQL completions, we follow the same path but with binary decision trees (BDT) [START_REF] Breiman | Classification and regression trees[END_REF], which is a tree splitting at each node on exactly two opposite conditions. In the sequel, we introduce an approach based on 1) the computation of a constrained BDT with k leaves from the data partition obtained before, and 2) the transformation of the BDT into SQL statements.

Obtaining a constrained BDT with k leaves from a given data partition

Clearly, we do not need to determine a full BDT since we just have to output k leaves from it, each leaf giving rise to one SQL completion. We assume our data allows the construction of a tree with at least k leaves. Constrained generation of BDT given a specific number of leaves has been studied in [START_REF] Wu | Decision tree induction with a constrained number of leaf nodes[END_REF]. In our case, we just need to explore levelwise the search space (breadth-first search) and stop as soon as the number of leaves exceeds k.

Indeed, the depth of the BDT is bounded by log 2 (k) and k -1. Both bounds are atteignable: the first one with a full binary tree and the second one with a right deep tree.

This optimisation turns out to be very efficient in practice.

To reach exactly the k leaves constraint, let us consider the figure 1: assume the number of leaves int the BDT is less than k a level i -1, and greater or equal to k at level k. If the number of leaves at level i is equal to k, then stop. Otherwise, while the number of leaves remains greater than k, replace two leaves at level i from the same parent by 1 turning this parent into a leaf at level i -1 (using a majority vote to assign a class to this new leaf).

Example 3.2. From the clustering in table 2, the binary decision tree of figure 2 can be obtained. In this running example, the decision tree leaves matches exactly with the clusters.

The previous example points out that the clustering and the binary decision tree may coincide. However, this is not true in general since some tuples may fall into the wrong cluster or some clusters could be lost by the binary decision tree. In a data exploration process, we argue this is not a real issue: the new queries proposed by our techniques are a first step to help the analyst to write her query.

Obtaining SQL statements from a BDT with k leaves

Once the binary tree has been constructed, each leaf can be reached through a unique decision path. The decision path from the root of the tree to a specific node can be written as the conjunction of each decision encountered along the road. This is why it is so convenient to go from a decision tree to a SQL query. After exploring all the path in the tree, each conjunction can be directly injected in the where clause of an SQL query, and therefore give a new completion.

Example 3.3. From the decision tree on figure 2, every completion from example 1.1 can be obtained easily.

Algorithm proposal

In order to combine the two steps described previously, and to specify how the completion set is to be computed, the algorithm 1 is proposed hereafter.

Lines 2-5, we identify first whether the outermost operator is a projection or not. In such a case, we remove it to augment the chances of clustering on pertinent attributes.

Algorithm 1: Query completion procedure

1 procedure Completion (Q, d, k); Input : A query Q over R, d a database over R, k the number of completions Output: Sc a set of k completions of Q 2 if Q = πX (Q ) ;
// remove the projection 3 then Indeed, data analysts do not necessarily select the attributes that are the most discriminant or the most interesting to learn on. Therefore, when evaluating the initial query, the returned attributes might not be the most useful to compute completions.

This first step consists in opening the query to as many attributes as possible within the tables concerned by the query. We have proposed a simple but effective solution, but there is still room for improvement, more attributes could be added or some attributes could be removed, especially those (string or categorical) with a very large number of different values.

Line 6, we compute the result set of the initial query. Clearly, if the size of the result is expected to be large, some restriction could be added to save time and ressources, for instance by limiting the output to the first 10 000 or 100 000 tuples or by using sampling techniques. Line 7, the clustering transforms the dataset wd into a labelled dataset lwd in which each tuple is labelled with the cluster it was assigned to. Line 8, a constrained BDT with k leaves is computed from the labelled dataset such that its number of leaves is equal to the k value. In other words, the BDT is built such that its depth is as small as possible while the number of leaves has to be equal to k, as explained in the previous section.

Lines 9-12 this procedure produces exactly k completions: for each leaf of the tree, the conjunction of clauses leading to it from the root is computed. This conjunction is then added to the selection clause of Q, creating a new completion.

The conditions from definition 2 are satisfied by the proposed algorithm as stated in the following property.

(Q, d, k) is a k-set completion of Q, i.e for {Q1, Q2, ...Q k } in completion(Q, d, k), and for all i, j ∈ 1..k, i = j: Qi is a completion of Q (1) ans(Qi, d) ∩ ans(Qj, d) = ∅ (2) k i=1 ans(Qi, d) = ans(Q, d) (3)
Proof.

(1) By construction, and with respect to definition 1, Qi is a completion of Q

(2) At each node of the binary decision tree, there is one split leading to the creation of two child nodes. This split is done on one attribute A, for one threshold value t if A is numeric or a value v otherwise. The first child node takes all tuples in the dataset for which A ≤ t (respectively A = v), the second child node takes the rest, i.e tuples for which A > t (respectively A = v) 4 . As a consequence, any tuple in the dataset reaches one and only one node at each split, and therefore one and only one leaf of the tree. As each completion corresponds to one leaf, they all contain different tuples from ans(Q, d).

( Clearly, we make use of machine learning algorithms that are currently well-known when solving various classification or prediction tasks. Usually those algorithms are fine-tuned to be perfectly fitted to the task at hand, requiring time and background knowledge from a data analyst [START_REF] Han | Data Mining: Concepts and Techniques[END_REF]. In our context, this is not possible, but optimal performance is not crucial.

The better the algorithm, the better the completions, but even with the double approximation from the clustering and the decision tree, the information from the completion set remains definitely useful as shown in the experiments.

IMPLEMENTATION AND EXPERIMEN-TATIONS

Algorithm implementation

Algorithm 1 was implemented using Python 3 and using SQLite5 as DBMS. For sake of simplification, the implementation is for now limited to numerical attributes. The kmeans algorithm is taken from the scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF] library. The binary decision tree classifier is also from this library, based on the CART algorithm [START_REF] Breiman | Classification and Regression Trees[END_REF], but adapted to comply with the constraint of the number of leaves.

SQL Editor Prototype

We also implemented a SQL editor Prototype, with a basic user interface, that in addition to basic SQL functionalities, offered the possibility of query completion. Also developed in Python, this interface consists in four distinct zones (see figure 3):

• A text field to write the query to be completed (A)

• A parameter field to specify the maximum number of completions to return (B)

• A zone to display the answer set of a query (C)

• A zone where the completion set of the input query is presented once computed (D)

Experimentations

The objectives of experimentation was to prove the utility of completion as presented in this paper. It was decided to explore two different categories of measures :

• How does the completion improves the query writing process: in terms of writing time, is it faster to write a query using completion ?

• How well can the completion be accepted by users ? Is it easy to use ? How well do users adapt to it ?

Organization

A group of 70 computer science student (last year bachelor students and master students) was gathered. They all had at least basic knowledge in SQL and data management. They all agreed to participate in a one hour experimentation that was meant to test the completion tool. They were initially only told that they would have to adress several SQL-related challenges.

Prior to the experiment, participants were randomly divided into two groups. The division was however balanced in terms of number of students from each level (bachelor, first year and second year master students). The experiment required to evaluate SQL queries on a database. For this, the first group (referred to as group CMP from now on) had access to the completion tool, while the other (referred to as group NoCMP from now on) had a tool that was designed to be similar to the one of group CMP, but without completion. This disposition was chosen to be able to compare the results of the two groups, i.e to see the difference between groups with and without completion, while working under similar conditions (softwares with similar functionalities in terms of classic querying tools).

Each group was asked the same ten questions on a database6 .

Design of the test

When conceiving the questions, our purpose was to propose a fair situation for groups CMP and NoCMP. For this reason, we eliminated several types of questions :

• Questions that were trivial with completion, but impossible to do without completion

• Questions for which completion has no interest: queries with empty result sets, dates comparison, specific operators from DBMS... All questions exposed a scenario, and then asked to find out the SQL query to solve the scenario. The questions were ordered from the easiest to the most difficult, and separated into two categories :

• The first three queries were classic SQL queries, that are typical of SQL lessons for beginners: they were questions directly and easily transformable into SQL queries, on which the completion tool was not useful. Those questions allowed to verify that each participant really had basic SQL skills. It was also a way to verify that group CMP and NoComp had similar results, and were therefore well balanced.

• The other questions (number 4 to 10) were designed to be more open-ended, in the sense that the conversion of the question into an SQL query was not straightforward. The purpose was to mimic the kind of loosely-specified questions a data analyst is confronted to when exploring unknown data, or answering questions from non-SQL users. The specification of questions was less strict, as selection conditions were not specified in terms of numbers, but using adjectives such as higher, bigger, lower, above average, low, etc. However, the final SQL query required to identify numerical conditions to discriminate between the tuples, and to translate the description of data given in the question. But even with those specifications, the level of difficulty for the second group of questions was not easy to settle: formulating those vague questions requires to choose carefully the vocabulary used in the question.

To help the NoCMP group, and make sure they would still be able to complete the test, we added to types of information. First, we provided the number of tuples each query was supposed to return, to provide an indication. Second, for some questions, we proposed data visualizations and asked participants to formulate queries that would return specific datapoints of these visualizations. This was a way to ask participant to transform a visual pattern into a query, so they had to identify the pertinent conditions to characterize the given pattern.

Participants had one hour to answer the 10 questions. They had to read the question, use the tool to write queries and evaluate them on the database, and once they thought they had the right query, they had to submit it online. They were not told whether their answer was right or not: in a real life scenario, analysts have to know themselves if they reach their desired data or not. During the hour of experimentation, we were able to monitor the time each participant spent on each questions. After the experiment, we also checked whether the answers they submitted were correct or not. Moreover, we were able to say, for each question, if participants from group CMP had used completion or not to generate their submitted query.

At the same time, group CMP had to deal with an additional difficulty, as they had to handle the completion tool. Indeed, they had never used it before, and they did not receive any specific formation on how to use the tool before the test. They were only given a one-page instruction sheet on how completion worked (see website 7 ). But they did not get any additional time, and had to use the hour to both answer the questions and master the completion (even though they were not forced to use it). This was done to avoid influencing them on their use of the completion, and to see how they would adapt to this new functionality.

Results

Validation of experimental setup.

First, we validated that the constraint specified for question formulation. The objectives were fulfilled regarding the difficulty of questions as well as equity between groups. On figure 4 and5, we can see how participants felt regarding the difficulty of questions. In both groups, only 3.4% of participants felt like questions were too difficult. In both case, the majority of participants felt like questions were correctly ordered from easiest to more difficult. The only difference is that more people in group CMP felt like questions were too easy (31.1% against 6.9%), as the completion tool helped them in answering the questions that were supposed to be really difficult.

On this first evaluation, we met our objectives with respect to our questions difficulty. This is also an indication that query completion can make answering SQL questions easier for users.

Completion and query writing time.

To analyze the impact of completion regarding query writing time, the first result that is interesting to look at is how much time did each group spend on average answering each question: those results are presented on figure 6. There are several interesting points to notice on this figure : • For questions 1 to 3, the results of the two groups are similar, which was actually the initial objective. When completion was not necessary, the performance of both groups were equivalent.

• Question 4 was easy for both group, as could be expected as the visualization was here to help . Even though completion could have helped on this question, it does not seem to have made a difference, as the average answering time is very similar for both groups. This means that completion is not necessary if a good visualisation is available to the user.

• For questions 5 to 10, the difference between the two groups is much more important and it seems clear that group CMP performed considerably faster than group NoCMP. This is a strong argument to support the fact that SQL query completion can indeed make the SQL query writing faster. The difference is stronger for questions 7 and 8, which seem to have been the most difficult questions for participants.

However, figure 6 takes into account all answers from participants, which means that some of those answers might be wrong. And a participant who did not gave a good answer might have spent a lot of time on a question looking for the answer without finding it, or on the contrary given up quickly as he did not know how to fnd the answer. For this reason, figure 6 was recomputed, taking into account only the answering time from participants who had given the correct answer for the considered question: such results are presented on figure 7. The tendency is similar, and group Actually, results from group CMP are even slightly better, especially for more complex queries like for question 7 and 8.

To understand the behaviour of participants, it is possible to look at the boxplot of answering time per question for each group, on figure 8, which also take into account only correct answers. The main observation is that results of group CMP are much more packed than for group NoCMP: participants who had access to completion had a way to help them if they were stuck on a question, contrary to group NoCMP participant who had to search by themselves until they identified the answer. This is flagrant once again for question 7, where someone spent more than 25 minutes looking for the answer.

On this second evaluation, our initial objectives are completed: when evaluated in similar conditions, the group with access to completion performed faster than the group with only classic SQL tools.

Completion acceptance.

As mentioned previously, it was also possible to say whether a participant had used completion for a given question or not. The proportion of completion use per question is presented on figure 9. We only presented question 4 to 10 on which completion was possible. It can be seen on this figure that participants did not always use the completion tool. In total, 70% of participants used completion at least once, while the others completed the test without using it.

Additional results were analysed to understand those observations. We first analysed, the way participants had used completion: on figure 10, interesting patterns can be observed. The main observation to do is that once participants have used completion for a question, they are very likely to use again in the next question. This is indicated by the continuous blue lines on this figure. This is a really important result, as it showed that once a user has understood the utility of completion, he will use it again. This observation is particularly true for participants number 1 to 13, which Figure 10: Type of answer per question, for participants who used completion during the test in addition did not make many mistakes. Participants 14 to 19 also used completion a lot after their first use, but made more mistakes: when looking at their answering time, it seems that they did not have much time to complete the last questions, and therefore might have been in a rush and did not give correct answers. Finally, participants 20 to 24 seem to have tested completion, but preferred to finish the test without using it.

On figure 11, we divided group CMP into two groups for each question: participants who had submitted a query generated with completion (group CMP1), and others participants from group CMP in group CMP2. We then compared their average answering time for each questions, as well as for group NoCMP. It should be noticed that for each question groups CMP1 and CMP2 might be different as participant who used completion are different from one question to another. First, on question 4, group CMP1 is slower: as it is the first question on which completion could be used, we interpret this as the time necessary for participant to get familiar with the completion tool. Moreovoer, even though group CMP2 answered without completion, its behaviour is different from group NoCMP on question 4 to 10. Indeed, except for question 10 where it is the slowest group (but on previous figures, question 10 always has specific behaviours), the tendency of group CMP2 is closer to the one of group CMP1 than to the one of group NoCMP. This is explained by the fact that participants who did not use completion in group CMP were students good enough in SQL to be able to answer the question quickly: for them, taking the time to understand the completion tool would have been a waste of time as they were comfortable enough in SQLn an had enough information, to succeed the test without it. This correlates with figure 12: based on the participants study year and their self-estimated level in SQL, we divided group CMP into three categories of participants, novices, intermediates and experts. We then looked, for each category, what proportion of participants had used completion at least once. The results from figure 12 show that the group that used it the most is the one for intermediate level. Expert used it less, because as we explained, they were comfortable enough in SQL to answer questions quickly. More surprisingly, the novice category does not seem to have used it more than experts: the explanation for this is found when looking at the queries submitted by participants from this group. They tried to find queries more complicated than they actually were, as they had a really scholar approach of the test.

To summarize, we believe those thorough experimentations have reach their goals. We demonstrated that the group with the completion tool performed faster than the one without: on average, group CMP completed the test in 32 minutes, against 48 minutes for group NoCMP. This is not only because the tool allows to write faster, but mostly because it identifies conditions that take much more time to find manually, as it requires to try several values before finding the pertinent one. We saw that the tool is well accepted, depending of the participant's context and level in SQL: moreover, we showed that the use of completion was not a single isolated try by participants, but that a first use encouraged them to use it again. Once you got it, you have it forever.

RELATED WORK

As far as we know, SQL query completion is a new problem that has not been studied yet. Nevertheless, related contributions exists in the context of data exploration. The closest example is in [START_REF] Khoussainova | Snipsuggest: Context-aware autocompletion for sql[END_REF], that proposes an autocompletion tool for SQL, that provides context aware assistance in SQL queries writing. Even though it can suggest completions in various SQL clauses, the completions offered rely mostly on the schema and on the database's log, and does not look at the data itself contrary to our approach that relies on the database's content. Many approaches try to infer query based on example tuples, which are tuples manually labelled by the user. Among those we can cite [START_REF] Shen | Discovering queries based on example tuples[END_REF] that suggest a set of queries returning such example tuples. Another example is [START_REF] Bonifati | Interactive join query inference with jim[END_REF], where the objective is to infer the join query that will return the result expected by the user. Those approach are similar to ours in the sense that their purpose if to help query formulation. However, the labelling done by the user is a additional task she has to do in addition to the usual ones. In comparison, we only ask an input query from the user. The clustering phase of our solution is in charge of the labelling, which means many more tuples can be labelled as it is automatic. Moreover, it can lead the user to consider data she had not thought about before.

If we take the various component of the solution presented in this paper, they can be linked to several research areas. First, Reverse query engineering [START_REF] Tran | Query reverse engineering[END_REF][START_REF] Zhang | Reverse engineering complex join queries[END_REF] considers the following problem: given a tuple set T in a database d, find a query Q such that ans(Q, d) = T . Many theoretical results exist with respect to the language permitted to express Q, conjunctive queries and variants. This is what we do with the decision tree used to formulate a query returning the tuples from a cluster. However, in our context, some simplification is permitted since part of the query is known. Second, Redesciption mining [START_REF] Parida | Redescription mining: Structure theory and algorithms[END_REF] unifies considerations of conceptual clustering, constructive induction, and logical formula discovery. Nevertheless, they do not consider at all SQL queries as we do, and are interested in enumerating all possible redescriptions verifying some conditions, with enumeration techniques quite different from our proposition. Decision trees in databases have also been studied in various forms: in [START_REF] Cumin | Data exploration with sql using machine learning techniques[END_REF] they are used to reformulate in query for data exploration. We can also mention works on integrating decision trees into databases as objects that can be stored and queried, such as in [START_REF] Fromont | Integrating decision tree learning into inductive databases[END_REF] or [START_REF] Rehman | Enabling decision tree classification in database systems through pre-computation[END_REF]. Also related to our solution are predictive cluster trees that combine those two method into one [START_REF] Liu | Clustering through decision tree construction[END_REF].

Many recent works concern interactive data exploration in database, with techniques aiming at helping user understand and discover their data using machine learning. Some examples of such works are exposed in [START_REF] Papaemmanouil | Interactive data exploration via machine learning models[END_REF]. Many of those approaches also rely on manually labelled tuples : we can cite the AIDE framework offers [START_REF] Dimitriadou | AIDE: an active learning-based approach for interactive data exploration[END_REF] that tries to learn what tuples are of relevance for the user and which are not. The machine learning phase is essentially based on decision trees and SVM. Thereafter, this process was improved in [START_REF] Papaemmanouil | Interactive data exploration via machine learning models[END_REF], by using even more machine learning. This second paper uses the same framework, but completes it by identifying underlying user habits based on their labeling. Those habits are turned into attributes used in a clustering. This way, similar users are identified, which is used for speeding the process by using previous data exploration by similar users to give even more relevant tuples. We can see here many similar features with our query completion proposal. However once again those approaches require more work from the user.

More generally, there is a part of research trying to bridge the gap between machine learning and database. Surajit Chaudhuri in [START_REF] Chaudhuri | Data mining and database systems: Where is the intersection?[END_REF] argues that bringing databases and machine learning algorithms closer might only be beneficial in terms of performance. More concrete applications of this has actually been done, such as in [START_REF] Zou | Data Mining Using Relational Database Management Systems[END_REF] where an entire machine learning library has been adapted so that it is compatible with a storage of data in a DBMS instead of a data structure in main memory. Moreover, they also adapted the algorithms in order to make use of native SQL operators. There is also [START_REF] Wang | Atlas: A small but complete sql extension for data mining and data streams[END_REF] which is a SQL extension for data mining.

In conclusion, we can see that this query completion framework is part of a general branch of research towards data exploration, which is motivated by the new challenges that Big Data and the evolution of data science are bringing.

CONCLUSION

In this paper, we have adapted for the first time the powerful notion of completion to SQL queries, which could be particularly useful for data analysts in a data exploration process or for SQL developers. This functionality is a natural extension of SQL and could be integrated in every SQL editors associated to database management systems (DBMS).

Without any intervention required for the user, any SQL query can be completed automatically and should give rise to new ideas, new paths to the user in her quest to the elicitation of her data of interest. The completion is semantic, and relies on the data contained in the answer set of this initial query. The approach is based on classical machine learning algorithms, adapted to fit into the definition of the completion we have proposed.

A SQL editor prototype has been developed on top of which experimentations have been conducted over a set of 70 participants. It demonstrate the pertinence of such a tool in current DBMS: not only do participants get adapted to it easily, but it also allows to considerably improve and facilitate the SQL query writing process in the considered context. Contrary to syntactic completion tool, our approach does not only improve the writing itself, but it helps the analysts to identify data and to limit the number of iteration she has to do to identify relevant conditions to reach desired data.

In the current context where more and more data is being stored and analysed, such a proposal is a real help for data exploration, to assist analysts confronted to unknown databases, using completions to navigate and understand the data. Moreover, the solution is iterative and allows the user to modify a completion and to continue until she reaches what she was looking for. The completion is also a way to integrate knowledge on data, usually provided by data mining systems and tools, without leaving the context of DBMS.

Many extensions of this work can be envisioned, typically to extend the completion to different clauses of SQL, for instance the group by clause. This work is also a contribution to bridge the gap between database techniques and machine learning techniques.

Question 2 Maximum size limit authorized for a package is 9000 grams. However, some exceed this limit without being detected. Give the query to obtain the ID of packages whose weight exceed this limit. (Expected result size: 73 tuples)

Question 3 What query can you write to obtain the average length of packages sent less than 100 kilometers from your post office ? (Expected result size: 1 tuple) Question 4 A little bit interested by data analysis, a colleague of yours had, with a spreadsheet, visualized some curves from the database. By plotting packages prices against their height, he/she had noticed a group of packages very distinct and well separated from the others, which is presented on figure 13, and circled in red. Can you find the query that returns all packages belonging to this group ?(Expected result size: 33 tuples) Figure 13: Visualization for question 4

Question 5 According to some colleagues who've been working here for years, heaviest packages are the one going to very distant destinations. The intuition behind this is that has sending a package far away is expansive, customers many things in one package to compensate. Can you identify packages that do not comply with this, i.e that are not heavy but are sent far away ? (Expected result size: 13 tuples)

Question 6 Once at the regional sorting center, packages go through a machine that automatically sort them according to their destination. However, this machine is sometimes defective. Indeed, when a package is less than 480g, the machine does not always detect it, and a operator has to take it and process it manually. This phenomenon is marginal, but more likely to happen if in addition to its light weight, the packages in small regarding its length and width. On all packages registered in your database, 12 have caused a problem. Which query can identify those 12 packages ? Question 7 Some packages are sent to a city that is very close to your post office, less than 10km away. Moreover, some are very light (less than 550g), and you wonder why people pay the post office to transport them while they would quite easily do it themselves. One of your colleagues has an hypothesis : maybe those packages are cumbersome and therefore hard to transport. Can you identify packages validating this hypothesis ? (Expected result size: 8 tuples) Question 8 A customer arrives at the post office, because he needs the ID of a package he had send, but isn't able to find. In order to help him, he gives you a few informations: the package was light, less than 450g and its dimensions (mainly length and width) were surprisingly big in regard to its weight. Can you give the query returning such a package ? (Expected result size: 1 tuple) Question 9 When working at the front desk, one of your colleagues made a mistakes on four on the packages he registered. Luckily, he remembers their length was above 140cm, and he therefore applied a special tarification, as those kind of packages are more complicated to deliver due to their size. But he applied the wrong tarification, and those packages have therefore an abnormally elevated price. Can you identify those packages ? (Expected result size: 4) Question 10 At question 2, you showed that 73 packages are above the weight limit. But your colleagues in charge of putting packages in the trucks say that a third of packages are really heavy, and require two employees to be lifted, in order to avoid back pains. Can you modify the query for question 2 in order to identify those packages ? (Expected result size : 3073 tuples)

Figure 1 :

 1 Figure 1: Construction of a binary decision tree given a fixed number of leaves

4 Q

 4 = Q' 5 end 6 wd = ans(Q, d) ; // wd: working data 7 lwd = kmeans(wd, k) ; // lwd: labelled wd 8 treeWithKLeaves = LevelwiseBDT (lwd, k) 9 conjunctions = getRules(treeWithKLeaves) 10 Sc = {} 11 foreach c in conjunctions do 12 Sc = Sc ∪ σc(Q) 13 end 14 return Sc;

Property 1 .

 1 Let d a database over R, Q a query over R, and k an integer. completion

  ) By property of completion we have ans(Qi, d) ⊆ ans(Q, d), so we obtain n i=1 ans(Qi, d) ⊆ ans(Q, d). Moreover, as a node splits on opposite conditions, any tuple from ans(Q, d) satisfies one and only one condition at each split. Therefore any tuple t from ans(Q, d) necessarily ends up in the result set of a completion, so there exists i ∈ 1..n such that t ∈ ans(Qi, d) and therefore n i=1 ans(Qi, d) ⊇ ans(Q, d).

Figure 3 :Figure 4 :

 34 Figure 3: SQL query completion prototype

Figure 5 :

 5 Figure 5: Difficulty of questions perceived by group NoCMP participants

Figure 6 :

 6 Figure 6: Histogram of average answering time per question, for group CMP and group NoCMP

Figure 7 :

 7 Figure 7: Histogram of average answering time per group, for each question, only for correct answers

Figure 8 :Figure 9 :

 89 Figure 8: Boxplot of answering time per question, for groups CMP and NoCMP, only for correct answers

Figure 11 :Figure 12 :

 1112 Figure 11: Histogram of average answering time for questions 4 to 10, for groups CMP1, CMP2 and NoCMP

Table 1 :

 1 Running example: Employees dataset her data of interest. To the best of our knowledge, such a form of SQL query completion has not been studied yet.

	EmpNo LastName Gender Salary Commission
	e10	SPEN	F	41160	1300
	e20	THOMP	M	41250	7400
	e30	KWAN	F	39850	5200
	e40	SMITH	F	40525	1400
	e50	GEYER	M	40175	1100
	e60	STERN	M	39560	6200
	e70	PULASKI	F	40120	800
	e80	FREY	M	40625	6600
	e90	HENDER	F	39450	6700
	e100	SPEN	M	41560	900

Table 2 :

 2 Employees dataset labelled by clustering Example 3.1.Table 2 presents tuples from table

	EmpNo LastName Sex Salary Commission Cluster
	e10	SPEN	F	41160	1300	2
	e20	THOMP	M	41250	7400	1
	e30	KWAN	F	39850	5200	2
	e40	SMITH	F	40525	1400	2
	e50	GEYER	M	40175	1100	3
	e60	STERN	M	39560	6200	1
	e70	PULASKI	F	40120	800	2
	e80	FREY	M	40625	6600	1
	e90	HENDER	F	39450	6700	1
	e100	SPEN	M	41560	900	3

https://www.devart.com/dbforge/sql/sqlcomplete/

https://www.red-gate.com/products/sql-development/ sql-prompt/

In case of null values on A, one of the two conditions of a split should integrate a test of the form A IS NULL, not to miss any tuple.

https://www.sqlite.org/

Note to the reviewers: the DB schema and corresponding questions are available in appendix at your discretion. All experimentation material is available online at https: //marielgy.github.io/sql experimentation/

https://marielgy.github.io/sql experimentation/

APPENDIX

The presentation of the database used for our experimentations, as well as the questions asked to the participants, are presented in this appendix.

A. EXPERIMENTATION SCENARIO

You're a new member of a post office, in charge of packages. When you're not at the front desk taking care of customers, you have access to data recorded about the packages sent from your post office. For simplification, we will focus on the packages leaving the post office to other destinations.

Here is how the database was created : Table Packages has one entry per package that left your post office. From the destination of a package, you can see how far it was sent, by joining tables Packages (11000 tuples) and Cities (30 tuples) on attributes destination and city ID.

Questions are ordered from easiest to hardest :you should therefore answer them in the given order. First three questions are simple, while the others are voluntary more complex, and finding the required SQL query in questions 4 to 10 required more exploration.

B. QUESTIONS

Question 1 This first question is here so that you can get familiar with the data and the tools at your disposal. Please test the two tools (SQL software and online form for answers) with the following query, that is a join between the two tables (Expected result size: 10 999 tuples):


Antoine Picot

Gérard Bailly
email: gerard.bailly@icp.inpg.fr

Frédéric Elisei

Stephan Raidt

Scrutinizing natural scenes: controlling the gaze of an embodied conversational agent

Keywords: embodied conversational agents, face-to-face interaction, eye gaze, talking face, visual scene analysis

We present here a system for controlling the eye gaze of a virtual embodied conversational agent able to perceive the physical environment in which it interacts. This system is inspired by known components of human visual attention system and reproduces its limitations in terms of visual acuity, sensitivity to movement, limitations of short-memory and object pursuit. The aim of this coupling between animation and visual scene analysis is to provide sense of presence and mutual attention to human interlocutors. After a brief introduction to this research project and a focused state of the art, we detail the components of our system and confront simulation results to eye gaze data collected from viewers observing the same natural scenes.

Introduction

We produce around 250.000 saccades per day. The eyes of the authors of this paper cover approximately 7m per second when screening computer screens. Multiple factors influence the intensive activity of our gaze control system: perceptive salience of various elements of our field of view (color, shape, motion, etc), their pertinence according to the purpose of the current scan (searching for a particular object or face, decoding the intentions of a human agent, etc) or the a priori knowledge we have on each element of the multimodal scene (familiarity, expectations, etc). The main objective of this work is to determine automatically the successive centers of interest that will likely attract the attention and the gaze of our Embodied Conversational Agent (ECA) observing a dynamic natural scene. We particularly propose a gaze control system that identifies and tracks regions of interest, weights their salience and pertinence regarding to the cognitive task, handles a stack of attention and couples visual analysis with an effective gaze control.

Such a strong coupling between a detailed multimodal scene analysis and motor control is necessary for developing ECA sensitive to changes of their real or virtual environment. The environment includes of course the interlocutors: the objective of this grounding of cognitive states and actions is to give to human partners tangible signs of presence and awareness. These cues have an important impact on information processing during interaction in terms of comprehension, belief and cognitive load.

After a brief state of the art where we will detail two major contributions that have inspired this work, we will describe our own proposal and illustrate its properties with concrete examples. This technical presentation is followed by a comparative evaluation with eye-tracking data collected on human subjects.

State of the art

In order to plan their displacements, mobile robots have multiple sensors to build and analyze representations of their surrounding environment. Designing human-aware planning strategies is now a very challenging issue [START_REF] Alami | Toward humanaware robot task planning[END_REF]. Most of anthropoid robots or companion robots are sophisticated scene analysis systems (mostly using vision) to analyze human behavior, identify their activities and plan adequate motor responses. Social robots developed at MIT [START_REF] Brooks | The Cog Project: Building a Humanoid Robot[END_REF] control sensory-motor loops where mutual attention is essential for acquiring and maintaining a common representation space. Maintaining eye contact as well as moving the head and eyes to signal interest or desire to take or leave turn are essential cues for signaling that the loop is effective. Robots developed at Waseda University exhibit such multimodal attention: Robita for example is able to follow a multi-speaker conversation, signal with head and gaze movements that it effectively tracks turns and is thus in a position to take part in the conversation [START_REF] Matsusaka | Conversation robot participating in group conversation[END_REF]. It is also able to understand and generate multimodal deictic gestures.

Most virtual conversational agents have often poor or none information on the actual environment where the interaction takes place. In absence of a grounded perception, their control model of gaze is often based on statistical regularities such as probability density functions of blinking frequency, amplitudes of ocular saccades or durations of eye fixations. Lee et al. [START_REF] Lee | Eyes alive[END_REF] have thus proposed a statistical control model that takes into account the current cognitive activity of the talking agent (notably listening vs. speaking). If the generated saccades are preferred to a fixed or random gaze, the model should benefit from a finer description of the cognitive activities [see 4 and Raidt et al, this volume] as well as an effective coupling with a scene analysis. Proposals made by Courty [START_REF] Courty | Animation référencée vision : de la tâche au comportement[END_REF] for virtual scenes or by Gu and Badler [START_REF] Gu | Visual attention and eye gaze during multipartite conversations with distractions[END_REF] for static natural scenes do not address exactly the problem of scrutinizing dynamic natural scenes.

The robot Rackham, developed by LAAS in Toulouse, combines advantages of sense of presence obtained by the performative actions of its body and the communicative actions of our virtual talking face displayed on a screen embedded in the robot (see Fig. 1.). A first coupling of the multimodal scene analysis performed by Rackham with the gaze controller of the talking face has been performed and evaluated [START_REF] Clodic | Rackham: an interactive robot-guide[END_REF].

The objective of the present work is to endow this coupling with a more sophisticated gaze controller, capable of reproducing essential characteristics of human visual attention (this paper) and face-to-face interaction (Raidt et al, this volume).

Behavioral data

The process by which our eyes explore our field of vision consists in a series of saccades and fixations. A fixation here includes an optional smooth pursuit occurring when fixating a moving region of interest. Saccades are rapid movements of the eyes (approx. 25-40ms, 200°/s) that bring the region of interest (ROI) in the central receptive field of the retina (fovea) for further high resolution spectral analysis. Saccades are thus followed by a first fixation (approx. 300ms) followed by corrective fixations [or refixations as amplified by 27 in reading] or a smooth pursuit in case of a slowly moving object of interest. These two main components of gaze trajectory correspond coarsely to two complementary cortical pathways: a dorsal-temporal "where" pathway responsible for localizing multisensorial events in the scene -often termed as the fly detector -and a ventral-parietal "what" pathway responsible for object identification [START_REF] Mishkin | Object vision and spatial vision: two cortical pathways[END_REF]. Jeannerod [START_REF] Jeannerod | The cognitive neuroscience of action[END_REF] prefers a more specific differentiation between a pragmatic (perception for action) vs. a semantic (perception for comprehension) analysis of the scene.

Scrutinizing a scene (still image or video) does not only consist in producing saccades towards the most salient object to the next: cognitive demands have a strong impact on the gaze trajectory and object selection [START_REF] Yarbus | Eye movements during perception of complex objects[END_REF]. Vatikiotis-Bateson et al [START_REF] Vatikiotis-Bateson | Eye movement of perceivers during audiovisual speech perception[END_REF] have also shown that eye movements during audiovisual speech perception are also influenced both by the comprehension task and environmental listening conditions (signal-to-noise ratio). Attention mechanisms have also a strong impact on scene analysis [see 24 for impressive experiments on inattention blindness].

Computational models of visual attention and scene analysis

Several computational models of visual attention and scene analysis have been proposed to mimic behavioral data. Numerous models for computing salience maps for still images and videos have been proposed to analyze, encode or summarize visual scenes. We present briefly two models that have attracted our attention because they both have exogenous and endogenous pathways while offering very complementary approaches (cf. Fig. 2

. ).

Itti et al [START_REF] Itti | Realistic avatar eye and head animation using a neurobiological model of visual attention[END_REF] propose a neurobiological model of visual attention for the control of the movement of the head and eyes of a video-realistic avatar. This model has three main components: (a) a map that associates a degree of intrinsic salience to each pixel of an image by combining several elementary salience maps (movement, orientation, intensity, and color) computed at different scales (using a pyramidal decomposition of the image); (b) a pertinence map that weights this previous map according to the cognitive demand [for an updated proposal, see 20] and (c) an attention map that takes in charge the sequencing of interest points computation by inhibiting zones of interest already scanned (often called inhibition of return mechanism or IOR).

The model of visual attention proposed by Sun [START_REF] Sun | Hierarchical object-based visual attention for machine vision[END_REF] is based on a prior hierarchical segmentation of the scene into objects. Elementary processing units are not pixels but segments. The model also performs a syntactic scene analysis organizing segments by salience (from the most salient segment at the largest scale to the smallest) and embedding (from the object to its constituents). Sun also introduces a temporary IOR that restores attention when the appearance of a given segment changes.

Our model of visual attention

Similarly to Itti et al., the front-end of our model (see Fig. 3. ) is a saliency map without prior segmentation. A segmented object is however attached to the most salient interest point in the image by thresholding locally the map. Descriptors of the texture of the segment (notably in contrast with the surrounding region using linear discriminant analysis) are stored in a stack of attention. They are used to track the segment when in motion and also detect segment changes for temporary IOR.

Visual attention is implemented as a stack of attention that temporarily memorizes the position and textural characteristics of segments previously scanned. The stack can function as a FIFO (First-In First-Out) or a LIFO (Last-In First-Out). The most frequent usage is FIFO: it implements a temporary IOR. Each time a new ROI is detected, it is analyzed by the visual system (gaze is directed to it and a minimum fixation interval is planned for object recognition) and pushed on the stack. When the stack is full, the oldest ROI is popped off the stack and discarded. For determining the next most salient object in the scene, we subtract the saliency of all stored items in the stack from the saliency map. A stored item can thus only be scrutinized again if it has been popped off the stack by new incoming items or if its salience (thus its position or appearance) has changed.

The analysis of the current ROI can however be interrupted in order to process an exogenous stimulus that is particularly salient. In this case the stack functions as a LIFO: the current ROI is pushed on the stack and popped from the stack once the exogenous stimulus has been processed [START_REF] Godijn | The relationship between exognenous and endogenous saccades and attention, in The mind's eye: cognitive and applied aspects of eye movement research[END_REF].

Our implementation of temporary IOR consists in reactivating a ROI that has changed compared to its stored characteristics or that gains back focus after its removal of the stack due to its limited storage capabilities (the stack has only 4 slots, i.e. possibility of maintaining attention to only 4 ROIs). We also added a smooth pursuit mechanism based on a ROI tracker using Kalman filtering. A module for recognizing and scrutinizing specific objects has also been added to enhance attention towards ROI with high potential interest such as faces.

Note finally that this system includes an effective coupling between saccade generation and visual analysis: a retinal filtering centered on the current position of the fovea cone is applied to the image before computing the saliency map that is thus sensitive to the eye movements. This differs from Itti et al [START_REF] Itti | Realistic avatar eye and head animation using a neurobiological model of visual attention[END_REF] implementation where the center of the retinal filter is always placed at the center of the screen. We do not assume that the camera is monitored by the eye gaze controller as it is usually the case for anthropoid robots [START_REF] Breazeal | Designing Sociable Robots[END_REF].

Saliency map

The saliency map combines the responses of two image processing modules: (a) a "where" module combines orientation (0° and 90°) and movement maps computed at different scales on the raw image and combined by a simple addition; (b) a "what" module combines color and intensity maps computed after the retinal filter. This filter convolves the raw image with a Gaussian filter centered on the current convergence of the eye gaze. The resulting image is blurred according to the distance of the pixel to the center of the field of view. The final saliency map is obtained by summing these two maps normalized by their respective variance (obtained experimentally using a 10mn video). The pixel that is the next target of visual attention is the pixel with maximum salience (Winner Take All or WTA).

Smooth pursuit

Fig. 3. Synopsis of the proposed system of visual attention. The saliency map is computed using the same scheme as Itti et al [START_REF] Itti | Realistic avatar eye and head animation using a neurobiological model of visual attention[END_REF] except the fact that the retinal filter is centered on the current point of gaze interest.

Attention stack

Contrary to Itti et al where the interest region is first removed of the attention map and returns slowly to attention using a relaxation process, we adopt an attention stack where the position and characteristics of the current ROI is temporally stored. This scheme is very alike the STM (short-term memory) system proposed by Peters & O'Sullivan [START_REF] Peters | Bottom-up visual attention for virtual human animation[END_REF] except that not all salient objects are stored in the stack and that their locations are effectively stored. The attention drop is just obtained by subtracting the memorized salience of the ROI to the global saliency map. It will thus inhibit the relevant ROI even if its salience is high or will reactivate it if its characteristics changes. The stack has only 4 elements and functions normally as a FIFO: storing a new ROI pops the oldest stored ROI off the stack. An element is thus popped off the stack either if it is too old or because its characteristics has changed (an object passing in the foreground may for example hide the object in the background stored in the ROI or lightening conditions of the ROI may change and enlighten the object for bringing renewed attention to this area). The stack may also function as a LIFO, when the fixation of the current ROI (average 160ms) is interrupted by the coming out of a very salient object in the scene: the current ROI is pushed on the stack, the new ROI is then processed immediately and eventually pursued, and then the memorized ROI is popped off the stack for finishing the WHAT processing.

Smooth pursuit

In the Itti et al and Sun's proposals, the only module that underlies a possible smooth pursuit is the movement map: the most salient pixel or ROI is expected to coincide with the object in motion. But this is rarely the case, especially when several objects are moving in the scene: this could result in alternating between several points of attention. We have thus added a special module dedicated to smooth pursuit -based on a Kalman filter -that updates the characteristics of the current ROI. The pursuit stops when the estimated speed of the object reaches a minimum threshold. In this mode, the gaze is anchored to the object trajectory and the pursuit has priority over salience computation: the saliency map is only renewed every 5 images in order to be able to process very salient exogenous stimuli (see previous section). Note also that the control module of the eyes direction uses the estimated speed of the object to anticipate the next position of the object. Our ECA scrutinizing natural scenes. For sake of presentation, the image currently processed is incrusted in a semi-transparent screen placed in front of the ECA. A black circle materializes the current interest point determined by our model of visual attention. The results are given for a few key images of two videos. Top: the subject waves a book in front of the ECA and the smooth pursuit module takes in charge the gaze controller. Bottom: another subject passes in the back of the interlocutor and triggers a saccade to pursue this new and important object of interest.

Specific objects: face detection

Human vision system is face-aware: the neural activity in a specific zone of the temporal lobe significantly increases when we observe faces (even truncated) vs. images without faces or with destructured faces [START_REF] Perrett | Visual neurones responsive to faces in the monkey temporal cortex[END_REF]. Such hardwired detectors enable us to focus rapidly on objects of the scene that are semantically very important. The saliency map receives thus a third input: a face detector [we used the built-in OpenCV detector based on 17]. Eyes and mouth detectors are also used [START_REF] Jiang | Detection of glasses in facial images[END_REF] to verify the hypothesis and trigger a face-aware gazing of the main elements of the face [26, see also Raidt et al, this volume] Fig. 5. Our virtual talking face is driven by 12 facial degrees-of-freedom [START_REF] Bailly | Degrees of freedom of facial movements in face-to-face conversational speech[END_REF]. The eyes and eyelids movements are controlled by 5 degrees-of-freedom that capture the correlations between gaze and eyelids deformations [START_REF] Bailly | Embodied conversational agents : computing and rendering realistic gaze patterns[END_REF].

Results and evaluation

We present here results obtained on two live videos. The model of visual attention has been coupled with a model of control of the eye gaze of an ECA [START_REF] Bailly | Embodied conversational agents : computing and rendering realistic gaze patterns[END_REF][START_REF] Casari | Contrôle du regard et des mouvements des paupières d'une tête parlante virtuelle[END_REF] (see also Fig. 5) that takes care of binocular coordination, saccade generation and microsaccades during fixations. The trajectories generated by this coupled control (see Fig. 4) have been compared with eye tracking data collected on 5 viewers. Subjects were instructed to view the same videos for further description of each scene to the experimenter. Fig. 4 shows the superposition of the screen coordinates of computed and captured centers of attention.

In Scene 1, one subject first waves a blue book in front of him with his right arm, then a red book with his left arm and then the two books with both arms. This first scene aims at validating our system handling smooth pursuit and the attention stack (since we can only gaze at one object at one time!). Fig. 4 illustrates the results when the subject moves the two books at the same time: the gaze follows the blue book while the red book is ignored and will never be stored in the stack. This inattentional blindness [START_REF] Simons | Gorillas in our midst: sustained inattentional blindness for dynamic events[END_REF] is also present in the occulometric data. The major differences between computed and observed gaze (see Fig. 6) is due to reaction time (our system detects changes more rapidly than human observers) and pursuit of movements (our system pursue the arm gesture although the carried object is outside of the field of view whereas the human viewers exploit causal links between these two movements and switch rapidly back to the subject's face).

In Scene 2, one subject in the foreground faces the camera while several other subjects walk in the background, stop behind his shoulders and look at the camera. This scene aims at validating our face detector and the stack in LIFO mode (the examination of the face of the main subject is often interrupted by the other subjects passing through). Fig. 4 illustrates the push and pop of the main ROI of the scene to treat an interruption. The major differences between computed and observed gaze (see Fig. 7) concern the ordinates: the saliency map is too sensitive to saturated colors of the T-shirts that override the salience provided by the face detector.

Performances

This algorithm has been implemented in C language under Linux Red Hat 9. It uses the OpenCV 0.9.9 Intel library. The tests have been run using a 2002 Pentium 4 desktop at 3.2 GHz. We are close to real time: the processing rate is close to 0.08s per image i.e. 12 images per second.

Conclusions and perspectives

We described here a system for scrutinizing natural scenes and its coupling with a controller of the gaze of an ECA. Original components for this model of visual attention have been proposed and implemented: a stack of attention, an integrated face detector and a module for smooth pursuit. This system has been confronted to natural scenes and its prediction has been compared with oculometric data. This confrontation has shown the efficiency of the system in predicting a large part of the observed human behavior. It has also shown limitations and tracks for improvement, notably the importance of top-down processes, cognitive processes and a priori knowledge. Mirroring the attention stack and the saliency map, we are planning to add an intention stack [START_REF] Chopra-Khullar | Where to look? Automating attending behaviors of virtual human characters[END_REF] and a pertinence map [START_REF] Navalpakkam | Modeling the influence of task on attention[END_REF] so that the ECA can concentrate its attention to the objects and events directly concerned with its cognitive tasks. Both will determine what to do with salient objects: task-dependent irrelevant ROI should be discarded from the saliency map with a different mechanism than the stack of attention. The pertinence map provides an efficient way to smooth out unimportant ROIs.

A long-term memory component [START_REF] Peters | Bottom-up visual attention for virtual human animation[END_REF] should be also added to feed the intention stack with desired characteristics of the search (location, aspect, etc) for matching objects. The face detector is part of this component: faces and facial expressions are in fact expected to bring more information and comprehension of the scene than other salient ROIs. We have already considered its coupling with a model of mutual attention developed for face-to-face conversation (see Raidt et al, this volume).

Our objective is to develop a real-time implementation of such a sophisticated model of visual attention to quantify its impact on live situated face-to-face interactions where ECA and subjects are involved in collaborative tasks. We have already shown that a pertinent control of multimodal deictic gestures of an ECA has a strong influence on reaction time [START_REF] Raidt | Does a virtual talking face generate proper multimodal cues to draw user's attention towards interest points?[END_REF] and plan to use a similar evaluation paradigm for assessing mutual attention. Fig. 6. Comparing the displacement of the gaze focus (top: horizontal; bottom: vertical) predicted by our system with oculometric data (displayed as gauges with means and standard deviations) for scene 1. The major discrepancies are underlined. At t=6s, our system follows the arm movement while viewers go back to the face of the subject (see text for explanation).

Fig. 1 .

 1 Fig. 1. The Rackham robot interacting with a child (© LAAS Toulouse)

Fig. 2 .

 2 Fig. 2. Models for observing natural scenes. Left: eye saccades of the ECA developed by Itty et al [13] are sequenced by points of interest computed from a video input. Right: Sun [25] uses a multi-scale segmentation to scrutinize an image by successive zoom-ins and -outs.

Fig. 4 .

 4 Fig. 4.Our ECA scrutinizing natural scenes. For sake of presentation, the image currently processed is incrusted in a semi-transparent screen placed in front of the ECA. A black circle materializes the current interest point determined by our model of visual attention. The results are given for a few key images of two videos. Top: the subject waves a book in front of the ECA and the smooth pursuit module takes in charge the gaze controller. Bottom: another subject passes in the back of the interlocutor and triggers a saccade to pursue this new and important object of interest.

Fig. 7 .

 7 Fig. 7. Same as Fig. 6. but for scene 2. The gaze is often attracted by T-shirts (lower coordinates than faces, see text for explanation).

Acknowledgements. This work has been financed by the project « scrutation de scènes multimodales » supported by ELESA, the project « Deixis Multimodale » supported by GIS PEGASUS, and the project « Présence » of the cluster ISLE supported by Rhones-Alpes. A first implementation of the model proposed by Itti et al has been done by Romain Rossi.

Left


The SCOTCH way 3. Handling sub-architectures in SCOTCH 4. Conclusion

Context

Current trend in high-end computer architectures • Combine features from all the paths followed in the past 50 years • Very large numbers of PEs -Above the million for exascale-class machines -Small(er) amounts of memory per PE

• Non uniform architectures -Mix of the distributed-and shared-memory paradigms -Communication latency and bandwidth depends on the respective locations of intercommunicating processes

• Hierarchical architectures -Clusters of multiprocessor blades -Multi-or even many-core processors Impact on application software

• Target architectures have to be taken into account -Data locality is essential to achieve performance

• Writing and running software is likely to become more complex -Task-based programming models, runtime environments, etc.

• Interactions between software and system components will become the norm -Especially, the batch scheduler should tell the application what processing elements it assigns for its execution

• Process and/or data placement tools have to take scheduler information into account

2

The SCOTCH way

The SCOTCH project

• Toolbox of graph partitioning methods, which can be used in numerous contexts Partial cost function

• Distance information regarding external edges accounts for current knowledge within the recursive bi-mapping process • Based on a graph representation of the target architecture • Described by two elements:

f C (τ S,T , ρ S,T ) = v ∈ V (S ) {v , v } ∈ E(S) w({v , v }) |ρ S,T ({v , v })| D 0 D 1 D D 0 D 1 D F. Pellegrini & C. Lachat -
-Vertex labeling: describes the bipartitioning tree -Distance matrix: shortest distance between all processing elements

• Vertex labeling is defined through recursive bipartitioning

Algorithmically-defined architectures

• Provide all the necessary information thanks to hard-coded routines • Algorithmically-defined architectures are implemented as instances of an abstract "class" -E.g.: mesh2D, hcub, etc.

-The decomposition-defined architecture module also falls in this category, yet values are read from tables rather than being computed on the fly • Algorithmically-defined architectures can only describe complete computer systems -A part of a torus is not a torus! -Disconnected parts are not managed, either

• The decomposition-defined architecture is not scalable • Recursive bipartitioning makes sense only when all vertices and edges of the target architecture are meaningful

1 1 0 0 1 1 0 1
• We want to extract locality information out of the target architecture so as to bipartition the source graph in a way consistent with processor allocation • Multilevel is the usual suspect when thinking about locality • Recursive matching and coarsening allows one to build a locality-based bipartitioning tree of the sub-architecture

1 1 0 0 1 1 0 1 1 1 1 0 2 1 3 1 1 4 5
• By traversing the coarsening tree from its root, one can build a locality-preserving bipartitioning tree • Recursive coarsening is traditionally performed using:

-A graph description of the original architecture -Matchings that are computed on the given graphs

• In fact, we only need the matching to build the bipartition tree -Distances will be computed algorithmically and do not require graph data • Graph representation is mandatory to compute:

-Matchings -Distances

• That sounds much like the original deco architecture...

-But we want to get rid of the O(P 2 ) storage!

• In fact, we do not want exact distances -We just want to sort out local edges from long-distance edges • Mapping of bump on the previous subset of the 4x2 2D mesh:

-Relative average difference in distances between deco0 and deco2: 0.60

F

•F--

  Sequential SCOTCH library (v6.0) -Graph and mesh partitioning -Static mapping (edge dilation) -Graph and mesh reordering -Clustering -Graph repartitioning and remapping • Parallel PT-SCOTCH library (v6.1) -Graph partitioning (edge) -Static mapping (edge dilation) -Graph reordering -Graph repartitioning, remapping F. Pellegrini & C. Lachat -Mapping onto Architecture Parts -SIAM CS&E -March 18, 2015 Static Mapping • Defined as two applications from V (S) and E(S) of source graph S to V (T ) and {E(T )} * of target architecture graph T , respectively T S Communication cost function accounts for distance f C (τ S,T , ρ S,T ) = e S ∈E(S) w(e S )|ρ S,T (e S )| • SCOTCH was designed to compute mappings since its inception in 1992 Create a family of topologically equivalent coarser graphs by clustering groups of vertices -Compute an initial partition of the smallest graph -Propagate back the result, with local refinement • Speeds-up computations • Improves partition quality • Used both for k-way partitioning and bi-partitioning Follows a "divide & conquer" approach • Associates a part of the source graph to each part the target graph • Until each target subgraph is reduced to a single vertex, do: -Bipartition target graph -Use target graph bipartition imbalance to bipartition associated source graph F. Pellegrini & C. Lachat -Mapping onto Architecture Parts -SIAM CS&E -March 18, 2015

-

  Mapping onto Architecture Parts -SIAM CS&E -March 18, 2015 Target graph descriptions • In order to evaluate the partial cost function while (bi)partitioning the source graph, a target architecture description must provide three abstractions: Domain structure: represents a set of processors in the target architecture -Domain bipartitioning function: bipartitions a given domain into two disjoint subdomains -Domain distance function: provides (an estimate of) the distance between two domains in the target architecture • SCOTCH implements two families of target architecture descriptions:

-F

  Distance matrix is in O(P 2 ) in space (and time) -Yet, it can manage disconnected parts

-

  Matching is a local process by nature! F. & C. Lachat -Mapping onto Architecture Parts -SIAM CS&E -March 18, 2015

•F

  Tree is unbalanced but processors are distributed that way

•

  Multilevel architecture descriptions allow one to describe efficiently (disconnected parts of) large architectures • To date, implemented in SCOTCH only, not in PT-SCOTCH -Released soon in SCOTCH 6.0.5• PT-SCOTCH is planned to perform parallel static mapping starting from branch 6.1

	Conclusion
	-Standard deviation of distance difference between deco0 and deco2: 0.36
	Mapping time for bump Edge cut Edge dilation Mapping time for bump Edge cut 4 Conclusion	deco0 deco2 0.02s 0.04s 525 531 657 549 deco0 deco2 0.11s 0.19s 6495 6740
	Edge dilation	11490 10374

• Mapping of bump onto a 16x16 2D mesh:

-Relative average difference in distances between deco0 and deco2: 0.58 -Standard deviation of distance difference between deco0 and deco2: 0.50 -Prototype available since the PhD of S ébastien Fourestier, but needs intensive regression testing before release F. Pellegrini & C. Lachat -Mapping onto Architecture Parts -SIAM CS&E -March 18, 2015

F. Pellegrini & C. Lachat -Mapping onto Architecture Parts -SIAM CS&E -March 18, 2015

F. & C. Lachat -Mapping onto Architecture Parts -SIAM CS&E -March 18, 2015


Antonio Costanzo
email: antonio.costanzo@inria.fr

Valeria Loscri
email: valeria.loscri@inria.fr

Demo: A Context Aware Algorithm for an Adaptive Visible Light Communication System

In this work we propose a context-aware and adaptive Visible Light Communication (VLC) system, able to dynamically react to the environmental changes in order to keep a good communication quality. In particular, we focus on a frame synchronization technique implemented by appending a preamble (repetitive insertion of sequences) to the transmitted data. The size N (number of bits) of the preamble impacts on the performance of the communication system. A short dimension of the preamble is to be preferred to reduce the control overhead (i.e. it is not carrying data information) but it could be not sufficient to perform a good carrier recovery in the case of noisy environmental conditions. This aspect has been modeled as a multi-arm bandit problem and a Thompson Sampling approach is used to find the best value of N for each next transmission frame. Experimental results show the impact played by a correct choice of the parameter N on the reduction of the recovered carrier frequency variance and Bit Error Ratio (BER) in different environmental conditions.

Introduction

Recently, Visible Light Communication systems have gained a lot of attention and several new challenges in respect of traditional communication systems need to be identified and addressed in order to make this technology pervasive and ubiquitous as it is in its potentiality [START_REF] Dimitrov | Principles of LED Light Communications: Towards Networked Li-Fi[END_REF] [START_REF] Heydariaan | Embedded visible light communication: Link measurements and interpretation[END_REF]. Despite to this success, there are still several challenges that need to be correctly identified and addressed. In this work, we propose an adpative context-aware system, to dynamically compute the length of preamble of transmitted data. To show the approach flexibility, the algorithm has been implemented on a couple of low cost VLC prototypes consisting in an Arduino board, a driving circuit and a led array in the transmitter, a photo-diode, a trans-impedance amplifier and a sec-ond Arduino board in the receiver, including a proper "Virtual Instrument", developed using the commercial software LabView. Since different conditions need different values of preamble length, the system must be able to gather information about its environment at any given time and adapt its behaviors accordingly (context awareness). Based on these premises, we propose a dynamic computation of N as ideal size of preamble for carrier recovery by modeling it as a multi-arm bandit problem and apply Thompson sampling to select in a fast and efficient way the best value of N [START_REF] Maskooki | Competition: Channel exploration/exploitation based on a thompson sampling approach in a radio cognitive environment[END_REF]. An agent tries to achieve as much award as possible by playing the most rewarding arm among J arms (being J the possible choices of the size N, in a limited sub-set). Each arm rewards randomly upon being played according to an unknown distribution. Our goal is the minimization of the exploration to find the most rewarding arm. The learning approach has been implemented to the receiver side. We assumed that after the receiver computes the ideal value of N, it communicates this value to the transmitter that will consequently adapt the next frame.

System and Algorithm Description

Let'us consider the agent A as the algorithm defining the actions performed by an agent based on previous observations. In particular, we assume n j as the number of times j th arm (the size of preamble) has played after n steps and µ j to be expected reward of j th arm. The preamble size N is found in average µ j n j times in n j measurements. In order to reduce errors due to a variation of the recovered carrier, the criterion trigger we apply is based on a real time Bit Error Ratio measurement in the receiving stage. Moreover, the evaluation of the variance σ f i 2 of the carrier detected frequency in output to the phase locked loop after the i th received frame, has been considered as an other important parameter for testing the performances of proposed system. We assume to have an observation vector collecting S j observations after that we have selected the same size j n j times. Each size selection is assumed as a Bernoulli distribution with parametric µ j characterizing the parametric likelihood function for S j as:

p j (S j |µ j ) = µ j t j (1 -µ j ) n j -t j , (1)
where t j is the number of times the best choice in terms of preamble size j has been done. We assume (without loss of generality) that the parameter µ j is characterized with a Beta distribution as the prior for the distribution. This choice is motivated by the fact that Beta distribution is conjugate prior for the likelihood function in Equation [START_REF] Dimitrov | Principles of LED Light Communications: Towards Networked Li-Fi[END_REF]. Based on Bayes rule we obtain:

p j (µ j |S j ) = p j (S j |µ j ) Γ(α+β) Γ(α)Γ(β) µ j α-1 (1 -µ j ) β-1 p j (S j ) , (2)
where,

Γ(α) = ∞ 0 x α-1 e -x dx (3)
and α and β are the shape parameters of the Beta distribution; we assume (as it is in real world), that we do not have prior information on µ j and then initial values for α = β = 1 which yields uniform distribution. Substituting (1) in (2) yields,

p j (µ j |S j ) = Γ(α+β) Γ(α)Γ(β)
p j (S j ) µ j t j +α-1 (1µ j ) n j -t j +β-1 . (4) α = t j + α and β = n jt j + β can re-write (4) as:

p j (µ j |S j ) = Cµ j α -1 (1 -µ j ) β -1 (5)
Substituting the normalizing factor C we obtain,

p j (µ j |S j ) = Γ(α + β ) Γ(α )Γ(β ) µ j α -1 (1 -µ j ) β -1 , (6)
which is the beta distribution with parameters α and β ,

p j (µ j |S j ) = beta(α , β ). (7)
Thompson sampling preamble length selection algorithm is described in Algorithm 1.

Evaluation Results

We have performed a set of measurements of Bit Error Ratio ( Fig. 1) and carrier variance (Fig. 2) in a same environments with different light conditions: closed windows and artificial lights turned off in the first scenario, open windows and lamps turned on in the second one, with a fixed distance of 2.5 meters between transmitter and receiver. Experimental results show how, in order to achieve an effective reduction of both BER and detected central carrier variation, the optimal value of the preamble length significantly changes when light conditions change. Our adaptive approach dynamically sets the shortest synchronization frame in the two scenarios, that corresponds to ∼ 10 in the case of low-noisy environment and ∼ 35 in the case of higher noise. This confirms the effectiveness of an adaptive approach in order to dynamically considering short synchronization frames in low noise conditions and increase it if the scenario changes. Statistics on preamble selections in a changeable environment and a comparison between our approach and fixed preambles will be provided in a foreseeable extension of this work.

Algorithm 1 Thompson Sampling

Parameters: J: total number of preamble lengths j: index of the current preamble length n: total number of transmitted frames s j : current state of the preamble length j BER j : current BER of the preamble length j BER th : BER threshold t j : number of successful transmissions so far x j : empirical mean of the overall j states, α and β: a priori (beta distribution) model parameter α and β : a posteriori (beta distribution) model parameter SEND FEEDBACK(): Communicate new preamble length Initialization: minBER f ound = FALSE; 1: for all j do s j = 0; 2: end for 3: for all j do 4:

if BER j < BER th and !minBER f ound then 5: s j = 1 ;min B ER f ound= TRUE; 6: end if 7: update t j , n j , α j and β j 8: end for 9: while True do 10: for all j do 11: sample p j ∼ beta(α j , β j ) 12:

end for 13: m = arg max{p j } 14:

if BER m < BER th then 15:

s m = 1 16: else 17: s m = 0 18: SEND FEEDBACK() 19:

end if 20: update t j , n j , α j and β j 21: end while

Figure 1 .

 1 Figure 1. BER for different values of preamble length.

Figure 2 .

 2 Figure 2. Variance of recovered central carriers for different values of preamble length.

Acknowledgements

This work was partially supported by CPER DATA and by 21eme FUI, Store Connect project.