基于p-范数距离的Top-N查询处理

摘要

当今社会,信息量剧增,生活节奏加快,如何从大量信息中找寻符合我们要求的信息,已是我们不得不面对的问题。因此,Top-N查询越来越被广泛应用,几乎已涉及我们工作学习生活的各个方面。近年来,虽有很多人已提出一些算法来解决此问题,但仍然无法满足我们的需求。原因在于大多算法条件较为苛刻,比如重要的阈值算法(TA)要求排序函数是单调的,查询点是固定的且顺序访问是单向的。然而在许多应用中,这些条件无法同时满足,如查询点是任意的或排序函数是非单调的。与此同时,日益蓬勃发展的互联网中的信息检索采用了一种IR风格的检索方式,也就是关键字查询。但是,这类IR系统也存在两个不足:其一,这类IR系统只能提供有限的结构化数据查询能力;其二,这类IR系统通常缺乏查询优化机制。
　　针对上述问题,本文从泛函分析的角度提出一种适用于N维p-范数空间的Top-N查询算法,该算法不仅能够弥补现有方法的缺陷与不足,而且能够解决原有算法不能解决的问题。本文主要工作如下:
　　第一,提出一种新的位于n维实范数空间的查询模型,该模型具有如下特点:⑴排序函数是任意的p-范数距离,该距离不一定是单调的;⑵查询点(即一个实数向量)是任意的;⑶顺序访问可能是双向的。显然,TA-like算法不适用于该模型。
　　第二,对于n维实范数空间的一般p-范数,根据不同的数据访问方式,我们提出了pTA,pTAz和pNRA算法,分别针对如下三种情况:⑴所有列表同时支持顺序访问和随机访问;⑵限制顺序访问,即存在列表仅支持随机访问,不支持顺序访问;⑶所有列表只支持顺序访问,不支持随机访问。
　　第三,针对不同的低维数据(2,3,4维)和高维数据(25,50,104维),我们做了大量的实验来证明我们算法的有效性和高效性。实验结果表明,本文提出的算法能够更快地找到正确的Top-N结果。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪 论

1.1 研究背景及意义

1.2 本文主要工作及创新点

1.3 本文组织结构

第2章 Top-N查询研究综述

2.1 单调排序函数

2.2 非单调排序函数

2.3 本章小结

第3章 Top-N查询问题定义

3.1 相关概念

3.2 Top-N查询模型

3.3 本章小结

第4章 算 法

4.1 pTA算法

4.2 限制顺序访问的pTAz算法

4.3 不支持随机访问的pNRA算法

4.4 本章小结

第5章 实验过程及结果分析

5.1 实验环境和数据集

5.2 花费时间

5.3 N变化

5.4 pTAz算法分析

5.5 本章小结

第6章 总结与展望

6.1 工作总结

6.2 后续工作展望

参考文献

致谢

攻读学位期间取得的科研成果