Wojciech Bożejko
email: wojciech.bozejko@pwr.edu.pl

Piotr Nadybski
email: nadybskip@pwsz.legnica.edu.pl

Mieczys Law Wodecki
email: mieczyslaw.wodecki@uwr.edu.pl

Two step algorithm for virtual machine distributed replication with limited bandwidth problem

This article presents a proposal of solution for the problem of optimization of the virtual machine (VM) backup or replication process in architecture with multiple locations where efficient bandwidth usage and maximal tardiness for single VM are objectives. The two step algorithm is considered, where in the first step a set of tasks is partitioned into smaller subsets for load balancing. In the second step -tabu search algorithm is used to minimize weighted sum of tardiness. The paper contains the results of computational experiments on the scalability of the presented method.

Introduction

In the recent years cloud computing model has became one of the most commonly used architectures for modern IT systems. Many software developers or organizational end users decide to migrate from traditional server environment to cloud based solutions. Recent experiences of customers show that products in this group of technology are now mature, reliable and can offer us many benefits: security, demanded performance and reduced costs of exploitation of IT resources. What is more, the use of such a model of IT systems development changes quite radically the way of thinking about IT tools, which, regardless of their complexity and structure, is becoming just a service to the end user instead of being just a piece of hardware and software running on it [START_REF] Armbrust | A view of cloud computing[END_REF]. Undoubtedly, this simplicity is just a user's point of view. In fact, technical background in hardware, as well as in software layer, is much more complex and is based on many complementary technologies. The term cloud computing is not a name for a specific service or product. It is rather used to describe a certain model, a trend in the area of computer system engineering.

One of the most commonly used technologies connected with cloud computing is virtualization as it most often provides technical basis for cloud computing architecture. Virtualization involves separating the software from the physical environment in which it is run. The division may occur at a few levels. Infrastructure-as-a-Service (IaaS) is one of the possibilities [START_REF] Mell | The NIST definition of cloud computing[END_REF]. In this model the most important definition is a virtual machine (VM). This is a software implementation of a machine that executes programs operating systems and applications like a physical machine. Each virtual machine has its own set of virtual hardware that implements its functionality through the use of physical hardware. Essentially, many virtual machines can run on one physical computer simultaneously. The most important components of the typical platform for running virtual machines are: hardware components (a single server or a cluster of servers) delivering necessary computing power, memory and disk space for image files of virtual machines and hypervisor (Virtual Machine Manager -process running on physical machine responsible for realization of VM instruction on physical hardware). To ensure reliability and performance in bigger solutions serving dozens or hundreds VMs disk space is delivered usually by dedicated storage systems.

Reliability, in addition to functionality and performance, is the most important requirement of IT systems. Redundancy is one of the best practices in this field. This means that at least two components realize a specific function. If one fails, the other provides the continuous work of the system. For example, in the case of database servers the consistency of the two copies of the data in the both databases is required. In cloud computing infrastructure with virtual machines redundancy in most situation means that there are at least two data stores and hypervisor managing virtual machines on two separated hardware platforms. Undeniably both copies should be identical. Data integrity process is known as replication. There are many strategies for data replication. Among them there are synchronous, asynchronous and point-in-time replications. The first two of them assume that data will be distributed to all backup storages immediately (synchronous) or as soon as possible (asynchronous). Undoubtedly this is the best strategy in case of failure, nevertheless it requires a lot of hardware resources and very fast network connection between data stores. In point-in-time strategy data (for example periodic snapshots -state of a virtual machine at a particular point in time) is copied to backup localization.

With the progress of cloud technology deployment in real business solutions, the problem of workflow scheduling became an important field of interest for researches. Many of them were described in work Wu et al. [START_REF] Wu | Workflow scheduling in cloud: a survey[END_REF]. Commercial usage requires on-time resource delivery and guaranteed or predictable time of tasks processing, handling of failures, while costs of hardware resources, power consumption etc. should be reduced as much as possible. The most challenging aspect of the workflow scheduling problems solving process is the fact, that they are NP-hard, so finding optimal solution in those cases is usually impossible in acceptable time period. Problem of tasks scheduling, described in this paper is an example of this class of problems.

Problem description and preliminaries

There is an infrastructure for running clients virtual machines (Figure 1). Analysis of system load statistics shows that there are significant differences in the current use of resources in different parts of the day. In addition to the main data store, there are m backup localizations. Each VM should have one, as actual as possible, backup copy. During the normal system state secondary instance of virtual machine image is immediately synchronized with primary one. Due to big bandwidth usage a situation where users import, restore or create a new virtual machine is more problematic. In such a situation big amount of data is generated and needs to be replicated (Figure 2). To avoid decrease of the system performance, backup copies of new instances are made cyclic, only in the previously mentioned moments when the system usage level is expected to be acceptably low.

Basic assumptions:

-There is m backup localization and each of them is connected with primary location by connection of limited bandwidth. It means that in specified time only limited amount of data can be send. Let -There are n new machines (tasks) to be transferred to secondary location. Each VM has specified size, so transferring it to backup location takes particular period of time, depending on connection bandwidth. Each newly created VM has timer showing the period between creation moment and current time. The timer stops when backup process begins. Each machine should be replicated as soon as possible. There is due time for each new machine to be copied. If not, cost of the tardiness is counted for late replication. What is more, each virtual machine has priority, depending on customer costs plan or administrator's decision. V = {1, 2, ..., n} -set of tasks -new virtual machines, s v -size of machine v (v ∈ V), d v -due time for machine v replication, w v -positive weight of the virtual machine v tardiness.

-Tardiness is a time between the moment of completion the replication and due time:

T v = max{0, C v -d v } -tardiness, and
w v • T v -cost of v machine replication.
-The main goal is to make a backup copy of each new virtual machine and minimize the summary cost of the replication process. Summary cost is given by formula

n v=1 w v • T v .
As mentioned earlier in this document, finding global optimal solution due to computational complexity is not possible in most real situations where a set of solutions is too big to check all possibilities. For problem described above there is the two step algorithm proposed

Step 1: for each v ∈ V choose l ∈ L where V j < b l (this condition is true when the total bandwidth is sufficient) and j is a number true of machine planned to be replicated to location l (see Algorithm 1);

Step 2: sort the tasks for each location l to minimize cost.

General conception is shown in Figure 3.

Assign Virtual Machine to backup location

The main goal of the first step is to provide optimal use of all available bandwidth. This is a typical problem for issues related to the load balancing in computer networks. In algorithm described in this paper Weighted Least-Used strategy is implemented. It means that each time when location for the single Virtual Machine is chosen, the least heavily loaded backup storage is preferred [START_REF] Ellrod | Load Balancing -Least Connections[END_REF]. Level of load (CL) is calculated as

CL = k+1 i=1 s i b l ,
where k is a number of virtual machines already assigned to location l, the k+1 machine is the actually considered one and b l is maximal amount of data to be transferred during one cycle without overload to location l and s i is a size of machine i.

Tabu Search algorithm for The Single Machine Total Weighted Tardiness Problem

As a result of Step 1 all Virtual Machines are assigned for replication to one of the available backup locations. From this moment each channel can be considered separately and is known as The Single Machine Total Weighted Tardiness Problem (1|| w i T i , [START_REF] Wodecki | A Branch-and-Bound Parallel Algorithm for Single-Machine Total Weighted Tardiness Problem[END_REF], [START_REF] Wodecki | A block approach to earliness-tardiness scheduling problems[END_REF], see also [START_REF] Lin | A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem[END_REF], [START_REF] Bulbul | A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem[END_REF], [START_REF] Bożejko | Parallel genetic algorithm for minimizing total weighted completion time[END_REF]). As the problem is NP-hard, the heuristics algorithms are used instead of classic method. As the problem has applications in many fields of science and industry, this problem was the subject of many studies. For the purpose of this experiment classic form of the tabu search (TS) algorithm has been implemented. For neighborhood permutations generating s-moves there are used ( [START_REF] Bożejko | On the theoretical properties of swap multimoves[END_REF], [START_REF] Bożejko | Solving Permutational Routing Problems by Population-Based Metaheuristics[END_REF]). After preliminary calculations, tabu list length was set to 7. Table 2 contains average relative change between greedy algorithm (GREE) and tabu search optimized results for set of data used in this experiment. Due to greedy algorithm tasks are firstly ordered by d i (due time) from the shortest time to the longest and then, one by one, assigned to remote backup location where cost for this machine would be the lowest. The method presented in this paper, compared with GREE, allowed for a 40 to 50 percent reduction of the w i • T i cost, depending on the test set of data.

Conclusion

Strategy for scheduling backup or replication tasks in cloud computing, virtualization environment presented in this paper is based on two methods widely used for solving problems in industry and computer networks. Both of them used together as the two-step algorithm allow to improve performance and reduce time needed for operations. In the first step the size of problem is reduced by quick method, where each task is assigned to destination based on amount of data to be transferred and bandwidth usage of each available network connection. This operation reduces the size of a set processed by a more precise but also more complex algorithm used in the second step. The proposed method can produce less accurate results than in case, when classic heuristic like Tabu Search is only used, but should reduce processing delay. Further research is also possible for tabu search for or example more sophisticated method in the first step can be tested. The discussed method can be used for problems in cloud computing like non on-line replication, synchronization where many network connections, data storages or virtualization platforms are available. As the parameters of cost function are freely definable other use is also possible.

Fig. 1 .

 1 Fig. 1. Cloud architecture.

Fig. 2 .

 2 Fig. 2. Daily load condition of the system

Fig. 3 .

 3 Fig. 3. Conception of backup data flow.

Fig. 4 .

 4 Fig. 4. Computing time in (ms) for increasing number of VMs (50 iterations).

Table 1 .

 1 Computing time in (ms) for increasing number of VMs).

	VMs	storages iterations computing time
	50	5	50	294
	100	5	50	2578
	200	5	50	21538
	500	5	50	508956
	1000	5	50	6431293
	50	10	50	97
	100	10	50	930
	200	10	50	6331
	500	10	50	137865
	1000	10	50	1804413
	50	5	100	562
	100	5	100	3320
	200	5	100	45944
	500	5	100	860553
	1000	5	100	11504165

Table 2 .

 2 Algorithm 2 Pseudocode for GREE algorithm. Relative change (GREE and TS algorithms)

	sort V in ascending order by due time
	for all v in V do
	xv ← 1		index of optimal already found backup location for this VM
	y ←	n 1 i=1 (wi * Ti) + (wv * Tv)	n1 -number of backup tasks assigned already
	to location 1
	for all l in L do
	calculate C l =	n l i=1 (wi * Ti) + (wv * Tv)	Cost of tasks (vm) assigned to l
	location and task v
	if C l < y then
	xv ← l
	end if
	end for
	end for
	VMs/tasks	GREE cost	TS cost	Relative change
		50	1803	872	0.52
		100	8911	4493	0.50
		200	43318	24885	0.43
		500	253636	148099	0.42
		1000	1051256	624702	0.41

Algorithm 1 Pseudocode for least-used method. sort V in descending order for all v in V do

x ← 0 index of least loaded location y ← 0 index of least loaded and not overloaded location

Computational Experiments

Algorithm was implemented in C# language and tested on Intel i7 3537U (3.1 GHz) processor. In the first run the number of backup locations was set to 5. The set of VMs was randomly generated five times and the algorithm was run for each of them. Then the average time was calculated. The number of iterations for tabu search was set to 50. The operations were repeated for 100, 200 and 500 VMs. In the second run the number of backup location was set to 10. The rest of the procedure was unmodified. The results are presented in the Table 1 and Figure 2.

On the test platform, sets of few hundreds were computed in acceptable time of few minutes, especially when the number of locations was also 10 or more. The performed experiment proved that algorithm is more efficient in cases where more backup location is available. The reason for this is the fact that in such cases the whole set is subdivided into more smaller subsets that are optimized by tabu search.

As expected, with increasing amount of virtual machines to backup, the number of operations to be performed consequently increases very fast. It is worth mentioning that increasing number of backup location causes shorter completion time.


Micha L Woźniak
email: [michal.wozniak@pwr.edu.pl

Pawe L Ksieniewicz
email: pawel.ksieniewicz@pwr.edu.pl

Krzysztof Walkowiak
email: krzysztof.walkowiak]@pwr.edu.pl

Ensembles of Heterogeneous Concept Drift Detectors -Experimental Study

Keywords: data stream, concept drift, pattern classification, drift detector

For the contemporary enterprises, possibility of appropriate business decision making on the basis of the knowledge hidden in stored data is the critical success factor. Therefore, the decision support software should take into consideration that data usually comes continuously in the form of so-called data stream, but most of the traditional data analysis methods are not ready to efficiently analyze fast growing amount of the stored records. Additionally, one should also consider phenomenon appearing in data stream called concept drift, which means that the parameters of an using model are changing, what could dramatically decrease the analytical model quality. This work is focusing on the classification task, which is very popular in many practical cases as fraud detection, network security, or medical diagnosis. We propose how to detect the changes in the data stream using combined concept drift detection model. The experimental evaluations confirm its pretty good quality, what encourage us to use it in practical applications.

Introduction

The analysis of huge volumes and fast arriving data is recently the focus of intense research, because such methods could build a competitive advantage of a given company. One of the useful approach is the data stream classification, which is employed to solve problems related to discovery client preference changes, spam filtering, fraud detection, and medical diagnosis to enumerate only a few.

However, most of the traditional classifier design methods do not take into consideration that:

-The statistical dependencies between the observations of the given objects and their classifications could change.

-Data can arrive so quick that labeling all records is impossible.

This section focuses on the first problem called concept drift [START_REF] Widmer | Learning in the presence of concept drift and hidden contexts[END_REF] and it comes in many forms, depending on the type of change. Appearance of concept drift may potentially cause a significant accuracy deterioration of an exploiting classifier. Therefore, developing positive methods which are able to effectively deal with this phenomena has become an increasing issue. In general, the following approaches may be considered to deal with the above problem.

-Frequently rebuilding a model if new data becomes available. It is very expensive and impossible from a practical point of view, especially when the concept drift occurs rapidly. -Detecting concept changes in new data, and if these changes are sufficiently significant then rebuilding the classifier. -Adopting an incremental learning algorithm for the classification model.

Let's firstly characterize shortly the probabilistic model of the classification task [START_REF] Duda | Pattern Classification[END_REF]. It assumes that attributes x ∈ X ⊆ R d and class label j ∈ M = {1, 2, ..., M } are the observed values of a pair of random variables (X, J). Their distribution is characterized by prior probability

p j = P (J = j), j ∈ M (1)
and conditional probability density functions3

f j (x) = f (x|j), x ∈ X , j ∈ M. (2)
The classifier Ψ maps feature space X to the set of the class labels M

Ψ : X → M. (3)
The optimal Bayes classifier Ψ * minimizes probability of missclassification according to the following classification rule4 :

Ψ * (x) = i if p i (x) = max k∈M p k (x), (4)
where p j (x) stands for posterior probability

p i (x) = p i f i (x) f (x) (5)
and f (x) is unconditionally density function.

f (x) = M k=1 p k f k (x) (6)
Backing to the concept drift problem we may distinguished two types of drifts according its influence into probabilistic characteristics of the classification task [START_REF] Gama | A survey on concept drift adaptation[END_REF]:

virtual concept drift means that the changes do not have any impact on decision boundaries (some works report that they do not have an impact on posterior probability, but it is disputable), but they change unconditionally density functions [START_REF] Widmer | Effective learning in dynamic environments by explicit context tracking[END_REF].

real concept drift means that the changes have an impact on decision boundaries, i.e., on posterior probabilities [START_REF] Schlimmer | Incremental learning from noisy data[END_REF][START_REF] Widmer | Learning in the presence of concept drift and hidden contexts[END_REF].

Considering the classification task, the real concept drift is the most important, but detecting the virtual one could be useful as well, because in the case if we are able not only to detect the drift, but also distinguish between virtual and real concept drift, then we may decide if classifier's model rebuilding is necessary or not. Another taxonomy of concept drift bases on its impetuosity. We may distinguish:

-Slow changes (gradual or incremental drift). For the gradual drift for a given period of time examples from different models could appear in the stream concurrently, while for incremental drift the model's parameters are changing smoothly. -Rapid changes (sudden drift, concept shift).

A plethora of solutions have been proposed how to deal with this phenomena. Basically, we may divide these algorithms into four main groups:

1. Online learners [START_REF] Wozniak | A hybrid decision tree training method using data streams[END_REF] 2. Instance based solutions (also called sliding window based solutions) 3. Ensemble approaches [START_REF] Krawczyk | One-class classifier ensemble pruning and weighting with firefly algorithm[END_REF][START_REF] Ludmila | Classifier ensembles for changing environments[END_REF][START_REF] Ouyang | Study on the classification of data streams with concept drift[END_REF]

Drift detection algorithms

In this work we will focus on the drift detectors which are responsible for determining whether two successive data chunks were generated by the same distribution [START_REF] Harel | Concept drift detection through resampling[END_REF]. In the case the the change is detected the decision about collecting new data to rebuild new model could be made.

Concept drift detection

As we mentioned above the appearance of concept drift may potentially cause a significant accuracy deterioration of an exploiting classifier [START_REF] Lughofer | Handling drifts and shifts in on-line data streams with evolving fuzzy systems[END_REF], what is shown in Fig. 1.

Concept drift detector is an algorithm, which on the basis of incoming information about new examples and their correct classification or a classifier's performance (as accuracy) can return information that data stream distributions are changing. The currently used detectors return only signal about drift detection, which usually requires a quick classifier's model updating or that warning The drift detection could be recognized as the simple classification task, but from practical point of view detectors do not use the classical classification model. The detection is hard, because on the one hand we require quick drift detection to quickly replace outdated model and to reduce so-called restoration time. On the other hand we do not accept false alarms [START_REF] Gustafsson | Adaptive Filtering and Change Detection[END_REF], i.e., when detector returns that change appears, but it is not true. Therefore to measure performance of concept drift detectors the following metrics are usually used:

-Number of correct detected drifts.

-Number of false alarms.

-Time between real drift appearance and its detection.

In some works, as [START_REF] Bifet | CD-MOA: Change detection framework for massive online analysis[END_REF], aggregated measures, which take into consideration the mentioned above metrics, are proposed, but we decided not to use them because using aggregated measures do not allow to precisely analyse behavior of the considered detectors.

Description of the chosen drift detectors

Let us shortly describe selected methods of drift detection, which later will be used to produce combined detectors.

DDM(Drift Detection Method )

This algorithm [START_REF] Gama | Learning with drift detection[END_REF] is analyzing the changes in the probability distribution of the successive examples for different classes. On the basis of the mentioned above analysis DDM estimates classifier error, which (assuming the convergency of the classifier training method) has to decrease, what means the probability distribution does not change [START_REF] Raudys | Statistical and Neural Classifiers: An Integrated Approach to Design[END_REF]. If the classifier error is increasing according to the number of training examples then this observation suggests a change of probability distribution and the current model should be rebuilt. DDM estimates classification error, its standard deviation and stores their minimal values. If estimated error is greater than stored minimal value of error and two times its standard deviation then DDM returns signal that the warning level is achieved. In the case if estimated error is greater than stored minimal value of error and three times its standard deviation then DDM returns signal that drift is detected.

CUSUM (CUmulative SUM )

CUSUM [START_REF] Page | Continuous Inspection Schemes[END_REF] detects a change of a given parameter value of a probability distribution and indicated when the change is significant. As the parameter the expected value of the classification error could be considered, which may be estimated on the basis of labels of incoming objects from data stream. The detection condition looks as follows

