Font Size: a A A

An Improved Cost Model For Spatial Joins

Posted on:2008-10-31Degree:MasterType:Thesis
Country:ChinaCandidate:Y L ChenFull Text:PDF
GTID:2178360215459806Subject:Computer software and theory
Abstract/Summary:PDF Full Text Request
Because the spatial data is vast, multidimensional and out-of-order, the efficiency of spatial data query becomes the bottleneck of improving the performance of spatial database, spatial query optimization becomes the difficulty and innovation of spatial database application consequentially. The cost model is one of chief technologies of query optimization, During various queries, special join query is a basal and high-cost operation, so estimating the cost of join query is very important for spatial query optimization.This thesis starting with studying spatial index and spatial query technologies, investigates Yannis Theodoridis's spatial join cost model founded on R-tree deeply. This thesis analyzes the sample arithmetic of obtaining the actual data density deeply, researches using random data table in the cost model and gives corresponding formulas; this thesis divides the whole space into plentiful child spaces and obtains the actual density using sampling particularly; this thesis gives a series of regulations used to obtain every query window's density, using these regulations can avoid a mass of sampling operation and only add a spot of computing; this thesis improves the LRU permutation arithmetic and give PP-LRU arithmetic, which conserve valid middle nodes in the newest visited way in the query tree, theoretically this arithmetic can reduce the cost of join query greatly. On the base of using PP-LRU arithmetic as buffer strategy, these expandations and improvements make the cost model to have a greater performance.In the end, this thesis verifies the improved model through emulational experiments. The result of the experiments shows that the relative error of the improved cost model keeps below 13%, and the time spending of the improved model has a greater melioration compared with the old one.
Keywords/Search Tags:R-tree, spatial joins, cost model, random data table sampling, PP-LRU arithmetic
PDF Full Text Request
Related items