Abstract
A k-d tree indexing structure is a n-dimensional structure to organize n-dimensional data for speedy retrieval of information using associative search, where k represents the dimension of the search space. The data structure was proposed by Jon Louis Bentley and is well capable of handling different kinds of queries in a very efficient way. It is founded on the generalization of binary search tree to support data with multiple dimensions. While working with multidimensional data, we need an indexing structure to well organize the data. In this research paper, the authors are explaining the indexing structures based on k-d tree to hold multidimensional data.
Please note that the LNCS Editorial assumes that all authors have used the western naming convention, with given names preceding surnames. This determines the structure of the names in the running heads and the author index.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
J.T. Robinson, The K-D-B tree: a search structure for large multidimensional dynamic indexes, Ann Arbor, MI: Proceeding 1981 ACM-SIGMOD International Conference on Management of Data (1981), pp. 10–18
T. Matsuyama, L. Hao, M. Nagao, A file organization for geographic information systems based on spatial proximity, ScienceDirect. Comput. Vis. Graphics Image Process. 26, 303–318 (1984)
J. Dittrich, L. Blunschi, M.A. Vaz Salles, Indexing moving objects using short-lived throwaway indexes, in Advances in Spatial and Temporal Databases, vol. 5644 (Springer, Berlin, Heidelberg, 2009), pp. 189–207
H. Doraiswamy, A GPU-based index to support interactive spatio-temporal queries over historical data, in IEEE, IEEE 32nd International Conference on Data Engineering, Helsinki, Finland (2016)
P. Wu, Randomly projected KD-trees with distance metric learning for image retrieval, in International Conference on Multimedia Modeling, Advances in Multimedia Modeling, vol. 6524, Springer, Berlin, Heidelberg (2011), pp. 371–382
M.M.P. Crespo, Design, analysis and implementation of new variants of Kd-trees. Ph.D. Thesis (2010)
F. Gieseke, Buffer k-d trees: Processing massive nearest neighbor queries on GPUs, in Proceedings of the 31st International Conference on International Conference on Machine Learning, vol. 32, Beijing, China (2014), pp. 172–180
J. Jo, J. Seo, J.-D. Fekete, A progressive k-d tree for approximate k-nearest neighbors, in IEEE Workshop on Data Systems for Interactive Analysis, Phoenix, AZ, USA. IEEE (2017), pp. 1–5
F.O. Cabrera, M. Sánchez-Marré, Using NIAR k-d trees to improve the case-based reasoning retrieval, in Advances in Soft Computing and Its Applications. Lecture Notes in Computer Science, vol. 8266 (Springer, Berlin, Heidelberg, 2013)
D. Amalia, V. Estivill-Castro, C. Martínez, Randomized K-dimensional binary search trees, in International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 1533 (Springer, Berlin, Heidelberg) (1998)
X. Yang, MSKD: multi-split KD-tree design on GPU. Multimed. Tools Appl. 75, 1349–1364 (2016)
B.C. Ooi, Spatial kd-tree: a data structure for geographic database. Datenbanksysteme in Büro, Technik und Wissenschaft. Informatik-Fachberichte 136, 247–258 (1998)
O. Procopiuc, Bkd-tree: a dynamic scalable kd-tree, in Advances in Spatial and Temporal Databases. Lecture Notes in Computer Science, vol. 2750 (2003), pp. 46–65
G. Noël, S. Servigne, R. Laurini, The Po-tree: a real-time spatiotemporal data indexing structure (Berlin, Heidelberg, Springer, pp. 259–270). 978-3-540-22610-9 (2005)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Gill, S., Hooda, M. (2021). The Design Perspective of the Structures Based on k-d Tree. In: Rathore, V.S., Dey, N., Piuri, V., Babo, R., Polkowski, Z., Tavares, J.M.R.S. (eds) Rising Threats in Expert Applications and Solutions. Advances in Intelligent Systems and Computing, vol 1187. Springer, Singapore. https://doi.org/10.1007/978-981-15-6014-9_61
Download citation
DOI: https://doi.org/10.1007/978-981-15-6014-9_61
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-15-6013-2
Online ISBN: 978-981-15-6014-9
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)