Font Size: a A A

Improvements On The Cost Model For Spatial Joins Using R-Tree

Posted on:2007-11-12Degree:MasterType:Thesis
Country:ChinaCandidate:Y F JuFull Text:PDF
GTID:2178360185466858Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
Spatial join query is one of the most often used operation, and the data in spatial database is out-of-order and very large in amount, so estimating the cost of join queries is very important for spatial query optimization.The cost model for spatial joins is built on the base of principle of window query, and the original model in this thesis is the extension of the model for window query. In this model, the effect of an unfixed length buffer and the distribution of the storing data are discussed. On the other side, the model depends on a large volume of computation, so we need a long time to get the result.The kernel thought of the improved cost model in this thesis is exchanging memory space for time. In other words, the time complexity can be greatly reduced by using a little memory space. The auxiliary storage area of the model includes a fixed length buffer and a queue that is used to storage pairs of nodes those overlap most probably. The buffer can lead to page fault interrupts, so we build a probability model for it. A random variable of the page fault interrupt has an exponential distribution. The concrete implementation approach is to select most of pairs of nodes that intersect more probably, and to estimate the total cost by these pairs' average cost. The improved model can be applied to uniform and non-uniform data sets. Partitioning and sampling algorithms are proposed for non-uniform data sets, the cost summed from those data pieces is the total cost.The improved model is demonstrated with simulation data from all sides. From the results, we can see that the relative error is below 20%. Compared with the primary model, the improved one reduces the time complexity and gets the expectation effect.
Keywords/Search Tags:spatial joins, R-tree, non-uniform distribution, fixed length buffer, sampling
PDF Full Text Request
Related items