Mehdi Rouan Serik

Mejdi Kaddour
email: kaddour.mejdi@univ-oran.dz

Optimizing Deployment Cost in Camera-Based Wireless Sensor Networks

Keywords: Camera-based wireless sensor networks, minimum cost deployment, coverage quality, binary particle swarm optimization

We discuss in this paper a deployment optimization problem in camera-based wireless sensor networks. In particular, we propose a mathematical model to solve the problem of minimizing the number of cameras required to cover a set of targets with a given level of quality. Since solving this kind of problems with exact methods is computationally expensive, we rather rely on an adapted version of Binary Particle Swarm Optimization (BPSO). Our preliminary results are motivating since we obtain near-optimal solutions in few iterations of the algorithm. We discuss also the relevance of hybrid meta-heuristics and parallel algorithms in this context.

Introduction

Wireless Sensor Networks (WSN) are particular ad-hoc networks defined as a set of cooperating nodes disseminated in a given geographic area in order to collect its data about some phenomenon autonomously. Specifically, Camerabased wireless sensor networks (WSN) form an emerging research area with many promising applications. Potential applications include remote video surveillance, monitoring and assisting elderly and health patients, and habitat monitoring.

We study in this paper the cost deployment of camera-based WSNs, where the main concern is to determine the optimal minimum number of cameras, along with their positions and their orientations to track a given set of targets with a prescribed level of quality. This problem can be solved with various exact mathematical programming tools such as Branch and Bound. However, as the problem size increases, solving such problems using these exact methods becomes computationally intractable. In fact, Ai and Abouzeid [START_REF] Ai | Coverage by directional sensors in randomly deployed wireless sensor networks[END_REF] have demonstrated that this problem is NP-hard. A traditional way to deal with such difficult problems is to rely upon meta-heuristic methods. In particular, we adapt the generic procedure of Particle Swarm Optimization (PSO) to solve this deployment problem. We also introduce a quality coverage parameter which serves to ensure that each target in the solution is covered with a sufficient level of quality. Indeed, as the targeting objects move away from the sensing camera, the level of details falls off. Our preliminary results show that the proposed method behaves well both in computational performances and solution quality.

The rest of paper is organized as follows. Section 2 reviews the relevant literature on this topic. Section 3 formulates the problem and describes the proposed coverage model. The detailed mathematical model is given in Section 4, while the proposed PSO-based algorithm is described in Section 5. Section 6 assesses and discusses the obtained results. Finally, The last section concludes the paper and suggests some future research directions.

Related Works

Existing literature in the field distinguishes typically two important kinds of deployment problems: target coverage and area coverage. We focus here on the first one. One version of the problem consists on covering a maximum number of targets with a minimum number of sensors. In [START_REF] Ai | Coverage by directional sensors in randomly deployed wireless sensor networks[END_REF], authors proposed an exact integer linear program (ILP) and a Centralized Greedy Algorithm (CGA) for the maximum coverage with minimum sensors (MCMS) problem. Then, they provided a Distributed Greedy Algorithm (DGA) solution. They showed that DGA does better than the two other methods (ILP and CGA) by incorporating a measure of the sensors' residual energy into DGA. Aziz et. al. [START_REF] Aziz | A wireless sensor network coverage optimization algorithm based on particle swarm optimization and voronoi diagram[END_REF] proposed a new algorithm to optimize sensor coverage using PSO and Voronoi diagrams. PSO is used to find the optimal deployment of sensors providing the best coverage, while Voronoi diagram is used to evaluate the fitness of the solution. They showed that the proposed algorithm achieves a good coverage with a better time efficiency than existing approaches.

Authors in [START_REF] Xu | Camera network coverage improving by particle swarm optimization[END_REF] improved the field of view (FOV) coverage of a camera network. They considered randomly scattered cameras in a wide area, where each camera may adjust only its orientation and not its localisation. They also implemented a PSO algorithm and efficiently found an optimal orientation for each camera. They considered also region of interest in the search space (ROI) and occlusions. In [START_REF] Morsly | Particle swarm optimization inspired probability algorithm for optimal camera network placement[END_REF], authors considered the area coverage problem in a 2D/3Dgrid space. The solution process was based on Particle Swarm Optimization Inspired Probability (PSO-IP). For comparison purposes, they also implemented alternative methods based on Tabu Search, genetic algorithms and simulated annealing. Results showed that the proposed PSO-IP overcomes the three other methods especially with large instances. Unlike these two works, we deal with targets coverage not area coverage. We give also a mathematical model to the coverage problem. Note that our solution approach is partly inspired by this last work. But as far as we know, no existing work has formulated a problem similar to ours, in particular by considering a continuous measure of sensing quality.

Problem Definition

We assume that a set of N camera sensors {S i : i = 1, . . . , n} are deployed on the euclidean space A. For each camera S i , we are given its Cartesian coordinates (X S i , Y S i ) and its orientation ϕ in A. The field of vision of each camera is modeled as in [START_REF] Trucco | Model-based planning of optimal sensor placements for inspection[END_REF] by isosceles triangle as depicted in Fig. 1, where α represents the aperture of the camera and W d its working distance. A target located on the coordinates (x, y) is assumed to be covered by a given camera with coordinates (x s , y s ) if the three following constraints are satisfied:

X Y x s y s x y • • W d • S • • a α ϕ Field of View
cos(ϕ) • (x -x s ) + sin(ϕ) • (y -y s ) ≤ W d (1a) -sin(ϕ) • (x -x s ) + cos(ϕ) • (y -y s ) ≤ a 2W d • (cos(ϕ) • (x -x s ) + sin(ϕ) • (y -y s )) (1b) -sin(ϕ) • (x -x s ) + cos(ϕ) • (y -y s ) ≥ - a 2W d • (cos(ϕ) • (x -x s ) + sin(ϕ) • (y -y s )) (1c)

Coverage Model

Coverage models determine first if a given target can be covered or not by some sensor, but can also measure a corresponding quality parameter [START_REF] Wang | Coverage problems in sensor networks: A survey[END_REF]. This is ac-complished by calculating the geometric relation between sensors and targets.

In most cases, it consists in calculating the euclidean distance and angles, but some research works assume also that the sensing quality of a sensor is reduced with the increase of the distance away from the sensor [START_REF] Megerian | Exposure in wireless sensor networks: theory and practical solutions[END_REF], [START_REF] Veltri | Minimal and maximal exposure path algorithms for wireless embedded sensor networks[END_REF]. In our case, we make a similar assumption by adopting a directional disk model where the coverage parameter for a given sensor/target pair is represented by a non negative real number calculated as follows:

f (d(s, z)) = C d α (s, z) (2)
where d(s, z) is the distance separating camera s from target z, α is the exponent attenuation and C is a constant. In particular, we assume that quality decreases quadratically as a function of the distance (α = 2).

• R s φ s φ z ω (a) • s 1 • s 2 • s 3 • s 4 • s 5 • • • • (b)

Mathematical Model

The adopted model assumes a known number of targets, in a given space, where the objective is to cover these targets optimally. The objective of our optimization problem is defined as follows:

min n ∑ i=1 m ∑ k=1 O ik (3)
This objective implies the minimization of the number of deployed cameras, provided that the following constraints are satisfied.

m ∑ k=1 O ik ≤ 1, ∀i = 1, . . . , n. (4)
The above constraint ensures that at most one angle is active per each camera. ∑ m k=1 O ik = 0, corresponds to the situation where no camera is deployed at location i.

n ∑ i=1 b ij ≥ 1, ∀j = 1, . . . , t. (5)
This constraints ensures that each target is covered by at least one camera. Now, the minimum coverage quality for each target is satisfied through the following constraint:

n ∑ i=1 b ij C d α ij ≥ δ, ∀j = 1, . . . , t. ( 6
)
where C is a constant and α is the attenuation exponent.

Given some locations of a camera i oriented with angle k, the following three constraints enforce, as described above in (1a),(1b) and (1c), that some target j

