𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Partial Match Queries in Random Quadtrees

✍ Scribed by Chern, Hua-Huai; Hwang, Hsien-Kuei

Book ID
118181197
Publisher
Society for Industrial and Applied Mathematics
Year
2003
Tongue
English
Weight
180 KB
Volume
32
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Partial Match Queries in Random k-d Tree
Partial Match Queries in Random k-d Trees
✍ Chern, Hua-Huai; Hwang, Hsien-Kuei πŸ“‚ Article πŸ“… 2006 πŸ› Society for Industrial and Applied Mathematics 🌐 English βš– 315 KB
Asymptotic distributions for partial mat
Asymptotic distributions for partial match queries in K-d trees
✍ Ralph Neininger πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 229 KB

The distributional performance of the cost of a partial match query is investigated in some sorts of K-d trees. The trees under consideration are Bentley's K-d tree, the locally balanced K-d-t tree, and the random relaxed K-d tree. For each of these trees it is proved that in the uniform probabilist

Expected worst-case partial match in ran
Expected worst-case partial match in random quadtries
✍ Luc Devroye; Carlos Zamora-Cura πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 252 KB

We consider random multivariate quadtries obtained from n points independently and uniformly distributed on the unit cube of R d . Let Nn(y) be the complexity of the standard partial match algorithm for ΓΏxed vector y, where y is a vector in R s , 0 Β‘ s Β‘ d. We study Nn = sup y Nn(y), the worst-case