Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Rank selection in multidimensional data

Autor
Duch, A.; Jimenez, R.; Martinez, C.
Tipus d'activitat
Document cientificotècnic
Data
2009-11-04
Codi
LSI-09-32-R
Projecte finançador
Algoritmos: ingeniería y experimentación
Repositori
http://hdl.handle.net/2117/87150 Obrir en finestra nova
Resum
Suppose we have a set of K-dimensional records stored in a general purpose spatial index like a K-d tree. The index efficiently supports insertions, ordinary exact searches, orthogonal range searches, nearest neighbor searches, etc. Here we consider whether we can also efficiently support search by rank, that is, to locate the i-th smallest element along the j-th coordinate. We answer this question in the affirmative by developing a simple algorithm with expected cost O(na(1/K) log n), where n i...
Citació
Duch, A., Jiménez, R., Martínez, C. "Rank selection in multidimensional data". 2009.
Paraules clau
Multidimensional data, Rank selection, Search problems, Tree data structures
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants

Arxius