Imene Mami
email: imen.mami@lirmm.fr

Remi Coletta
email: coletta@lirmm.fr

Zohra Bellahsene

Modeling view selection as a constraint satisfaction problem

Using materialized views can highly speed up the query processing time. This paper deals with the view selection issue, which consists in finding a set of views to materialize that minimizes the expected cost of evaluating the query workload, given a limited amount of resource such as total view maintenance cost and/or storage space. However, the solution space is huge since it entails a large number of possible combinations of views. For this matter, we have designed a solution involving constraint programming, which has proven to be a powerful approach for modeling and solving combinatorial problems. The efficiency of our method is evaluated using workloads consisting of queries over the schema of the TPC-H benchmark. We show experimentally that our approach provides an improvement in the solution quality (i.e., the quality of the obtained set of materialized views) in term of cost saving compared to genetic algorithm in limited time. Furthermore, our approach scales well with the query workload size.

Introduction

The information stored at the warehouse is often organized in materialized views which represent pre-computed portions of the most frequently asked queries [START_REF] Randall | Materialized views in oracle[END_REF]. Using materialized views can improve the performance and speed up the processing of queries since the access to materialized views can be much faster than recomputing the views. However, these materialized views have to be maintained in response to changes to the underlying base relations. In most cases it is wasteful to maintain a view by re-computing it from scratch. Often, it is cheaper to compute only the changes in the view to update its materialization which is called the incremental view maintenance.

Materializing all the input queries can achieve the lowest query cost but the highest view maintenance cost which can cause overhead to the system. Besides, the query result can be too large to fit in the available storage space. Hence, there is a need for selecting a set of views to materialize by taking into account three important features: query cost, view maintenance cost and storage space.

The problem of choosing which views to materialize that minimize the total query cost given a limited amount of resource such as total view maintenance cost and/or storage space is known as the view selection problem. This is one of the most challenging problems in data warehousing [START_REF] Widom | Research problems in data warehousing[END_REF]. The view selection problem is a NP-complete problem since the search space for the optimal solution grows exponentially as the problem size increases [START_REF] Gupta | Selection of views to materialize in a data warehouse[END_REF][START_REF] Gupta | Selection of views to materialize under a maintenance cost constraint[END_REF].

In this paper, we propose a new approach to the view selection problem which minimizes the total query cost under the case where (i) the limited resource is the total view maintenance cost, assuming unlimited amount of storage space if we consider that storage space is cheap and not regarded as a critical resource anymore and (ii) both space and maintenance cost constraints exist.

Although, several heuristic algorithms have been proposed in literature to solve the view selection problem such as deterministic algorithms i.e., greedy algorithms [START_REF] Gupta | Selection of views to materialize in a data warehouse[END_REF][START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF][START_REF] Gupta | Selection of views to materialize under a maintenance cost constraint[END_REF][START_REF] Roy | Efficient and extensible algorithms for multi query optimization[END_REF][START_REF] Mistry | Materialized view selection and maintenance using multi-query optimization[END_REF][START_REF] Mistry | Materialized view selection and maintenance using multi-query optimization[END_REF][START_REF] Satyanarayana | View relevance driven materialized view selection in data warehousing environment[END_REF][START_REF] Baril | Selection of materialized views: A cost-based approach[END_REF], randomized algorithms i.e., genetic algorithms [START_REF] Zhang | Genetic algorithm for materialized view selection in data warehouse environments[END_REF][START_REF] Lee | Speeding up materialized view selection in data warehouses using a randomized algorithm[END_REF][START_REF] Horng | Applying evolutionary algorithms to materialized view selection in a data warehouse[END_REF][START_REF] Xu | Materialized view selection as constrained evolutionary optimization[END_REF][START_REF] Lawrence | Multiobjective genetic algorithms for materialized view selection in olap data warehouses[END_REF][START_REF] Weiss | Towards materialized view selection for distributed databases[END_REF] and simulated annealing algorithms [START_REF] Kalnis | View selection using randomized search[END_REF][START_REF] Derakhshan | Simulated annealing for materialized view selection in data warehousing environment[END_REF][START_REF] Derakhshan | Parallel simulated annealing for materialized view selection in data warehousing environments[END_REF] or hybrid algorithms [START_REF] Zhang | An evolutionary approach to materialized views selection in a data warehouse environment[END_REF] which combine the strategies of pure deterministic algorithms and pure randomized algorithms.

These heuristic algorithms provide reasonably good solutions. However, there is no guarantee of performance because the greedy nature or the random characteristic of the algorithms may make them converging to poor local minima. An exact resolution for the view selection problem is prohibited since an exhaustive search cannot compute an optimal solution within a reasonable time due to the complexity of the problem.

Yet, over the past ten years, effective paradigms for exact resolution of NPcomplete problems have been proposed, such as constraint programming (CP), structured around annual competitions [START_REF] Lecoutre | Promoting robust black-box solvers through competitions[END_REF]. Furthermore, constraint programming has proven to be a powerful technique for modeling and solving combinatorial problems [START_REF] Dincbas | Solving large combinatorial problems in logic programming[END_REF]. We have designed a new approach for solving the view selection problem involving constraint programming. Our approach consists in modeling the view selection as a Constraint Satisfaction Problem (CSP). Our main contributions are:

1. We propose a new approach to the view selection problem. We model this problem as a constraint satisfaction problem (CSP). Then, a constraint programming (CP) solver can be applied to set up the search space by identifying a set of views that minimizes the total query cost. 2. We address the view selection under the case where (i) the limited resource is the total view maintenance cost, assuming unlimited amount of storage space if we consider that storage space is cheap and not regarded as a critical resource anymore and (ii) both space and maintenance cost constraints exist. 3. We highlight the anytime behavior of our approach which is able to provide a near optimal solution to the view selection problem during a given time interval. The quality of this solution may be improved over time (if the CPU time is available). 4. We have implemented our approach and compared it with a randomized method (i.e., genetic algorithm). We experimentally show that our approach provides better performance resulting from evaluating the quality of the solutions in term of cost savings and scales well with the query workload.

The rest of this paper is organized as follows. Section 2 describes the problem of view selection. Section 3 provides an overview of our approach and describes how to model the view selection problem as a constraint satisfaction problem (CSP). In section 4, are provided the experiments results. Section 5 contains a brief survey of related work. Finally, in section 6 we conclude and plan for future work.

Problem specification

The general problem of view selection is to select a set of views to be materialized that minimizes the cost of evaluating the query workload modeled by the frequently asked queries, given a limited amount of resource, e.g., total view maintenance cost and/or storage space. In this paper, we consider selectionprojection-join (SPJ) queries that may involve aggregation and group by clause as well.

In order to detect overlapping between queries of workload and capture the dependencies among the queries, the view selection is represented as an AND-OR view graph [START_REF] Gupta | Selection of views to materialize in a data warehouse[END_REF]. The union of all possible execution plans of each query forms an AND-OR view graph where the common sub-expressions are represented once. The AND-OR view graph is a Directed Acyclic Graph (DAG) composed of two types of nodes: Operation nodes (Op-nodes) and Equivalence nodes (Eqnodes). Each Op-node represents an algebraic expression (Select-Project-Join) with possible aggregate function. An OR-node represents a set of logical expressions that are equivalent (i.e., that yield the same result). The Op-nodes have only Eq-nodes as children and Eq-nodes have only Op-nodes as children. The root nodes are equivalence nodes representing the queries of workload and the leaf nodes represent the base relations. Equivalence nodes in the AND-OR view graph correspond to the views that are candidates for materialization.

A sample AND-OR view graph is shown in figure 1. Circles represent operation nodes and boxes represent equivalence nodes. For example, in this figure, view v 1 , corresponding to a single query, can be computed from v 3 and r 2 or v 4 and r 3 . If there is only one way to answer or update a given query, the graph becomes an AND view graph. We explore the view selection problem in the context of AND-OR view graph, which allows a single query to be answered and updated from multiple paths, since a good selection of materialized views can only be found by considering the optimization of both global processing plans and materialized view selection [START_REF] Zhang | An evolutionary approach to materialized views selection in a data warehouse environment[END_REF].

To each equivalence node which represents a view, is associated the following metadata:

-Query cost Qc which represents the cost of computing a view from its related base relations and/or views. -Maintenance cost M c which is the cost required for updating a view when the related base relation is changed. -Read cost Rc that denotes the size of the view. -Query frequency f q (if the equivalence node is a root node) which describes the frequency of posing a given query. -Update frequency f u which represents the frequency of updating a view in response to change to the underlying data.

The general view selection problem for AND-OR view graphs can be formulated as follows: Given an AND-OR view graph G, select the set of views to materialize that minimizes the total query cost under the following cases:

-Where only the maintenance cost constraint is considered. Here, we address the view selection problem by constraining the total maintenance cost needed to update the materialized views while assuming unlimited amount of storage space. -Where both maintenance cost and space constraints exist. In this case, we have a total maintenance cost limit but also a bound on the total storage space required to materialize the selected views.

3 A new approach to the view selection problem

Motivations

In this section, we present our approach for selecting a set of views to be materialized. The optimal solution is the one which selects the right materialized views (equivalence nodes) of the AND-OR view graph that minimizes the total query cost subject to certain constraints such as space and maintenance cost constraints. However, the search space for the optimal solution is very large since it entails a great number of comparisons between all possible subsets of views.

