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

李夢雪

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

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

中圖分類號：TP391 ? ? ? ? 文獻標志碼：A ? ? ? ? 文章編號：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

前言

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

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

1 內(nèi)容簡介

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

2 問題描述

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

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

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

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

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

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

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

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

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

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

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

3.1 僅倒排文件（IFO）

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

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

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

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

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

對于空間距離為dist的新對象，如果從dist和當前 MinTR計算的組合分數(shù)超過閾值，算法停止，因為它保證所有“未見”對象的分數(shù)不會低于當前第k個對象。

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

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

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

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

IR-tree混合索引：

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

（1）倒排文件

倒排文件由兩部分組成。

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

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

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

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

（2）IR-tree混合索引實例

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

參考文獻：

[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.