【摘要】

本篇论文就Skyline查询算法进行研究，从穷举法入手，总结经验。发现BFS遍历冗余后，利用反向遍历的思想，设计了基于B-Tree和BNL结合的高效检索算法。在检验检索结果的正确性后，通过程序随机查询关键词，得到多组关键词的检索时间，最后发现论文设计的高效检索算法在yago数据集下5个关键词内的检索中具有不到10s的平均检索时间。

目录

【摘要】

第一章 skyline查询背景简介

1.1 简介（问题1：描述skyline的应用范围）

1.2 相关工作

第二章 穷举法查询计算

2.1 BFS计算语义距离&分块剪枝处理

（1）算法描述

（2）算法步骤

（3）算法实现伪代码

（4）算法评价与分析

2.2 BNL算法（块嵌套环算法）

（1）算法描述

（2）算法步骤

（3）算法实现伪代码

（4）算法复杂度分析评价

2.3穷举检索

第三章 高效检索算法设计

3.1 B-Tree结构存储关键词

（1）结构背景简介

（2）基本结构介绍

（3）结构改进用于语义地点查询

（4）基于语义地点B-Tree的相关操作实现

3.2 基于B-Tree的初阶检索算法

（1）算法描述

（2）算法步骤

（3）算法伪代码

（4）算法复杂度分析评价

3.3 核心算法：基于B-Tree的高阶检索算法

（1）有助于理解算法的相关定义

（2）算法描述

（3）算法步骤

（4）算法伪代码

（5）算法复杂度分析评价

3.4 针对单个关键词查找的最终优化

3.5 高效检索算法的确定

第四章 实验分析算法性能

Ø 实验环境&配置：普通的PC；

Ø 算法实现语言：C/C++；

Ø 编译运行软件：DEV 5.11。

4.1 对检索结果的正确性进行验证

4.2  yago_small小数据集下算法性能测量

4.3 yago数据集下

第五章 问题解答

5.1 问题1

5.2 问题2

5.3 问题3

第六章 结论&进一步工作

6.1 实验总结

6.2 进一步工作