Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Selection by rank in K-dimensional binary search trees

Autor
Duch, A.; Jimenez, R.; Martinez, C.
Tipus d'activitat
Article en revista
Revista
Random structures and algorithms
Data de publicació
2014-08-01
Volum
45
Número
1
Pàgina inicial
14
Pàgina final
37
DOI
https://doi.org/10.1002/rsa.20476 Obrir en finestra nova
URL
http://onlinelibrary.wiley.com/doi/10.1002/rsa.20476/abstract Obrir en finestra nova
Resum
In this work we show how to augment general purpose multidimensional data structures, such as K-d trees, to efficiently support search by rank (that is, to locate the i-th smallest element along the j-th coordinate, for given i and j) and to find the rank of a given item along a given coordinate. To do so, we introduce two simple, practical and very flexible algorithms - Select-by-Rank and Find-Rank - with very little overhead. Both algorithms can be easily implemented and adapted to several spa...
Paraules clau
K-dimensional search trees, Limit-theorem, Multidimensional data, Multidimensional data structures, Partial match, Partial match queries, Probabilistic analysis of algorithms, Recursive algorithms, Selection
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants