大规模稀疏关系数据索引技术研究

论文摘要

在许多网上社群管理系统中（CWMS）,为了管理其中的稀疏数据,大规模稀疏数据表（LST）相关的存储结构正在被越来越多的采用。一个LST通常含有数千以上的属性,并且一条记录仅在少数属性上有定义。在LST中,定义在几个数字和文本混合属性上的低维结构化相似性查询是最常见的操作。但是许多和LST相关的Web 2.0服务的特性使得已有的大多数多维索引都不能适用。近期关于LST的研究多集中于如何存储数据表和建立一种简单的倒排索引来提高LST上的数据管理效率。到目前为止,还没有针对LST的其他新索引结构被提出。已有的倒排索引可以被很快的访问,但是它不包含任何与数据内容有关的信息,故而不能有效的减少查询过程中对数据表文件的随机访问次数。本文提出了基于过滤-检查策略,维护近似数据内容,且保证访问效率的iVA-file索引结构,设计了nG-Signature作为近似表示字符串数据的近似向量,并改进了已有的针对数字数据的近似向量编码方法。同时,本文还提出了新的基于扫描索引方式的查询执行方法。基于真实数据集的全面的测试证明了iVA-file在查询效率方面明显优于已有的技术,且保持了理想的更新速度。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景
• 1.2 国内外研究现状
• 1.3 本文主要研究内容及章节安排
• 第2章 预备知识和相关技术
• 2.1 预备知识
• 2.1.1 问题定义
• 2.1.2 编辑距离
• 2.2 相关技术
• 2.2.1 Interpreted Schema 数据表文件结构
• 2.2.2 VA-file
• 2.2.3 属性上的倒排索引
• 2.2.4 编辑距离的计算
• 2.2.5 编辑距离的估计
• 2.2.6 Singnature File
• 2.2.7 n-gram 上的倒排索引
• 2.3 本章小结
• 第3章 iVA-file 索引设计
• 3.1 设计目标和基本思想
• 3.2 iVA-file 结构
• 3.3 文本属性编码
• 3.3.1 nG-signature
• 3.3.2 使用nG-signature 估计编辑距离
• 3.3.3 nG-signature 的参数影响
• 3.4 数字属性编码
• 3.5 iVA-file 的建立与更新
• 3.6 本章小结
• 第4章 利用iVA-file 进行查询处理的方法
• 4.1 过滤-验证与同步扫描
• 4.2 kNN 查询过程
• 4.3 Select 查询过程
• 4.4 本章小结
• 第5章 实验结果及分析
• 5.1 实验设定
• 5.2 查询效率测试
• 5.3 更新效率测试
• 5.4 本章小结
• 结论
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