Centre de documentation
scientifique

Multi-way distance joins queries in spatial databases / A. Corral in Geoinformatica, vol 8 n° 4 (December 2004)  

Public [article]  inGeoinformatica > vol 8 n° 4 (December 2004) . - pp 373 - 402 Titre : Multi-way distance joins queries in spatial databases Type de document : Article/Communication Auteurs : A. Corral, Auteur ; Y. Manolopoulos, Auteur ; Y. Theodoridis, Auteur ; M. Vassilakopoulos, Auteur Année de publication : 2004 Article en page(s) : pp 373 - 402 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] base de données localisées [Termes IGN] graphe [Termes IGN] jointure spatiale [Termes IGN] requête spatiale Résumé : (Auteur) Let a tuple of n objects obeying a query graph (QG) be called the n-tuple. The "Ddistance-value" of this n-tuple is the value of a linear function of distances of the n objects that make up this n-tuple, according to the edges of the QG. This paper addresses the problem of finding the K n-tuples between n spatial datasets that have the smallest Ddistance-values, the so-called K-multi-way distance join query (K-MWDJQ), where each set is indexed by an R-tree-based structure. This query can be viewed as an extension of K-closest-pairs query (K-CPQ) for n inputs. In addition, a recursive non-incremental branch-and-bound algorithm following a depth-first search for processing synchronously all inputs without producing any intermediate result is proposed. Enhanced pruning techniques are also applied to n R-trees nodes in order to reduce the total response time and the number of distance computations of the query. Due to the exponential nature of the problem, we also propose a time-based approximate version of the recursive algorithm that combines approximation techniques to adjust the quality of the result and the global processing time. Finally, we give a detailed experimental study of the proposed algorithms using real spatial datasets, highlighting their performance and the quality of the approximate results. Numéro de notice : A2004-393 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE/INFORMATIQUE Nature : Article DOI : 10.1023/B:GEIN.0000040832.25622.8d En ligne : https://doi.org/10.1023/B:GEIN.0000040832.25622.8d Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=26920 [article]

Exemplaires(1)

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