基于Hilbert曲线的STR索引改进算法

An Improved STR-tree Spatial Index Algorithm Based on Hilbert-curve

递归网格排序算法(sort-tile-recursive,STR)是一种性能优良的静态变体,其构建效率高效,查询性能较为优良,但是没有很好的兼顾到数据本身的聚集特性。Hilbert曲线具有较好的数据聚集特性,但是存在一定信息的丢失。本文利用Hilbert曲线的聚集性来提高STR-树的数据聚集性能,提出了一种基于Hilbert编码的STR索引改进算法,并在改进中弥补信息丢失的问题。算法首先按照MBR的Hilbert值进行排序,根据节点容量生成子节点,形成各聚类中心,针对Hilbert异常值采用距离约束条件进行处理;迭代以上过程,生成Hilbert STR-树。研究结果表明,该算法的查询效率优于STR-树和R树。

The Sort-Tile-Recursive（STR）is a static R-tree variation,with outstanding build efficiency and acceptable query efficiency.The only problem the aggregation of data.Hilbert curve can ensure data aggregation however,some other information missed.In order to solve deficiency STR-tree,an improved STR-tree spatial index algorithm based on Hilbert-curve is proposed.This paper focuses on the offset caused by dimensionality reduction during the build process.algorithm sorts the objects by the Hilbert value of its MBRs,generates the temp-abstract nodes according to the node capacity,and records the center of each cluster.Second,the algorithm processes Hilbert outliers by adding the distance constraint.Third,iterating the above process until Hilbert STR-tree is built.Both theoretic analysis and experiments indicate that our algorithm performs more efficiently than the STR-tree querying.