XML data sources are gaining popularity in the context of Business Intelligence and On-Line Analytical Processing (OLAP) applications, due to the amenities of XML in representing and managing complex and heterogeneous data. However, XML-native database systems currently suffer from limited performance, both in terms of volumes of manageable data and query response time. Therefore, recent research efforts are focusing on horizontal fragmentation techniques, which are able to overcome the above limitations. However, classical fragmentation algorithms are not suitable to control the number of originated fragments, which instead plays a critical role in data warehouses. In this paper, we propose the use of the K-means clustering algorithm for effectively and efficiently supporting the fragmentation of very large XML data warehouses. We complement our analytical contribution with a comprehensive experimental assessment where we compare the efficiency of our proposal against existing fragmentation algorithms.
Gorla and Betty @cite_31 exploit for vertical fragmentation of relational databases. Authors consider that association rules provide a natural way to represent relationships between attributes as implied by database queries. Basically, their solution consists in adapting the well-known algorithm Apriori @cite_19 by selecting the non-overlapping item-sets having highest support and by grouping their respective attributes into one partition. Then, the algorithm exploits a cost model to select an optimal fragmentation schema.Darabant and Campan @cite_22 propose using -means clustering for efficiently supporting horizontal fragmentation of object-oriented distributed databases. This research has inspired our work. In more detail, the method proposed in @cite_22 clusters object instances into fragments via taking into account all complex relationships between classes of data objects (aggregation, associations and links induced by complex methods). Finally, Fiolet and Toursel @cite_13 propose a parallel, progressive to fragment a database and distribute it over a data grid. This approach is inspired by the sequential clustering algorithm @cite_21 that consists in clustering data by means of projection operations.
@cite_22 @cite_21 @cite_19 @cite_31 @cite_13
2161048172 1977496278 1506285740 2020396904 2136603929
Vertical and horizontal fragmentations are central issues in the design process of distributed object based systems. A good fragmentation scheme followed by an optimal allocation could greatly enhance performance in such systems, as data transfer between distributed sites is minimized. In this paper we present a horizontal fragmentation approach that uses the k-means AI clustering method for partitioning object instances into fragments. Our new method applies to existing databases, where statistics are already present. We model fragmentation input data in a vector space and give different object similarity measures together with their geometrical interpretations. We provide quality and performance evaluations using a partition evaluator function Data mining applications place special requirements on clustering algorithms including: the ability to find clusters embedded in subspaces of high dimensional data, scalability, end-user comprehensibility of the results, non-presumption of any canonical data distribution, and insensitivity to the order of input records. We present CLIQUE, a clustering algorithm that satisfies each of these requirements. CLIQUE identifies dense clusters in subspaces of maximum dimensionality. It generates cluster descriptions in the form of DNF expressions that are minimized for ease of comprehension. It produces identical results irrespective of the order in which input records are presented and does not presume any specific mathematical form for data distribution. Through experiments, we show that CLIQUE efficiently finds accurate cluster in large high dimensional datasets. A new approach to vertical fragmentation in relational databases is proposed using association rules, a data-mining technique. Vertical fragmentation can enhance the performance of database systems by reducing the number of disk accesses needed by transactions. By adapting Apriori algorithm, a design methodology for vertical partitioning is proposed. The heuristic methodology is tested using two real-life databases for various minimum support levels and minimum confidence levels. In the smaller database, the partitioning solution obtained matched the optimal solution using exhaustive enumeration. The application of our method on the larger database resulted in the partitioning solution that has an improvement of 41.05 over unpartitioned solution and took less than a second to produce the solution. We provide future research directions on extending the procedure to distributed and object-oriented database designs. The increasing availability of clusters and grids of workstations provides cheap and powerful ressources for distributed datamining. To exploit these ressources we need new algorithms adapted to this kind of environment, in particular with respect to the way to fragment data and to use this fragmentation. An "intelligent" distribution of data is required and can be obtained from clustering. Most existing parallel methods of clustering are developped for supercomputers with shared memory and hence can not be used on a Grid. This paper presents a new clustering algorithm, called Progressive Clustering, which executes a clustering in an efficient and incremental distributed way. The data clusters resulting from this algorithm can subsequently be used in distributed data mining tasks.