is covered properly if b ij = 1. m ∑ k=1 O ik cos(ϕ k ) • (x t j -x i ) + sin(ϕ k ) • (y t j -y i ) ≤ d + L 1 (1 -b ij ), ∀i = 1, . . . , n, ∀j = 1, . . . , t. ( 7
) m ∑ k=1 O ik -sin(ϕ k ) + a 2d cos(ϕ k ) (x t j -x i ) + cos(ϕ k ) - a 2d sin(ϕ k ) (y t j -y i ) ≤ L 2 (1 -b ij ) ∀i = 1, . . . , n, ∀j = 1, . . . , t. ( 8
) m ∑ k=1 O ik sin(ϕ k ) - a 2d cos(ϕ k ) (x t j -x i ) -cos(ϕ k ) - a 2d sin(ϕ k ) (y t j -y i ) ≤ L 3 (1 -b ij ) ∀i = 1, . . . , n, ∀j = 1, . . . , t. (9)
where L 1 , L 2 , L 3 are large constants, which are introduced to make theses constraints meaningless when b ij = 1.

The above objective with the introduced constraints define a mixed-integer problem which is hard to solve in general. In particular, it is not easy to move from one solution to another when applying some meta-heuristic algorithm for example. Hence, we relax this model by moving the coverage constraints ( 5)-( 6) into the objective, as follows.

min n ∑ i=1 m ∑ j=1 O ij - n ∑ i=1 t ∑ j=1 b ij 1 + C d α ij (10)
Subject to (4),( 7)-( 9).

Particle Swarm Optimization

Particle swarm optimization (PSO) is a meta-heuristic method invented by Russel Eberhart (Electrical Engineer) and James Kennedy (socio-psychologist) in 1995. This algorithm, inspired by social behaviour, has been introduced as an optimization tool dealing with real numbers initially and with integers lately [START_REF] Poli | Particle swarm optimization[END_REF]. It is mostly inspired from the manner in which a flock of birds moves with various individuals leading the flock during the travel at different periods of time. The PSO algorithm consists of a group of individuals named particles. Each particle p < Swarm_size is a potential solution to an optimization problem, having its own position in the space search. After each iteration, it moves in function of one of its components:

-Actual velocity V ; -Best solution L b ; -Actual position X ; -Best neighbourhood solution G best ;

The movement of each particle obeys to the equations:

V k+1 = ω.V k + C 1 r 1 (P b -X k ) + C 2 r 2 (P g -X k ) (11)
X k+1 = X k + V k+1 (12)
where X = (x ik ), V = (v ik ), i = 1, 2, . . . , n, k = 1, 2, . . . m, denote the distance/angle and the velocity vectors, respectively. ω is the inertia weight, r 1 and r 2 are two random numbers uniformly chosen in [0, 1], and C 1 , C 2 are constant values. Finally k is the iteration index.

A given solution for the deployment problem is a number of cameras with corresponding positions and active angles (see Fig. 3a). We adopt a binary representation of the position vector X. Besides, since PSOs require movements, we define two different types of moves:

1. Rotation: selecting a different camera for an active camera. 2. Displacement: moving one camera from position i to position i . These movements are guided by the velocity parameter. Thus, we redefine [START_REF] Wang | Coverage problems in sensor networks: A survey[END_REF] as follows:

V = (v ik , ∀k = 1, 2, . . . , m) = 1 if alea > 1 1+(G best -L b ) 0 otherwise ( 13
)
Where alea is a random number from [0, 1], then Eq. ( 12) become:

X k+1 = X k ⊕ V k+1 (14)
A camera rotation is defined through the logical operator "exclusive OR", i.e., to invert a zero bit to one in the X vector, while a camera displacement is defined through a binary shift, and this will be a position swap. As a stopping criteria, we define a maximum number of iterations. Algorithm 1 gives an overview of our implemented PSO.

For comparison purposes, we implemented a standard Simulated Annealing Algorithm (SA) [START_REF] Van Laarhoven | Simulated annealing[END_REF]. The basic idea behind comes from the principles of statistical mechanics whereby the annealing process requires heating and then slowly cooling a substance to obtain a strong crystalline structure. At each iteration, a random neighbour is generated. Movements that improve the cost function are always accepted. Otherwise, the neighbour is selected with a given probability that depends on the current temperature and the amount of degradation ∆E of the objective function. This probability is calculated as follows:

P(∆E, T) = e -∆E T
where ∆E represents the fitness difference. This is algorithm is used in largescale optimization problems in wireless sensors networks as in [START_REF] Morsly | Particle swarm optimization inspired probability algorithm for optimal camera network placement[END_REF], [START_REF] Kannan | Simulated annealing based wireless sensor network localization with flip ambiguity mitigation[END_REF].

Algorithm 1 Proposed PSO algorithm

Experiments and Results

We discuss in this section various experiments related to our approach. First, the most important parameter to be defined in order to implement a PSO algorithm is the solution coding or representation. Each solution is encoded in binary where the vector X represents camera positions and angles (Fig 3a ) and (Fig 3b). The experiments were executed on a computer with Intel © Core TM i3-2350 M CPU @ 2.30 GHz CPU and 4.0 GB of RAM. Table 2a gives parameters used to implement the method. Swarm_size and Steps represent the number of particles (potential solutions) involved in PSO and iteration's number, respectively. C 1 and C 2 represent learning factors of the algorithm, most often set to 2.0 [START_REF] Gorse | Binary particle swarm optimisation with improved scaling behaviour[END_REF]. W d represents the working distance of a camera (extrinsic parameter), X max and Y max are the grid dimensions. Q max and Q min are, respectively, the maximum and the minimum quality coverage of a camera. Here we require a certain level of quality in target covering. C is a constant which specifies how the quality coverage decreases when moving away from the sensor.

1 i n X 1 • • • 0 • • • 0 • • • 1 • • • 1 • • • 0 1 k m 1 k m 1 k m (a) O im = 1 (b)
In Fig 4, we give an initial solution then a final one found by PSO algorithm. The figures show that we can easily find a good solution consisting of two cameras covering nine targets. As shown in Tab 2b, finding such a solution does not require more than a hundred of iterations in a very brief time for a small number of targets (less than a half of a second). We observe also the high success rate over all executions. As shown in (Fig 4d) we clearly obtanin better average fitness by the proposed PSO than the one obtained by the SA for fifty executions of the two methods.

Finally, note that compared to Y. Morsly et. al. approach in [START_REF] Morsly | Particle swarm optimization inspired probability algorithm for optimal camera network placement[END_REF] and Yi-Chun Xu et al. in [START_REF] Xu | Camera network coverage improving by particle swarm optimization[END_REF], we consider a coverage quality parameter and deal with targets instead of area coverage. Here we must determine camera's positions and orientation, while coverage quality can be specified by the user. Even if we assume mobile targets, the proposed method can easily re-adapt the solution to the new scenario; this is guaranteed by the camera's movement (displacement and rotation).

Conclusion

We have proposed a mathematical mixed-integer model for the deployment of camera-based wireless sensor networks. Solving such models with exact is only feasible with small problem instances, beyond which, the use of approximative method such as meta-heuristics is required. In literature, only a few papers treat the target-based coverage model along with a coverage quality parameter. Hence, we have introduced an additional problem parameter to account for coverage quality. We have adapted a PSO algorithm to minimize the number of active cameras used to cover targets with certain quality. The proposed method gives easily a significant improvement of the initial random solution in few steps. Compared to SA, our PSO returns better solutions. We envisage later to calculate exact solutions by a ILP solver and then compare the results with ours. Moreover, we are working to introduce connectivity and energy-efficiency criteria to our problem. Finally, we are considering to use parallel versions of PSO and evaluate their performance over multiple platforms.

Fig. 1 :

 1 Fig. 1: Camera's field of view.

Fig. 2 :

 2 Fig. 2: Illustrations of : (a) Directional Model ; (b) Three active cameras covering 4 targets.

Fig. 3 :

 3 Fig. 3: PSO solution: (a) X Position vector; (b) Active angle.

Fig. 4 :

 4 Fig. 4: Illustrations of: (a) Initial target positions; (b) Random initial solution; (c) Final solution found by PSO; (d) PSO vs SA.

Table 1 :

 1 Table 1 define the formal notations used in our model. let b ij and O ik binary variables defined as follows: Problem's formal notations.

	b ij =	1 if camera at position i covers target j 0 otherwise
	O ik =	1 if camera at position i has active angle k 0 otherwise

Table 2 :

 2 PSO and SA parameters and executions.

	(a)	(b)
	Parameters Values Swarm_size 30 Steps 300 C 1 , C 2 1.4 n 10 m 8 t 10 L 1 , L 2 , L 3 Max_DBL C 10.0 Q max 0.4 Q min 0.05 W d 10 X max , Y max T 1000.0 100	Exec Fit. n s n t Steps time (s) 1 -7.018 2 9 200 0.706 2 -7.050 3 10 167 0.566 3 -8.057 2 10 85 0.109 4 -7.033 2 9 52 0.041 5 -7.048 3 10 1 0.003 6 -7.036 2 9 269 0.78 7 -7.032 2 9 61 0.052 8 -7.035 2 9 170 0.12 9 -7.058 3 10 131 0.509 10 -7.058 3 10 61 0.05


Saida Ishak Boushaki

Nadjet Kamel
email: nkamel@usthb.dz

Omar Bendjeghaba

Improved Cuckoo Search Algorithm for Document Clustering

Keywords: Document Clustering, Vector Space Model, Cuckoo Search, Cosine Similarity, F-measure, Purity, Metaheuristic, Optimization

Efficient document clustering plays an important role in organizing and browsing the information in the World Wide Web. K-means is the most popular clustering algorithms, due to its simplicity and efficiency. However, it may be trapped in local minimum which leads to poor results. Recently, cuckoo search based clustering has proved to reach interesting results. By against, the number of iterations can increase dramatically due to its slowness convergence. In this paper, we propose an improved cuckoo search clustering algorithm in order to overcome the weakness of the conventional cuckoo search clustering. In this algorithm, the global search procedure is enhanced by a local search method. The experiments tests on four text document datasets and one standard dataset extracted from well known collections show the effectiveness and the robustness of the proposed algorithm to improve significantly the clustering quality in term of fitness function, f-measure and purity.

Introduction

The high advance of the internet has led to exponential growth of the amount of information available in the World Wide Web (WWW). Consequently, exploring the data and finding the relevant information on the web became hard tasks. Over the past decades, many approaches have been developed in order to manage and organize efficiently this large set of documents. For this purpose, clustering is the well known method used by the scientific community dealing by the datamining. It is unsupervised technique [START_REF] Jain | Data clustering: a review[END_REF] [2], that extract hidden structural characteristics in the data and gathering the highly similar objects in the same group, whereas segregates dissimilar objects in different ones. Due to the importance task of the clustering technique, it has been applied in variety engineering and field like image segmentation, pattern recognition and gene-expression. The algorithms of clustering are divided into different categories: hierarchical clustering algorithms, nominal data clustering, density based clustering, cohonen networks and partitioning relocation clustering. The last category of clustering contains algorithms with linear time complexity. This makes the partitional algorithms more suitable for web clustering. One of the most famous partitional algorithms is the K-means [START_REF] Huang | An Improved K-means Clustering Algorithm[END_REF] due to its simplicity and efficiency. However, this algorithm may give a poor results this is due to its random initialization and local exploration, which leads to a local minimum. Actually, nature inspired algorithms cope the shortcoming of a local solution by a global one [START_REF] Hruschka | A Survey of Evolutionary Algorithms for Clustering[END_REF]. One of the most recent metaheuristic algorithms is cuckoo search (CS) optimization [5] [6]. It is based on the interesting breeding behaviour such as brood parasitism of certain species of cuckoos and typical characteristics of Lévy flights. The results of experiment comparison show that the cuckoo search algorithm outperform the most famous metaheuristics [START_REF] Ishak Boushaki | A New Algorithm for Data Clustering Based on Cuckoo Search Optimization[END_REF] [8] [START_REF] Civicioglu | Comparative Analysis of the Cuckoo Search Algorithm[END_REF]. In order to improve the clustering result, and inspired from the hybrid algorithm proposed in [START_REF] Ishak Boushaki | A New Hybrid Algorithm for Document Clustering Based on Cuckoo Search and K-means[END_REF], we propose in this paper a new algorithm for document clustering, based on CS. In this algorithm, CS is enhanced by additional functions. Which make it superior to conventional CS in term of fitness, convergence speed and external quality.

The remaining of this paper is organized as follows: in section 2, we present most recent metaheuristics algorithms proposed for web document clustering. In section 3, the formal definitions of document clustering are presented. In section 4, we present the fundamental steps of a cuckoo search algorithm for the clustering problem. The improved cuckoo search adapted for document clustering is presented in section 5. Numerical experimentation and results are provided in Section 6. Finally, the conclusion and future work are drawn in Section 7.

Related Works

Document clustering based on nature inspired algorithms is an active research field. In 2013, Kamel et al. [START_REF] Kamel | A Sampling-PSO-K-means Algorithm for Document Clustering[END_REF] overcome the weakness of K-means in the initial seed by a hybrid algorithm based on K-means, PSO and Sampling algorithms for document clustering. Leticia Cagnina et al. [START_REF] Cagnina | An Efficient Particle Swarm Optimization Approach to Cluster Short Texts[END_REF] have presented an improved version of the discrete particle swarm optimization (PSO) algorithm. This version includes a different representation of particles, a more efficient evaluation of the function to be optimized and some modifications in the mutation operator. In 2014, Wei Song et al. proposed a fuzzy control genetic algorithm (GA) in conjunction with a novel hybrid semantic similarity measure for document clustering. It outperforms the conventional GA [START_REF] Song | Fuzzy Control GA with a Novel Hybrid Semantic Similarity Strategy for Text Clustering[END_REF]. In 2013, A novel document clustering algorithm based on ant colony optimization algorithm was proposed by Kayvan Azaryuon and Babak Fakhar. It improves the standard ants clustering algorithm efficiency by making ant movements purposeful, and on the other hand, by changing the rules of ant movement [START_REF] Azaryuon | A Novel Document Clustering Algorithm Based on Ant Colony Optimization Algorithm[END_REF]. S. Siamala Devi et al. have used the hybrid K-means with harmony search (HS) to do the comparison between the concept called coverage factor and the concept factorization method for document clustering problem [START_REF] Devi | Hybridization of K-means and Harmony Search Method for Text Clustering Using Concept Factorization[END_REF]. The experimental results show that factorization produces better results. Recently, the experimental results of [START_REF] Ishak Boushaki | A New Algorithm for Data Clustering Based on Cuckoo Search Optimization[END_REF] shown that the cuck-oo search (CS) clustering achieves best results compared to the well known and recent algorithms: K-means, particle swarm optimization, gravitational search algorithm, the big bang-big crunch algorithm and the black hole algorithm. More recently, in our previous work, we have proposed a new hybrid algorithm for document clustering based on CS and K-means [START_REF] Ishak Boushaki | A New Hybrid Algorithm for Document Clustering Based on Cuckoo Search and K-means[END_REF]. This new hybrid algorithm outperforms the CS and K-means in term of fitness and external quality.

Formal Definitions

Let S be a set of

n objects 1 O , 2 O ,.., n O , each object is defined in multi dimen- sional space. Clustering S into k clusters means dividing it into k groups or clus- ters 1 C , 2 C ,.., k C , such that:                     S C C C C C C K j i i .. j i and k 1,.., j k, 1,.., i for k 1,.., i for 2 1 (1)
In addition, the objects in the same cluster are similar and the objects in different clusters are dissimilar. This property is proportional to the quality of the clustering.

In our case, data are documents. They are represented by using the vector space model (VSM) [START_REF] Ishak Boushaki | A New Hybrid Algorithm for Document Clustering Based on Cuckoo Search and K-means[END_REF] [START_REF] Salton | A Vector Space Model for Automatic Indexing[END_REF].

The cosine distance is the most used and the best one for document clustering [START_REF] Huang | Similarity Measures for Text Document Clustering[END_REF]. Given two documents

  j i j t i j i v v v v d d  , cos (2)

Cuckoo Search Clustering Algorithm

For solving the clustering problem, the standard cuckoo search algorithm is adapted to reach the centroids of the clusters that optimize predefined fitness function. We have used the fitness function presented in [START_REF] Zhao | Empirical and Theoretical Comparisons of Selected Criterion Functions for Document Clustering[END_REF]. The goal of this function is to find the solution that maximizes the similarity between each document and the centroid of the cluster that is assigned to. This objective function is given by the following formula:

