面向關系數(shù)據庫的關鍵字近似搜索技術研究.pdf

1、近年來Web數(shù)據大量增長，如何為用戶提供有效的搜索技術成為研究的熱點。在分布式環(huán)境下，通過數(shù)據收集，得到的Web數(shù)據主要存儲在關系數(shù)據庫中，大量來自不同數(shù)據源的Web數(shù)據，具有異構模式。在目前的發(fā)展階段，搜索引擎是支持用戶查詢請求的重要手段。用戶根據興趣，通過搜索引擎接口輸入相關的關鍵字，系統(tǒng)提供快速響應回答用戶的請求。很多情況下，用戶提交的請求不能與數(shù)據庫中的數(shù)據進行精確匹配，例如：用戶對數(shù)據了解的程度有限、錄入的數(shù)據包含錯誤信息、來

2、自多個數(shù)據源的數(shù)據存在不一致性等。因此，在關系數(shù)據庫上有效地支持近似關鍵字搜索帶來了一系列新的挑戰(zhàn)，諸如，面向關系數(shù)據庫的近似查詢處理，字符串近似匹配的執(zhí)行效率和查詢結果的排序等問題。本文針對上述問題進行研究，主要工作包括以下幾點：
　　 (1)為改善對關系元組中字符串數(shù)據的近似查詢效率，提出一種新穎的索引結構，簡稱VGRAM（變長GRAM）。與傳統(tǒng)的解決近似字符串查詢的索引方法相比，VGRAM索引不但節(jié)省了近似查詢算法的時間，

3、并且將索引的空間縮小了1倍以上。同時，該技術具有很好的可移植性，任何一個基于gram思想的近似字符串查詢算法都可以采用該索引技術并提高原有算法的執(zhí)行效率。其主要思想是：在字符串集合中，選擇高質量的變長gram來支持該集合上的查詢。重點研究的問題包括：如何從特定集合中選擇高質量的gram、如何基于預選的gram將字符串分解成一組變長的gram集合，以及分析兩個gram集合間的相似度同它們編輯距離間的關系?；谡鎸崝?shù)據集上大量的實驗測試結果

4、表明，VGRAM索引技術可以顯著地改善最新的三種經典算法的查詢性能。
　　 (2)提出了基于代價的高質量gram選擇技術。當采用基于gram的倒排列表作為索引結構時，索引項gram的選取直接決定索引結構，進而決定近似查詢的執(zhí)行效率。針對gram索引項集和查詢性能間的關系，提出一種計算兩個字符串公共gram數(shù)目的下限的動態(tài)規(guī)劃算法，以提高下限值，從而獲得更快的近似匹配時間。系統(tǒng)地分析gram索引結構對近似匹配性能的影響，并提出一個

5、自動構造高質量gram索引項集的算法。在真實數(shù)據集上的實驗展示了這些技術對查詢性能的改善。就目前所知，這是第一個基于代價分析的gram選擇方法。
　　 (3)針對有限的form查詢接口進行查詢擴展，提出基于form查詢接口的改菩近似搜索能力的查詢重寫技術。很多近似搜索引擎為用戶提供form接口，用戶通過form接口提交關鍵字并獲得搜索結果。返回給用戶的結果大多數(shù)是根據填寫在查詢接口中不同值域內的關鍵字計算得到的，導致查詢結果的查

6、全率(recall)很低。本文提出一種數(shù)據挖掘方法，通過對歷史查詢及其結果進行挖掘分析，得到一組查詢重寫知識，包括數(shù)據項樹和推理規(guī)則。利用這些重寫知識，可以對用戶查詢進行擴展，以提高基于form的近似搜索能力，特別是查全率。從不同Web網站上隨機選取的3,800篇文檔組成的測試集上的實驗結果表明：所提出的數(shù)據挖掘和查詢重寫方法獲得的平均查準率和查全率均高于80％，而假通過率低于2.0％。
　　 (4)針對關系數(shù)據表之間以及元組間

7、的數(shù)據依賴關系，提出一種支持關系數(shù)據庫的關鍵字近似搜索的語義評價模型，包括語義相關度計算和語義評分函數(shù)。基于提出的語義評分函數(shù)，提出兩種以數(shù)據塊為處理單位的Top-k搜索算法，分別為BA(Blocking Algorithm)算法和EBA(Early-stopping Blocking Algorithm)算法。EBA在BA基礎上引入了過濾閾值以便盡早終止算法的迭代過程。實驗結果顯示所提出的語義評分函數(shù)保證了搜索結果的高查準率和查全率，