Our motivation to use constraint programming in solving the view selection problem is that it is known to be a powerful approach for modeling and solving combinatorial problems such as Job Shop Scheduling [START_REF] Caseau | Improved clp scheduling with task intervals[END_REF]. The success of using constraint programming for combinatorial optimization is due to its combination of these three features [START_REF] Wallace | Practical applications of constraint programming[END_REF]:

-High level modeling. Constraint programming provides a rich constraint language to model the problem as a Constraint Satisfaction Problem. In the following subsections, we give a formal definition of CSP and show how to model the view selection problem as a CSP. -Constraint propagation. This leads to a reduction of the search space, by excluding solutions where the constraints become inconsistent. For example, in the case of solving the view selection problem under the maintenance cost constraint, all the view combinations which violate this constraint are discarded. -Search. Constraint programming offers facilities to control the search behavior deciding which alternative (i.e., views combination) to try first.

Preliminaries

In this subsection, we introduce the CSP model that we have used in our approach. A constraint satisfaction problem (CSP) is composed of: A CSP consists in finding solutions by assigning values to its variables that satisfy all its constraints. Our approach consists in modeling the view selection problem as a CSP. Its resolution is supported automatically by constraint solver embedded in the constraint programming language.

-A set of variables V AR = {var 1 ,

Modeling View Selection Problem as a CSP

Formulating the view selection problem as a constraint satisfaction problem (CSP) consists in specifying the variables of the CSP, their domains, and the constraints that are over them in the context of view selection. In the following, we describe each part of the specification.

Variables & Domains

The variables of the CSP considered in modeling the view selection problem are:

-M at vi which denotes for each view v i (equivalence node in the AND-OR view graph) , if it is materialized or not materialized. It is a binary variable,

d M atv i =0,1 (0: v i is not materialized, 1: v i is materialized). -Qc(v i ) that

Constraints

The constraints which describe the relationship between the variables defined above are:

-The query and maintenance cost corresponding to a view are implemented by using a depth-first traversal of the AND-OR view graph. We use the cost formulae described in [START_REF] Roy | Efficient and extensible algorithms for multi query optimization[END_REF][START_REF] Mistry | Materialized view selection and maintenance using multi-query optimization[END_REF] to compute these two costs (defined in a recursive way).

Query Cost:

Qc(v i ) = ComputingCost(v i ) if M at vi = 0 min(ComputingCost(v i ), ReadingCost(v i )) otherwise ComputingCost(v i ) = min opj ∈child(vi)   cost(op j ) + v k ∈child(opj ) Qc(v k )  
The query cost corresponding to view v i which is an equivalence node in the AND-OR view graph, is the minimum cost paths from v i to its related views or base relations, if v i is not materialized. Otherwise, if v i is materialized, we use the minimum of the cost of reading v i and the minimum cost paths as defined above.

Each minimum cost path is composed of all the cost of executing the operation nodes on the path and the query cost corresponding to the related views or bases relations of v i . The costs of executing the operations: selection, join, projection and aggregation are estimated according to the formulas given in [START_REF] Chirkova | A formal perspective on the view selection problem[END_REF] for cost operation estimation. In this paper, these costs are calculated in terms of number of tuples in the involved relations.

View maintenance cost:

M c(v i ) = 0 if M at vi = 0 dr l ∈dif f Relations(vi) M cost(v i , dr l ) otherwise M cost(v i , dr l ) = min opj ∈child(vi)   cost(op j , dr l ) + v k ∈child(opj ) U pdatingCost(v k , dr l )   U pdatingCost(v k , dr l ) = M cost(v k , dr l ) if M at v k = 0 min(M cost(v k , dr l ), δ(v k , dr l )) otherwise
The maintenance cost of view v i , if it is materialized, is computed by summing the number of changes in the base relations from which v i is updated. If v i is not materialized, then there is no maintenance cost. We assume incremental maintenance to estimate the view maintenance cost. Therefore, the maintenance cost is the differential results of materialized views given the differential (updates) of the bases relations. Let δ(v i , dr l ) denotes the differential result of view v i , with respect to update dr l .

The view maintenance cost is computed similarly to the query cost, but the cost of each minimum path is composed of all the cost of executing the operation nodes with respect to update dr l on the path and the maintenance cost corresponding to the related views of v i . We have been inspired by the formula given in [START_REF] Mistry | Materialized view selection and maintenance using multi-query optimization[END_REF] for estimating the cost of executing the operation nodes in response to changes to the base relations.

-The total maintenance cost of the set of materialized views is less than U which is the total view maintenance cost limit.

vi∈V (G)

(M at vi * (f u (v i ) * M c(v i ))) ≤ U
Note that V (G) represents all the views in the AND-OR view graph, M c(v i ) is the cost of maintaining a materialized view v i and f u (v i ) is the update frequency of the view v i . Here, the view selection is decided under the maintenance cost constraint.

-The total space occupied by the materialized views M is less than S which is the maximum storage space.

vi∈V (G)

(M at vi * Rc(v i )) ≤ S Recall that Rc(v i )
is the size of the view v i . If the space constraint is considered, views are selected to be stored only if the necessary space for their materialization is at most S.

-Minimize the total query cost.

minimize   vi∈Q(G) (f q (v i ) * Qc(v i ))  
In this formula, Q(G) represents all the queries (root nodes in the AND-OR view graph), Qc(v i ) is the query cost of the view v i and f q (v i ) is the query frequency of the view v i . The total query cost is computed by summing over the cost of processing all the queries of workload.

Experimental Evaluation

We have implemented our approach and compared it with a randomized method because in previous studies [START_REF] Xu | Materialized view selection as constrained evolutionary optimization[END_REF][START_REF] Derakhshan | Simulated annealing for materialized view selection in data warehousing environment[END_REF][START_REF] Derakhshan | Parallel simulated annealing for materialized view selection in data warehousing environments[END_REF], it was shown that randomized algorithms provide a significant improvement in the performance compared to deterministic algorithms. The most commonly used randomized algorithms in the context of view selection are simulated annealing algorithms and genetic algorithms. The motivation to compare our approach with genetic algorithm is based on the observation that genetic algorithm in contrast with simulated annealing algorithm use a multi-directional search which allows to find a point near the global optimum [START_REF] Lee | Speeding up materialized view selection in data warehouses using a randomized algorithm[END_REF]. A comparison with hybrid approaches has not been made because of their excessive computation time [START_REF] Zhang | An evolutionary approach to materialized views selection in a data warehouse environment[END_REF]. The goal of the experiments is the comparison of the solution quality resulting from evaluating the quality of the obtained set of materialized views in term of cost savings between our method and genetic algorithm.

Experiment Settings

The computer used for experimentation was an Intel Core 2 Duo P8600 CPU @ 2.40 GHz machine running with 3GB of RAM and Windows XP Professional SP3. The program was written in Java using JDK/JRE 1.6.0. We chose a workload of one hundred queries defined over the database schema of the TPC-H benchmark [START_REF]TPC-R Benchmark Standard Specication 2.01[END_REF]. We then randomly assigned values to the frequencies for access and update based on uniform distribution. In all experiments, the quality of the solutions found by the genetic algorithm and our method was respectively measured as a ratio of the total query cost obtained using the genetic algorithm and the constraint solver over the total query cost when all the views are not materialized. Thus, we consider the "Without-Mat" approach which does not materialize views and always recomputes queries as a benchmark for our normalized results. The ratio was computed and averaged over several runs for the genetic algorithm because of his probabilistic behavior.

We have implemented the genetic algorithm presented in [START_REF] Weiss | Towards materialized view selection for distributed databases[END_REF] by incorporating space and maintenance cost constraints into the algorithm. The values for population size and probabilities of the crossover and mutation operators are assigned based on studies conducted by [START_REF] Goldberg | Genetic Algorithms in Search Optimization and Machine Learning[END_REF][START_REF] Michalewicz | Genetic algorithms + data structures = evolution programs[END_REF]. In order to let the genetic algorithm converge quickly, we generated an initial population which represents a favorable view configuration rather than a random sampling. Favorable view configuration such as the views which satisfy the maintenance cost and space constraints if they exist are most likely selected for materialization.

Experimental Results

The constraint solver for solving the view selection problem as a constraint satisfaction problem (CSP) is aimed to provide the optimal solution (see figure 2(a)). However, this is not feasible at large scale because of the great number of comparisons between all possible subsets of views which are candidate for materialization. One way to avoid an explosion in the search space is to explore a strictly limited number of possibilities. In this case, the constraint solver is aimed at simply finding a feasible solution in which all constraints are satisfied. Figure 2(b) shows the quality of the solutions returned by our approach involving 30 queries as a function of execution time. We can see, our approach provides near optimal solutions quickly. Indeed, after only few minutes (i.e., 3 minutes and 24 seconds), the solution found lies within 79,84% of the optimal solution. The quality of this solution is improved over time. In the next experiments, the constraint solver was left to run until the convergence of the genetic algorithm. Fig. 2: The solution quality of our approach over time (nb of queries=30).

Experiments under the maintenance cost constraint

In this section, we compare the performance resulting from evaluating the quality of the solutions found by our approach and genetic algorithm in the context where the view selection is constrained by a total view maintenance cost limit U . In these experiments, U is computed as a function of U (Q) which is the total maintenance cost when all queries (i.e., root nodes in the AND-OR view graph) are materialized [START_REF] Kalnis | View selection using randomized search[END_REF]. We set U to be 4%, 8%, 16%,..., 32% of U (Q). Figure 3 compares experiment results of our approach with that of genetic algorithm while varying the values of U for a workload involving 70 queries. We can see in figure 3 that our approach generates solutions with cost less than that returned by the genetic algorithm when U < 32% of U (Q). For large values of U (U >= 32% of U (Q)), solutions returned by the genetic algorithm have better quality compared with our approach. This is because the genetic algorithm converges faster when we relax the maintenance cost constraint and our approach needs more time to achieve better quality. However, this would not be seen as a drawback since the time bound for the update is usually very tight compared with the time required for maintaining all the query workload. Figure 4 shows the costs of the workload involving 10,20,30,40,50,60,70,80,90 and 100 queries in order to test the scalability of the view selection methods according to the number of queries. The maintenance cost constraint U was set to 16% of U (Q). This graphics shows that our approach provides an improvement in the quality of the obtained set of materialized views in term of cost savings compared with the genetic algorithm. Furthermore, our method supports scalability when the number of queries increases.

Fig. 5: The solution quality as a function of available storage space (number of queries=70, U =50% of U (Q)).

Experiments under the maintenance cost and space constraints

In order to compare the performance of the view selection methods in the context where both maintenance cost and space constraints exist, we set U to 50% and give restrictive values to the space constraint S. In these experiments, S is computed as a function of S(Q) which is the size of the whole workload [START_REF] Kalnis | View selection using randomized search[END_REF]. We varied S between 4% and 32% of S(Q). solutions than the genetic algorithm in the case where the storage space is the restrictive constraint. Experiment results depicted in figure 6 shows how well the view selection methods scale with the problem size. The maintenance cost constraint was set to 50% of U (Q) and the space constraint to 20% of S(Q). The size of the problem varied from 10 to 100 queries. We observe that our approach provides the lowest query cost while varying the number of queries. Therefore, our approach outperforms the genetic algorithm for all query workload size. We also show that our approach can be applied to large number of queries.

Related Work

As mentioned in the introduction, the view selection problem is a NP-complete problem. Several view selection methods have been proposed in the literature to address the view selection problem. They can be classified into three major groups:

Deterministic algorithms based methods

Such methods usually provide a solution to the view selection problem either by applying exhaustive search or by applying heuristics i.e., greedy algorithms to reduce the search space. In [START_REF] Ross | Materialized view maintenance and integrity constraint checking: Trading space for time[END_REF], an exhaustive approach is presented for finding the best set of views to materialize. [START_REF] Labio | Physical database design for data warehouses[END_REF] presents an optimal algorithm based on A* algorithm [START_REF] Nilsson | Problem-Solving Methods in Artificial Intelligence[END_REF] that vastly prune the search space compared to the algorithm proposed in [START_REF] Ross | Materialized view maintenance and integrity constraint checking: Trading space for time[END_REF]. However, an exhaustive search cannot compute an optimal solution within a reasonable time due to the complexity of the problem. Many approaches [START_REF] Gupta | Selection of views to materialize in a data warehouse[END_REF][START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF][START_REF] Gupta | Selection of views to materialize under a maintenance cost constraint[END_REF][START_REF] Roy | Efficient and extensible algorithms for multi query optimization[END_REF][START_REF] Mistry | Materialized view selection and maintenance using multi-query optimization[END_REF][START_REF] Mistry | Materialized view selection and maintenance using multi-query optimization[END_REF][START_REF] Satyanarayana | View relevance driven materialized view selection in data warehousing environment[END_REF][START_REF] Baril | Selection of materialized views: A cost-based approach[END_REF] using a kind of greedy strategy to avoid having to traverse the solution space in an exhaustive search manner have been designed. However, greedy algorithms are unsatisfactory in term of the solution quality i.e., the quality of the obtained set of materialized views because the greedy nature of the algorithm makes it susceptible to poor local minima (initial solutions influence the solution greatly). In contrast with these work, our approach provides a suitable trade-off between the computation time and the solution quality. Indeed, we have shown that our approach provides a good solution quality in a limited time. This is due to the use of constraint propagation technique and facilities for controlling search behavior that are the features of constraint programming.

Randomized algorithms based methods

Randomize algorithms such as simulated annealing algorithms [START_REF] Derakhshan | Simulated annealing for materialized view selection in data warehousing environment[END_REF][START_REF] Derakhshan | Parallel simulated annealing for materialized view selection in data warehousing environments[END_REF][START_REF] Kalnis | View selection using randomized search[END_REF] and genetic algorithms [START_REF] Weiss | Towards materialized view selection for distributed databases[END_REF][START_REF] Horng | Applying evolutionary algorithms to materialized view selection in a data warehouse[END_REF][START_REF] Lee | Speeding up materialized view selection in data warehouses using a randomized algorithm[END_REF][START_REF] Xu | Materialized view selection as constrained evolutionary optimization[END_REF][START_REF] Lawrence | Multiobjective genetic algorithms for materialized view selection in olap data warehouses[END_REF] have been used and explored for the selection of materialized views in order to improve the quality of the solution. These algorithms use a randomized search strategy for deciding which views to materialize. Randomized algorithms provide a better solution quality than greedy algorithms. However, they may have a tendency to converge towards local optima. Besides, their successes often depend on the set-up of the algorithm as well as the extremely difficult fine-tuning of algorithm that must be performed during many test runs. In our approach, we simply model view selection as a constraint satisfaction problem (CSP) and its resolution is supported automatically by constraint solver embedded in the constraint programming language. Besides, our approach provides better results compared with genetic algorithm in term of the solution quality.

Hybrid algorithms based methods

Hybrid algorithms combine the advantages of pure deterministic algorithms and pure randomized algorithms. A hybrid approach has been applied in [START_REF] Zhang | An evolutionary approach to materialized views selection in a data warehouse environment[END_REF] for the view selection problem which combine heuristic algorithms i.e., greedy algorithms and genetic algorithms. They prove that hybrid algorithms provide better performance than either the genetic algorithms or heuristic algorithms used alone in terms of solution quality. However, they often require longer computation time and may be impractical due to their excessive computation time.

Conclusion

In this paper, we have presented a new approach to the view selection problem which is based on constraint programming. More specifically, the view selection problem has been modeled as a constraint satisfaction problem (CSP). Its resolution has been supported automatically by constraint solver embedded in the constraint programming language. We have performed several experiments and comparison with a randomized method i.e., genetic algorithm. The experiment results have shown that our approach provides better performances compared with the genetic algorithm in term of the solution quality (i.e., the quality of the obtained set of materialized views) in a limited time. More precisely, we have demonstrate experimentally that our approach provides better results compared with genetic algorithm in term of cost savings when the view selection is decided under the case where (i) only the maintenance cost constraint is considered, assuming unlimited amount of storage space and (ii) both maintenance cost and space constraints exists. We have also shown that our approach supports scalability when the number of queries increases. As a future work, we are planning to apply our approach to a distributed database setting. Our current approach simply takes into account the space and maintenance cost constraints. These constraints will be per machine in a distributed context. Also, resource constraints such us CPU, IO, network bandwidth and the location of materialized views will have to be taken into consideration. These new constraints will easily be handled with our approach.

Fig. 1 :

 1 Fig. 1: The AND-OR view graph of the two queries Q 1 and Q 2 .

  represents the query cost corresponding to a view v i . The domain is a finite subset of N * such as d Qc(vi) ⊂ N * . -M c(v i ) which is the maintenance cost corresponding to a view v i , where d Qc(vi) ⊂ N * .

  (a) Until optimal solution (b) Until 10 minutes

Fig. 3 :

 3 Fig. 3: Comparison of the view selection methods while varying the maintenance cost constraint (nb of queries=70).

Fig. 4 :

 4 Fig. 4: Evaluating the performance while varying the number of queries (U =16% of U (Q)).

Figure 5 Fig. 6 :

 56 Fig. 6: The quality of results as a function of the number of queries (U =50% of U (Q), S=20% of S(Q)).


Character Recognition based on DTW-Radon

Keywords: Character Recognition, Radon Transform, DTW

The paper presents a method for isolated offline character recognition using radon features. The key characteristic of the method is to use DTW algorithm to match corresponding pairs of radon histograms at every projecting angle. Thanks to DTW, it avoids compressing feature matrix into a single vector which may miss information. Comparison has been made with the state-of-the-art of shape descriptors over several different character as well as numeral datasets from different scripts.

I. INTRODUCTION

With the advent of handwriting recognition technology since a few decades [START_REF] Plamondon | On-line and off-line handwriting recognition: A comprehensive survey[END_REF], [START_REF] Arica | An overview of character recognition focused on off-line handwriting[END_REF], applications are challenging. For example, OCR is becoming an integral part of document scanners, and is used in many applications such as postal processing, script recognition, banking, security (signature verification, for instance) and language identification. In handwriting recognition, feature selection has been an important issue [START_REF] Ivind Due Trier | Feature extraction methods for character recognition-a survey[END_REF]. Both structural and statistical features as well as their combination have been widely used [START_REF] Heutte | A structural/statistical feature based vector for handwritten character recognition[END_REF], [START_REF] Foggia | Combining statistical and structural approaches for handwritten character description[END_REF]. Structural features tend to vary since characters' shapes vary widely. As a consequence, local structural properties like intersection of lines, number of holes, concave arcs, end points and junctions change time to time. In those situations, statistical approaches [START_REF] Jain | Statistical Pattern Recognition: A Review[END_REF] tolerate to a few extent, with no substantial change in the global signatures. Therefore, the present work is inspired to use statistical feature to represent off-line isolated characters.

Owing to large variation in shapes and writing styles, OCR systems (for unconstrained scripts in particular) do not provide optimal accuracy. Despite those circumstances, it is desirable to develop shape representation such that it can be used for machine recognition [START_REF] Shinghal | A method for selecting constrained hand-printed character shapes for machine recognition[END_REF], [START_REF] De Campos | Character recognition in natural images[END_REF]. To represent shape of the character, contour-based shape descriptors have been widely used in comparison to region-based ones. Fourier processing of the image is an example of using contour information [START_REF] Granlund | Fourier Preprocessing for Hand Print Character Recognition[END_REF], [START_REF] Hopkins | A fourier-descriptor-based character recognition engine implemented under the gamera open-source document-processing framework[END_REF]. Besides, curvature approaches have been used [START_REF] Kopf | Enhancing curvature scale space features for robust shape classification[END_REF], [START_REF] Khoddami | Farsi and latin script identification using curvature scale space features[END_REF] where shape is described in the scale space by the maximum number of curvatures. Further, the Shape Context (SC) [START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF], [START_REF] Tepper | A decision step for shape context matching[END_REF] is robust to small perturbations while it does not guarantee scale-invariance. On the other side, common methods on region-based shape descriptors are based on moment theory [START_REF] Flusser | On the independence of rotation moment invariants[END_REF] including geometric, Legendre, Zernike [START_REF] Kim | A region-based shape descriptor using zernike moments[END_REF], and Pseudo-Zernike moments. Contourbased descriptors on the whole, are appropriate for silhouette shapes since they cannot capture the interior content as well as disconnected shapes or shapes with holes. To represent internal structure of the shape, unlike in Fourier Descriptors (FD), Zhang and Lu [START_REF] Zhang | Shape-based image retrieval using generic fourier descriptor[END_REF] have proposed a region-based Generic Fourier Descriptor (GFD) that avoids the problem of rotation in the Fourier spectra. Recently, use of polar shape descriptors has been mentioned in [START_REF] Frejlichowski | Analysis of four polar shape descriptors properties in an exemplary application[END_REF]. Overall, from almost all global signal based descriptors [START_REF] Zhang | Review of shape representation and description techniques[END_REF], the use of normalisation in order to satisfy common geometric invariance properties introduces errors as well as they are sensitive to noise, eventually affecting the whole recognition process.

In document analysis and recognition (character recognition in particular), a single and integrated open source tool-set will be a global choice since it can be re-used as plug and play [START_REF] Hopkins | A fourier-descriptor-based character recognition engine implemented under the gamera open-source document-processing framework[END_REF] as a generic model. Another common implementation problem is the inability to assume the shape distribution of the patterns in the feature space. Consequently, non-parametric methods are much more practical. Moreover, those methods in general, use linear functions to describe classifiers. Besides, feature selection must be sufficiently enriched with important information. To represent the pattern, global shape representation is a premier choice due to its simplicity as well as it sometimes does not require extra pre-processing and segmentation process as in local pattern representation. To accomplish recognition, matching is another concern. Feature selection corresponds to the matching techniques. For instance, fixed size pattern representation as in global signal based shape descriptors [START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF], [START_REF] Zhang | Shape-based image retrieval using generic fourier descriptor[END_REF], [START_REF] Kim | A region-based shape descriptor using zernike moments[END_REF], [START_REF] Tabbone | A new shape descriptor defined on the radon transform[END_REF], provide immediate matching while DTW for instance, has been popularly used for non-linear sequences having potentially different lengths.

In those respects, the paper presents a simple idea to represent isolated character via radon transform [START_REF] Deans | Applications of the Radon Transform[END_REF] and recognition is made with the help of DTW [START_REF] Kruskall | The symmetric time warping algorithm: From continuous to discrete[END_REF]. Thanks to DTW, it avoids compressing pattern representation into a single vector -as in [START_REF] Tabbone | A new shape descriptor defined on the radon transform[END_REF], for instance -which may miss information. The concept of the work is originally derived for off-line signature verification [START_REF] Coetzer | Off-line Signature Verification[END_REF], [START_REF] Kolhe | Dynamic time warping based static hand printed signature verification[END_REF]. In this paper, the method has been tested over several different numeral and character datasets from different scripts such as Roman, Devanagari, Bangla, Oriaya and Japanese-katakana.

The remaining of the paper is organised as follows. The proposed method is explained in Section II, which mainly includes character representation and matching. Section III provides a series of tests. In Section IV, results are analysed thoroughly. The paper is concluded in Section V.

II. METHOD

A. Pre-processing

The preliminary task is to do pre-processing since characters tend to be highly degraded as they are taken from newspaper, postal cards etc. under varying different lighting conditions, for instance. It mainly considers stroke synthesis, thresholding, gray-scale to binary conversion; noise removal, foreground textual information extraction by removing background [START_REF] Alginahi | Preprocessing techniques in character recognition[END_REF]. However, this introduces many adhoc techniques. In this work, isolated character images are simply converted to binary. While converting, an average grayscale pixel intensity values is used to make a threshold. Fig. 1 shows a few examples of it. In this illustration, binary conversion is followed by contour detection and thinning.

B. Feature Selection

Besides pre-processing, recognition system is based on how characters are represented [START_REF] Ivind Due Trier | Feature extraction methods for character recognition-a survey[END_REF]. In this work, radon transform is used to represent patterns [START_REF] Deans | Applications of the Radon Transform[END_REF].

As shown in Fig. 2, a collection of projections of the pattern at different angles refers to radon transform [START_REF] Deans | Applications of the Radon Transform[END_REF]. In other words, radon transform for any pattern f (x, y) and for a given set of angles can be thought of as computing the projection of all non-zero points. The resulting projection is the sum of the non-zero points for any pattern f (x, y) in each direction, which eventually form a matrix. Therefore the integral of f over a line L(ρ, θ) defined by ρ = x cos θ + y sin θ can formally be expressed as,

R(ρ, θ) = ∞ -∞ ∞ -∞ f (x, y)δ(x cos θ + y sin θ -ρ)dxdy
where δ(.) is the Dirac delta function, δ(x) = 1, if x = 0 and 0 otherwise. Also, θ ∈ [0, π[ and ρ ∈] -∞, ∞[. For radon transform, L i be in normal form (ρ i , θ i ). Following Fig. 2 (c), for all θ i , the Radon transform now can be described as the length of intersections of all lines L i . Note that the range of ρ i.e., -ρ min < ρ ≤ ρ max is entirely based on the size of pattern. Radon transform itself does not satisfy invariance properties. In this work, it is assumed that the characters are vertically aligned. While, translation and scaling are considered. In case of translation, image centroid (x c , y c ) is used such that translation vector is u = (x c , y c ): R(ρx c cos θy c sin θ, θ). Therefore, translation of f results in the shift of its transform in ρ by a distance equal to the projection of translation vector of the line L (see Fig. 2 (b)). For scaling, features are normalised into [0, 1] at every projecting angle.

C. Feature Matching

Given a query pattern P q and database P d , matching has been done between corresponding histograms of R q (ρ, θ) and R d (ρ, θ). In radon matrix, for each projecting angle θ i , column (vertical line in Fig. 4) refers to as histogram of radon features. Let us say histograms {H θi } i=0,...,Θ-1 . Radon transform generates different ρ size according to the image size. Keeping images into their original sizes, DTW algorithm [START_REF] Kruskall | The symmetric time warping algorithm: From continuous to discrete[END_REF] is proposed to match corresponding radon histograms.

Let us consider two column vector sequences from R(ρ, θ), representing histograms H q and H d of length K and L, respectively H q = {h q k } k=1,...,K and H d = {h d l } l=1,...,L . At first, a matrix M of size K × L is constructed. Then for each element in matrix M, local distance with an initial condition D(1, 1) = δ(1, 1) such that it allows warping path going diagonally from starting node (1, 1) to end (K, L). The main aim is to find the path for which the least cost is associated. The warping path therefore provides the difference cost between the compared sequences. Formally, the warping path is, W = {w t } t=1...T where max(k, l)

≤ T < k + l -1 and t th element of W is w(k, l) t ∈ [1 : K] × [1 : L] for t ∈ [1 : T ].
The optimised warping path W satisfies the following three conditions. c1. boundary condition: w 1 = (1, 1) and w T = (K, L) c2. monotonicity condition:

k 1 ≤ k 2 ≤ • • • ≤ k K and l 1 ≤ l 2 ≤ • • • ≤ l L c3
. continuity condition: w t+1w t ∈ {(1, 1)(0, 1), (1, 0)} for t ∈ [1 : T -1] Now the global distance between H q and H d can be defined as,

∆ H q , H d = D(K, L) T ,
where T is the number of discrete warping steps along diagonal DTW-matrix. Fig. 5 shows an example of it. Aggregating distances between histograms in all corresponding projecting angles θ i between P q and P d yields a global pattern-matching score,

Dist(P q , P d ) = Θ-1 i=0 ∆(H q θi , H d θi ).
Scores are normalised in [0, 1] by, Dist(.)-Dist min. (.) Dist max. (.)-Dist min. (.) .

III. EXPERIMENTS

A. Datasets

Several different datasets from different scripts1 are tested. They are categorised into two groups: Numeral and Character. For Numeral category, Roman, Bangla, Devanagari and Oriya [START_REF] Bhowmik | An hmm based recognition scheme for handwritten oriya numerals[END_REF], [START_REF] Bhattacharya | Handwritten numeral databases of indian scripts and multistage recognition of mixed numerals[END_REF] are used, while Roman, Bangla as well as Katakana (Japanese) character are used in character category.

B. Comparison World -Benchmarking Methods

A set of major global signal based shape descriptors such as R-signature [START_REF] Tabbone | A new shape descriptor defined on the radon transform[END_REF], GFD [START_REF] Zhang | Shape-based image retrieval using generic fourier descriptor[END_REF], SC [START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF] and Zernike [START_REF] Kim | A region-based shape descriptor using zernike moments[END_REF] have been implemented.

For those descriptors, it is important to fit the best parameters. For GFD, the parameters are tuned as, radial (4 : 12) and angular (6 : 20) frequencies to get the best combinations. For SC, the test follows [START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF] i.e., 100 number of sample points are used. In case of Zernike, 36 Zernike functions of order less than or equal to 7 has been used. For radon, number of projecting angle is considered i.e., [0, π[ by default.

C. Evaluation protocol

While experimenting, every test sample is matched with training candidates and the closest one is reported. The closest candidate corresponds to the labelled class, which we call recognition. To evaluate the performance of the method, X -fold Cross-Validation (CV) has been implemented unlike traditional dichotomous classification. In X -fold CV, the original sample for every class is randomly partitioned into X sub-samples. Of the X sub-samples, a single sub-sample is used for validation, and the remaining X -1 sub-samples are used for training. This process is then repeated for X folds, with each of the X sub-samples used exactly once. Eventually, a single value results from averaging all. The opposite process holds for inverse X -fold CV. While experimenting, tests move from normal X -fold CV to inverse.

D. Experimental Results

Table I shows the average recognition rates for all datasets using X -fold CV. In all datasets, D-Radon supersedes all methods, while providing a marginal difference with SC. GFD is lagging behind the first two best performers. Zernike provides substantial difference in recognition rate against GFD, SC and D-Radon. While, R-signature performs far behind the all with the difference fairly in large amount.

Considering such datasets, we have observed that SC performs close to D-Radon, except the two character datasets: Bangla and Katakana. GFD and SC almost go equally.

IV. EXPERIMENTAL RESULTS ANALYSIS

Considering the datasets (cf. Section III-A) used, methods (cf. Section III-B) are analysed in response to the evaluation protocol (cf. Section III-C) based on experimental results in Table I (cf. Section III-D). In addition, a few common difficulties in character recognition will be highlighted. Multi-class similarity is one of the major problems in character recognition as shown in Fig. 8 (a). In addition, shape descriptors with rotation invariance properties have been affected from those samples as shown in Fig. 8 (b). These are the major reasons affecting those existing methods. Missing parts as well as long ascender and/or descender part of the stroke affects SC severely compared to GFD. Due to these circumstances, existing methods require more training samples in order to get varieties of writing. This has been proved in experimental results (see Table I) where substantial decrement in recognition rate has been observed from X -1 to X -4, where X = 5. Despite, D-Radon provides fairly better in those situations. Besides, scale invariance does not affect much as it employs DTW for radon features alignment.

Another important issue is computational complexity. In D-Radon, running time complexity is high since it uses DTW for matching, however it is largely depend on how big the image is. As far as concern to computational cost, the observed average running time for all methods is provided in Table II. All tests have been made using MATLAB 7.8.0 in Linux platform.

V. CONCLUSION AND FUTURE PERSPECTIVES

A method for character recognition based on the combination of radon features for representing pattern and dynamic programming for matching, has been presented. It supersedes the state-of-the-art of shape descriptors for isolated off-line character recognition over several different publicly available datasets.

Computing radon transform is quite immediate. But the running time complexity lies in matching. However, it could be substantially reduced by using optimised DTW [START_REF] Salvador | Toward accurate dynamic time warping in linear time and space[END_REF].

Figure 1 .

 1 Figure 1. An example of binarisation.

  Figure 2. Radon transform.

Figure 3 .

 3 Figure 3. Radon features for corresponding samples.

Figure 4 .

 4 Figure 4. Radon histogram at every projecting angle θ i .

0 19 Figure 5 .

 195 Figure 5. Computing DTW distance between two non-linear sequences.

Figure 6 . 2

 62 Figure 6. 2 numeral samples from 4 different known scripts for 10 (0-9) classes.

Figure 7 .

 7 Figure 7. A sample per class from 3 different known scripts: 27 classes for Roman, 50 classes for Bangla and 47 classes for Katakana (Japanese).

  Character pairs having similar symmetric shape.

Figure 8 .

 8 Figure 8. Difficulties in character recognition -a few examples.

Table I AVERAGE

 I RECOGNITION RATE IN % USING X -FOLD CROSS-VALIDATION (X = 5)

		Training R-sign. Zernike GFD SC D-Radon
	1. Numeral Datasets
		X -1	78	83	97 98	100
	Roman	X -2	75	78	95 97	100
	10×100	X -3	70	74	94 96	98
		X -4	66	67	91 96	98
		X -1	58	44	98 98	98
	Oriya	X -2	52	38	96 95	98
	10×100	X -3	46	43	85 93	97
		X -4	43	32	72 92	95
		X -1	55	40	86 96	97
	Devanagari	X -2	54	40	84 94	96
	10×300	X -3	50	38	81 93	96
		X -4	46	34	69 87	95
		X -1	48	47	73 95	95
	Bangla	X -2	48	44	69 94	94
	10×400	X -3	46	43	68 91	93
		X -4	44	40	64 89	92
	2. Character Datasets
		X -1	80	77	96 99	100
	Roman	X -2	77	74	94 98	98
	27×100	X -3	75	67	93 97	98
		X -4	69	58	91 98	97
		X -1	22	11	23 55	77
	Bangla	X -2	18	09	22 49	74
	50×20	X -3	14	06	18 46	72
		X -4	11	06	16 43	71
		X -1	69	42	88 91	96
	Katakana	X -2	66	37	85 87	95
	47×200	X -3	63	34	84 84	94
		X -4	59	28	78 81	91

ISI character datasets for Indian scripts, CVPR unit, India ETL3 and ETL5 datasets for Roman and Katakana scripts, AIST, Japan


Florian Grond
email: fgrond@techfak.uni-bielefeld.de

Alexandre Bouënard
email: alexandre.bouenard@mcgill.ca

Thomas Hermann
email: thermann@techfak.uni-bielefeld.de

Marcelo M Wanderley
email: marcelo.wanderley@mcgill.ca

VIRTUAL AUDITORY MYOGRAPHY OF TIMPANI-PLAYING AVATARS

Music performance is highly related to instrumentalists' movements and one of the biggest challenges is the identification and understanding of gesture strategies according to the plethora of musical nuances (dynamics, tempo, etc..) available to performers. During these past few years, a novel approach has been elaborated, consisting in studying movement strategies through auditory rendering. In this paper, we focus on the auditory analysis of timpani (percussion) gestures. We present a novel interface combining movement simulation and sonification as a means of enhancing the auditory analysis of timpani gestures. We further report the results from an evaluation of this interface, where we study the contributions of sonification to the multimodal display.

INTRODUCTION

Musical performances are usually and naturally associated with instrumentalists' gestures, the importance of which has been intensively documented and studied [START_REF] Wanderley | The Musical Significance of Clarinetists' Ancillary Gestures: An Exploration of the Field[END_REF][START_REF] Nussek | Music and Motion: How Music-related Ancillary Body Movements Contribute to the Experience of Music[END_REF]. Performer gestures can traditionally be divided into two categories: effective and ancillary ones. Effective gestures are those that are directly involved in the sound production, sometimes fingers and hands, as for the clarinet or the piano. Conversely, ancillary gestures are not directly involved in sound production processes, but are omnipresent in musical performance and are an integral part of the performers expressivity.

The existence of such variabilities in instrumental gestures are the common basis of gesture studies, usually conducted through the analysis of motion data captured from real instrumentalists performing with varying expressiveness and various gesture articulations. The availability of such data makes the analysis immediately relevant for the performing subject, and allows the exploration of the influence of music variations on instrumental gestures, such as gesture anticipation phenomena occuring under musical nuances and tempo changes [START_REF] Dahl | Playing the Accent: Comparing Striking Velocity and Timing in Ostinato Rhythm Performed by Four Drummers[END_REF][START_REF] Rasamimanana | Effort-based Analysis of Bowing Movements: Evidence of Anticipation Effects[END_REF][START_REF] Bouënard | Gesture Control of Sound Synthesis: Analysis and Classification of Percussion Gestures[END_REF]. However the inter-dependance and high dimensionality of gesture data makes it difficult to study the gesture-sound relationship apart from a divide-and-conquer approach.

In this work we propose an approach combining movement simulation and sonification for enhancing the perception of these subtle variations occuring in instrumental gestures. The interface allows for the selection of a wide range of gesture parameters as well as their mapping to sonification methods. In our case we study the gesture patterns of timpani players. With timpani players the movements of the whole mallet-arm-shoulder system participates to the effective gestures, and changes in gesture articulations can alter the gesture strategies involved in the system. For instance musical nuances can influence preparatory gestures preceding beat impacts, especially for mallet extremity trajectories [START_REF] Bouënard | Gesture Control of Sound Synthesis: Analysis and Classification of Percussion Gestures[END_REF]. The simulation of the instrumental gesture comes into play, as a possibility to systematically control and study a variety of movement parameters.

The paper is organized as follows: section 2 discusses the proposed work in the light of previous contributions, both regarding gesture sonification and modeling. The framework used to model and simulate timpani gestures is presented in section 3, providing the essential knowledge about the in-and-outs on which the sonification is based. Section 4 details the sonification process of our work, and particularly the sonification methods used. The user interface is presented in section 5, as well as relevant experiments that are possible to run with it. Section 6 presents a psychophysical experiment that has been conducted with our simulation/sonification framework. Finally, section 7 discusses our approach and concludes with further perspectives.

RELATED WORK

Gesture Sonification

Displays for movements of the human body are first and foremost visual, a self-evident approach, since the human visual and cognitive system seems highly adapted to perceive and interpret human motion [START_REF] Johansson | Visual Motion Perception[END_REF]. However, sonification offers novel inspection techniques that complement visual analysis by transforming data into audible sound. Specific sonifications for this purpose have already been developed to some extent by the authors [7,[START_REF] Verfaille | Sonification of Musician's Ancillary Gestures[END_REF][START_REF] Grond | Methods for Effective Sonification of Clarinetists' Ancillary Gestures[END_REF]. This perception mode is beneficial for the movement data of timpani players for two reasons: On the one hand, multivariate data sets with complex information such as fast transient motions can be perceived as one auditory stream. On the other hand the repetitive nature of timpani playing makes it easy for the listener to establish similarities and differences in what is presented acoustically, thereby making immediately sense of the auditory informa-tion channel. Sonifications in this field have so far only represented data that are directly related to the movement. However in simulations, there are additional interesting data-streams such as efforts for instance, which need to be displayed.

Simulated torques are such effort-related parameters, and can be understood as the turning force that moves the structure of the avatar, similarly to the force exerted through the muscles of the real performer onto its joints. This situates our work in a long tradition of sonification which is the auditory display of electromyography (EMG) data. Early descriptions, can be found in 1958 [START_REF] Miller | ELECTROMYOGRAPHY -Uses and Limitations[END_REF] where different conditions can be clearly distinguished acoustically. Recent research has been conducted in [START_REF] Pauletto | Interactive Sonification of Complex Data[END_REF] where modern sonification methods are employed and the effect of the interactive nature of EMG sonification has been studied. In this paper we introduce sonification of torques from movement simulations and demonstrate on a selected example how they can be integrated as interesting dynamic features in an acoustic display.

More specifically, torques have already been used in [START_REF] Effenberg | Motion-Lab Sonify: A Framework for the Sonification of Human Motion Data[END_REF] as a sonification parameter, considering the avatar motion into a lowdimensional PCA-space and using torques at the global level of the human body. Our sonification work differently uses torques at the joint level and makes no dimension-reduction hypothesis of the avatar motion, thereby allowing the sonification of the motion of each individual joint and to perceive its contribution to the global motion. Additionally, we use SuperCollider as sound synthesis engine which allows for a more flexible sound design compared to the MIDI controled synthesis.

With respect to multimodal perception, interesting work can be found in [START_REF] Guttman | Hearing What the Eyes See[END_REF] which shows that sound dominates the temporal perception and visualization dominates the spatial perception. The potential of sound to alter visual perception is demonstrated in [14,[START_REF] Sekuler | Sound alters Visual Motion Perception[END_REF].

Despite all these initial contributions to gesture sonification and established results from perceptional psychology, audio-visual displays of complex and specific movements such as the avatar in our case have not been evaluated so far. This is why we decided to perform a psychophysical experiment to investigate the effect of sonification in a discrimination task.

Gesture Modeling

The modeling of instrumental gestures has often been under attention in computer music, mostly as a means of understanding the relationship between actions applied to music instruments and the resulting sounds. Based on models emulating real-world gesture mechanisms, another important benefit of such a modeling/synthesis approach is the interest to submit novel gesture parameters to sound rendering processes. Modeling gesture parameters can be more-or-less bounded to the gesture-sound interaction process. Strongly related to the interaction phase is the modeling for instance of contact [START_REF] Avanzini | Physical Modeling of Impacts: Theory and Experiments on Contact Time and Spectral Centroid[END_REF] or attack [START_REF] Demoucron | On the Control of Virtual Violins: Physical Modelling and Control of Bowed String Instruments[END_REF] parameters. Other contributions aim at modeling complete instrumental gestures, including preparatory phases in addition to the interaction process. Early works have involved for instance MIDI-driven [18] or physicallysimulated gestures [START_REF] Gibet | Gestural Control of Sound Synthesis[END_REF]. More recent attempts include such modeling/synthesis approach using pre-recorded motion data combined with optimized dynamic systems [START_REF] Rasamimanana | Geste Instrumental du Violoniste en Situation de Jeu : Analyse et Modélisation[END_REF], or statistical gesture models [START_REF] Bevilacqua | Continuous Realtime Gesture Following and Recognition[END_REF][START_REF] Maestre | Statistical Modeling of Bowing Control Applied to Sound Synthesis[END_REF].

Another promising approach is to combine real body motion data alongside with the simulation of physics laws, thereby maintaining the sensorimotor realism of synthesized gestures with regards to the performing task, as well as the responsive behavior of gestural actions towards the surrounding environment [START_REF] Bouënard | Synthesis of Music Performances: Virtual Character Animation as a Controller of Sound Synthesis[END_REF]. This has been successfully applied in the particular case of the modeling and simulation of percussion gestures to control sound synthesis processes [START_REF] Bouënard | Advantages and Limitations of Simulating Percussion Gestures for Sound Synthesis[END_REF]. Such an approach can also have benefits for the sonification process, as it provides not only kinematic clues about timpani gestures -such as position, velocity and accelerationbut also physical ones like forces and torques that can be related to effort parameters during simulated performances. Such a gesture model can therefore propose gesture parameters not easily available in motion capture settings, and also expand the reality in the virtual domain for creating novel instrumental situations.

GESTURE MODELING AND SENSORIMOTOR CONTROL

This section presents the framework used to model and simulate timpani gestures. This work is based on the sensorimotor model detailed in [START_REF] Bouënard | Synthesis of Music Performances: Virtual Character Animation as a Controller of Sound Synthesis[END_REF]. Here we only present the essential information about the model to help the reader to understand its underlying mechanisms, i.e. how pre-recorded real motion data used in conjunction with our model can be useful to recover estimated physical features about the original motion. We furthermore highlight the interest of such models for sonification purposes.

Modeling and Control

Figure 1 gives a summary of the data streams involved in the gesture model, first by invoking a physics model parameterized by anthropometric and biomechanical parameters coming from real motion data. A second step is to control the model through a sensorimotor control strategy based on the percussion gesture trace: mallet extremity trajectories.

The gesture model is represented by a skeleton T composed of a set of rigid bodies. The skeleton can cope both with static and dynamic parameters, cf. equation [START_REF] Wanderley | The Musical Significance of Clarinetists' Ancillary Gestures: An Exploration of the Field[END_REF]. Static parameters include parameters related to the human anthropometry, such as limbs' mass mi, density ρi, inertia tensor Ii. Dynamic parameters can also be taken into account, such as the way skeleton limbs are articulated with each other. This involves especially how biomechanical parameters of joints like stiffness k j s and damping k j d model tension/relaxation properties of human joints.

T = [{mi, ρi, Ii} i∈[1...N ] , {k j s , k j d } j∈[1...M ] ] (1)
FP = m.ΓP (2) τP = IP . Ω + Ω.IP .Ω (3)
Once the presented static/dynamic attributes of the gesture model are parameterized, a realistic simulation can be settled, setting the model in motion according to the laws of physics. The physics simulation processes at every time-step the linear acceleration ΓP and angular velocity Ω of each rigid body composing the gesture skeleton, cf. equations ( 2) and (3). This process consequently needs the knowledge of physical forces FP and torques τP to be applied on the rigid bodies to put the gesture skeleton into motion.

The described gesture model has several advantages, (a) it takes the anthropomorphic and biomechanical properties of the human body into account, and (b) it allows the modeling of gesture responsiveness to external disturbances. However, these advantages turn rapidly into diffculties when the question comes to determining this huge set of parameters, especially considering the complexity of the human body.

A method is of course to consider a simplified gesture model with regards to the number of limbs and joints' degrees of freedom, and to relate this limited set to anthropomorphic tables. In our case, the anthropometry arises from pre-recorded motion data, and we consider a system representing the upper-body augmented with mallets totalling 11 rigid bodies articulated by 33 degrees of freedom, and specifically for each arm, 4 bodies (clavicle, upper arm, forearm, mallet) and 12 degrees of freedom (neck, shoulder, elbow, wrist).

Another difficulty resides in the processing of forces/torques to set the gesture model into motion, especially when noticing that no unique couple (forces, torques) exists at each simulation step-time, so that the gesture model can achieve the task. We propose a control strategy composed of a cascaded combination of two inverse processes that infer an estimation of the needed forces/torques based on real motion data.

ΘC = K -1 (XC ) (4) τC = D -1 (ΘC ) (5)
The first inverse process K -1 infers joint angle trajectories ΘC (neck, shoulder, elbow, wrist) from pre-recorded trajectories of mallet extremity XC , equation ( 4). The second inverse process D -1 infers the torques τC to apply on limbs (clavicle, upper arm, forearm and mallet) from the computed joint angle trajectories ΘC , cf. equation [START_REF] Bouënard | Gesture Control of Sound Synthesis: Analysis and Classification of Percussion Gestures[END_REF]. More details about the sensorimotor control scheme involving these inverse processes as well as algorithmic issues are available in [START_REF] Bouënard | Synthesis of Music Performances: Virtual Character Animation as a Controller of Sound Synthesis[END_REF].

Simulation Aspects for/in Sonification

The sensorimotor control of the proposed gesture model enables the simulation of whole arm gestures from the specification of mallet extremity trajectories. As a result, the sensorimotor control and simulation of the gesture model provides kinematic motion parameters such as limbs positions and orientations (and their respective time derivatives), as well as physical motion parameters such as As an illustration of generated kinematic parameters, the prerecorded height trajectory of the mallet extremity given as an input to our gesture model is depicted in Figure 2(a) (black line), in comparison to the simulated height trajectory (grey line). This shows an accurate tracking of the initial trajectory between the various beat impacts represented by the local extrema on the trajectories. Figure 2(b) presents the simulated height trajectories of arm joints: wrist (black), elbow (dark grey) and shoulder (light grey). Typically, one can notice the entrainment of wrist and elbow heights compared to the height of the mallet extremity, while the shoulder height is somewhat constant.

As for physical parameters, Figures 2(c) and 2(d) show torque curves, respectively for the wrist (transversal component) and the elbow (flexion component). These two torque curves reveal two behaviors which differ from their macro/micro action on the motion control. On the one hand, the flexion component of the elbow torque curve, Figure 2(d), shows a macro action in the sense that forearm movements show a sort of pendulum motion. During preparatory phases (between two beat impacts), this macro action is characterized by an increase of flexion torque during the first half for elevating the forearm, and a decrease during the second half since the weight of the forearm helps in gaining momentum in the view of the next beat impact. On the other hand, the transversal component of the wrist torque curve, Figure 2(c), shows a micro action in the sense that wrist torques seem to act on motion control around beat impacts. Wrist torques indeed rapidly increase slightly before impacts, remain almost constant during impact time, and rapidly decrease slightly after impacts. This micro action could for instance be explained by the need of fine control interaction mechanisms during beat impacts.

Combining such kinematic (limbs position, orientation) as well as physical parameters (torques) can finally be of great interest since all of these parameters are not easily visually accessible. Particularly in the case of estimated torques, while such parameters could be involved in playing strategies and variations in gesture articulations, findind an auditory representation appears to be a much more relevant approach, than a visual representation that would probably just overload the visualization.

As an illustration, we investigated this point by studying the effect of physics parameters of a simulated timpani performance on the generated torques. We specifically investigated the effect of a variation of the mallet mass on the generated torques at the wrist level. Figure 3 reflects this study in the case of a simulation of a single roll played legato, and especially shows wrist torque trajecin relation with the mass variation. Figure 3(a) represents the height of the mallet extremity during the single roll simulation, while Figure 3(e) shows the piecewise increase/decrease of the mallet mass along the simulation, with a maximum mass factor of eight times the original mallet mass. Figures 3(b-c-d) show respectively the corresponding torque trajectories at the wrist level (for each component transversal-flexion-twist) in response to the mallet mass variation, as well as with their up-down envelopes. The difference between up-down envelopes, i.e. torque ranges curves, are represented for each component in Figures 3(f-g-h). Interestingly, these range trajectories reflect the torque increase for each component involved during the simulation as a means of counteracting the growing mass of the mallet. This same cause/effect relationship can also be seen during the decrease of the mallet mass, where torque ranges decrease progressively.

GESTURE SONIFICATION

The gesture sonification was designed by carefully mapping movements to sound parameters based on our earlier experience of movement sonifications [START_REF] Grond | Methods for Effective Sonification of Clarinetists' Ancillary Gestures[END_REF]. We further decided to leave the control of some aspects of the sonification to the user. The guidelines of the mapping design can be summarized as follows:

1. Sonification of the motion data: all moving joints, shoulder, elbow, wrist as well as the mallet should be included into the sonification. The various moving parts should be as good as possible distinguishable in the resulting sound stream so that one can perceive the different movement patterns as acoustically well articulated and distinct. The sonification should lead to an auditory gestalt that allows to add complementary information from the simulation. 2. Since the movement directions from the timpani player such as up-down, back-forth and left-right correspond to the base vectors of the coordinate system, the joint positions (x, y, z) and their velocities can be directly mapped to sound parameters. The up and down movement should be acoustically distinguishable. 3. The amplitude of the velocity of each joint component was normalized for each channel over different gesture articulations. This decision was made since we wanted to make sure that even minute movements from the shoulder would be loud enough in order to compare it with the strong amplitude variations on the wrist or mallet. Furthermore the normalization factor was the same for the left and the right part of each component, so that asymmetries in the movement could be detected in the sonification. The scaling was performed over all the different gesture articulations. 4. The torques of shoulder, elbow and wrist should be integrated into the sound stream. Since the torques are vectors whose orientation is of interest, they should be mapped to a sonification parameter that still allows to attribute the resulting sound to the same joint. 5. The sonification of the left and right sides of the avatar should be distributed to the stereo panorama, as this mapping allows for a natural separation and distinction of the alternating dynamics of the arm movement. 6. The user should have control over relevant sonification parameters. More specifically the user should be able to either explore only the sonification of the movement patterns or mix them together with the sonification of the torques.

In the implementation of these guidelines, we decided for a mix between additive and subtractive synthesis schemes. For the velocity of the components (x, y, z) of each joint a sound was generated with a base frequency and a set of 5 overtones, whose gain was decaying with reciprocal to its order, The set of overtones ensured that the sound of each joint did not disappear in the overall sound stream, and could still be perceived as a tone with a defined pitch. The base frequency of the tone was modulated by the corresponding component of the torque. The gain of this sound was controlled by the velocity of the joint component. Analogous to a whitening procedure the mapping of the normalized data was given by velocity[0.0 ... 0.4] → gain [-60 ... 0] dB, using a linear, clipped mapping function with the given range limits. The mixing between additive and subtractive synthesis was controlled by the sign of the correspondent velocity component.

The implementation in the SuperCollider [START_REF] Mccartney | Rethinking the Computer Music Language: SuperCollider[END_REF] Herein LinXFade2 is a unit generator that fades between the two synthesis unit generators Klank for substractive synthesis and Klang for additive synthesis. The unit generator Klank implements an array of two pole resonant filter based on [START_REF] Steiglitz | A note on Constant-Gain Digital Resonators[END_REF] where the bandwidth is given as 60dB ring decay time.

The input signal for the subtractive synthesis noise is noise. The parameter ring is an array with the 60dB ring decay time for each filter partial. The parameter mix ranging from -1 to 1 was mapped to the torques, while gain corresponded to the component velocity, both with flexible scaling.

Additionally we added a basic psychoacoustic amplitude compensation as provided by SuperCollider with the Class AmpCompA, implementing an ANSI A-weighting curve. Here freq is the frequency for which the amplitude is compensated for and freqmin is the lowest frequency for which the compensation function applies.

We developed two frequency schemes that were mapped to the 12 components of the moving joints. The were linearly mapped on the pitch scale with equidistant intervalls between 3 octaves and 7 semitones covering a frequency range between 100 and 1200 Hz. In the first mapping we grouped the frequencies with respect to joints starting with the shoulder's x, y, z component for the 3 lowest frequencies the middle ones to elbow and arm-wrist ending up with the 3 highest assigned to the x, y, z component of the stick.

The second scheme grouped the frequencies according to the x, y, z directions of movement, by assigning the 4 lowest frequencies to all the x components of shoulder, elbow, arm-wrist and stick. The middle and highest 4 frequencies to the y and z component respectively.

THE USER INTERFACE

For a better control of the sonification process we developed a minimal graphical user interface. In this interface a rendered video of the avatar was played back simultaneously with the sonification of the movement data, as depicted on Figure 4.

The sonification of each component for each joint can be switched on and off individually. For each joint all the 3 components can also be switched on simultaneously. The individual and grouped component for each joint can also be controlled for both sides of the timpani player, Figure 4(a). The amount of mixing between additive and subtractive synthesis can also be adjusted by a slider (bottom part of Figure 4(a)).

4(b) further shows that the playback range of the data could be set as well as the playback speed. A play button starts and stops the sonification. A second button next to it allows to change the scaling of the data from individual to global maxima. Additionally the two frequency mapping schemes can be selected through a toggle. In the background there is a fullscreen graphical display of the velocity of each component of the joint. Depending on what data is selected for sonification the corresponding part of the graphical display is highlighted.

Video examples of the application together with examples from the subsequently described user test can be found on the web: http://tinyurl.com/2vo3k4w

EVALUATION OF THE MULTIMODAL DISPLAY

While developing the application our assumption, that sonification together with a visual representation influences the perception of the avatars' movements was supported through working experience. After some time of learning how to read the visual representation of the avatar, different gesture articulations could be distinguished. Sonification however seemed to highlight immediately the differences in the movement patterns. We were interested to evaluate the impact of sonification on untrained users' capability to discern gesture articulations and therefore set up a psychophysical experiment.

As a null hypothesis, we assumed that the display contained no relevant information which would help the subjects to distinguish different gesture articulations. Hence deciding wether two gesture articulations were the same or different would correspond to a discrete random process. By testing this on each of the three stimulus cases -i.e. auditory, visual and audio-visual individually -we wanted to find out in which particular way sonification contributes to the perception of the avatar's movements in the multimodal display.

The Experiment

The subjects were confronted with pairs of stimuli and were asked to rate if they perceived them as same or different. The stimuli consisted of 4 seconds of the the avatars movements, the starting point of which were slightly varied. Therefore the subjects could not base their decision on auditory or visual cues from the beginning or the end of the stimuli.

At the beginning of the experiment, the subjects were briefly instructed how to proceed by showing them one short excerpt of the kind of stimuli they would encounter. This instruction phase was kept short in order to avoid learning effects to set in. Further, the subjects were instructed that they would have to distinguish four different gesture articulations of the avatar: accent (A), legato (L), staccato (S), vertical accent (V).

The combination of all four gesture articulations gives 16 pairs, 4 of them with the same stimulus and 12 with different stimuli. In order to balance the ratio between same and different stimuli pairs we added the 4 pairs with the same stimulus a second time, giving a ratio of 12 different to 8 same stimuli pairs. For the sonification the second frequency scheme as described above was chosen. Playback speed was set to the original speed of the simulation. 12 tests subjects were recorded, of them were female. The age ranged from 22 to 34 years. The three stimuli condition auditory, visual, and audio-visual were systematically varied. We therefore recorded two subjects for each of the possible permutations of the 3 stimuli pairs. The sequence of stimuli within one condition was randomized. The whole experiment lasted about 20 minutes for a single subject. The visualization of the avatar was presented from within the application on a flat screen and the display of the time-series and the data-selection interface was minimized, the sound was displayed via K 272 HD headphones. After the experiment the subjects were asked if they play an instrument and how the different presentation forms helped them to accomplish the task.

Results

The evaluation of the results from the experiment are compiled in Figure 5. The histograms show in the vertically axis a scalar value for similarity (0 -1) which was the mean rating of all subjects for a given stimuli condition. The first four vertical bars represent the cases where the same stimuli in one pair were compared by the subjects. The fact that none of four combinations were rated unanimously as same is due to the variation in the beginning of the playback as explained earlier. This phase-shift seems to noticeably influence the perception and gestalt formation of rhythmic structures. The following 12 pairs are those where the subjects were confronted with different stimuli. They are ordered such that the combination AL and its inverse are next to each other. The null hypothesis represents the horizontal line at 0.5, which is equivalent to random guessing. The other dashed horizontal lines represent the 95% confidence interval. It differs for the first four cases since they appeared twice as often in the stimuli. Hence the total numbers of samples n and therefore the probability of deviating from the null hypothesis differed.

In the case of the auditory-only display, we find that the 4 stimuli pairs with the same gesture articulations received high mean values for similarity. Most of the pairs with stimuli of different gesture articulations received small similarity values, except the first AL and LA (outside the confidence interval) and the last two (SV, VS). In fact, these two pairs contained gesture articulations, which are very similar to each other. The similarity rating for both was around random rating except for the case LA, which had a tendency to be wrongly rated as similar.

In the case of the visual-only display the subjects had apparently more difficulties to recognize the same gesture articulations. Also different gesture articulations were recognized with less confidence except for the combination SL. Interestingly when comparing with the auditory-only condition, combinations AL and LA made of visually similar movements became less similar although found with ratings close to random rating. However VS was significantly wrongly rated as similar.

In the case of audio-visual display, we see how the good recognition of the same gesture articulations from the auditory part was adopted. Also the discrimination of the very distinct gesture articulations was apparently easy. The similar gesture articulation pairs (AL, LA, SV, VS), however could not be distinguished adequately compared to auditory-only and visual-only conditions. They were even more wrongly rated as similar.

The feedback from the subjects was very diverse. Most mentioned that they found it easier to use the sonification for the discrimination task. Some mentioned that they would have preferred to practice before the actual experiment. Subjects also reported that it was difficult to follow two features in the visual display at the same time, such as the movement of shoulder and hand wrist. One subject explicitly reported that the unimodal auditory and vi- sual stimuli, were easier for the given task. In the multimodal case this subject said it seemed to have overheard certain acoustic differences.

Conclusions from the Experiment

The evaluation of the experiment shows audio and visual displays contains relevant information for the subjects to partly succeed in solving the given discrimination task. The phase in which a repetitive movement is started seems to have a noticeable effect for the auditory as for the visual gestalt formation in perception. The combined visual and auditory information in the display however did not lead to a better discrimination, but rather emphasized the confusion of gesture articulations (AL, LA, SV, VS) detaining common features. Therefore similar gesture articulations had a tendency to be rated as same. Sonification seemed to influence the subjects' confidence to recognize gesture articulations as different, for those cases where it was more obvious. We think that this can be explained within the framework of cognitive load theory [START_REF] Kalyuga | The Expertise Reversal Effect[END_REF][START_REF] Oviatt | When Do We Interact Multimodally? Cognitive Load and Multimodal Communication Patterns[END_REF], where evidence can be found that if we split our attention onto two perceptional modes, like auditory and visual, both of these modes have only limited resources and therefore have difficulties to perform well for a given task.

SUMMARY AND FUTURE WORK

In this paper we have introduced a method and tool for the sonification in combination with the visualization of simulated avatar movements. We have given examples where data from the simulation like torques can be interestingly integrated into the sonification concept. In a psychophysical experiment we investigated some basic properties the presented audio-visual display. The results from the experiment show that sonification is at least as useful for discriminating movement patterns as the visual representation of the avatar. However the combined multimodal display does not provide the user with more clues to discriminate the movements.

Our results open up interesting research questions to be answered in the future. The first one is if we can design a multimodal interface with a better perceptual integration of both visual and auditory modalities. If so, can similar gesture articulations be better differentiated? Furthermore, it would be interesting to find out how experience with the multimodal display changes with learning and how we make use of the auditory and visual information if they are presented at the same time. We also plan to evaluate systematically how the sonification of torques is integrated with the visual display, knowing that they are practically invisible in the movement itself. We further want to investigate how people make use of the data-selection interface in order to better understand the different gesture articulations. Here we are particularly interested how many data channels need to be sonified in order to evoke noticeable differences. This is important in so far as in a visual display we can decide where to look, whereas it is far more difficult to willingly isolate selected features in an auditory stream. This is where the interactive aspect of the sonification interface can a beneficial role.

Figure 1 :

 1 Figure 1: Sensorimotor simulation of percussion gestures: motion capture data from real timpani performers are used to identify mallet extremity trajectories as well as biomechanical parameters, which are the inputs of physics-sensorimotor framewrok for simulating timpani gestures.

Figure 2 :

 2 Figure 2: (a) Recorded (black) and simulated (grey) vertical trajectories of mallet extremity, (b) simulated vertical trajectories of wrist, elbow and shoulder joints (respectively black, dark grey and light grey), (c) simulated curves of wrist transversal-torque, and (d) elbow flexion-torque. Sphere markers on each timeline represent time occurences of beat impacts.

Figure 3 :

 3 Figure 3: Investigation on the effect of mallet mass on wrist torques -simulation of a single roll played legato, mallet height extremity (a), under a mass variation of the mallet (e). Simulated curves of wrist transversal-torque (b), flexion-torque (c) and twist-torque (d) with their up-down envelopes, as well as their respective ranges (f-g-h).

  a) The data selection interface together with (b) the visualization of the avatar.

  AA LL SS VV AL LA AS SA AV VA LS SL LV VL SV VS 0LL SS VV AL LA AS SA AV VA LS SL LV VL SV VS 0VV AL LA AS SA AV VA LS SL LV VL SV VS 0

Figure 5 :

 5 Figure 5: Histograms of the rating from the pairwise stimuli for the three conditions auditory, visual and audio-visual.

ACKNOWLEDGMENTS

The authors would like to thank all the people who have kindly accepted to take part to the user test experiments, as well as for all of their feedback. This work was partially supported by the Natural Sciences and Engineering Research Council of Canada (Discovery and Special Research Opportunity grants).