𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Expected worst-case partial match in random quadtries

✍ Scribed by Luc Devroye; Carlos Zamora-Cura

Book ID
104294265
Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
252 KB
Volume
141
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

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 time for partial match. Among other things, we show that partial match is very stable, in the sense that sup y Nn(y)=inf y Nn(y) β†’ 1 in probability.

πŸ“œ SIMILAR VOLUMES

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
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
Discontinuous information in the worst c
Discontinuous information in the worst case and randomized settings
✍ Aicke Hinrichs; Erich Novak; Henryk WoΕΊniakowski πŸ“‚ Article πŸ“… 2012 πŸ› John Wiley and Sons 🌐 English βš– 180 KB

## Abstract We believe that discontinuous linear information is never more powerful than continuous linear information for approximating continuous operators. We prove such a result in the worst case setting. In the randomized setting we consider compact linear operators defined between Hilbert spa