Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 03 janvier 2012 à 14h30 en B311, Nicolas Broutin nous parlera de : Recherches partiellement spécifiées dans les arbres multidimensionnels

Résumé : Nous considérons la recherche d'éléments dans des structures de données multidimensionnelles (quad trees, k-d trees), en particulier lorsque certaines coordonnées ne sont pas spécifiées (partial match query). Nous supposons que les données consistent en un ensemble de points uniformes dans le carré unité. Pour ce modèle, dans une structure contenant n points, Flajolet et Puech ont montré que le nombre de noeuds C_n(U) à visiter pour répondre à une requête demandant l'ensemble des données dont la première coordonnée est x=U est tel que E[C_n]\sim κ nβ, où κ et β sont des constantes explicites. Nous développons une approche basée sur l'analyse des coûts C_n(s) pour des requêtes à x=s fixé. Nous donnons en particulier des estimations précises de la variance et de la distribution limite de C_n(s) lorsque n\to\infty. Nos résultats permettent de décrire un processus limite pour C_n(s) lorsque s varie dans (0,1).

Travail en collaboration avec Ralph Neininger et Henning Sulzbach.

 [Slides.pdf]


Dernière modification : Monday 18 March 2024 Valid HTML 4.01! Valid CSS! Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr