基于模拟退火算法的空间度量物化选择

Selective materialization of special measures based on simulated annealing algorithm

为了解决空间OLAP的响应速度存在着存储空间和时间代价的矛盾,通过空间立方体的选择物化方法来实现空间要素有效而实用的选择合并,提高联机分析的响应速度.采用模拟退火算法,以空间对象面状区域的合并为例,进行空间度量物化选择,将模拟退火算法融入PIA算法中,同时把空间对象（面状）与其它类型的空间对象（点状、线状）的关联关系（交、含、邻）作为空间对象合并的共享性与实用性的考查指标,加入目标函数当中.实验结果表明：随着空间对象数据的增加,模拟退火算法与PIA算法,两种算法的时间代价仅有较少的增长,均具较好的伸缩性,在空间对象数目100-400时,PIA算法优于模拟退火算法,当空间对象数目大于400后模拟退火算法时间代价缓慢增长,而PIA算法时间代价急剧增大;在模拟退火算法中空间对象集合的空间关联度越高,选中几率越高.融入PIA的模拟退火算法具有良好的伸缩性,并提高了空间度量合并解的优化,增加了空间度量选择物化的实用性.

In order to solve the contradiction between storage space and storage time of spatial OLAP response speed, the selective materialization method of spatial cubes was developed. This method adopts the simulated annealing algorithm and takes the area regional merger of spatial objects as example to achieve the materialized selection of spatial measure. The simulated annealing algorithm was introduced into the pointer intersection algorithm（PIA）, and the associated relation（intersect, include and adjacent） of spatial objects （area） and other types of space objects （point, line） was taken as test indicators for the characters of the common sharing and practicality of combining spatial objects, which joined the objective function. The results show that： with the data of spatial objects increased, the time cost of simulated annealing algorithm and PIA increases a little and both of them perform a better scalability. When the number of spatial objects is from 100 to 400, PIA is superior to the simulated annealing algorithm; when it is over 400, the time cost of simulated annealing algorithm grows slowly, while the time cost of PIA increases rapidly. The higher is the degree of spatial correlation of spatial objects setting in the simulated annealing algorithm, the higher is the probability of being selected. The simulated annealing algorithm combining with the pointer intersection algorithm optimizes the merge solution of spatial measurement, and enhances the practicability of the selective materialization of spatial measurement.