g t = max(0, g t-1 + t -ξ) > treshold (7)
where g 0 = 0 and t stands for observed value of a parameter in time t (e.g., mentioned above classification error). ξ describes rate of change. Te value of treshold is set by an user and it is responsible for detector's sensitivity. Its low value allows to detect drift quickly, but then a pretty high number of false alarms could appear [START_REF] Bifet | CD-MOA: Change detection framework for massive online analysis[END_REF][START_REF] Gama | A survey on concept drift adaptation[END_REF].

Test PageHinkley

It is modification of the CUSUM algorithm, where the cumulative difference between observed classifier error and its average is taken into consideration [START_REF] Sebastiao | A study on change detection methods[END_REF].

Detectors based on Hoeffding's and McDiarmid's inequalities

The interesting drift detectors based on non-parametric estimation of classifier error employing Hoeffding's and McDiarmid's inequalities were proposed in [START_REF] Inocencio | Online and non-parametric drift detection methods based on hoeffding's bounds[END_REF].

Combined concept drift detectors

Let's assume that we have a pool of n drift detectors

Π = {D 1 , D 2 , ..., D n } (8)
Each of them returns signal that warning level is achiever or concept drift is detected, i.e.,

D i =    0 if drif t is not detected 1 if warning level is achieved 2 if drif t is detected (9)
As yet not so many papers deal with combined drift detectors. Bifet et al. [START_REF] Bifet | CD-MOA: Change detection framework for massive online analysis[END_REF] proposed the simple combination rules based on the appearance of drift once ignoring signals about warning level. The idea of combined drift detector is presented in Fig. 4. Let's present three combination rules which allow to combine the concept drift detector outputs. Because this work focuses on the ensemble of heterogeneous detectors, therefore only the combination rules using drift appearance signal are taken into consideration.

ALO (At Least One detects drift)

Committee of detectors makes a decision about drift if at least one individual detector returns decision that drift appears (not all of the detectors can return warning signal).

ALO(Π, x) = 0 n i=1 [D i (x) = 2] 1 n i=1 [D i (x) = 0] (10)
where [] denotes Iverson bracket.

ALHD (At Least Half of the detectors detect Drift)

Committee of detectors makes a decision about drift if at half of individual detectors return decisions that drift appears.

ALHW D(Π, x) = 0 n i=1 [D i (x) = 2] < n 2 1 n i=1 [D i (x) = 2] n 2 (11)

AD (All detectors detect Drift)

Committee of detectors makes a decision about drift if each individual detector returns decisions that drift appears.

ALHW D(Π, x) = 0 n i=1 [D i (x) = 2] < n 1 n i=1 [D i (x) = 2] n (12)
Let's notice that proposed combined detectors are de facto classifier ensembles [START_REF] Wozniak | A survey of multiple classifier systems as hybrid systems[END_REF], which use deterministic (untrained) combination rules. They do not take into consideration any additional information as about individual drift detector's qualities. In this work, we also do not focus on the very important problem how choose the valuable pool of individual detectors. For classifier ensemble such a process (called ensemble selection or ensemble pruning) uses diversity measure [START_REF] Ludmila | Combining Pattern Classifiers: Methods and Algorithms[END_REF], but for the combined detectors the measures have been using, thus far is impossible, because of different nature of the decision task.

Experimental research

Goals

The main objective of the experimental study was evaluating the proposed combined concept drift detectors and their comparison with the well-known simple methods. To ensure the appropriate diversity of the pool of detectors we decided to produce an ensemble on the basis of five detectors employing different models presented in the previous section. For each experiment we estimated detector sensitivity, number of false alarms and computational complexity of the model, i.e., commutative running time.

Set-up

We used the following models of individual detectors: As we mentioned above we use the individual detectors to build three combined ones based on the ALO, ALHD, and AD combination rules.

All experiments were carried out using MOA (Massive Online Analysis) 5 and our own software written in Java according to MOA's requirements [START_REF] Bifet | Moa: Massive online analysis[END_REF].

For each experiment 3 computer generated data streams were used. Each of them consists of 10 000 examples:

-Data stream with sudden drift appearing after each 5.000 examples.

-Data stream with gradual drift, where 2 concept appear.

-Data stream without drift.

The stationary data stream (without drift) was chosen because we would like to evaluate the sensitivity of the detector, i.e., number of false alarms.

Results

The results of experiment were presented in Tab.1-36

Discussion

Firstly we have to emphasize that we realize that the scope of the experiments was limited therefore drawing the general conclusions is very risky. For each experiments the detector based on Hoeffding's inequality (HDDM W) [START_REF] Inocencio | Online and non-parametric drift detection methods based on hoeffding's bounds[END_REF] outperformed other models. The combined detectors have not behaved well for sudden and frequent drift (see Tab.1), because some of them (as ALO) has to low sensitivity or so high sensitivity (as for AD) caused a high number of false alarms. The computation time of AD detector was similar as in the case of HDDM A or HDDM W, but as we mentioned before the number of false alarms was not acceptable. For gradual drift the combined detectors ALHD and AD behaved similar as individual detectors. For stationary stream they have not presented so high sensitivity (similar as individual detectors). Probably, not so impressive results of combined detectors have been caused by the fact that we nominated the the individual models arbitrary and we did not check how adding or removing detector from the pool could impact on the combined detector quality. Additionally, HDDM W and HDDM A detectors strongly outperformed other models, what could cause that the decision of the detector ensemble was the same as the dominant models. The similar observation has been reported for the classifier ensemble using deterministic combination rules. On the basis of the experiment we are not able to say expressly if the combined concept drift detectors are promising direction. Nevertheless, we decided to continue the works on such models, especially for a pool of homogeneous detectors and method which are able to prune the detector ensemble. We have also to notice the main drawback of the proposed models, which are more complex than single ones. On the other hand we have to notice that using the proposed method of parallel inter-connection is easy to parallelize and could be run in a distributed computing environment.

Final remarks

In this work three simple combination rules for combined concept drift detectors were discussed and evaluated on the basis of the computer experiments for different data streams. They seem to be an interesting proposition to solve the problem of concept drift detection, nevertheless the results of experiments do not confirm their high quality, but as we mentioned above it is probably caused by very naive choice of the individual models of the detector ensemble.

It is worth noticing that we assume the continue access to class labels. Unfortunately, from the practical point of view it is hard to be granted that labels are always and immediately available, e.g., for credit approval task the true label is usually available ca. 2 years after the decision, then such labeled example could be worthless as come from outdated model. Therefore, during constructing the concept drift detectors we have to take into consideration the cost of data labeling, which is usually passed over. It seems to be very interesting to design detectors on the basis of a partially labeled set of examples (called active learning) [START_REF] Greiner | Learning cost-sensitive active classifiers[END_REF] or unlabeled examples. Unfortunately, unsupervised drift detectors can detect the virtual drift only, but it is easy to show that without access to class labels (then we can analyse the unconditionally probability distribution only f (x)) the real drift could be undetected [START_REF] Sobolewski | Concept drift detection and model selection with simulated recurrence and ensembles of statistical detectors[END_REF].

Let's propose the future research directions related to the combined concept drift detectors:

-Developing methods how to choose individual detectors to a committee, maybe dedicated diversity measure should be proposed. In this work the diversity of the detectors was ensured by choosing different detector's models, but we may also use the same model of detector but with different parameters, e.g., using different drift confidences and warning confidences for detector based on McDiarmid's inequality. -Proposing semi-supervised and unsupervised methods of combined detector training. -Proposing trained combination rule to establish the final decision of the combined detector and to fully exploit the strengths of the individual detectors. -Developing the combined local drift detectors, probably employing the clustering and selection approach [START_REF] Jackowski | Adass+ the hybrid training method of a classifier based on a feature space partitioning[END_REF][START_REF] Kuncheva | Clustering-and-selection model for classifier combination[END_REF], because many changes have the local nature and touch the selected area of the feature space or selected features only.

-Employing other interconnections of detectors (in this work the parallel architecture was considered only) including serial one.

Fig. 1 .

 1 Fig. 1. Exemplary deterioration of classifier accuracy for sudden drift (left) and incremental one (right).

Fig. 2 .

 2 Fig. 2. Idea of drift detection.

Fig. 3 .

 3 Fig. 3. Idea of combined drift detector.

-

  DDM with window includes 30 examples. -HDDM A -detector based on McDiarmid's inequality analysis with the following parameters: drift confidence 0,001, warning confidence 0,005, and one-side t-test. -HDDM W -detector based on Hoeffding's inequality analysis with the following parameters: drift confidence 0,001, warning confidence 0,005, and one-side t-test. -Cusum with window includes 30 examples, δ = 0, 005 and lambda = 50 -Page-Hinkley test with window includes 30 examples, δ = 0, 005, lambda = 50, and α = 1

Table 1 .

 1 Results of experiment for data stream with sudden drift

	detector	no. of real drifts	no. of corrected detected drifts	average detection delay	no. of false detections	time
	DDM	20	20	71,45	0	1,47
	HDDM A	20	19	19	1	1,79
	HDDM W	20	20	11,65	0	1,71
	PageHinkley	20	1	102	0	1,61
	CUSUM	20	20	141,95	0	1,59
	ALO	20	0	-	78	4,93
	ALHD	20	1	102	0	4,76
	AD	20	20	29,8	6	4,85

Table 2 .

 2 Results of experiment for data stream with gradual drift

	detector	no. of real drifts	no. of corrected detected drifts	average detection delay	no. of false detections	time
	DDM	1	1	235	2	1,44
	HDDM A	1	1	310	1	1,65
	HDDM W	1	1	242	1	1,62
	PageHinkley	1	1	340	1	1,59
	CUSUM	1	1	346	1	1,62
	ALO	1	1	235	10	4,89
	ALHD	1	1	346	1	4,86
	AD	1	1	299	2	4,95

