基于p-范數(shù)距離的Top-N查詢處理.pdf

1、當(dāng)今社會(huì),信息量劇增,生活節(jié)奏加快,如何從大量信息中找尋符合我們要求的信息,已是我們不得不面對(duì)的問題。因此,Top-N查詢?cè)絹碓奖粡V泛應(yīng)用,幾乎已涉及我們工作學(xué)習(xí)生活的各個(gè)方面。近年來,雖有很多人已提出一些算法來解決此問題,但仍然無法滿足我們的需求。原因在于大多算法條件較為苛刻,比如重要的閾值算法(TA)要求排序函數(shù)是單調(diào)的,查詢點(diǎn)是固定的且順序訪問是單向的。然而在許多應(yīng)用中,這些條件無法同時(shí)滿足,如查詢點(diǎn)是任意的或排序函數(shù)是非單調(diào)的。

2、與此同時(shí),日益蓬勃發(fā)展的互聯(lián)網(wǎng)中的信息檢索采用了一種IR風(fēng)格的檢索方式,也就是關(guān)鍵字查詢。但是,這類IR系統(tǒng)也存在兩個(gè)不足:其一,這類IR系統(tǒng)只能提供有限的結(jié)構(gòu)化數(shù)據(jù)查詢能力;其二,這類IR系統(tǒng)通常缺乏查詢優(yōu)化機(jī)制。
　　針對(duì)上述問題,本文從泛函分析的角度提出一種適用于N維p-范數(shù)空間的Top-N查詢算法,該算法不僅能夠彌補(bǔ)現(xiàn)有方法的缺陷與不足,而且能夠解決原有算法不能解決的問題。本文主要工作如下:
　　第一,提出一種新的位

3、于n維實(shí)范數(shù)空間的查詢模型,該模型具有如下特點(diǎn):⑴排序函數(shù)是任意的p-范數(shù)距離,該距離不一定是單調(diào)的;⑵查詢點(diǎn)(即一個(gè)實(shí)數(shù)向量)是任意的;⑶順序訪問可能是雙向的。顯然,TA-like算法不適用于該模型。
　　第二,對(duì)于n維實(shí)范數(shù)空間的一般p-范數(shù),根據(jù)不同的數(shù)據(jù)訪問方式,我們提出了pTA,pTAz和pNRA算法,分別針對(duì)如下三種情況:⑴所有列表同時(shí)支持順序訪問和隨機(jī)訪問;⑵限制順序訪問,即存在列表僅支持隨機(jī)訪問,不支持順序訪問;⑶