Research on Construction of K-d Tree Based on Euclidean Distance

Hua Feng Ding; Wei Qing Wang; Yuan Zhang; Xing Jiang Xiao; Jun Xu

doi:10.4028/www.scientific.net/AMR.268-270.994

Paper Titles

A New Speech Enhancement Method Based on Genetic Algorithm
p.969

Design and Implementation of Minimum Hop Routing Algorithm with Reliability Assurance for WSN
p.975

Using Depth Image in 3D Model Retrieval System
p.981

An Intrusion Detection Based on Markov Model
p.988

Research on Construction of K-d Tree Based on Euclidean Distance
p.994

A Two-Layered Model for Distributed Data Mining in Grid Environments
p.1000

The Implementation of Data Warehouse Supporting Intuitionistic Fuzzy Data
p.1006

The Research of Tri-Networks Integration Security Control System
p.1012

Algorithms Research in the Application of Lorenz Time Series Prediction
p.1017

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 268-270Research on Construction of K-d Tree Based on...

Research on Construction of K-d Tree Based on Euclidean Distance

Abstract:

Traditional k-d tree is constructed according to the order in which data appear, so the balance and depth of the constructed k-d tree are not ideal. To overcome the disadvantages of the construction of traditional k-d tree, this paper proposes a new constructing method based on Euclidean distance so that the construction begins with the center of the data, and every time the points of the nearest distance are used to construct k-d tree, so k-d tree generated in this way is relatively better balanced and has better depth, therefore good searching performance is achieved.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 268-270)

Pages:

994-999

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.268-270.994

Citation:

Cite this paper

Online since:

July 2011

Authors:

Hua Feng Ding, Wei Qing Wang, Yuan Zhang, Xing Jiang Xiao, Jun Xu

Keywords:

Depth, Euclidean Distance, K-D Tree, Multi-Dimension

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] J L Bentley. Multidimensional Binary Search Trees Used for Associative Searching [J]. Communications of the ACM, 1975: 18（19）：509-517.

DOI: 10.1145/361002.361007

Google Scholar

[2] Sproull R F. Refinements to nearest-neighbor searching in k-dimensional trees [J] . Algorithmica, 1991, 6 (4) : 579—589.

DOI: 10.1007/bf01759061

Google Scholar

[3] HUANG He, SHI Zhong-Zhi, ZHENG Zheng. Similarity search based on shape k-d tree for multidimensional time sequence[J ]s. Journal of Software, 2006, 17(10): 2048−(2056).

DOI: 10.1360/jos172048

Google Scholar

[4] WANG Bi, HUO Hongwei. A Multidimensional Declustering Method Based on K-D Tree[J ]. Computer Engineering. 2003, 29 (3): 105-107.

Google Scholar

[5] LIU W ei-bin, YUAN Bao-zong. Optimizing computation of distance map based on optimal k-d Tree k-NN searching algorithm. JOURNAL O F THE CHINA RAILWAY SOCIETY, 2001, 23 (3): 66-71.

Google Scholar

[6] SUN Zong-can, TAO Lan, QI Jian-dong, WANG Bao-ying. K-means clustering algorithm base on k-d tree[J ]. Computer Engineering and Design, 2004, 25(11): 2054-(2057).

Google Scholar