en fr Cost-based query-adaptive clustering for multidimensional objects with spatial extents Groupement dObjets Multidimensionnels Etendus avec un Modèle de Coût Adaptatif aux Requêtes Report as inadecuate




en fr Cost-based query-adaptive clustering for multidimensional objects with spatial extents Groupement dObjets Multidimensionnels Etendus avec un Modèle de Coût Adaptatif aux Requêtes - Download this document for free, or read online. Document in PDF available to download.

1 SMIS - Secured and Mobile Information Systems PRISM - Parallélisme, Réseaux, Systèmes, Modélisation, UVSQ - Université de Versailles Saint-Quentin-en-Yvelines, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8144

Abstract : We propose a cost-based query-adaptive clustering solution for multidimensional objects with spatial extents to speed-up execution of spatial range queries e.g., intersection, containment. Our work was motivated by the emergence of many SDI applications Selective Dissemination of Information bringing out new real challenges for the multidimensional data indexing. Our clustering method aims to meet several application requirements such as scalability many objects with many dimensions and with spatial extents, search performance high rates of spatial range queries, update performance frequent object insertions and deletions, and adaptability to object and query distributions and to system parameters. In this context, the existing indexing solutions e.g., R-trees do not efficiently cope with most of these requirements. Our object clustering drops many properties of classical tree-based indexing structures tree height balance, balanced splits, minimum object bounding in favor of a cost-based clustering strategy. The cost model takes into account the performance characteristics of the execution platform and relies on both data and query distributions to improve the average performance of spatial range queries. Our object clustering is based on grouping spatial objects with similar intervals positions and extents in a reduced subset of dimensions, namely the most selective and discriminatory ones relative to the query distribution. The practical relevance of our clustering approach was demonstrated by a series of experiments involving large collections of multidimensional spatial objects and spatial range queries with uniform and skewed distributions.

Résumé : Nous proposons une méthode de groupement en clusters d-objets multidimensionnels étendus, basée sur un modèle de co^ut adaptatif aux requêtes, pour accélérer l-exécution des requêtes spatiales de type intervalle e.g., intersection, inclusion. Notre travail a été motivé par l-émergence de nombreuses applications de dissémination sélective d-informations posant de nouveaux défis au domaine de l-indexation multidimensionnelle. Dans ce contexte, les approches d-indexation existantes e.g., R-trees ne sont pas adaptées aux besoins applicatifs tels que scalabilité beaucoup d-objets avec des dimensions élevées et des extensions spatiales, performance de recherche taux élevés de requêtes, performance de mise à jour insertions et suppressions fréquentes d-objets et adaptabilité à la distribution des objets et des requêtes, et aux paramètres systèmes. Dans notre méthode, nous relâchons plusieurs propriétés spécifiques aux structures d-indexation arborescentes classiques i.e. équilibrage de l-arbre et du partitionnement, englobement minimal des objets en faveur d-une stratégie de groupement basée sur un modèle de co^ut adaptatif. Ce modèle de co^ut tient compte des caractéristiques de la plateforme d-exécution, de la distribution spatiale des objets et surtout de la distribution spatiale des requêtes. Plus précisément, la distribution des requêtes permet de déterminer les dimensions les plus sélectives et discriminantes à utiliser dans le regroupement des objets. Nous avons validé notre approche par des études expérimentales de performance impliquant de grandes collections d-objets et des requêtes d-intervalles avec des distributions uniformes et non-uniformes.

Mots-clés : indexation multidimensionnelle objets multidimensionnels étendus groupement requêtes spatiales de type intervalle modèle de coût adaptatif aux requêtes





Author: Cristian-Augustin Saita -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents