RB树:一种支持空间近似关键字查询的外存索引

摘要：

空间近似关键字查询包含一个空间条件和一组关键字相似性条件,这种查询在空间数据库中返回同时满足以下条件的对象:1)对象的位置信息满足查询中的空间条件;2)对于查询中的任何一个关键字,对象中至少包含一个关键字与其相似度大于给定阈值.随着当前数据的爆炸性增长,空间数据库无法完整地存放在内存中,因此空间数据库需要支持空间近似关键字查询的外存索引.目前,还没有在外存中支持精确的空间近似关键字查询的索引结构.设计了一种新型的外存索引RB树,在外存中支持精确的空间近似关键字查询.RB树支持的空间近似关键字查询包括多种空间条件,如范围查询、NN查询,同时支持多种关键字相似性度量,包括编辑距离、规范化编辑距离等.通过真实数据中的性能测试验证了RB树的效率.

关键词：空间数据库、关键字、查询处理、索引、外存

所属期刊栏目：49

分类号：TP311.13(计算技术、计算机技术)

资助基金：国家"九七三"重点基础研究发展计划基金项目2006CB303005;国家自然科学基金项目60903016,60533110,60773063;教育部新世纪优秀人才支持计划基金项目NCET-05-0333;黑龙江省教育厅科学技术研究项目11531276

在线出版日期：2012-12-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：2142-2152