基于位置感知的top-k文本檢索混合索引框架研究

李夢(mèng)雪

摘 ?要：在移動(dòng)Web搜索中人們希望搜索到的目標(biāo)對(duì)象既滿足地理位置相近性，又滿足描述文檔相關(guān)性。由此產(chǎn)生的地理位置和文檔相融合的top-k查詢既考慮位置鄰近性又考慮文本相關(guān)性。文章介紹的基于位置感知的top-k文本檢索索引，利用倒排文件進(jìn)行文本檢索，R-tree進(jìn)行空間相近性查詢。因此考慮了文本相關(guān)性和位置鄰近性，并且能夠獲得top-k查詢結(jié)果。

關(guān)鍵詞：位置感知;top-k;IR-tree;倒排文件

中圖分類號(hào)：TP391 ? ? ? ? 文獻(xiàn)標(biāo)志碼：A ? ? ? ? 文章編號(hào)：2095-2945（2020）19-0010-03

Abstract： In mobile Web search， the target object that people want to search not only satisfies the proximity of geographical location， but also satisfies the relevance of description documents. The resulting top-k query which combines geographic location and document considers both location proximity and text relevance. The location-aware top-k text retrieval index introduced in this paper uses inverted files for text retrieval and R-tree for spatial proximity query. Therefore， text relevance and location proximity are considered， and top-k query results can be obtained.

Keywords： location awareness; top-k; IR-tree; inverted file

前言

移動(dòng)Web搜索技術(shù)的興起在一定程度上推動(dòng)傳統(tǒng)互聯(lián)網(wǎng)獲取地理空間維度。地理位置和文檔的融合使查詢能夠同時(shí)考慮位置鄰近性和文本相關(guān)性。當(dāng)今，絕大多數(shù)的商業(yè)搜索引擎提供基于位置的服務(wù)，比如地圖服務(wù)、本地搜索和本地廣告服務(wù)等。

本文介紹的一種新的top-k查詢，考慮了與關(guān)聯(lián)對(duì)象的位置鄰近性和文本相關(guān)性。該查詢的結(jié)果是根據(jù)排序函數(shù)排列的k個(gè)對(duì)象列表，這些對(duì)象與查詢位置的距離最近且文本描述與查詢短語(yǔ)最相關(guān)，這種類型的查詢稱為位置感知的top-k文本檢索（簡(jiǎn)稱LkT）查詢。

1 內(nèi)容簡(jiǎn)介

本文主要介紹了以下兩方面內(nèi)容：（1）一種索引框架，用于處理基于位置感知的top-k文本檢索（LkT）查詢。該框架集成了用于文本檢索的倒排文件和用于空間相近性查詢的R-tree。（2）基于框架，介紹了一種稱為IR-tree的索引方法，它本質(zhì)上是一個(gè)擴(kuò)展了倒排文件的R-tree。

2 問題描述

設(shè)D是空間數(shù)據(jù)庫(kù)。D中的每一個(gè)空間對(duì)象定義為一組數(shù)對(duì)（O.loc，O.doc），其中O.loc是多維空間的位置描述符，O.doc是對(duì)象的描述文檔。文檔O.doc由一個(gè)向量表示，其中每個(gè)維度對(duì)應(yīng)于文檔中的一個(gè)不同的項(xiàng)。向量中的項(xiàng)的值由語(yǔ)言模型[1]計(jì)算，如下：

其中tf（t，O.doc）表示的是t項(xiàng)在文檔中出現(xiàn)的次數(shù)，tf（t，Coll）是t項(xiàng)在空間數(shù)據(jù)庫(kù)D的文檔集合Coll中的計(jì)數(shù);tf（t，O.doc）/O.doc是t項(xiàng)在文檔O.doc中的極大相似估計(jì)值，tf（t，Coll）/Coll是t項(xiàng)在集合Coll中的極大相似估計(jì)值，是Jelinek-Mercer平滑方法的一個(gè)平滑參數(shù)。為了便于理解，tf（t，O.doc）用代表本文運(yùn)行的例子中t項(xiàng)的權(quán)重。

一個(gè)位置感知的top-k文本檢索（LkT）查詢?yōu)榻o定的查詢Q在數(shù)據(jù)庫(kù)D中檢索k個(gè)對(duì)象，以便它們的位置與Q中指定的位置最接近，它們的文本描述與Q中的關(guān)鍵字最相關(guān)。

在形式上給定一個(gè)查詢Q=（loc，keywords），其中Q.loc是位置描述符，Q.keywords是關(guān)鍵字集合，返回的對(duì)象根據(jù)排名函數(shù)f（D，P（Q.keywords|O.doc））進(jìn)行排序，其中D是Q和O之間的歐幾里得距離，P（Q.keywords|O.doc）是從文檔的語(yǔ)言模型產(chǎn)生查詢Q.keywords的概率。根據(jù)此排名函數(shù)計(jì)算出k個(gè)對(duì)象的排序列表能高效地應(yīng)答LkT查詢。其中如下：

本文中排名函數(shù)為查詢Q中對(duì)對(duì)象O進(jìn)行排序的歸一化因子的線性插值[2]：

其中∈（0，1）是用來(lái)平衡空間鄰近性和文本相關(guān)性的參數(shù);Q和O之間的歐幾里得距離D（Q.loc，O.loc）由maxD歸一化，maxD可為D中兩個(gè)對(duì)象之間的最大距離;使用maxP將概率分評(píng)分歸一化到（0，1）的范圍，maxP計(jì)算方法為：

使用每個(gè)單詞的最大語(yǔ)言模型來(lái)計(jì)算概率值的上限。排名函數(shù)計(jì)算的分?jǐn)?shù)越低越好。等式（3）中的允許用戶在查詢時(shí)設(shè)置文本相關(guān)性和位置接近性之間的權(quán)重。

在圖1中描述了8個(gè)空間對(duì)象O1...O8，等式（4）顯示了八個(gè)對(duì)象的文檔和詞匯的關(guān)系矩陣M。在矩陣中，行和列分別表示詞匯和文檔。例如，矩陣顯示了文檔O1.doc包含了“Chineses”詞匯5次和“restaurant”這個(gè)詞5次。

給定一個(gè)具有位置信息Q.loc的查詢Q，如圖1所示，Q.keywords=（Chinese restaurant），對(duì)象O1是根據(jù)公式（4）（=0.3）得到的top-1查詢的結(jié)果。

3 現(xiàn)有方案處理LkT查詢

僅倒排文件（IFO）和R-tree+倒排文件（RIF）兩種方案。

3.1 僅倒排文件（IFO）

其思想是利用倒排文件對(duì)所有對(duì)象的文本相關(guān)度得分（對(duì)應(yīng)于公式（3）中運(yùn)算符“+”的右操作數(shù)）進(jìn)行計(jì)算，獲得一個(gè)排序列表，按分?jǐn)?shù)的升序排列。然后掃描列表，計(jì)算查詢的空間接近程度，直到進(jìn)一步掃描不會(huì)生成top-k結(jié)果。該算法只使用倒排文件。

該方案需要解決的問題是何時(shí)停止掃描。在掃描過(guò)程中，該算法保持對(duì)組合排序分?jǐn)?shù)的跟蹤（在公式（3）中定義，分?jǐn)?shù)越低越好）。當(dāng)前第k個(gè)對(duì)象的排序分?jǐn)?shù)用閾值來(lái)表示，對(duì)于一個(gè)新對(duì)象T，如果它的倒排序分值大于閾值，算法將會(huì)停止，因?yàn)門之后所有對(duì)象在倒排序列中的得分將會(huì)超過(guò)閾值的分?jǐn)?shù);否則，繼續(xù)檢索，計(jì)算新的排序分?jǐn)?shù)，并與閾值進(jìn)行比較，確定閾值是否需要更新。

3.2 R-tree+倒排文件（RIF）

該算法分兩個(gè)階段使用R-tree和倒排文件。倒排文件用于計(jì)算IFO的列表不排序。然后使用R-tree遞增地查找最近的鄰接節(jié)點(diǎn)[3]，并檢查無(wú)序排序中對(duì)象的文本相關(guān)性分?jǐn)?shù)。

在此過(guò)程中，算法對(duì)倒排序列中最小的文本相關(guān)度分?jǐn)?shù)（MinTR）進(jìn)行跟蹤，對(duì)當(dāng)前第k個(gè)對(duì)象的組合排序分?jǐn)?shù)（公式（3））進(jìn)行跟蹤，用閾值表示。

對(duì)于空間距離為dist的新對(duì)象，如果從dist和當(dāng)前 MinTR計(jì)算的組合分?jǐn)?shù)超過(guò)閾值，算法停止，因?yàn)樗ＷC所有“未見”對(duì)象的分?jǐn)?shù)不會(huì)低于當(dāng)前第k個(gè)對(duì)象。

4 基于位置感知的top-k文本檢索混合索引框架（IR-tree）

該框架將R-tree和倒排文件集成到一個(gè)新的索引中，即倒排文件R-tree（IR-tree），其中包括一個(gè)使用IR-tree處理LkT查詢的算法。

R-tree[4]是空間查詢的主要索引，而倒排文件是文本信息檢索[5]的最有效索引。它們是被分別開發(fā)的，用于不同類型的查詢。

利用這兩個(gè)技術(shù)來(lái)開發(fā)一種有效處理LkT查詢的方法。要實(shí)現(xiàn)這個(gè)目標(biāo)，一種簡(jiǎn)單的方法是使用倒排文件生成許多基于文本相關(guān)性的候選對(duì)象，然后使用其他索引計(jì)算候選對(duì)象的空間距離。但是，這種方法效率并不好，因?yàn)闆]有一種合理的方法來(lái)確定第一步所需的候選對(duì)象數(shù)量，以確保最后找到top-k對(duì)象。IR-tree混合索引結(jié)構(gòu)，以一種組合的方式使用這兩種索引結(jié)構(gòu)。

IR-tree混合索引：

IR-tree本質(zhì)上是一個(gè)R-tree，其中的每個(gè)節(jié)點(diǎn)都通過(guò)位于節(jié)點(diǎn)的子樹中包含的對(duì)象的倒排文件進(jìn)行充實(shí)。在IR-tree中，葉子節(jié)點(diǎn)N包含若干個(gè)（O，rectangle，O.di）形式的記錄，其中O是指數(shù)據(jù)庫(kù)D中一個(gè)對(duì)象，rectangle是對(duì)象O的邊界矩形，O.di是對(duì)象O的文檔標(biāo)識(shí)符。葉子節(jié)點(diǎn)也包含一個(gè)指向被索引對(duì)象的文本文檔的倒排文件的指針。

（1）倒排文件

倒排文件由兩部分組成。

a.在文檔集合中所有不同術(shù)語(yǔ)的詞匯表。

b.一組發(fā)布列表，每一個(gè)都與術(shù)語(yǔ)t相關(guān)。每個(gè)發(fā)布列表都是一系列的數(shù)對(duì)，其中d為包含項(xiàng)t的文檔，wd，t為文檔d中項(xiàng)t的權(quán)值。

非葉節(jié)點(diǎn)R包含表單（cp， rectangle， cp.di）的若干記錄，其中cp是R的子節(jié)點(diǎn)的地址，rectangle是子節(jié)點(diǎn)記錄中所有矩形的最小邊界矩形，cp.di是偽文檔標(biāo)識(shí)符。

偽文檔是混合索引結(jié)構(gòu)中的一個(gè)重要概念。它代表所有子節(jié)點(diǎn)記錄中的所有文件，使我們能夠評(píng)估一個(gè)根植于cp的子樹所包含的所有文檔的文本相關(guān)性查詢的范圍。被cp.di 引用的每一個(gè)偽文檔中的t的權(quán)值是根植于cp的子樹所包含的文檔相應(yīng)權(quán)值的最大值。

（2）IR-tree混合索引實(shí)例

