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.
| Dernière modification : Thursday 21 November 2024 |
|
Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr |