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

Abstract

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.