Carregant...
Carregant...

Vés al contingut (premeu Retorn)

On the cost of fixed partial match queries in K-d trees

Autor
Duch, A.; Lau, G.; Martinez, C.
Tipus d'activitat
Article en revista
Revista
Algorithmica
Data de publicació
2016-08-01
Volum
75
Número
4
Pàgina inicial
684
Pàgina final
723
DOI
https://doi.org/10.1007/s00453-015-0097-4 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/89860 Obrir en finestra nova
URL
http://link.springer.com/article/10.1007%2Fs00453-015-0097-4 Obrir en finestra nova
Resum
Partial match queries constitute the most basic type of associative queries in multidimensional data structures such as K-d trees or quadtrees. Given a query q=(q0,…,qK-1) where s of the coordinates are specified and K-s are left unspecified (qi=*), a partial match search returns the subset of data points x=(x0,…,xK-1) in the data structure that match the given query, that is, the data points such that xi=qi whenever qi¿*. There exists a wealth of results about the cost of partial match sea...
Citació
Duch, A., Lau, G., Martínez, C. On the cost of fixed partial match queries in K-d trees. "Algorithmica", 1 Agost 2016, vol. 75, núm. 4, p. 684-723.
Paraules clau
Multidimensional Search, Partial Match Search, K-dimensional Search Trees, Analysis Of Algorithms, Multidimensional Data Structures, Binary Search-trees, Multidimensional Data, Range Search, Quadtrees
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants