An algorithm for constructing spatial vector data storage based on KD-tree and density estimation


  • Ning Wang



Spatial vector data, KD-tree, Density estimation, Locality-sensitive hashing


With the widespread application of spatial vector data in various fields, this paper proposes a novel algorithm for constructing spatial vector data storage. The algorithm is based on KD-tree and density estimation techniques, aiming to improve the storage efficiency and query performance of large-scale spatial vector data. The algorithm first efficiently organizes spatial vector data using KD-tree, and then performs density estimation based on the Locality Sensitive Hashing (LSH) algorithm. Algorithm optimizations for spatial partitioning are applied to the KD-tree construction algorithm, reducing the search range during queries and improving retrieval speed. By testing with Green Tide data, the algorithm based on KD-tree and density estimation demonstrates higher query efficiency and better scalability across multiple test datasets. Particularly, when dealing with large-scale datasets characterized by non-uniform data distributions, this algorithm significantly improves data retrieval speed while maintaining low storage overhead.


Vo H T, Bronson J, Summa B, et al.Parallel visualization on large clusters using MapReduce[C]//Large Data Analysis and Visualization (LDAV), 2011 IEEE Symposium on IEEE,2011:81-88.

Yang X, Liu S, Feng K, et al. Visualization and adaptive subsetting of earth science data in HDFS: A novel data analysis strategy with hadoop and spark[C]//Big Data and Cloud Computing (BDCloud), Social Computing and Networking (SocialCom), Sustainable Computingand Communications (SustainCom) (BDCloud-SocialCom-SustainCom), 2016 IEEE International Conferences on IEEE2016:89-96.

Eldawy A, Mokbel M F, Jonathan C. Hadoop Viz:A MapReduce framework for extensible visualization of big spatial data[C]//Data Engineering (ICDE), 2016 IEEE 32nd International Conference on IEEE, 016601-612.







How to Cite

Wang, N. (2024). An algorithm for constructing spatial vector data storage based on KD-tree and density estimation. Journal of Computing and Electronic Information Management, 12(2), 25-29.

Similar Articles

1-10 of 49

You may also start an advanced similarity search for this article.