圖2演示了圖1中8個(gè)對(duì)象的混合索引。表1顯示了葉節(jié)點(diǎn)的倒排文件（圖2中的InvFile 4、InvFile 5、InvFile 6和InvFile 7）。表2顯示的是非葉節(jié)點(diǎn)的倒排文件內(nèi)容（如圖2所示的InvFile1，InvFile2，InvFile3）。例如restaurant一詞在節(jié)點(diǎn)R5的記錄R2中的權(quán)值是7，這是這個(gè)詞在節(jié)點(diǎn)R2三個(gè)文檔（O3，O4，O8）中的最大的權(quán)值。

（3）最小空間-文本距離MINDST

最小空間-文本距離MINDST是用于查詢處理的重要度量。在混合索引中給定一個(gè)查詢Q和節(jié)點(diǎn)N，度量MINDST在查詢Q和位于節(jié)點(diǎn)N的矩形內(nèi)的對(duì)象之間給實(shí)際空間-文本距離提供了一個(gè)下限值。該邊界值可用于排序和有效地修剪混合索引中的搜索空間路徑。

定義1.混合索引中查詢點(diǎn)Q與節(jié)點(diǎn)N的距離，表示為MINDST（Q，N），定義如下：

其中，maxD和maxP與公式（3）中的是一樣的;

在公式（2）中把O.doc替換為N.doc（節(jié)點(diǎn)N的偽文檔）可以計(jì)算出P（Q.keywords|N.doc）; MIND（Q.loc，N.rectangle）是Q.loc和N.rectangle之間的最小歐幾里得距離。

提出的混合索引結(jié)構(gòu)的一個(gè)顯著特征是，在查詢處理方面繼承了R-tree的良好屬性。

定理3.1：給定一個(gè)查詢點(diǎn)Q和一個(gè)節(jié)點(diǎn)N，其矩形包含一組對(duì)象SO={Oi，1im}，則下面的式子成立：

證明：由于對(duì)象O包含在節(jié)點(diǎn)N的矩形中，所以Q.loc和N.rectangle之間的最小歐幾里得距離不大于Q.loc和O.loc之間的歐幾里得距離：

對(duì)每一項(xiàng)t，N.doc.t（在N.doc中的項(xiàng)的權(quán)值，它是節(jié)點(diǎn)N的偽文檔）是節(jié)點(diǎn)N中所有文檔的值中的最大值。因此：

根據(jù)等式（3）和（5）可以得到：MINDST（Q，N）DST（Q，O），因此完成了證明。

當(dāng)搜索與查詢Q最接近的k個(gè)對(duì)象的混合索引時(shí)，必須在混合索引的每個(gè)訪問節(jié)點(diǎn)上決定首先搜索哪個(gè)記錄。度量MINDST提供了到節(jié)點(diǎn)中每個(gè)記錄的距離近似值，因此可以用于指導(dǎo)搜索。只有在查詢Q中的關(guān)鍵字的發(fā)布列表，而不是所有的發(fā)布列表，才被加載到節(jié)點(diǎn)的內(nèi)存中加以計(jì)算MINDST。

5 結(jié)束語(yǔ)

本文中用于處理LkT查詢的IR-tree混合索引框架集成了傳統(tǒng)的R-tree和倒排文件，R-tree是空間查詢的主要索引，倒排文件是文本檢索最有效索引。同時(shí)利用MINDST度量對(duì)空間文本距離進(jìn)行剪枝，最終得到符合條件的top-k結(jié)果。以此為依托可以進(jìn)一步開發(fā)剪枝算法來(lái)優(yōu)化查詢結(jié)果。

參考文獻(xiàn)：

[1]J.M.Ponte and W.B.Croft. A language modeling approach to information retrieval.In SIGIR，1998：275-281.

[2]B.Martins，M.J.Silva， and L.Andrade.Indexing and ranking in geo-IR systems.In GIR，2005：31-34.

[3]G.R.Hjaltason and H.Samet.Distance browsing in spatial databases. ACM Trans.Database Syst.1999，24（2）：265-318.

[4]A.Guttman.R-trees： a dynamic index structure for spatial searching.In SIGMOD，1984：47-57.

[5]J.Zobel and A.Moffat. Inverted fifiles for text search engines.ACM Comput.Surv.2006，38（2）：56.