Fitness Maximize      k i C d i l i l c d 1 , cos (3)
Where:

k is the number of clusters and   The cuckoo search clustering algorithm (CSCA) is given by the following steps [START_REF] Ishak Boushaki | A New Algorithm for Data Clustering Based on Cuckoo Search Optimization[END_REF] [10]:

Improved Cuckoo Search Clustering Algorithm

Cuckoo search clustering algorithm can achieve the best global solution compared to most other metaheuristics. Usually, this global solution is obtained after huge number of iterations due to the slow convergence of the algorithm. It is obvious that in CSCA, the research area is explored using the standard cuckoo function [START_REF] Xing | Innovative Computational Intelligence: A Rough Guide to 134 Clever Algorithms[END_REF]. In the present work, we propose to perform after each new solution generated by the standard cuckoo function an auxiliary local research in the research area in order to improve the solution. If this local search finds a solution that is better than the existing one, then it will be replaced by the new reached one.

For each current solution (host nest), the local search procedure exploits this one by calculating the gravity center of each cluster using the equation ( 4). Thus, the solutions are replaced only if their new fitness is better. The pseudo code of the new improved cuckoo search clustering algorithm (ICSCA) is presented in Fig. 1.

    i l C d l i i d n gc 1 (4)

Fig. 1. ICSCA procedure

To illustrate this idea, we give an example. In Fig. 2, we have three clusters and we can see that the objects are more similar to their gravity center than to the centroid generated by the standard cuckoo function.

Begin

Fig. 2. Example of local search

To illustrate this idea, we give an example. In Fig. 2, we have three clusters and we can see that the objects are more similar to their gravity center than to the centroid generated by the standard cuckoo function.

We should notice that another primary function must be performed after each new generated solution. The main goal of this function is to ensure that there is no empty cluster. The simple way for doing this is to replace the empty cluster by a random one.

Experiments and Results

In order to test the efficiency of each auxiliary function added to the standard cuckoo search clustering algorithm, we compare between three algorithms: standard cuckoo search clustering algorithm (CSCA), standard cuckoo search algorithm augmented by the change empty cluster function (CSDC+CEC) and the improved cuckoo search document clustering (ICSCA) enhanced by the local search procedure and the change empty cluster function.

Datasets

Two kinds of datasets are used in the whole of experiments: four text document datasets and one standard dataset. The text document datasets are extracted from two well known collections: Classic3 [START_REF] Tunali | Classic3 and Classic4 DataSets[END_REF] and Text REtrieval Conference (TREC) collections [21]. The description detail of text document datasets is given in Table 1, where the standard dataset is obtained from the famous UCI Machine Learning Repository. The description detail of standard dataset is given in Table 2.

Data

Related Parameters

For the purpose of comparison, the number of iterations is fixed to 100 iterations for the text datasets and only 20 iterations for the Iris standard dataset. We note that for all runs, the probability of worse nests was set to 0.25, while the population size was set to 10. The cosine distance is used as similarity measure for all experiment tests.

Results and Comparisons

The three algorithms: (CSCA), (CSDC+CEC) and (ICSCA) are compared for the different datasets in term of best fitness value and two external validity indexes (Fmeasure and purity). In Table 3 we present the best fitness value of the three algorithms for each datasets.

As we can see from this table, the ICSCA can reach the best results in comparison with the CSCA and CSCA+CEC. In addition, the CSCA+CEC is better than CSCA and the gap between them is proportional to the number of clusters. As the number of cluster increases, more than the gap increases. For each datasets, the convergence behaviors in term of fitness function obtained by the different algorithms are illustrated in Fig. 3, Fig. 4, Fig. 5, Fig. 6 and Fig. 7.

From these figures, it is clear that the ICSCA can reach the best results in a few iterations number for all datasets. Also, we should notice that the gap between graph variation obtained by the CSCA, and CSCA+CEC algorithms is proportional to the number of cluster. In fact, they are close to each other for Classic300 dataset and Classic400. This is due to the small probability of empty cluster. However, for the Tr12 dataset the gap is more significant due to the big number of clusters.

From Fig. 7, it is obvious that the proposed algorithm speed up the convergence behavior of fitness function. Thus, the cosine distance is accurate for the clustering of the standard dataset. The recorded F-measure and purity by the different algorithms for each dataset is given in Table 4. and Table 5. From these tables, it is clear that the proposed algorithm can improve significantly the quality of the clustering results.

Conclusion

The paper presents an improved cuckoo search clustering algorithm (ICSCA). The novelty of the proposed algorithm is to enhance the conventional cuckoo search clustering by a local search procedure. The experiment results show that the proposed ICSCA is more robust than the CSCA+CEC and CSCA, in term of fitness value, fmeasure and purity, when applied on four well known text document dataset and Iris standard dataset. Furthermore, the percent improvement of ICSCA upon the CSCA+CEC is significant.

The proposed ICSCA can also speed up significantly the convergence behavior when applied on Iris standard dataset. Therefore, the cosine distance is accurate for the clustering of the standard dataset. Finally, as future work, we plan to extend the proposed approach for the incremental document clustering.

  is given by the following formula:

  Where i v is the norm of the vector i v To evaluate the quality of clustering results, we have used two external quality indexes: the famous F-measure and Purity [2] [10].

Fig. 3 .

 3 Fig. 3. Graph variation of fitness function of Classic300

Fig. 3 .Fig. 4 .Fig. 5 .

 345 Fig. 3. Graph variation of fitness function of Classic400

Fig. 6 .

 6 Fig. 6. Graph variation of fitness function of Iris

While (t < Max_Iter) or (stop criterion)

  1. Generate randomly the initial population of nb_nest host nests; 2. Calculate the fitness of these solutions and find the best solution; 3. Compare the new solutions with the old solutions, if the new solution is better than the old one, replace the old solution by the new one ; (d) Generate a fraction (p a ) of new solutions to replace the worse nests; (e) Compare these solutions with the old solutions. If the new solution is better than the old solution, replace the old solution by the new one; (f) Find the best solution; 4. End while; 5. Print the best nest and fitness;

; (a) Generate nb_nest new solutions with the cuckoo search; (b) Calculate the fitness of the new solutions; (c)

Table 1 .

 1 Summary of text document datasets

	datasets	Number of	Number	Classes description	Number
		documents	of terms		of groups
	Classic300	300	5471	100, 100, 100	3
	Classic400	400	6205	100, 100, 200	3
	Tr23	204	5833	6, 11, 15, 36, 45, 91	6
	Tr12	313	5805	9, 29, 29, 30, 34, 35, 54, 93	8

Table 2 .

 2 Description of standard dataset

	datasets	Number of	Number of	Classes description Number of
		instances	attributes		groups
	Iris	150	4	50, 50, 50	3

Table 3 .

 3 Best fitness value

	Datasets	CSCA	CSCA+CEC	ICSCA
	Classic300	28.0540	28.3145	56.3282
	Classic400	36.7592	36.8108	70.5629
	Tr23	29.1706	59.4068	88.5799
	Tr12	35.7372	41.5007	93.4783
	Iris	149.6669	149.7503	149.8383

Table 4 .

 4 F-measure comparison of CSCA, CSCA+CEC and ICSCA on the differents datasets.

	Datasets	CSCA	CSCA+CEC	ICSCA
	Clasic300	0.3800	0.4160	0.7728
	Classic400	0.4109	0.4308	0.6878
	Tr23	0.3997	0.4636	0.5476
	Tr12	0.2851	0.4187	0.6017
	Iris	0.7778	0.9131	0.9666

Table 5 .

 5 Purity comparison of CSCA, CSCA+CEC and ICSCA on the differents datasets.The calculated percents that ICSCA improve upon the CSCA+CEC, in terms of fitness function (CPF), f-measure (CPFM) and purity (CPP) is presented in Table6. It can be stated from this table that the proposed ICSCA is more effective than the CSCA+CEC.

	Datasets	CSDC	CSDC+CCN	ICSDC
	Classic300	0.3854	0.3895	0.7863
	Classic400	0.3933	0.4071	0.6468
	Tr23	0.3138	0.4672	0.4710
	Tr12	0.3923	0.4865	0.6532
	Iris	0.6667	0.9158	0.9697

Table 6 .

 6 Percents improvements of ICSCA improve upon the CSCA+CEC

	Datasets	CPF(%)	CPFM(%)	CPP (%)
	Classic300	0.4973	0.4616	0.5046
	Classic400	0.4783	0.3736	0.3705
	Tr23	0.3293	0.1533	0.0080
	Tr12	0.2552	0.3041	0.2552
	Iris	0,0022	0,0553	0,0555


Marcin Gorawski
email: marcin.gorawski@polsl.pl

Krzysztof Pasterak
email: krzysztof.pasterak@polsl.pl

Research and Analysis of the Stream Materialized Aggregate List

Keywords: Materialized Aggregate List, Stream Data Warehouse, Stream Processing

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Nowadays, the necessity of processing, storing and analyzing of very large data volumes (considered also as BigData) is constantly growing. This implies development of newer and more advanced systems, that are able to satisfy this need. Moreover, from the perspective of various enterprises, organizations and other data producers and consumers, the outcome information is expected to be reliable, most up-to-date and obtained in the shortest time possible. These requirements determine the attractiveness of solutions already present on market, as well as constitute new objectives for developers [START_REF] Stonebraker | The 8 requirements of real-time stream processing[END_REF].

In the following paper we focus on Stream Data Processing Systems (SPS). They are designed to process current and continuously generated data with relatively high frequency. When non-stream solutions (i.e. those relying on persistent data) are concerned, processing unit enforces collecting data from sources. Stream oriented systems have to process incoming data almost instantly as they arrive, since data are produced and actively delivered by sources. There are representative examples of Stream Processing Systems [1-6, 26, 27], however they are relatively not as popular as classic, traditional data storage systems.

The example of application involving instant and immediate analysis of data delivered continuously is a liquefied petrol storage and distribution system. Such an installation consists of multiple petrol stations, where various measurements are gathered and transmitted to the centralized or distributed analysis platform.

Each petrol station is equipped with fuel tanks where liquefied fuel is stored and dispensing devices which act as sale endpoints. These appliances generate two streams of data supplemented with delivery records entered by station workers or detected automatically. Usually fuel volume and temperature is measured in tanks, whereas the amount of sold fuel is returned from meters installed in dispensers.

The common analysis performed upon the aforementioned values aims to detect various anomalies and other adverse phenomena that can occur at petrol stations. The most dangerous example is fuel leak [START_REF] Gorawski | Liquefied petroleum storage and distribution problems and research thesis[END_REF][START_REF]Preventing Leaks and Spills at Service Stations. A Guide for Facilities[END_REF], which introduces very serious consequences to the environment. In order to prevent such a threat, it is crucial to detect any volume of fuel leaked from tank and piping as fast as possible.

This paper is organized as follows. Section 2 contains information concerning data stream storage problems with theoretical base of a Stream Materialized Aggregate List (StrMAL) described. In Section 3 the architecture of StrMAL is presented along with examples of its most important features. Section 4 contains test results performed over a StrMAL engine, whereas Section 5 summarizes the paper.

Data Stream Storage

A Data stream [START_REF] Gilbert | Surfing wavelets on streams: One-pass summaries for approximate aggregate queries[END_REF][START_REF] Gorawski | The design of stream database engine in concurrent environment[END_REF][START_REF] Gorawski | Evaluation and development perspectives of stream data processing systems[END_REF][START_REF] Gorawski | A survey of data stream processing tools[END_REF] can be defined as an infinite sequence of tuples with unique timestamps and attributes carrying information describing various phenomena at subsequent moments of time. Stream Processing Systems usually do not provide any storage operation in their work flow, since they are designed to produce answers immediately as new data arrive. Optional data storage is sometimes used to provide static data as an extension to stream data.

Under certain circumstances an instant access to historical data stored in a database, as well as efficient processing performed on current data is required. Analyzing the history is necessary in learning process, where different trends, dependencies, and rules are discovered and remembered [START_REF] Sigut | Applying pattern classification techniques to the early detection of fuel leaks in petrol stations[END_REF]. Later, gathered knowledge is used to filter current stream in order to detect any desired events. This process frequently involves browsing data on a certain level of detailin other words -on different aggregation levels. Moreover, data retrieval and aggregation operations should not interfere with insertion of newly arrived data, which often cannot be completely eliminated.

The problem of processing both stored and current data has lead to the idea of the Stream Data Warehouse [START_REF] Bateni | Scheduling to minimize staleness and stretch in real-time data warehouses[END_REF][START_REF] Golab | Scheduling updates in a real-time stream warehouse[END_REF][START_REF] Kakish | Etl evolution for real-time data warehousing[END_REF][START_REF] Polyzotis | Meshing streaming updates with persistent data in an active data warehouse[END_REF][START_REF] Thiele | Multi-objective scheduling for real-time data warehouses[END_REF][START_REF] Vassiliadis | Near real time etl[END_REF]. It is an unified processing platform capable to produce immediate answers to complex queries concerning current and archived data. In current mode, data can be processed before they are persisted in any data structure, as in Stream Processing Systems.

Problems and issues

As a consequence of data stream nature, it is virtually not possible to store a whole stream in a memory. In addition, at a given moment of time, the stream contains only the most current tuples, since all read before have been already removed and archived, which forces searching the history (database).

Moreover, data in a stream are produced relatively frequently and in a unpredictable manner, which causes database to be updated very often and irregularly. High intensity of modifying transactions, being made in parallel with queries consisting of large range data retrieval, can lead to serious decrease in overall performance.

Relative database systems are designed to execute versatile CRUD (Create, Read, Update and Delete) operations on the whole dataset stored inside their internal memory. However, in stream appliances, updates take place only at the end of a time frame, i.e. tuples arrive and are organized ascending by timestamps. In this cause, it is not possible that once stored piece of data is updated.

Repetitive execution of the same or similar operations (e.g. aggregation) of the same datasets is usually time consuming and thus leading to unnecessary delays. In order to prevent these adverse situations, results of time costing operations can be stored along with query parameters to provide access to once computed values. As mentioned before, there are no updates on historical data causing the materialized data to be immutable.

Stream Materialized Aggregate List

Many items that are sequentially arranged (as tuples in a data stream) can be stored in a list data structure. In such a form, it is easy to view all subsequent elements in proper order. When browsing tuples from a stream, consecutive retrieving is the only operation considered here, which can be described as forward iterating over list.

An aggregate list [START_REF] Gorawski | Multi-thread processing of long aggregates lists[END_REF][START_REF] Gorawski | On efficient storing and processing of long aggregate lists[END_REF][START_REF] Gorawski | Towards storing and processing of long aggregates lists in spatial data warehouses[END_REF] can be defined as a sequential data structure, containing a subset of an aggregated stream (stream of aggregated tuples). It is stored in memory and acts as a physical representation of stream, beginning from certain moment of time. Because of the limited capacity of list, it is assumed that all aggregates already read can be replaced with more fresh data.

When considering various data collections, extracting data access operations into a separate interface is a common practice. Such an interface is called an iterator and is used to traverse any data structure (as aggregate list for example). Thus, an iterator can be used for retrieving tuples from a stream.

The aforementioned issues became a motivation for designing a solution which is capable to provide an uniform access to any data stream, efficiently manage available memory, and avoid redundant operations. It is done by using aggregate list, iterator interface, and aggregate materialization techniques. The solution has been named a Stream Materialized Aggregate List [START_REF] Gorawski | Time complexity of page filling algorithms in materialized aggregate list (mal) and mal/trigg materialization cost[END_REF] and is designed to act as a data storage tier of a Stream Data Warehouse [START_REF] Gorawski | Advanced data warehouses. Habilitation[END_REF].

It is possible to create several iterators attached to a single list and pointing to different elements. In such a situation, the distance (measured in time units) between them is unconstrained and can be arbitrary long, causing the whole list to occupy very large amount of memory. In order to prevent this situation, the following solution is used: the aggregate list itself is not located in memory, instead its active fragments (tuples being currently in use) are stored inside each iterator.

Moreover, in order to increase memory management efficiency, the following solution is used [START_REF] Gorawski | On efficient storing and processing of long aggregate lists[END_REF][START_REF] Gorawski | Towards storing and processing of long aggregates lists in spatial data warehouses[END_REF]: each iterator contains a static array which corresponds to an iterator-specific aggregate list fragment. As far as successive aggregates are retrieved from an iterator and become outdated, they are replaced by newer ones. Each array is logically divided into pages (basic units). Due to that, certain number of ready-to-read aggregates is always available. When the need of new aggregates creation occurs, a whole page at once is produced and replaces the old one.

Architecture of StrMAL

The Stream Materialized Aggregate List was implemented using multilayer concept. Each of them is realizing separate functionalities and is responsible for another stage of aggregates production. Figure 1 presents the overall architecture of StrMAL. Four layers have been denoted by the following acronyms: SDL, APL, DML, and CL -they are described later in the text.

In the Stream Distribution Layer (SDL) the process of aggregate list production begins with collecting data required for aggregation. It is done, depending on start time specified in query, by using current or historical stream. This layer provides a uniform access to data streams, irrespective of their origin (source) and start time.

The Aggregate Production Layer (APL) retrieves desired streams from the SDL and, basing on parameters obtained from client, performs aggregation. Outcome aggregates are delivered to clients and materialized (persisted for future use).

The Data Materialization Layer (DML) involves persisting aggregates in database, along with query parameters. Besides storing, this layer also provides searching and retrieving mechanisms. Cache memory (LRU buffer) is used to achieve better performance of I/O operations.

The Client Layer (CL) is responsible for communication with clients and providing them aggregates produced in the APL with data retrieved from the SDL or materialized aggregates read from the DML. It integrates all mentioned layers and uses them to prepare, produce, and serve results.

Current and Historical Stream Support

One of the major tasks of the Stream Distribution Layer is to collect tuples from current stream and store them temporally in a buffer called History Table (HT). It is performed in order to provide a flexible bridge between current and historical data. When the SDL is queried for a data stream beginning from a certain timestamp, first it performs a lookup over the HT to determine whether the desired data have been already produced -and when it is true -if they are still in the HT or have been persisted in a database.

The Stream Distribution Layer can operate in four states, depending on the distance between current and searched time. Each state determines the source from which data are retrieved and other working principles, such as next state reached under state-specific circumstances. These states are named as follows:

1. TAB -tuples are read from the History Table, 2. DB -tuples are read from a database, 3. SYNC -synchronization with the current stream, 4. CUR -tuples are read from the current stream.

The TAB is the starting state, when the SDL is queried with a specific timestamp and the History Table is searched to find whether the desired tuple is present in it. When the tuple is not found in the HT, it either has not been generated and acquired by the system or it has been archived and stored in a database. In the former case the SDL remains in the TAB state waiting for tuple to appear in the HT, whereas in latter cause, the SDL switches into the DB state and reads tuples from a database until the end of batch (certain number of tuples) is reached. After that, the SDL switches back into the TAB state.

In the other situation, after successful lookup, SDL remains in TAB state until the end of HT is reached (there are no more tuples to read). Such a circumstance denotes that next tuple ought to be retrieved from the current stream. However this process cannot simply be performed by switching into CUR state (when subsequent tuples are read from the current stream). SDL needs to synchronize with the current stream -it is done by entering SYNC state. In that state the SDL assures that no tuples will be omitted during switching -i.e. tuples being removed from the current stream and not yet written into the HT.

Test results

First test was conducted in order to verify the impact of History Table on archived tuple read time. The objective to that study was to simulate the situation involving reading subsequent tuples from current stream with variable time gap (delay) between each read operation. In such a case client reading tuples desynchronizes with stream and is obliged to perform a lookup in database containing archived data. When HT is used, it stores recent history of stream and allows the client of SDL to retrieve desired data from buffer instead of database.

Figure 3 presents tuple read time (in microseconds) with buffering in HT applied depending on HT size (in number of tuples). Three different delays were used: 1 s, 2 s, and 5 s. The starting size of HT was set to 8 and it was doubled respectively when there were any calls to database. The test was finished when all tuples were read from the buffer allowing client not to operate on persistent storage at all. Results show that tuple read time when using HT in 100% is about 6 times shorter than in the 5 s delay example (where almost 100% of read operations were made on a database). Next test was conducted to verify the percentage of HT calls in historical data retrieval depending on aggregate consumption time. Aggregates were read from CL and the following delays were introduced: 300 ms, 400 ms, 500 ms, 550 ms, 600 ms, 750 ms, and 1000 ms. Such values have been selected after preliminary tests which showed that below 300 ms there are no calls to any historical data because every tuple is read directly from the current stream. Between 500 ms and 600 ms an additional measure was performed (at 550 ms) due to high variability in that range. Four different sizes of History Table were used: 8, 16, 64, and 256 (measured in number of tuples).

Figure 4 shows that for two first examples (HT sizes: 8 and 16) the percentage of calls to HT suddenly dropped from 100% to about 10% at delay set to about 600 ms. It means that 90% of calls to historical data sources were made to database causing the overall aggregate production time to be longer. When HT size was set to 256 tuples about 40% of calls were still made to HT, even when aggregate consumption time was equal to 1 s.

Results of performed tests showed that using the History Table as buffering mechanism, while performing seamless switching between historical and current data sources, is legitimate. Tuple read time is noticeably shorter and database system is less loaded causing the whole process of aggregate production more efficient. In this paper we have described the architecture of the Stream Materialized Aggregate List engine, which is a component of Stream Data Warehouse, responsible for storing and serving data streams on various levels of aggregation. The StrDW itself is still at the planning stage, while its components, such as described StrMAL engine, are being intensively developed and tested.

In the nearest future we intend to design all concepts and modules of the StrDW, with spatial indexing, distributed architecture and low-latency query processing issues included. The target system is expected to process data streams in OLAP manner, allowing the analysis on currently changing multidimensional aggregated data to be performed in decision supporting applications with critical time requirements with distributed environment and concurrency issues involved, such as the aforementioned liquefied petrol storage and distribution system.

Fig. 1 .

 1 Fig. 1. Architecture of the StrMAL engine

Figure 2

 2 presents state diagram of the Stream Distribution Layer.

Fig. 2 .

 2 Fig. 2. State diagram of the SDL

Fig. 3 .

 3 Fig. 3. Tuple read time depending on HT size

Fig. 4 .

 4 Fig. 4. Percentage of HT calls depending on aggregate consumption time


Tahar Ziouel
email: t_ziouel@esi.dz

Khalissa Amieur-Derbal

Kamel Boukhalfa
email: kboukhalfa@usthb.dz

SOLAP On-the-Fly Generalization Approach Based on Spatial Hierarchical Structures

Keywords: On-the-fly map generalization, Hierarchical spatial structures, Spatial data warehouses, SOLAP

On-the-fly generalization, denotes the use of automated generalization techniques in real-time. This process creates a temporary, generalized dataset exclusively for visualization, not for storage or other purposes. This makes the process well suited to highly interactive applications such as online mapping, mobile mapping and SOLAP. BLG tree is a spatial hierarchical structure widely used in cartographic map generalization and particularly in the context of web mapping. However, this structure is insufficient in the context of SOLAP applications, because it is mainly dedicated to the geographic information processing (geometric features), while SOLAP applications manage a very important decision information that is the measure. In this paper, we propose a new structure, SOLAP BLG Tree, adapted to the generalizaion process in the SOLAP context. Our generalization approach is based on this structure and uses the simplification operator. Combining the topological aspect of geographical objects and the decisional aspect (the measure). Our experiments were performed on a set of vector data related to the phenomenon of road risk.

Introduction

Business intelligence is a major decision-making tool for strategic and daily management of data in the enterprise. It provides essential information in several forms to users (decision makers) so that they can analyze and manage their business by taking effectives decisions. Data warehousing and On Line Analytical Processing (OLAP) are technologies intended to support business intelligence. Indeed, Analysts and decision makers in the enterprise can thus analyze interactively and iteratively multidimensional data at a detailed or aggregated level of granularity through online Analytical Processing tools, OLAP, [START_REF] Chaudhuri | An overview of data warehousing and olap technology[END_REF] [2] [START_REF] Thomsen | OLAP solutions: building multidimensional information systems[END_REF]. Nevertheless, these data may have a geographic component that OLAP systems cannot process due their lack of tools for managing spatial data. A new technology has so, emerged, Spatial OLAP (SOLAP), resulting from integrating GIS technology (Geographic Information System) and OLAP [START_REF] Rivest | Solap technology: Merging business intelligence with geospatial technology for interactive spatio-temporal exploration and analysis of data[END_REF] [START_REF] Malinowski | Advanced data warehouse design: from conventional to spatial and temporal applications[END_REF].

SOLAP has been defined by [START_REF] Bédard | Spatial olap[END_REF] as a visual platform built especially to support rapid and easy spatio-temporal analysis and exploration of data following a multidimensional approach comprised of aggregation levels available in cartographic displays as well as in tabular and diagram displays.

SOLAP enriches the analysis of classical OLAP systems capabilities in many ways. For instance, providing visual information through maps and interacting with them by formulating queries directly on the cartographic display. Thus, the cartographic component in OLAP systems represents a graphic interface to spatial data warehouses (SDW) which introduce spatial data as subject or analysis axes.

In this context, the analysis of multi-dimensional spatial data often requires navigating through different levels of detail, in order to study the evolution of a phenomenon (fact), and thus allows an effective decision-making. On-the-fly generalization process is therefore well suited to this context, because it can interactively adapt the visualized geographic information to decision-makers needs [START_REF] Bimonte | Spatial olap and map generalization: Model and algebra[END_REF]. However it only addresses the cartographic aspect, at the expense of the decisional one, which is important in multidimensional analysis.

Widely addressed in cartography, on-the-fly generalization, well suited to highly interactive applications such as SOLAP, consists in generating temporary data at different levels of detail from the most detailed level. Different on-thefly generalization approaches have been developed [START_REF] Bereuter | Algorithms for on-the-fly generalization of point data using quadtrees[END_REF] and classified in two main groups. The first group relies on fast map generalization algorithms that generate coarser levels-of-detail in real-time. [START_REF] Weibel | Generalization, on-the-fly[END_REF]. The second group utilizes hierarchical spatial data structures [START_REF] Van Oosterom | Towards a true vario-scale structure supporting smooth-zoom[END_REF] [START_REF] Van Oosterom | Data structures for continuous generalisation: tgap and ssc[END_REF]. To the best of our knowledge, no work has proposed a generalization approach for SOLAP, nor the consideration of the decision making aspect (measure) in the generalization process.

In this paper, we propose an on-the-fly generalization approach for SOLAP systems. The approach we propose integrates topographic appearance (distance) and decision-making aspects (measure) for an on-the-fly generalization suited to cartographic experts and decision makers.

The present paper is organized as follows; the next section introduces some research work related to the addressed issue. Section 3 presents a detailed description of the proposed approach. The different steps of our experiments and some results are described in section 4. Section 5 concludes the paper and presents some perspectives.

Related work

Several research work have addressed the generalization for more than three decades [START_REF] Sarjakoski | Conceptual models of generalisation and multiple representation[END_REF] [13] [START_REF] Stanislawski | Generalisation operators[END_REF]. On-the-fly generalization has emerged with the development of highly interactive applications of cartography such as web mapping. The main used operators are selection and simplification [START_REF] Bereuter | Algorithms for on-the-fly generalization of point data using quadtrees[END_REF]. Among research work that have adressed on-the-fly generalization, we can cite [15] [16] carried in the contexte of the European project GiMoDig [START_REF]GiMoDig: Geospatial info-mobility service by real-time data-integration and generalisation[END_REF]. The objective of this project is to develop and test methods for providing spatial data to mobile users through real-time generalization. The work presented in [START_REF] Lejdel | Genetic agent approach for improving on-the-fly web map generalization[END_REF], combines multiple representation and cartographic generalization and uses an implementation of multiagent system where each agent was equipped with a genetic patrimony.

Since cartographic generalization creates a hierarchy of levels of detail, it is natural to use hierarchical structures such as tree structures for storage of the geometry (point, line, polygon) of an object in the highest level of detail. This structure is enriched with information that reflect the importance of a hierarchical level, from which, requested levels of detail may be generated. The generalization process is therefore, speeded up with rapid access to the elaborate structures. For each type of spatial data, corresponds an appropriate hierarchical structure that enables interactive and rapid generalization of geographic objects. BLG tree (Binary Line Generalization tree) has been proposed for linear objects [START_REF] Van Oosterom | The reactive-tree: A storage structure for a seamless, scaleless geographic database[END_REF] [START_REF] Van Oosterom | Variable-scale topological data structures suitable for progressive data transfer: The gap-face tree and gap-edge forest[END_REF], it applies the simplication generalization operator that uses a variant of the Douglas-Peucker algorithm [START_REF] Douglas | Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[END_REF]; instead of deleting the less important vertices, it stores them in the structure. The GAP tree (Generalized Area partitionning) has been proposed for the selection and fusion of polygons [START_REF] Van Oosterom | Variable-scale topological data structures suitable for progressive data transfer: The gap-face tree and gap-edge forest[END_REF] [10] [START_REF] Van Oosterom | Data structures for continuous generalisation: tgap and ssc[END_REF]. The Quadtrees have been proposed for point objects point objects, they allow applying the selection, simplification, aggregation and displacement operators [8] [22].

Furthermore, as we have already mentioned in Section 1, and to the best of our knowledge, there are no research work that have addressed integration of generalization in SOLAP. Nevertheless, some work focused on integration of spatial data as dimension or fact in SDW [START_REF] Rivest | Solap technology: Merging business intelligence with geospatial technology for interactive spatio-temporal exploration and analysis of data[END_REF] [START_REF] Bimonte | Spatial olap and map generalization: Model and algebra[END_REF].

In this paper, we propose to integrate on-the-fly generalization process in SOLAP, to adapt the level of detail that meets the decision-makers needs. The approach we propose focuses on linear objects that represent rivers, roads, etc. These latters constitute a geographical dimension linked to the phenomenon of road risk that we consider as use case study. BLG tree structure is dedicated to cartographic generalization of linear objects (roads in our case study). However, this structure cannot be efficiently used in decision-making process, because they don't consider the main decisional information in SOLAP, that is the measure.

To better understand this problem, we propose the example illustrated in Figure 1. The analyzed map contains six objects with associated measures. As presented in this example, among the objects at the most detailed level , the object C possesses the greatest measure (30), despite its geometric size is not indicative (see figure 1.a). When reducing the scale, the classical generalization process is triggered, considering only the topographic aspect, the object C is imperceptible (see figure 1.b) despite its decision relevance (the greatest measure) compared to the objective of the analysis performed by the decision-makers.

We propose a generalization approach based on a new version of BLG tree adapted to SOLAP called SOLAP BLG tree.

Proposed approach

The main objective of our approach is to develop an on-the-fly generalization system adapted to SOLAP applications. This system must be able to combine the decision and cartographic aspects to produce maps adapted to the needs of decision makers. Figure 2 shows the overall architecture of our approach. The spatial data warehouse stores decision data (measures, fact, dimensions, etc.) and cartographic data. The latter represented in a single level of detail (the highest one). When the user sends his request, the result is extracted from the stored data. It does not necessarily reflect the level of detail requested by the decision maker, therefore an on-the-fly generalization process is necessary to adapt this result to the expressed need.

Spatial data warehouse

Scale reduction

Request results

Decision Maker (Request)

Process steps

Generalized map

On-the-fly generalization module

SOLAP BLG tree creation

Extraction of the requested level of detail

Fig. 2. Global architecture of our approach

The generalization process that we propose is based on SOLAP BLG tree structure. A set of parameters related to the decision aspect is integrated to the structures including the importance function, aggregation etc. All these concepts are described as in the following sections.

SOLAP BLG tree

The creation of the SOLAP BLG tree revolves around two main steps: (1) the attribution of an importance value to each point of the polyline and (2) Creating the Hierarchy considering the importance of the points. Indeed, a polyline object (road, river, etc.) consists of a set of points (vertices). SOLAP BLG tree stores these points in a hierarchical structure. Each node of the structure consists of a point of the polyline along with its importance value elaborated by the following function: the importance I(p) for each point p will be determined according to its distance D(p) and its associated measure M (p) as follows:

I(p) = f (D(p), M (p))
. This function can be described by the sum of its cartographic importance (distance) and its decisional importance (measure):

I(p) = D(p) + M (p) (1)
The distance D(p) is the orthogonal distance between the segment connecting the two end points and the point p of the polyline. M (p) represents the measure at the point p. A node in the structure is created to represent a point p i , which importance value is M (p i ).

The polyline (p 1 , p n ) will be processed as follows: If the node root is represented by p k (a point on the polyline) having the highest importance value, the creation of other nodes follows an iterative process addressing all the points of the segments [p 1 , p k ] and [p k , p n ]. To illustrate this process, we propose the following example on road risk analysis; we focus on the number of accidents recorded on road segments connecting ten cities represented by c 1 to c 10 points (see Figure 3). Each segment carries a measure that represents the number of accidents reported on the segment connecting city c i to city c i+1 . We emphasize that in this case, the measures are associated with road segments, or the process requires their transposition to the endpoints constituting these segments. To do this we propose that the measure of each point p i is determined by the maximum value of the measure of the segments to which the point pi belongs: Let M (p i ) be the measure at point p i .

M (p i ) = M ax(M ([p i-1 , p i ]), M ([p i , p i+1 ])
Furthermore, the values of the measures and distances such as identified have different domains. Indeed there is a significant difference between these two parameters. A normalization step is thus necessary, in order to make the values comparable to each other. To do this we will restrict values between 0 and 1. For each value V of a measure or a distance, its normalized value V is calculated as follows:

V = V -V min V max -V min (2)
Thus, the BLG structure of the original polyline depicted in figure 3 is as shown in figure 4.

Proposed generalization process

The on-the-fly generalization process adapted to SOLAP context is guided by the SOLAP BLG tree structure according to the method described below.

Once these structures built, they are saved in a session work. When navigating between the different levels of detail, the on-the-fly generalization process is triggered to retrieve only the visible points in the required level of detail. The selection of these points is performed by comparing the importance values previously stored with a threshold value. The latter is determined by the visualization scale and other cartographic parameters that require the intervention of an expert cartographer. In the context of this work we used experimentally determined thresholds. Indeed, the threshold determines the tree traversal depth, by selecting only the nodes whose relevance value is greater than the threshold.

Measures aggregation

The measures associated with the different objects are subject to an aggregate function that determines the measures of the resulting objects. This maintains the importance of the decision-making aspect of the different requested levels of detail. This aggregation function is developed according to the analyzed fact. For example for the analysis of the road risk phenomenon, the proposed aggregation function is the sum function, to preserve the information on the total number of accidents on the generalized object.

To aggregate polylines measures, we propose the creation of a data structure, containing the values of the measures associated with the different segments constituting the initial polyline depicted in Figure 3 as shown in the example of table 1. During the generalization with the BLG tree, we obtain a new polyline where the segments S i to S k are removed and replaced by a new segment formed by the first point of S i and the last point of S k , to evaluate the measure associated with this new segment, one can read the above table and sum the measures corresponding to the segments from S i to S k .

To illustrate this process we will use the polyline shown in Figure 5, in each segment we took the values of measures in accordance with the table above. After simplification of the polyline we get two segments formed by the points C 1 , C 5 and C 10 , the points C 2 through C4 are deleted along with the points C 6 through C 9 . The measure associated with the new segment [C 1 , C 5 ] represents the sum of the measures contained in the table (measure of the segments S 1 through S 4 ). It is therefore clear that the displayed map will be simplified in order to highlight the information requested by the query.

Experimentation

The validation of our approach involves the construction of the proposed spatial structure SOLAP BLG tree used in in the implemented generalization process. We choose the road risk as a case study given its socio-economic impact worldwide. According to statistics from the World Health Organization [START_REF] Bencherif | Les accidents de la route dans les médias de masse en algérie. du traitement de l'information à sa diffusion[END_REF], the road causes each year more than 1.2 million deaths and between 20 to 50 million wounded. In a previous work, we addressed this phenomenon by incorporating spatial information [START_REF] Amieur | De la conception d'un entrepôt de données spatiales à un outil géo-décisionnel pour une meilleure analyse du risque routier[END_REF] [START_REF] Derbal | Spatial data warehouse and geospatial decision making tool for efficient road risk analysis[END_REF].

Our tests are performed on vector spatial data. We used multiple softwares and hardawre ressources to implement our generalization prototype : Our experiments were performed on a data set that represents the road theme of Dar El Beida municipality in Algiers enriched by different measures representing the number of accidents recorded on the considered roads (Figure 6).

SOLAP BLG tree Test

To test the SOLAP BLG tree, we selected a road in Dar El Beida municipality. This road is shown in red in Figure 6. It includes 28 segments each one having a measure. Our generalization system simplifies this road at smaller scales, taking into account the decision aspect (measures). Following the proposed approach, the generalization of the selected road allows to restore only the segments points visible at the required scale. From a more detailed scale, we can analyze the results obtained at different scales (see Figure 5). For example in scale 1: 5000 all relevant segments road except the segment S2 are visible on the map, whereas, at the scale 1: 10,000, there are only four relevant segments and at the scale 1: 50,000 relevant segments are no longer visible.

Figure 10 shows a comparison between the results of the generalization with SOLAP BLG as part of this work and the results of the generalization with the classic BLG tree. We can see that at the same scale 1: 10 000, relevant road segments are visible in the case of SOLAP BLG tree (segments S13, S16, S22 and S26), while they are no longer in the case of classical BLG tree, despite This paper presented an on-the-fly generalization approach adapted to SOLAP applications. This process is intimately linked to the highly interactive applications in cartography such as web mapping, mobile mapping and SOLAP applications. But this latters, require the simultaneous consideration of cartographic and decisional aspects by integrating the measure in the process.

Our proposed approach is based on SOLAP BLG tree, it consists on adapting BLG tree structure, initially dedicated to cartographic generalization, to SOLAP. It focuses on linear objects (roads in our case study) and integrates the measure in order to adapt the level of detail that meets the decision-makers needs.

To validate our approach, we chose the road risk phenomenon as analysis subject, this is particularly due to its worldwide socio-economic impact. In addition, the use of map in the analysis of such phenomenon is of major interest for decision-makers because it is closely related to geographic information represented by the road object and the locality to which it belongs. In our experiments, we have highlighted the contribution of the proposed structure in the context of SOLAP through the various implemented functions such as importance function, and whose application has allowed preserving measures while providing cartographic perceptibility.

As future issues, we suggest : (1) improving the current solution by adapting the other generalization operators (as is smoothing, displacement, typification, exaggeration, etc.) to SOLAP applications. This will allow generating a better quality of maps and hence, improve the decision making process. (2) Adapt the generalization process to SDW by using another generalization approach, for example, the one, based on rapid generalization algorithms and (3) elaborate a comparative study between the implemented approaches according to some defined criteria in order to assess their effectiveness in a given context of use.

Fig. 1 .

 1 Fig. 1. Traditional generalization results

Fig. 3 .

 3 Fig. 3. Polyline (road) representation in SOLAP

Fig. 4 .

 4 Fig. 4. The built SOLAP BLG tree structure

Fig. 5 .

 5 Fig. 5. SOLAP BLG tree generalization results

  (1) Oracle 11g Enterprise Edition as DBMS (Management System Database) via its component Oracle Spatial. (2) Oracle MapViewer for viewing the map of the analyzed area. (3) Oracle Weblogic Server on which MapViewers components are deployed. (4) Oracle Map Builder was used to load the geographical data in the DBMS and the construction of the map. (5) Oracle JDeveloper tool as a code editor.

Fig. 6 .

 6 Fig. 6. Road network of Dar El Beida and the selected road

Figure 7 Fig. 7 .Fig. 8 .

 778 Figure 7 illustrates a detailed representation of the selected route; segments with the highest number of accidents are highlighted.

Fig. 9 .

 9 Fig. 9. Generalization results guided by SOLAP BLG tree

Fig. 10 .

 10 Fig. 10. Comparaison between the results of generalization by the SOLAP BLG tree and the BLG tree

Table 1 .

 1 Data structure dedicated to measures storage

	Segment S1 S2 S3 S4 S5 S6 S7 S8 S9
	Measure 10 13 7 50 10 2 4 25 15