基于PQR-tree的空间查询代价模型  

A Cost Model for Spatial Queries Based on PQR-tree

作　　者：李博涵[1] 秦小麟[1] 陈逸菲[1] 刘亚丽[1] 

机构地区：[1]南京航空航天大学计算机科学与技术学院,江苏南京210016

出　　处：《计算机工程与科学》2012年第5期161-167,共7页Computer Engineering & Science

基　　金：国家自然科学基金培育基金-基本科研业务费专项科研项目(NS2012023);中国博士后科学基金资助项目(20100481133);江苏省博士后基金资助项目(1001005B);江苏省普通高校研究生科研创新计划资助项目(CX10B-112Z);南京航空航天大学博士学位论文创新与创优基金资助项目(BCXJ10-07);工信部电子信息产业发展基金资助项目

摘　　要：空间信息处理和地理信息系统等领域的数据管理涉及到海量、高维空间数据对象的处理。本文针对传统数据索引结构在处理这类空间数据时所存在的内存使用过大、I/O消耗过多等问题,通过改进选择查询的代价模型,给出了基于PQR-tree的查询和代价模型,以提高空间数据查询的性能。提出了基于PQR-tree的三阶段并行查询的方法,分别在任务创建、分配、执行阶段进行优化。提出在任务创建和任务分配阶段应用于空间查询中过滤和精炼阶段的有效算法。测试表明,本文算法在处理各种不同分布类型数据集过程中有效降低了空间数据处理对时间和空间的代价和需求,并且并行机制下的代价模型在预测和评估方面也具有较好的精确度。The operation of spatial data objects is frequently involved in many applications with mass and high dimensional data sets,such as spatial information and GIS.The traditional index has disadvantages with too much memory and I/O consumption in handling this kind of queries.This paper presents the PQR-tree and cost model for spatial queries using PQR-tree.With the improvement of the select query cost model,the corresponding query and cost model are given based on PQR-tree.In order to improve the performance of the query of spatial data,a three-phase parallel query method is presented.And the optimization is executed respectively in the task creation,the distribution,and the execution stages.The effective filtering and refining algorithm can improve the performance in task creation and task distribution which are applied to spatial query.The experiment shows that the model has a degree of accuracy,and the above methods can reduce the cost of time and spatial requirements with different data sets.Given that parallel mechanism treats targets efficiently,this paper proposes a parallel mechanism cost model by using parallel query methods.

关 键 词：四叉树 R-TREE 查询代价模型 并行机制 精炼 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]