Table 3 .

 3 Results of experiment for data stream without drift

	detector	no. of real drifts	no. of corrected detected drifts	average detection delay	no. of false detections	time
	DDM	0	0	-	0	1,4
	HDDM A	0	0	-	0	1,65
	HDDM W	0	0	-	0	1,59
	PageHinkley	0	0	-	0	1,53
	CUSUM	0	0	-	0	1,61
	ALO	0	0	-	0	7,79
	ALHD	0	0	-	0	4,84
	AD	0	0	-	0	4,92

We assume continuous attributes, but for discrete ones we have to take into consideration corresponding conditional probabilities p(x|j)

[START_REF] Duda | Pattern Classification[END_REF] We assume so-called 0-1 loss function. For different loss function the optimal algorithm minimizes so-called overall risk[START_REF] Duda | Pattern Classification[END_REF].

http://moa.cms.waikato.ac.nz/

The detailed results of the experiments could be found https://drive.google. com/drive/u/0/folders/0B8ja_TIQel7KbnJMblJJUzltNzQ

Acknowledgements

This work was supported by the statutory funds of the Department of Systems and Computer Networks, Faculty of Electronics, Wroclaw University of Science and Technology and by the Polish National Science Centre under the grant no. DEC-2013/09/B/ST6/02264. This work was also supported by the AGH Statutory Funds no. 11.11.230.017. All computer experiments were carried out using computer equipment sponsored by ENGINE project(http://engine.pwr.edu.pl/).


H Jaap Van Den Herik
email: jaapvandenherik@gmail.com

Innovation and Big Data

Keywords: big data, obstacles, sensitive data, safeguards, turn around management, narrative science

Innovation is an essential issue for companies and educational institutes. We have seen that well-known companies came into trouble since they did not innovate in time. They kept their well-established way of operating and adhered to their old-fashioned business models. The main topic of this contribution is to address the question: to what extent can the availability of Big Data support the innovation attempts of companies and educational institutes?

We start by mentioning five examples of innovation and relate them to data science and big data. We describe basic concepts and developments. We then formulate six possible classes of obstacles and take into account the use of sensitive data. Finally, we arrive at two conclusions and three recommendations.

Introduction

The current technological development is in a state of flux. New applications are followed by even newer ones. Many scientists see this concatenation of applications as a disruptive chain. For a proper understanding we mention five new developments (or applications of well-known concepts): (1) autonomous cars, (2) blockchains, (3) crowd sourced online dispute resolutions, (4) Airbnb, and (5) Uber Taxi. They can be seen as new paradigms that result from the combination of new and old technologies.

The question to what extent big data does support the innovation can be answered by investigating the string of activities that takes place in the study of data science. Data science is a new discipline in the academic world and in particular in the research world. It originates from computer science (informatics) and statistics. Big Data has mitigated the use of samples as is exploited by statisticians. This implies that for a proper handling of the available data no longer the well-known statistical sample techniques are sufficient, but that a new statistical approach has to be developed, i.e., reasoning in a Bayesian network.

In data science we nowadays distinguish seven phases of activities. They are: (1) collecting data, (2) cleaning data, (3) interpreting data, (4) analyzing data, (5) visualization of data, (6) narrative science, and (7) the emergence of new paradigms. The last phase has been instantiated by the five examples at the beginning of this section. Below we will discuss the following topics and their obstacles: Real big data (section 2); Definitions (section 3); Small data (section 4); Turn around management (section 5); Criminal behavior (section 6); Conclusions (section 7), and Safeguards and recommendations (section 8).

Real Big Data

There are only two research areas where we face real big data, viz. particle physics (e.g., at Cern) and astrophysics (e.g., at Lofar). Two other areas where the storage of data is extremely large are DNA-research and Geo-research (in general). For social sciences we see enormous amounts of data stored in Wikileaks, on Dating sites, and in the Panama papers. Here we meet our first class of obstacles. They consist of transport problems, complexity problems, and reputation damage:

Obstacles (

Definitions

Big Data is a kind of container concept. Almost all disciplines have their own definition of Big Data. In this contribution we provide two definitions: a technical one and a business one. The technical definition is by Tom [START_REF] White | Hadoop: The Definitive Guide, 3rd Edition. Storage and Analysis at Internet Scale[END_REF].

Technical Definition: "Big Data is the term for a collection of data sets so large and complex that it becomes difficult to process using on-hand databases management tools or traditional data processing applications."

The challenges capture The second class of obstacles is defined by the characteristics of the collection of Big Data at hand. They are called the five V's:

Obstacles (class 2)

The five V's are:

1. Volume 2. Velocity 3. Variety 4.

Veracity 5. Value

The business definition of Big Data has been formulated by James [START_REF] Phillips | Pass summit 2015 -Microsoft foundation session -Business Intelligence[END_REF]. Business Definition: "Big Data focuses on value creation, viz. to obtain operational benefits from data, and will then exploit the benefits for performance improvements." Two important capabilities are:

(1) Companies learn faster on their business trend, (2) Companies can rely faster on the new trends than their competitors. The third class of obstacles is defined by legal requirements and competitive behavior:

Obstacles (class 3)

• The intention to make infringements on the legal requirements with reference to the commercial competition.

Examples come from the auto industry, among them Volkswagen.

Small Data

Next to big data there is small data. They constitute techniques which enables effective use of Big Data. A telling example is cookies. Originally, cookies were meant to bring relevant input to places where they are in a better environment, i.e., to be of better use in their "ecosystem". Nowadays cookies are used for: personalization, profiling, advertisements, recording of behavior and for "selling purposes". The fourth class of obstacles is defined by privacy and security issues:

Obstacles (class 4)

The main obstacles for small data are • Privacy • Security Big data can be used for monitoring the life cycle of companies. We assume that the life cycle traverses through the following six stages: (1) Foundation of the company, (2) Establishing a healthy company, (3) Strategic crisis, (4) Earning crisis, (5) Liquidity crisis, and ( 6) Bankruptcy (cf. Adriaanse, 2015). We will see the following development A proper recording of data within the company may serve as monitoring system and even as alert system for unexpected developments. The availability of big data will make the prediction very accurate.

The fifth class of obstacles is defined by privacy and ethical considerations as well as by commercial competition and legal opportunities:

Obstacles (class 5)

The main obstacles for use of big data in Turn around management.

• Privacy • Ethical considerations • Commercial competition • Legal opportunities

Criminal behavior

An important case showing criminal behavior is the marathon bombing in Boston. We illustrate this marathon bombing by three pictures. In April 2014 an unexpected bomb exploded at the end of the Boston Marathon (see picture 1). There were sensor images and recorded pictures. The crowd was so big that no criminals involved in the attack could be identified. The police quarantined the city and attempted to find the criminals in their computer databases. They could not identify them. Finally, one brother was killed by police force (Dzjochar Tsjarnajev) in a gunfight and one day later Tamerlan Tsjarnajev was arrested albeit by a coincidence through a blood trace observed by an alert citizen.

If the bomb had been inspected accurately, it could have been established that its origin was Chechnya or a neighbor area, which would have refined the number of candidate criminals considerably. Once the criminals were caught, the recorded images afterwards produced evidence for what has happened and where the guilty persons stayed during the explosion To investigate such criminal behavior with modern technological means we see that a combination of Big Data, High Performance Computing, and Deep Learning is most effective. These three components form the basis of narrative science. It means that an intelligent program constructs the story and points to the criminals. This approach is also known under the name story telling. For lawyers it is called argumentation theory. The sixth class of obstacles is defined by privacy, public safety, technicalities of narrative science, and sensitive data:

Obstacles (class 6)

• Privacy • Public safety

Safeguards and Recommendations

To keep the delicate balance mentioned above, two safeguards are possible.

• To diminish attention and research efforts for Big Data and Deep Learning.

• To increase attention and research efforts for Big Data and Deep Learning. From these two safeguards our preference goes to the second safeguard, provided that we are allowed to introduce three specific safeguards.

These are our recommendations.

• Increase research on AI systems for Big Data and Deep Learning with emphasis on moral constraints. • Increase research on AI systems for Big Data and Deep Learning with emphasis on the prevention of AI systems to be hacked. • Establish (a) a committee of Data Authorities and (b) an ethical committee.

Conclusion 2 :

 2 For all who are working in the area of Technological Innovation and Social Innovation the Extrapolation as shown in below is relevant (cf. Van den Herik and Dimov, 2011).

Class 1) Big Data Obstacles

	CERN	1. Transport problems
	LOFAR	(accessibility)
	DNA	2. Complexity problems
	GEO	(unrelated data)
	Wikileaks	3. Reputation damage
	Dating sites	(side-effects / non anticipated)
	Panama papers

•

  Narrative science • Sensitive dataThe investigations of criminal behavior have an important obstacle class 6 to take into account, viz. sensitive data (cf. Van Eijk, 2015):

		Sensitive Data
		Obviously, some data are really personal, i.e., data revealing
		(1) racial or ethnic origin,
		(2) political opinions,
		(3) religious or philosophical beliefs,
		(4) trade-union membership, and
		(5) the processing of data concerning health or sex life
		The general rule for companies is that the processing of
		sensitive data is prohibited without explicit consent
		(Directive 95/46/EC, article 8).
	The "scientific" development of "disruptive" technology, the Road to Deep Lear-
	ning, is:
		The Road to Deep Learning
		Artificial Intelligence	1950-1990
		Machine Learning	1990-2000
		Adaptivity	2000-2005
		Dimension Reduction	2005-2010
		Deep Learning	2010-2015
		Big Data & HPC	2012-2017
		New Statistics	2014-2019
	7 Conclusions
	From the above line of reasoning on the obstacles that occur when Big Data research
	is involved we may conclude the following:
	Conclusion 1: For a legitimate commercial interest, a legal foundation is a
	necessary requirement. Such a requirement should constitute a careful balance
	between
	•	the legitimate commercial interest,
	•	the fundamental rights and liberties of the persons who possess the data (or
		to whom the data can be attributed). Keep here in mind the sensitive data.

Acknowledgements

This insight overview is the result of my cooperation with many colleagues. The following colleagues are singled out for their contribution to this article. I would like to thank Rob van Eijk, Daniel Dimov, Joost Kok, Aske Plaat, and Joke Hellemons. Moreover, I am grateful to Wladyslaw Homenda from Vilnius for the stimulating discussions we have had and for the invitation to communicate on Innovation.


Jiří Ševčík

Jiří Dvorský It4innovations

Techniques of Czech Language Lossless Text Compression

Keywords: lossless data compression, czech language, linguistic, morphology, graphs

For lossless data compression of the texts of natural language and for achieving better compression ratio we can use linguistic and grammatical properties extracted from the text analysis. This work deals with usage of word order, word categories and grammatical rules in sentences and sentence units in Czech language. Special grammatical properties of this language which are different from for example English language are used here. Further, there is an algorithm designed for searching similarities in analyzed sentence structures and its next processing to final compressed file. For analysis of the sentence units a special tool is used which allows parsing on more levels.

Introduction

Within the compression we can encounter several data types. These types can be graphic data, sound data or a text in natural language. All these types have different statistic properties and dependences following from them. In case of the text compression we can point out that the character of given language has an influence on the compression itself. From this finding we can deduce that knowledge of the language structures and rules can influence the final compression ratio if we use it properly. Our work focuses on these properties. It is not a general system which processes any kind of language, but Czech language. On account of the fact that Czech language belongs to different category than English language, there will be mentioned examples in both languages for better understanding.

Language categories

Czech belongs to Slavic languages. These languages, similarly to English, belong to Indo-European languages. We can divide Czech language into two categories: standard Czech language which is used for official communication and common Czech language which is used in daily communication between people. In Czech language we can find many dialects. Czech vocabulary is mainly Slavic, but it can adopt words from other languages, for example from German or Polish.

The number of language properties which are different for described categories is higher, but it is sufficient for basic understanding. Thanks to this understanding we can point out the fact that in case of inflected languages is the word arrangement looser than in the analytic languages. The word order is mainly influenced by semantic point of view of the whole sentence or by its grammatical arrangement. Knowledge of this property is one of the crucial features of our work and the whole principle of the data preprocessing for compression is built on this property. There are many branches that deal with grammatical arrangement and with natural language analysis on different levels and its importance and contribution to this work will be mentioned in following parts.

Previous work

We can find a large number of researches or works that deal with the compression which specializes on a particular language. The largest amount of them deals with English text or with Indo-European languages [START_REF] Yuret | Discovery of Linguistic Relations using Lexical Attraction[END_REF][START_REF] Bach | Lexical Attraction for Text Compression[END_REF]. We can find also special compressing methods for different language categories such as Arabic [START_REF] Awajan | Multilayer model for Arabic text compression[END_REF] or Chinese [START_REF] Chang | A Data Compression System for Chinese Fonts and Binary Images Using Classification Techniques[END_REF] language. Since we are dealing with a compression of text only lossless principles will be mentioned. There exist also methods for loss compression with the informational content maintained but based on the aim of this work we will not deal with them.

In a number of these works we can encounter also preprocessing. It divides the compression into two sequential parts -preprocessing algorithm and compression algorithm. First algorithm transforms the input data for the compression based on its own compression scheme and these modified data he will deliver to the second algorithm which will, based on some standard or special methods, compress it. Decompression works just the opposite way. In the case of preprocessing algorithm we can encounter various general methods. The closest one to the topic of this work is the one on the level of words [START_REF] Moffat | Word-Based Text Compression, Software, Practice and Experience[END_REF], symbols or sentential units. Another interesting method is the compression based on syllables [START_REF] Lanský | Compression of Small Text Files Using Syllables[END_REF][START_REF] Akman | Lossless Text Compression Technique Using Syllable Based Morphology[END_REF].

Linguistics

The problem of compressing a natural language is therefore large and we can approach it with different perspectives. The aim of this work is to use some of these specific attributes and characteristics of Czech language and with the use of that attain a better compression ratio. Therefore we have to use possibilities of a science related to the language -linguistics. It represents a large group of sub-fields of study which deal with a large spectrum of language attributes from grammatical and syntactic parts to for example special usage related to the fields as sociology or psychology. We can divide it into general linguistics, applied linguistics or language linguistics. Further we can divide it based on its aims -in our case we will specialize in descriptive linguistics and theoretical linguistics. It, based on Czech linguistic tradition [START_REF] Hajicova | Úvod do teoretické a počítačové lingvistiky, I. svazek -Teoretická lingvistika[END_REF], incorporates many subsystems because we can understand the language as a system. On theoretical level we can divide these subsystems into three categories: phonetics, grammar and syntax. Related to the aim of this work we will specialize on the second category which is divided into morphology and syntax.

Morphology we can describe as a discipline which deals with the study of the creation of words their declension and deriving of new words. Further we analyze the structure of particular words or whole word form. For the analysis of words we use morphematics. Basic morphological unit is an component which has a particular meaning -morpheme. If standing alone it may not be even a word. In the basic division morpheme may be lexical (word base) root of the word which represents action or characteristic or morpheme gramattical (afix ) which defines grammatical categories (sematics) [START_REF] Hajicova | Úvod do teoretické a počítačové lingvistiky, I. svazek -Teoretická lingvistika[END_REF].

Another characteristic which morphology deals with is the study of grammatical categories which determine the meaning of particular morphemes. The most general category is a word class which is in the Czech language divided into ten types. Those can be divided based on the mentioned possibility if the flex (inflected words) may be used or not (inflexible words). To inflected words belong nouns, adjectives, pronouns, numerals and verbs and to Inflexible words are adverbs, prepositions, conjunctions, particles and interjection.

Morphological analysis lies on analyzing of a particular word form without taking the context into consideration. The output of this analysis are two components. One of them is the mentioned lemma and the second one is the morphological tag which comprises of 15 symbols (in special cases even 16). Each of these 15 positions are related to a particular morphological category and to every value of this category a particular symbol corresponds to [START_REF] Hana | Manual for Morphological Annotation, Revision for the Prague Dependency Treebank 2[END_REF]. In most of the cases it is a capital letter of alphabet or another alternative is a lower case letter. The last possible characteristic is "-" when used it means that for that particular word the morphological category is not applicable which is related to the rules of Czech language and grammar. A typical example is the case in verbs. The most important categories are (the number symbolizes the position in the tag) pos, gender, number, case, person, tense and grade.

The opposite procedure of analysis is the morphological synthesis. Here, in order to acquire a particular word we need to know its basic lemma form and morphological tag. There are various morphological taggers for the Czech language and each processes the text in a different way. Among the most well-known belong Free morphology tagger of Jan Hajič [START_REF] Hajič | Disambiguation of Rich Inflection (Computational Morphology of Czech)[END_REF] and Ajka system [START_REF] Sedlacek | Morfologicky analyzator cestiny[END_REF]. Another category is the syntactic discipline. Its primary use in linguistics is to study the relationships between the words in a single clause or the relationships of individual clauses or sentences. It can be said that it is a study of the general sentential structure and its parts.

In European linguistics the dependency description is used to describe the structure of the sentence. Here, the verb is considered to be the central part of the clause or the sentence. The whole structure of the sentence is described in the form of tree where each node represents an individual constituent. The borders between the nodes represent dependency relations and each node has only a single superordinate parent node. Here the verb is the root node. The nodes in the tree are arranged structurally according to their dependency relations and also linearly according to their sequence in the sentential word order.

Computer linguistics

The described linguistic disciplines are difficult and complex field and a "handmade" analysis of the grammatical constituents or units is very demanding not only with the respect to time. Here the use of computers comes in the picture. Such processing is called Natural language processing. It is a field that links not only linguistics and informatics but also other fields such as acoustics in case of spoken word synthesis.

The corpus is the important term here. It is a structured set of texts/literature or even transcriptions of a spoken language. This set includes other information about the linguistic informations of the given text. Such information is crucial for us because they are syntactic and morphological. Various languages, including the Czech language, have many corpuses. For our task the Prague Dependency Treebank [START_REF] Honetschläger | The Prague Dependency Treebank 3[END_REF] is the most interesting. It has been developed since the middle of the 1990s in Institute of Formal and Applied Linguistics, Charles University in Prague and its actual version 3.0. comprises of several millions of entries. This corpus, besides other functions, includes two aforementioned levels, that is the morphological layer (m-level) and analytical/syntactic layer (a-level). A tectogrammatical layer is also included, however it is not crucial for our task. The actual data is stored in the structured format PML (Prague Markup language) which is based on the well-known marking XML and thus the computer data processing is made easier.

The resulting dependency tree includes the description of dependencies in the line descendant -parent between the individual constituents of the sentential whole. Such analytical tag is called afun and there are twenty-eight types of them. The second most important information included is the morphological part which records the lemma form to each grammatical constituent and a complete morphological tag. The last presented tool is Treex [START_REF]Treex Highly Modular NLP Framework[END_REF] which is capable of processing the text, creating its morphological and syntactic analysis and generate the resulting PML set. The tool can be configured, schemes and required resulting layers for the output adjusted and it also allows a reverse morphological synthesis. In total, twenty-three attributes are available, the majority of which is not important for our task (for example specialized linguistic categories of particular words) but we shall deal with them in the subsequent phases of development. One of them is for example is spaces after attribute which allows a detection of whitespace after given word and use of this information in the set of resulting trees.

The previous text proves that processing and analysis of the text can be done on the lowest levels even in the complex language such as Czech. It can be also said that despite the free word-order the clause or the grammatical constituent need to have a certain structure resulting from the given grammatical rules. The idea of our task, that deals with the use of the described analytical tool Treex as a part of the preprocessing in a compressive algorithm, is based on these premises. The progress of the preprocessing can summed up into several parts. The processing of the input text by analyser, finding similarities in tree structures while using the knowledge of grammatical rules and subsequent compression of the individual parts by compressive algorithms.

Processing of the text

Treex analyser is to be used for the analysis of the compressed text. The program can be used in a graphic mode via web program as well as a console application. After morphological and syntactic analysis is done, the output is transferred to the next part of the algorithm. Thus the analyser runs as the individual process and later a greater integration and interconnection with the preprocessing algorithm could be one of the subsequent parts of the development. But in the current phase the manner how the analysis runs is sufficient.

Similarities in tree structures

In informatics and in other fields of course, the graph theory offers countless of possibilities and thus there is no need, considering the length and the character of this paper, to deal with it in-depth. For our case, the searching for similarities in graphs is the most important. The search is to be done in two, mutually collaborating levels. The algorithm works in several phases:

1. The initial phase takes place during the actual processing of the input text in Treex analyser. Here we observe whether the afun Coord appears in the morphological analyses because here it serves as the coordinate function for grammatical constituents; Namely the symbols "," and "a". In such case the whole tree is divisible into grammatical constituents. After the conclusion of this initializing phase the trees are divided in two sets (hereinafter referred to as A and B ). 2. The first similarity phase: Here, and also in the following phase, the work is done by the general algorithm for similarity search in the graph. The manner and evaluation of similarities is to be discussed later. The algorithm first processes the set tagged as divisible i.e. A. In case there are more trees with necessary similarity, they are moved into resultant set C. 3. The phase of division -A division into sentential units is to be done for all the remaining trees from the set A. The division is made on the spot of the occurrence of the Coord afun. Thus two subtrees are created, to which we assign the information about the linking coordinating function and which tree is their parent. The division into subtrees is done recursively because of the possibility of several Coords appearing in the single tree. After all subtrees are determined for the individual tree, they are moved into set B where all trees gained from the first phase can be found. 4. The second similarity phase. The same procedure as in the set A is used for the set B with the exception that all trees are to be moved into the resultant set.

As another possibility we have synthesis and modification of these phases in two which shall look as follows:

1. The first phase -after processing the text in Treex, the sentences where Coord afun occurs, will be divided into subtrees that will be saved into set together with all other trees that could not be divided. 2. The second phase -The similarity algorithm is applied on the whole set.

In the current phase of this work we cannot decidedly tell which procedure shall bear better results. It can be assumed that the processing of divided sentential units [START_REF] Kazik | Lingvistická komprese textu[END_REF] will enhance the overall compression ratio but considering the small modification of preprocessing algorithm both alternatives shall be tested.

Comparing the similarity in graphs

The issue of comparing and defining the similarity of graphs is not unusual and there are many theoretical and practical works that deal with the topic. Thus there is plenty of research material and completed theoretical solutions. We are especially interested in the research group created under Czech Technical University in Prague. This group which consists of the members of well-known The Prague Stringology Club created a research group Arbology in 2008. Their work deals with the use of known algorithms from stringology for work with trees and tree-like structures [START_REF] Melichar | Introduction to Arbology[END_REF]. The scope of their work is thus very large. In our work we can use the tree similarity on several levels which again reflect the variability of the Czech language and grammar.

Structural similarity A clause or a grammatical constituent can be regarded as a tree without further research of its attributes and dependency functions between the individual nodes.

Word-order similarity This similarity has already been mentioned -there are certain similarities to be found even in the free word-order. Example: "Voda je studená." (Water is cold.), "Básničky se nám líbily." ("We liked a poems.") -subject "Voda" and "Básničky" and predicates "je studená" and "se nám líbily".

Morphological similarity The most frequent similarity can be found in the same grammatical case of the words. Example: "Honzík a Anička se domluvili, že se odpoledne sejdou na hřišti."

("Honzik and Anicka agreed that they will meet on the playground on the afternoon."). Subject "Honzík" and subject "Anička" are grammatically connected and both are in nominative case. Preposition "se" and adverb "hřišti" are grammatically connected and both are in accusative case.

It can be seen that the similarity of the grammatical constituents can be found on several levels. Our goal is to create such an algorithm that will be capable of processing all input trees and create the smallest possible output set of trees for them on all similarity levels. The algorithm will be capable to determine whether it is suitable for particular clause to create a new tree if there is a similarity with the already existing output tree. Or whether an existing should be used considering that the original tree is modified and the modification is saved as the additional information. The modification will be most commonly used in addition or removal of the node in the tree or change of some morphological tags.

Tag compression

This idea of processing and subsequent compression seemed, after initial testing and several tests, very promising. However, we started encountering one significant problem with the speed of the text analysis using Treex. At first this did not seem as an obstacle but in case of several megabytes of input text the speed of analysis took tens of minutes. This duration was of course also caused by a nonoptimized usage of the individual tool. After evaluating options and factoring that our development is at the beginning, it was decided that in the first phase of the development the morphological analysis shall be handled by a different tool called MorphoDiTa [START_REF] Strakova | Open-Source Tools for Morphology, Lemmatization, POS Tagging and Named Entity Recognition[END_REF]. Another supportive argument for this choice was the fact that we needed to achieve some initial results that would allows as to verify that our input assumptions for compression based on the utilisation of knowledge of grammatical structure and rules of the Czech language are correct. This would confirm the assumption that the devised algorithm will be effectual. Therefore we decided, for the time being, to use a different tool.

Unlike Treex, the MorphoDiTa executes the text analysis only on the morphological level, ignoring the syntactic or tectogrammatical layer. Due to this focus, the tool is much faster and it can be also used for the reverse generating of the original word, if the lemma and morphological tag are known. There are more tools suitable for the operation, however MorphoDiTa was chosen for its simple integration into our current task. There is also a possibility to work the tool into our algorithm because it can be used as a standalone tool or a library, which was another reason for the use. Thanks to the output information that had been provided by MorphoDiTa, our subsequent research focused on the possible compression forms of the morphological tag (see the previous chapters). This seems sufficient because these tags are utilised very often in the complex algorithm which we already devised, and their analysis will make the following work easier.

As already described, the tag itself consists of 15 marks. Because the marks (to make things easier we shall use only this designation as the detailed description can be found here [START_REF] Hajič | Disambiguation of Rich Inflection (Computational Morphology of Czech)[END_REF][START_REF] Hana | Manual for Morphological Annotation, Revision for the Prague Dependency Treebank 2[END_REF]) correspond to grammatical categories and advanced rules of the Czech language. From this knowledge we can extrapolate the fact that some marks can be used only if other signs occur or in case when we cannot use any mark in combination with the group of other -symbol "-".

The most important mark in the tag are the first (POS ) and the second (SUBPOS ) marks according to which it can be clearly said what combinations of marks will appear in the subsequent positions and which positions will remain empty. After applying this knowledge, it is possible to employ compression into the following form. All this on condition that in case of decompression we will be able to assemble the original tag.

Example -original tag : N N I P 1 -----A -----Example -no gaps: N N I P 1 A Another possibility is the elimination of the first mark -POS based on the condition of its reverse deducibility from the sign SUBPOS.

Example -POS elimination: N I P 1 A These pieces of information allow us to effectively compress the whole mark. Another problem we have dealt with is the manner of how the tag is saved which went through two phases. During the course of the research we arrived to several possibilities. As the first we could name these: -Saving the whole sign as the text without compression. -Saving the mark as the text after the previous two-stage compression. This possibility seems as a very ineffective one. Given the assumption that in the each position only a limited and finite number of symbol can appear, the further research was lead in this direction. The first possibility lies in the assignment of the numerical indication of the individual signs within its category only.

Example -numeric: 34 3 2 1 1

As evident, a greater efficiency can be achieved. However this state was not final and thanks to the extracted knowledge of the structure of the sign, it is possible to make the numerical indication even more efficient by very simple means. We know that the certain category of the signs can be used only in the case of use of the certain POS /SUBPOS, therefore we can divide the signs into other categories and use the numbering only within a frame of these smaller categories. This way we reduce the highest used numbers.

Example -numeric, reduced: 34 2 1 1 1

In the following part of the research, our concern proceeded towards the possibilities of saving the sequences of numbers that represent tags. In the current phase of the development we work with several possible variants:

saving the number as float/int, encryption of the number using the existing coding algorithms, binary representation of the number, combination of several possibilities.

The first possibility was quickly dismissed for the inefficiency which mainly lied in the compression of small numbers. There the second option as utilized why using elias-gamma coding [START_REF] Elias | Universal codeword sets and representations of the integers, Information Theory[END_REF]. This manner of encoding is further used in other parts of this task and the final values are recorded using this method. Another possibility -the binary representation of the number -is currently in the phase of development but it is possible to say that this method seems applicable. The principle lies in finding of the highest possible number which needs to be encoded, then in the determination of the number of bites that represent it, thus also determining the number of bites upon which all other numbers will be represented. The last possibility related to the combination of various techniques offers a huge space for experimenting. It is for example expected that the algorithm alone will determine the most suitable methods (or the their combinations) of encoding for the given initial text.

Coding of lemmas

The current version of the algorithm uses LZ algorithms [START_REF] Ziv | A universal algorithm for sequential data compression[END_REF] for the compression of lemmas as it currently seems as sufficient enough. However further ahead we expect to use other tests for different compression algorithms which are primarily intended for the compression of text.

Organisation of saving

After analysis and text processing, all unique lemmas and tags are arranged according to their frequency. They are kept in the list for the final processing. Therefore it is important for us to use the optimal encoding of sequences of numbers also due to saving of position and indexes. The resulting compressed file is sorted into three parts:

1. The list of all lemmas found in the text 2. The list of all signs found in the text 3. For the every word the original text here is represented by a pair of indexes that are referring to the previous two lists.

Here, the usage of various methods of encoding will be advantageous according to the total size of lists of lemmas/tags. As already stated, in the current phase we use only one method of the numerical coding.

The use of external corpuses

One of the possible extensions for achieving of the best possible compression is the use of external dictionaries, both for lemmas and tags. In case of tags the use is simpler because the number of possible combinations can be unambiguously determined. According to it, all possible variations are generated. This method is rather more difficult with lemma dictionaries. As the language that is still being used, the Czech constantly develops and thus the new words and lemmas are being created. On the other hand, some words become archaic and less used. In this case, the generating of all lemmas is inefficient and insufficient. There is another factor to consider; that in various types of texts (fiction, spoken word, scientific texts) the frequency of words is vastly different. Another drawback is the non-existence of the word/lemma of the original text in the given corpus. A typical example are for example the additional postfixes of lemmas which are added by analyser for better accuracy.

The corpora are available in several categories at UCNKP [19]. Organised corpora of words and their lemmas for different categories of text and period of time can be acquired from there. On closer examination one can see that for different types of text the frequencies do differ and thus there is no universal list that could be considered as the best for all types. The initial thought of using the corpus lied in the method that the compressed file will not include the first two lists with lemmas and tags and that the pair of indexes, representing the initial text, will refer to positions in external corpora. This method should ensure the smaller size of the resulting file, however for the reverse decompression it will be necessary to use the external file with corpus which might not be really optimal.

In the initial experiment of our work, the general corpus SYN2010 was used. The corpus includes more than 30,000 lemmas. During the tests, we compared the intersection of lemmas included in this corpus with lemmas appearing from the set of literature of fiction (which is used in our other tests). After evaluation, the corpus was found insufficient for our testing set because of the great number of missing lemmas. However, despite these initial findings we plan to use these corpora at least for the specific types of initial tests. Recently, the corpus SYN2015 has been available which, besides morphological analysis, also includes the syntactic analysis. For the next parts of our work we shall use this corpus as it cancels the necessity to use the external tools MorphoDiTa or Treex for the creation of input text analysis during the testing.

Results

Brief characteristic of files used in the test is given in Table 1. Due to the aforementioned reasons, our tests dealt with a single method of compression which is:

the compression of the lemma forms using LZ, encoding of tags using the numerical encoding, representation of indexes of the initial text using elias-gamma code.

After the evaluation of the results, see Table 2, we arrived at several conclusions which will assist us in our further work. The most substantial part, which influences the final size of file the most, is the encoding of indexes. The method of encoding we chose does not seem as the most suitable in case of truly huge numbers which obviously results from this type of elias-code. Another crucial factor is the size of occurrence of the original tags in the text. It can be seen that if the initial set of words increases hundredfold then the number of the original tags increases only twice as much. This fact underlines the attributes of the Czech language and supports our assumptions that despite the complexity of the rules of language, the regularities in structural composition can be found.

The similar ratio can be seen even in the number of the original lemmas but here the size ratio is not so prominent. But this is the result (besides other things) of the selection of the input text that was analysed and compressed.

Conclusion and future works

It can be said that the first phase of our tests met its purpose and confirmed our initial assumptions while setting the direction of further research. The results alone are not the best possible (due to the chosen methods of encoding), however the improvement of the methods and their optimization will make the main content of our work. After we finish this phase, we shall focus on the possibility of at least partial integration of external dictionaries and then on the search of similarities at several levels.

Table 1 .

 1 File characteristics

	File	File size	Number	Number of	Number of
		(megabytes)	of words	unique lemmas	unique tags
	A	1	359,614	14,854	574
	B	5	1,764,258	34,286	718
	C	10	3,578,666	41,466	733
	D	50	17,874,992	110,254	911
	E	100	35,635,693	162,935	981

Table 2 .

 2 Compression results

	File	Lemma Lemma index	Tags	Tag index Compression ratio
		(bits)	(bits) (bits)	(bits)	(≈%)
	A	452,896	3,867,038	7,155	1,896,490	74
	B	1,015,200	19,518,472	9,148	9,394,852	71.2
	C	1,237,792	39,005,856	9,304	18,913,870	70.5
	D 3,301,856	197,755,574 12,132	94,951,596	70.6
	E	4,945,152	395,358,961 13,123 189,143,515	70.3

Acknowledgment

This work was supported by The Ministry of Education, Youth and Sports from the National Programme of Sustainability (NPU II) project "IT4Innovations excellence in science -LQ1602" and from the Large Infrastructures for Research, Experimental Development and Innovations project "IT4Innovations National Supercomputing Center -LM2015070".


Krzysztof Misztal
email: krzysztof.misztal@uj.edu.pl

Jacek Tabor
email: tabor@ii.uj.edu.pl

Jakub Hy

Optimal ellipse based algorithm as an approximate and robust solution of minimum volume covering ellipse problem

Keywords: smallest ellipse problem, computational geometry, optimal ellipse, online algorithm

We propose a algorithm to give a approximate solution of a minimal covering circle or ellipse of a set of points. The iterative algorithm is based on the optimal ellipse which best describe a given set of points.

Introduction

In order to more realistically simulate the behavior of solid in games, we have to check especially if they collide with each other every time they move, and if they do, we have to do something about it. This lead us to game physics engine that gives the game's world life. Understanding collision physics in 2D and 3D games [START_REF] Lin | Collision detection between geometric models: A survey[END_REF][START_REF] Jiménez | 3d collision detection: a survey[END_REF][START_REF] Ericson | Real-time collision detection[END_REF] is particularly important for game developers. The collision detection algorithms depends on the type of shapes that can collide. We can consider e.g. rectangle to rectangle or circle to circle collisions. In general case we will have a simple generic shape that covers the entity known as a "hitbox" so even though collision may not be pixel perfect, it will look good enough and be performance across multiple entities.

This problem can be also reformulated as finding the unique minimum volume covering ellipse (MVCE) problem of finite set of points in N -dimensional real space (namely in IR N ) if we consider just elliptical generic shapes. Such an ellipse has appealing mathematical properties which makes it theoretically interesting and practically useful. This convex constrained problem arises in a variety of applied computational settings, particularly in data mining and robust statistics. For example in computational statistics, the minimum-volume ellipsoid covering k of m (0 ≤ k ≤ m, k, m ∈ IN) given points in IR N is well-known for its affine equivariance and positive breakdown properties as a multivariate location and scattering estimator [START_REF] Croux | Location adjustment for the minimum volume ellipsoid estimator[END_REF]. In the area of robust statistics and data mining, efficiently finding outliers is a challenge that has attracted much research interest [START_REF] Knorr | Robust space transformations for distancebased operations[END_REF]. Indeed, one can identify data outliers quickly if one can compute the minimum-volume ellipsoid quickly, because outliers are essentially points on the boundary of the minimum-volume covering ellipsoid.

In this paper we focus on the image data, namely the points from IR N . The extended version for arbitrary dimension with streaming approach is prepared as a full paper and will be published in the future.

A new algorithm for finding the MVCE is based on the Mahalanobis distance [START_REF] Mahalanobis | On the generalized distance in statistics[END_REF] and uses the statistical and analytical properties of circular and elliptical objects, is proposed herein. The main advantage of the proposed method is that no complicated mathematical computation is involved in the implementation. Thus its evaluation is very fast. However the outcome ellipse is not optimal one -this will be disused in further part of this article.

We compare our algorithm with the incremental algorithm of Welzl, with move-to-front heuristic [START_REF] Welzl | Smallest enclosing disks (balls and ellipsoids)[END_REF] -the whole implementation is described in [START_REF] Gärtner | Smallest enclosing circles-an exact and generic implementation in c++[END_REF].

The remainder of the paper is organized as follows: in the next section we present basics of the covariance matrix and Mahalanobis distance. In the third section we provide the algorithm for finding approximate minimal covering ellipse. The next section gives same experiments o illustrate the performance of our method. Finally, the last section contains some concluding remarks and possible directions of future work.

Mathematical basis

Covariance matrix and optimal ellipse

Multivariate and multidimensional analysis has been one of the most important areas in the modern statistics. Thus, the researchers have developed many useful techniques to efficiently describe the behavior of complicated data.

The definition of the covariance matrix states as follows, if set C is discrete, namely C = {x i } N i=1 ⊂ IR N , then the covariance matrix equals

Σ C = 1 N N i=1 (x i -m C )(x i -m C ) T , where m C = 1 N N i=1
x i is a mean of set C. In the general case by the covariance matrix of a set we understand the covariance of the uniform normalized density on S.

Theoretically, covariance is the object which represents the true statistical independent structure of the underlying population units. On the other hand, if based solely on empirical data, only a small piece of the independent structure is obtained. It is therefore important to select the efficient representations of the data for sampling the covariance matrix.

Remark 1. In practice the mean and the covariance matrix for a given set C ⊂ IR N is unknown. Thus they must be estimated from random variables (observed samples) by well-known estimators

mC = n i=1 w i x i , ΣC = n i=1 w i ( n i=1 w i ) 2 - n i=1 w 2 i n i=1 (x i -mC )(x i -mC ) T ,
where x i ∈ C for i = 1, . . . , n and w i -the weight of the point x i . If all weights are the same, the weighted mean and covariance reduce to the sample mean and covariance. The weight assigned with the point of space will be used to store (and use) the information about color while the work is done with grayscale images. For a binary image a natural simplification is employed: 1 for the foreground color (usually black) and 0 for the background color (usually white).

Remark 2. The above consideration discuses discrete sets. In general case the basic definition of covariance matrix can be stated as follows. For a random variable with a probability density function f : IR N → IR the covariance matrix of set S ⊂ IR N can be computed 3 as

Σ S = S (x -µ)(x -µ) T f (x)dx,
where µ is an expected value (mean) of set S.

Pixels on image as a atomic piece of information in covariance matrix

When we apply the above investigations to image data, we shall threat a single pixel (point with coordinates (x, y)

∈ ([1, w] ∩ Z Z) × ([1, h] ∩ Z Z),
where w × h is the size of the image) like a square. It allows to convert the discrete data of an image to continuous, which is more natural and consistent with the human perception of images. To calculate the measure of such transformation we use the following remark.

Remark 3. Consider a set P ⊂ δ •Z Z N which represents the set S = P +[-δ 2 , δ 2 ] N for δ > 0.
Then, obviously, covariance matrix is

Σ S = Σ P + Σ [-δ 2 , δ 2 ] N = Σ P + 1 12 δ N +2 I,
where I denotes the identity matrix. This can be used to compute the measure and covariance of S efficiently.

In the case of the image data we set δ = 1, which is because the coordinates of each pixel are integers.

In general case we have to determine the appropriate value of δ, for which investigated dataset can be threated as a subset of δ • Z Z N . This section is concluded with a simple, but important observation for singletons in image data, namely for X = {x 0 } we get

m X = x 0 , Σ X = 1 12 I, card(X) = 1,
where I denotes identity matrix and x 0 ∈ Z Z 2 .

An in-place covariance modification

Following theorem highlights how mean and covariance matrix will change if we add same points to the set, which will be used for the algorithm in the further part of this work. While new algorithm in each step modify mean and covariance matrix respectively to added point, this theorem allows as not to recalculate the whole covariance matrix each time -we just calculate the change of covariance matrix.

Theorem 1 ([9]

). Let U , V be given finite subsets of IR N . Assume additionally that U ∩ V = ∅. Then

m U ∪V = p U m U + p V m V (1) Σ U ∪V = p U Σ U + p V Σ V u + p U p V (m U -m V )(m U -m V ) T (2)
where

p U := card(U ) card(U ) + card(V ) , p V := card(V ) card(U ) + card(V )
.

Mahalanobis distance

It is well-known that the Euclidean distance between two points x and y in real space is given by

x -y = (x -y) T (x -y) = (x -y) T I(x -y), for x, y ∈ IR N ,
where T denotes the transpose operation and I is the identity matrix. It follows immediately that all points with the same distance from the origin x -0 = c satisfy x 2 1 + . . . + x 2 n = c 2 , which means that all components of the observation x contribute equally to the Euclidean distance of x from the center.

However, in statistics variability (how the set is spread out or closely clustered) is also considered. If the correlation between variables is to be taken into account when computing statistical distance, then we use Mahalanobis distance, which can be defined as follows.

Definition 1 (Mahalanobis distance). Let C denote the given subset of IR N . By m C the mean value of C is denoted, and the covariance matrix of C is denoted by Σ C . The statistical distance or Mahalanobis distance between two points x, y ∈ IR N is defined as

x -y Σ C = (x -y) T Σ -1 C (x -y). (3)
If y = 0 then the equation ( 3) is the general equation of an ellipsoid centered at the origin. In practice the center of the observations will differ from the origin, thus the distance from the mass center of observed samples chosen y = m C will be of interest.

Ellipse in Mahalanobis transformed space

A brief summary of the Mahalanobis distance and transform properties was given in previous section. Some important observations crucial in the construction of the following algorithm with the use of Mahalanobis distance will be hereby presented.

Recall the value of the Mahalanobis distance of the unit N -dimension ball receptively to covariance matrix Σ can be calculated, namely

B Σ (x 0 , R) := {x ∈ IR N : x -x 0 Σ ≤ R}.
The following knowledge is crucial for the algorithm construction.

Theorem 2 ([10]

). Consider uniform probability density on the ellipse E ⊂ IR N with mean m E and covariance Σ E . Then

E = B Σ E m E , √ N + 2 . ( 4
)
Theorem 2 gives the equation for optimal ellipse for given set and has the following consequences in understanding of the elliptical pattern recognition. Moreover, it describe how to reconstruct the set if we just have mean and covariance matrix. Remark 4. Theorem 2 gives the necessary and sufficient condition for a given shape to be elliptical (generalization of plane ellipse) -general ellipse in arbitrary dimension. Namely, it can be stated that an object E ⊂ IR N is an ellipse if and

only if it can be approximated by B Σ E m E , √ N + 2 or, that is, E ≈ B Σ E m E , √ N + 2 .
The above considerations gives us the specified condition to decide whether or not the current point x from the cluster C ⊂ IR N belong to the "elliptical" part of the cluster. Namely, the condition for point x is given by

(x -m C ) T Σ -1 C (x -m C ) ≤ √ N + 2,
where m C and Σ C denote the mean and covariance of C respectively. This gives as full necessarily information for construction the proper algorithm for finding approximate minimum volume covering ellipse.

The algorithm

In this section we introduce the algorithm for finding approximate minimum volume covering ellipse. We will describe this algorithm using Figure 1 At the beginning of the algorithm we calculate the optimal ellipse for C, by calculating the mean and covariance matrix denoted m 0 and Σ 0 respectively. The optimal ellipse is current approximation of minimal covering ellipse.

Then in each i-step we proceed as follows:

we check which of points in C are not covered by current approximation of minimal covering ellipse -we denote the set consist of such points by l i . If the set l i is empty we end the algorithm; we calculate the mean and covariance matrix for set l i and denoted them m i and Σ i respectively; we update the current approximation of minimal covering ellipse according Theorem 1; then we proceed to next step.

The pseudo-code of the algorithm can be stated as follows:

Algorithm 1 Finding approximate minimum volume covering ellipse

initial conditions C = {xi}i=1,...,M ⊂ IR N put l0 ← {x1, . . . , xM } put m0 ← m l 0 put Σ0 ← Σ l 0 put n0 ← card(l0) put i ← 0 repeat li+1 ← ∅ for each x in li do if x ∈ BΣ i (mi, √ N + 2) then li+1 ← li+1 ∪ {x} end if end for mi+1 ← n i n i +n i+1 mi + n i+1 n i +n i+1 m l i+1 Σi+1 ← n i n i +card(l i+1 ) Σi + n i+1 n i +card(l i+1 ) Σ l i+1 + + n i n i +card(l i+1 ) n i+1 n i +card(l i+1 ) (mi -m l i+1 )(mi -m l i+1 ) T ni+1 ← ni + card(li+1) i ← i + 1 until li = ∅
The outcome of this algorithm are the mean and covariance matrix of approximate covering ellipse.

The following comment are needed to clarify the algorithm statements and used notations:

the m i and m li denotes the mean of current approximation of convex hull and the mean value of set l i respectively; the Σ i and Σ li denotes the covariance matrix of current approximation of convex hull and the covariance matrix value of set l i respectively; the condition x ∈ B Σi (m i , √ N + 2) means that for tested x we get

(x -m i ) T Σ -1 i (x -m i ) > √ N + 2;
calculation of m i+1 and Σ i+1 in each step are done according to equations ( 1) and ( 2) from Theorem 1.

The new algorithm in simple illustrations

Emo Welzl [START_REF] Welzl | Smallest enclosing disks (balls and ellipsoids)[END_REF] proposed a simple randomized algorithm for the minimum covering circle problem that runs in expected O(N ) time, based on a linear programming algorithm of Raimund Seidel [START_REF] Seidel | Small-dimensional linear programming and convex hulls made easy[END_REF]. The algorithm is recursive, and takes as arguments two sets of points S and Q. The algorithm computes the smallest enclosing circle of the union of S and Q, as long as every point of Q is one of the boundary points of the eventual smallest enclosing circle. Thus, the original smallest enclosing circle problem can be solved by calling the algorithm with S equal to the set of points to be enclosed and Q equal to the empty set; as the algorithm calls itself recursively, it will enlarge the set Q passed into the recursive calls until it includes all the boundary points of the circle.

In this work we compare result of our new algorithm with the incremental algorithm of Welzl implemented in CGAL library [START_REF]The CGAL Project: Cgal, Computational Geometry Algorithms Library[END_REF]. The Figure 2 compares the results of finding smallest enclosing ellipse for same set of image data. As we can observe the results sames to be identical. However, the time needed to calculate those results differ for both algorithm -compare with Table 1. Thus our algorithm seem to be better in time consuming tests.

To confirm this we choose the benchmark image -Figure 3 -which has originally size 300 x 300 pixels and contains 8000 black pixels (points of interest). Then we resize the original image according to sizes given in Table 2. For each sizes we calculate the execution time of both algorithms.

This experiments shows that indeed the authors' algorithm is faster. However it seam that the complexity of new algorithm is also O(N ), but this complexity in this case is realized with smaller constance then in case of Welzl algorithm.

Conclusions

Int this paper the new approach for finding minimal covering ellipse was presented. This new method based on calculating the covariance matrix and interpret this according to behavior of Mahalanobis distance. The main advantage of this approach is that the results can be obtained very quickly. We are planning to test this approach for streaming data, to detect the changes in stream data trends.

Acknowledgement

The research of Krzysztof Misztal is supported by the National Science Centre (Poland) [grant no. 2012/07/N/ST6/02192].

Fig. 1 :

 1 Fig. 1: New algorithm for finding minimal covering ellipse: (a) original image and (b)-(f) steps of the algorithm.

Fig. 2 :

 2 Fig. 2: Comparison of results of two algorithm: CGAL implementation of the incremental algorithm of Welzl (second column) and authors' algorithm applied for certain shapes (first column).

Fig. 3 :

 3 Fig. 3: Input, output from CGAL

Table 1 :

 1 Execution time for authors algorithm vs. CGAL implementation of the incremental algorithm of Welzl.

	Image name from Figure 2 CGAL (ms) Authors (ms)
	(a)	643	19
	(b)	926	37
	(c)	1126	32
	(d)	542	48
	(e)	958	15
	(f)	294	13

Table 2 :

 2 Comparison of execution time for image presented on Figure 3 for different image size (first column) calculated with CGAL implementation of the incremental algorithm of Welzl and authors' method Image size No. of black pixels CGAL (ms) Authors' (ms)

	300x300	8000	1364	28
	270x270	6624	1181	22
	243x243	5371	777	18
	219x219	4329	660	15
	197x197	3465	573	14
	177x177	2945	541	12
	159x159	2295	379	9
	143x143	1925	266	8

If the set S is discrete, namely S = {xi} N i=1 , then the covariance matrix equalsΣS = 1 N N i=1 (xi -µ)(xi -µ) T , where µ = 1 N N i=1 xi is a mean of set S.