𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Partial Match Queries in Random k-d Trees

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

Book ID
118180441
Publisher
Society for Industrial and Applied Mathematics
Year
2006
Tongue
English
Weight
315 KB
Volume
35
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

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

Partial Match Queries in Random Quadtree
Partial Match Queries in Random Quadtrees
✍ Chern, Hua-Huai; Hwang, Hsien-Kuei πŸ“‚ Article πŸ“… 2003 πŸ› Society for Industrial and Applied Mathematics 🌐 English βš– 180 KB
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

Efficient sets in partial k-trees
Efficient sets in partial k-trees
✍ Jan Arne Telle; Andrzej Proskurowski πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 652 KB