On the average performance of fixed partial match queries in random relaxed K-d trees

Home | About RECERCAT | Contact

Català | Castellano

All of RECERCAT

By Communities &
Collections By Defense Date By Authors By Titles By Subject

This Collection

By Defense Date By Authors By Titles By Subject

Statistics

View Statistics All RECERCAT

My RECERCAT

Other repositories directory

RECERCAT Home > Universitat Politècnica de Catalunya > Documents de recerca > View document

To access the full text documents, please follow this link: http://hdl.handle.net/2117/24268

dc.contributor	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor	Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
dc.contributor.author	Duch Brown, Amalia
dc.contributor.author	Lau Laynes-Lozada, Gustavo Salvador
dc.contributor.author	Martínez Parra, Conrado
dc.date	2014
dc.identifier.citation	Duch, A.; Lau, G.; Martínez, C. On the average performance of fixed partial match queries in random relaxed K-d trees. A: International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms. "AoFA 2014: 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms: UPMC-Jussieu Paris, France, June 16–20, 2014: talks". Paris: 2014, p. 103-114.
dc.identifier.uri	http://hdl.handle.net/2117/24268
dc.language.iso	eng
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
dc.subject	Computer algorithms
dc.subject	Partial match
dc.subject	K-d trees
dc.subject	Multidimensional data structures
dc.subject	Associative queries
dc.subject	Algorismes computacionals
dc.title	On the average performance of fixed partial match queries in random relaxed K-d trees
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/conferenceObject
dc.description.abstract	We obtain an explicit formula for the expected cost of a fixed partial match query in a random relaxed K-d tree, that is, the expected cost for a query of the form q = (q0 , q1 , . . . , qK-1 ) with 0 < s < K specified coordinates with values z0 , . . . , zs-1 ¿ (0, 1). This is a generalization of previous results in the literature for s = 1. Qualitatively similar results hold for standard K-d trees and we conjecture that this also holds for other multidimensional tree structures such as quadtrees and K-d tries.
dc.description.abstract	Peer Reviewed

Show simple item record

All of RECERCAT

This Collection

Statistics

My RECERCAT

Related documents

Other documents of the same author