|
Title:
|
Quad-kd trees: A general framework for kd trees and quad trees
|
|
Author:
|
Bereczky, Nikolett; Duch Brown, Amalia; Németh, Krisztián; Roura Ferret, Salvador
|
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals |
|
Abstract:
|
We introduce the quad-kd tree: a general purpose and hierarchical data structure for the storage of multidimensional points. Quad-kd trees include point quad trees and kd trees as particular cases and therefore they could constitute a general framework for the study of fundamental properties of trees similar to them. Besides, quad-kd trees can be tuned by means of insertion heuristics and bucketing techniques to obtain trade-offs between their costs in time and space. We propose three such heuristics and we show analytically and experimentally their competitive performance. Our analytical results back the experimental outcomes and suggest that the quad-kd tree is a flexible data structure that can be tailored to the resource requirements of a given application. |
|
Abstract:
|
Peer Reviewed |
|
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
-Data structures (Computer science)
-Quad trees
-kd trees
-Multidimensional data structures
-Associative retrieval
-Estructures de dades (Informàtica) |
|
Rights:
|
|
|
Document type:
|
Article - Submitted version
Article |
|
Share:
|
|
