The Study Of Selectivity Estimation Based On The Key Word Of Road Network

Selectivity estimation based on road network keyword means calculating the points of interest which are conform to the requirements of space and the keyword. At present, the traditional query algorithm used to solve such problems, but consider the large amount of the road network data, query time will be long. Selectivity estimation is an estimation based on pretreatment, compared with the traditional query, selectivity estimation can reduce the query time, but its application in the network only involves the spatial location information, not include keywords estimate. Therefore quickly solve this problem maintaining high accuracy which is the research emphasis in this paper.For solving such problems, FSLK selectivity estimation algorithm(First Spatial Last Keywords) based on road network keyword is proposed. FSLK algorithm is a kind of selectivity estimation algorithm processing spatial information and keyword information based on partition, this paper has done the following work for proposing FSLK algorithm:First of all, the paper use partition method processing selectivity estimation based on the road network keyword. In this paper, by using the partition algorithm based on Voronoi diagram, the road network is divided into multiple partitions, pretreat the partitions using selectivity estimation. After the pretreatment, firstly do selectivity estimation on the unit of partition, then do selectivity estimation on each partition, and using formula combine the estimation of the road network space and the keyword results. By the method of partition, FSLK algorithm combines the selectivity estimation of road network space and keywords, the experimental results show that FSLK algorithm, get both accuracy and efficiency, and has low memory usage.Secondly, presents two improved estimation algorithm which are the improved local density method and improved VSOL, one is used on space estimating of FSLK road network partition, the other one is used on FSLK selectivity estimation of keywords. Improved local density method has redefined the local point density, proposing the formulas for calculating space partition, make its can be used on estimating multi-partition road network space; Improved VSOL optimized then generation of VSOL hash function and using dynamic iteration processing VSOL K-means, used on estimating keywords of the multi-partition road network selectivity. Experiments show that the two improved algorithms make FSLK algorithm is more efficient than the traditional query, and the result of the estimate is precise.