Centre de documentation
scientifique

Merging R-trees: efficient strategies for local bulk insertion / L. Chen in Geoinformatica, vol 6 n° 1 (March - May 2002)  

Public [article]  inGeoinformatica > vol 6 n° 1 (March - May 2002) . - pp 7 - 34 Titre : Merging R-trees: efficient strategies for local bulk insertion Type de document : Article/Communication Auteurs : L. Chen, Auteur ; R. Choubey, Auteur ; E.A. Rundensteiner, Auteur Année de publication : 2002 Article en page(s) : pp 7 - 34 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Bases de données localisées [Termes IGN] arbre-R [Termes IGN] index spatial [Termes IGN] indexation spatiale [Termes IGN] intégration de données [Termes IGN] jeu de données localisées [Termes IGN] requête spatiale Résumé : (Auteur) A lot of recent work has focussed on bulk loading of data into multidimensional index structures in order to efficiently construct such structures for large data sets. In this paper, we address this problem with particular focus on R-trees - which are an important class of index structures used widely in commercial database systems. We propose a new technique, which as opposed to the current technique of inserting data one by one, bulk inserts entire new data sets into an active R-tree. This technique, called STLT (for small-tree-large-tree), considers the new data set as an R-tree itself (small tree), identifies and prepares a suitable location in the original R-tree (large tree) for insertion, and lastly performs the insert of the small tree into the large tree. Besides an analytical cost model of STLT, extensive experimental studies both on synthetic and real GIS data sets are also reported. These experiments not only compare STLT against the conventional technique, but also evaluate the suitability and limitations of STLT under different conditions, such as varying buffer sizes, ratio between existing and new data sizes, and skewness of new data with respect to the whole spatial region. We find that STLT does much better (in average, about 65%) than the existing technique for skewed data sets as well for large sizes of both the large tree and the small tree in terms of insertion time, while keeping comparable query tree quality. STLT consistently outperforms the alternate technique in all other circumstances in terms of bulk insertion time, especially, even up to 2,000% for the cases when the area of new data sets covers up to 4% of the global region covered by the existing index tree; however, at the cost of a deteriorating resulting tree quality. Numéro de notice : A2002-107 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE/INFORMATIQUE Nature : Article DOI : 10.1023/A:1013764014000 En ligne : https://doi.org/10.1023/A:1013764014000 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=22022 [article]

Exemplaires(1)

Code-barres	Cote	Support	Localisation	Section	Disponibilité
057-02011	RAB	Revue	Centre de documentation	En réserve L003	Disponible

GBI : a generalized R-tree bulk-insertion strategy / R. Choubey (20/07/1999)  

Public contenu dans Advances in spatial data bases, SSD '99, 6th International Symposium, Hong Kong, China, July 20-23, 1999 / Ralf Hartmut Güting (1999)   Titre : GBI : a generalized R-tree bulk-insertion strategy Type de document : Article/Communication Auteurs : R. Choubey, Auteur ; L. Chen, Auteur ; E.A. Rundensteiner, Auteur Editeur : Berlin, Heidelberg, Vienne, New York, ... : Springer Année de publication : 20/07/1999 Collection : Lecture notes in Computer Science, ISSN 0302-9743 num. 1651 Conférence : SSD 1999, 6th International Symposium Advances in spatial data bases 20/07/1999 23/07/1999 Hong Kong Chine Proceedings Springer Importance : pp 91 - 108 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Bases de données localisées [Termes IGN] arbre-R [Termes IGN] groupe [Termes IGN] index spatial [Termes IGN] indexation spatiale [Termes IGN] requête spatiale Résumé : (Auteur) A lot of recent work has studied strategies related to bulk loading of large data sets into multidimensional index structures. In this paper, we address the problem of bulk insertions into existing index structures with particular focus on R-trees - which are an important class of index structures used widely in commercial database systems. We propose a new technique, which as opposed to the current technique of inserting data one by one, bulk inserts entire new incoming datasets into an active R-tree. This technique, called GBI (for Generalized Bulk Insertion), partitions the new datasets into sets of clusters and outliers, constructs an R-tree (small tree) from each cluster, identifies and prepares suitable locations in the original R.-tree (large tree) for insertion, and lastly performs the insertions of the small trees and the outliers into the large tree in bulk. Our experimental studies demonstrate that GBI does especially well (over 200% better than the existing technique) for randomly located data as well as for real datasets that contain few natural clusters, while also consistently outperforming the alternate technique in all other circumstances. Numéro de notice : C1999-057 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE/INFORMATIQUE Nature : Communication DOI : 10.1007/3-540-48482-5_8 En ligne : https://doi.org/10.1007/3-540-48482-5_8 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=65823