论文部分内容阅读
当今社会，信息量剧增，生活节奏加快，如何从大量信息中找寻符合我们要求的信息，已是我们不得不面对的问题。因此，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结果。