Randomized K-dimensional binary search trees
Visualitza/Obre
Estadístiques de LA Referencia / Recolecta
Inclou dades d'ús des de 2022
Cita com:
hdl:2117/84547
Tipus de documentReport de recerca
Data publicació1998-10-02
Condicions d'accésAccés obert
Tots els drets reservats. Aquesta obra està protegida pels drets de propietat intel·lectual i
industrial corresponents. Sense perjudici de les exempcions legals existents, queda prohibida la seva
reproducció, distribució, comunicació pública o transformació sense l'autorització del titular dels drets
Abstract
This paper introduces randomized K-dimensional binary search trees
(randomized Kd-trees), a variant of K-dimensional binary trees. This
data structure allows the efficient maintenance of multidimensional
records for any sequence of insertions and deletions; and thus, is
fully dynamic. We show that several types of associative queries are
efficiently supported by randomized Kd-trees. In particular, a
randomized Kd-tree with n records answers exact match queries in
expected O(log n) time. Partial match queries are answered in
expected O(n^{1-f(s/K)}) time, when s out of K attributes
are specified, with 0 < f(s/K) < 1 a real valued function of s/K.
Nearest neighbor queries are answered on-line in expected O(log n) time.
Our randomized algorithms guarantee that their expected
time bounds hold irrespective of the order and number of insertions
and deletions.
Forma partLSI-98-48-R
Col·leccions
Fitxers | Descripció | Mida | Format | Visualitza |
---|---|---|---|---|
R98-48.ps | 756,9Kb | Postscript | Visualitza/Obre |