基于容忍因子的近似最近鄰混合查詢算法

賀廣福，薛源海，陳翠婷，俞曉明，劉欣然,3，程學旗

1. 中國科學院計算技術研究所，北京 100190；2. 中國科學院大學，北京 101408；3. 北京郵電大學，北京 100876

0 引言

近年，近似最近鄰搜索（approximate nearest neighbor search，ANNS）已經在圖像搜索[1-3]、信息推薦[3-4]、序列匹配[5]、大語言模型應用[6]等領域成為一個重點研究課題?；诮平張D的ANNS算法在處理大規模高維數據搜索時顯示出較高的搜索效率和準確性[7]。隨著人們對高精度信息檢索的需求不斷增長，同時使用結構化信息和非結構化信息進行混合查詢（hybrid query）的方式也得到了廣泛應用。例如在電商的商品搜索中，可能需要依據圖片這類非結構信息和生產日期、價格、銷量等結構化信息進行混合查詢，精確地搜索相關產品。然而，ANNS主要關注非結構化信息，對結構化信息的影響關注較少，這導致ANNS在滿足結構化約束信息檢索需求方面的表現并不理想。

為了解決這類問題，研究者們在相關領域提出的混合查詢方法一般可以分為3類[8]，即前處理（pre-process）、后處理（post-process）和內聯處理（inlineprocessing）。其中前處理需要大量的時間和空間來構建數據結構[9-10]；后處理需要對檢索的結果進行修正，存在一定的誤差和不確定性[11]；內聯處理方法可以直接在查詢過程中進行最近鄰的計算，具有高效、準確的特點，尤其是對實時性要求較高的應用場景[12-14]。

在非結構化信息檢索中，基于近鄰圖類的ANNS算法在高維度、大規模數據集上表現優異，因此擴展此類方法的內聯處理混合查詢具有較好的應用前景，是ANNS領域的重要研究分支?；诮張D的內聯混合查詢中，一般使用貪心過濾搜索（filtered greedy search，FGS）算法在近似近鄰圖上檢索路由[8,12,15]。但是，該方法在查詢時僅依據滿足結構化約束的點進行路由，降低了ANNS在構建索引時近鄰圖的連通性預期，導致檢索結果的精確度下降。

針對上述挑戰，本文提出了一種基于容忍因子的過濾貪心搜索（tolerance factor based filtered greedy search，TF-FGS）算法。TF-FGS算法通過引入容忍因子，在不改變索引結構的前提下保留近鄰圖的連通性，從而解決由于結構化約束對搜索算法造成的影響，提升了結果準確率。同時，TF-FGS算法保留了與沒有結構化約束的ANNS近似的搜索效率。實驗表明，在混合查詢場景中，本文提出的方法在不犧牲檢索效率的前提下，有更好的搜索準確率。

本文的主要貢獻如下。

● 分析了FGS算法存在的問題。在搜索過程中，路由候選集合所有向量必須滿足結構化約束，過度約束了可路由的路徑，影響了路由過程中近鄰圖的連通性，導致搜索準確率下降。

● 提出了一種TF-FGS算法，在不改變索引結構的條件下，允許不滿足結構化約束的向量參與路由，在維持原有檢索效率的同時，提升了檢索結果的準確率。

● 在不同類型的基準數據集上進行了實驗，驗證本文提出的TF-FGS算法相比FGS算法，在保持查詢效率不變的情況下，提高了混合查詢的準確率。

1 問題定義

本節定義了最近鄰搜索、近似最近鄰搜索、混合場景下的近似最近鄰問題。

1.1 最近鄰搜索和近似最近鄰搜索

在實際應用中，需要在高維數據集中進行最近鄰搜索。但是，高維數據距離計算開銷很大，精確搜索的查詢效率很低，無法滿足實際需求。因此，一般設計近似最近鄰搜索算法來解決最近鄰搜索問題。ANNS算法的目標是最大化為：

高效地召回擁有k個向量的C集合，其中，G表示在P中距離xq最近的k個向量。

1.2 結構化約束

在數據集P中，向量x∈P包含了若干屬性或者標簽Fx ?F，其中F表示向量上有限個標簽或者屬性。結構化約束條件為C=φ( Fx )，定義為由向量的屬性或標簽F構成的邏輯關系表，值為True（滿足約束）或False（不滿足約束）。結構化約束按照約束條件的不同，一般分為等值約束、多值約束和區間約束。

經過結構化約束后的向量集合為PC，其滿足：

不滿足結構化約束的向量集合為：

可以使用不滿足結構化約束的向量比例來表示結構化約束強度：

1.3 帶結構化約束的近似最近鄰搜索

給定查詢條件為目標向量xq，最近鄰結果個數為k，結構化約束為C，帶結構化約束的近似最近鄰搜索需要從PC中查詢距離xq近似最近的前k個向量。此時算法目標precision@k中的G為在PC中距離xq最近的k個向量。

2 相關工作

在ANNS算法上擴展結構化數據過濾是解決混合查詢的重要方法。按照結構化約束相對向量檢索召回的先后順序，可將這些算法分為后處理、前處理和內聯處理。其中基于近鄰圖索引結合過濾貪心搜索算法的內聯混合查詢（inline hybrid query）表現出較好的檢索效率和較低的額外開銷。

2.1 后處理類混合查詢方法

最直接的方法是后處理類的混合查詢方法：在查詢時，先執行非結構化查詢，然后應用非結構化約束信息來過濾非結構化查詢召回的數據。例如，京東的Vearch[11]首先通過ANNS獲取滿足非結構化約束的候選集，然后在候選集上執行標簽過濾，得到最終結果。這種方法很容易在原來的方法上擴展實現。但是，由于結構化約束是用戶輸入的查詢條件，非結構化查詢階段召回的數據中是否有滿足過濾條件的向量具有較大的不確定性，特別是對于嚴苛的過濾條件，會導致滿足約束的向量很少，可能必須召回大量候選向量才能在后處理時召回期望的查詢結果。

2.2 前處理類混合查詢方法

與后處理的混合查詢方法相反，有些研究者提出了前處理方法：用結構化約束屬性構建額外的索引，召回滿足過濾條件的向量，然后再使用原來的ANNS方法查詢非結構數據。構建額外的索引結構往往需要高昂的計算或者存儲代價。

Xu等人[18]提出的MA-NSW算法為每個屬性構建一個近鄰子圖，形成一個多層次的索引結構，在執行查詢時，先通過導航樹映射到滿足結構化約束的近鄰子圖，再在子圖上執行ANNS獲取滿足結構化約束的混合查詢結構。MA-NSW算法實現了高效的混合查詢，但是在結構化屬性比較多的情況下，其樸素地為每一條結構化數據組合構建子圖的方式將導致巨大的時空構建復雜度，從而難以普及應用。Weaviate[10]和Milvus[9]均在原來的ANNS查詢前，通過結構化約束過濾出符合條件的向量列表（approval list），而在非結構化查詢時，僅考慮此列表中的向量。此向量列表在大規模檢索中需要較大的額外內存開銷。

2.3 內聯處理類混合查詢方法

有些算法可以在原來非結構查詢的過程中動態地應用后處理方法，被稱為內聯處理方法。此類方法中的典型代表是FAISS-IVF[12]，它將向量索引和結構化約束屬性同時進行倒排索引，在查詢時同時篩選結構化和非結構化信息。Pinecone的混合搜索也利用該方法[13]。后續也有一些研究者提出了基于樹和基于量化方法的混合查詢方法，例如王夢召等[14]提出的NHQ方法。

2.4 基于近鄰圖的混合查詢方法

在非結構化查詢場景下，基于哈希的方法使用哈希函數將數據點映射到哈希桶中，從而實現近似最近鄰搜索。哈希函數具有高效的查詢速度，尤其適用于高維數據，但是哈希方法存在哈希沖突問題，即不同的數據點可能映射到相同的哈希桶中，導致查詢結果不準確?；跇浣Y構的方法，例如R-Tree[19]、KD-Tree[20-21]和Ball-Tree[20,22]，通過遞歸地劃分數據空間，可以快速定位最近鄰，同時還可以有效地剪枝，減少搜索空間。但是在高維數據場景中，樹結構很容易變得不平衡，導致搜索效率下降。

但是，基于近鄰圖的索引，如HNSW[23]、NSG[24]、SSG[25]和Vamana[15]，在針對特定召回率時，與KD-Tree、IVF、LSH等索引相比，效率提高了一個數量級[7]，而且隨著數據規模的增加，這種差距只會更大。因此，擴展基于近鄰圖的ANNS索引支持混合查詢，可以實現更高吞吐量和更優召回率。

前人的研究大多使用過濾貪心搜索算法來擴展基于近鄰圖的混合查詢。如Jayaram 等人[15]提出的Disk ANN 和Gollapudi 等人[8]提出的Filtered Disk ANN，均使用過濾貪心搜索算法實現混合查詢。該方法會在搜索時依據結構化約束條件進行剪枝，可以快速收斂檢索結果，具有優秀的檢索性能。但是，這樣做會破壞最近鄰圖的連通性假設，有一定的副作用。例如在過于嚴苛的結構化條件約束下，符合條件約束的向量很少，在路由時，要么無法到達最近鄰，要么到達最近鄰需要進行更多跳的搜索。

本文提出的算法在不改變索引結構的條件下，通過控制容忍因子來調節點參與路由的比例，緩解結構化約束條件對近鄰圖連通性的影響，從而解決過濾貪心搜索算法的結構化約束問題。

3 過濾貪心搜索算法問題分析

本節首先進行了基于近鄰圖索引和過濾貪心搜索算法的混合查詢實驗。實驗表明，大多數場景下，過濾貪心搜索算法有較高的檢索準確率；但是在結構化約束條件過強時，可能會出現檢索準確率下降的問題。然而，強結構化約束條件下的混合查詢是重要的應用場景之一，為了進一步提升用戶搜索體驗，亟須解決該問題。本文從過濾貪心搜索算法的原理出發，分析了該問題的原因。

3.1 FGS混合查詢實驗

本文使用了基準數據集GloVe[26]中的GloVe.6B.50d進行實驗，該數據集包含了來自維基百科2014和Gigaword5的400 000個詞匯及其對應的向量。但是該數據集缺少數據屬性或者標簽F，本文隨機生成了用于結構化約束的屬性，并從數據集中隨機選擇了10 000條數據進行實驗。

圖1 頂點的度分布與約束條件強度的關系（縱坐標將頂點的度分為10 個區間，統計每個區間的頂點個數）

圖2 檢索精確度與約束條件強度Q 的關系

從上述實驗中可以得到以下結論。

● FGS算法在多數場景下能保證檢索精確度。但是，在結構化約束強度Q過大時，檢索準確率較低。特別是在極端情況下，檢索準確率趨于0。

● 結構化約束強度Q與近鄰圖聯通性成反相關。結構化約束強度Q越大，則搜索路由時索引的連通性越弱；反之，索引的連通性越強。

● 近鄰圖的連通性對FGS算法檢索精確度有決定性的影響。當近鄰圖的連通性較高時，檢索精確度較高；反之，精確度較低，并趨向于0。因此改進檢索路由中的連通性，可以提升檢索結果的精確度。

3.2 FGS算法原理

FGS算法的基本思想是從初始查詢向量集合ep出發，執行深度優先的貪心路由策略，不斷地逼近查詢向量xp并記錄遍歷過的向量，從滿足約束條件的已知向量中選擇與xp距離最近的前k個作為檢索結果，其詳細過程如算法1所示。

算法1：FGS.過濾貪心搜索算法.

輸入：近鄰圖G，導航向量集合ep，查詢向量xq，路由候選集合大小ef，結構化約束條件c

輸出： L 包含了k個xq的近似最近鄰；V 包含了所有訪問過的向量信息

其中， dist(xp,xq)表示間距離度量的方法，例如歐氏距離、余弦距離等；N(G,p)表示在近鄰圖索引G中獲取向量p的鄰居列表；chooseNNearest( L,xq,k)表示從候選集合中獲取距xq最近的前k個向量。

在某一跳的搜索過程中，從當前跳的起始位置出發，將起始向量的鄰居中符合結構化約束的向量記錄到候選集合中。例如圖3（a）中，假設當前跳為關鍵路徑上的0號向量，那么本跳搜索過程中會將所有符合結構化約束的向量均標記為1（下一跳的序號），這些標記為1的向量會加入候選集合中。

圖3 FGS 和TF-FGS 路由路徑選擇策略對比（圖中向量為隨機生成的二維向量，橫縱坐標為向量的值，取值范圍均為[0, 1]）

遍歷完關鍵路徑上某個向量的所有鄰居后，依據與xq的距離壓縮候選集合，選擇距離xq最近的且未訪問過的向量作為下一跳起始位置。如圖3（a）中關鍵路徑上的1號向量即為下一跳的起始位置。

循環執行上述步驟，直到遍歷完所有候選集合的向量。最后，將候選集合中距離xq最近的前k個向量作為結果輸出。

3.3 FGS算法問題分析

從上述算法流程中可以看出，候選集合在FGS算法中有兩個重要用途：緩存可能的下一跳起始位置和緩存檢索結果。在搜索過程中，由于FGS算法將兩種功能均通過候選集合體現，候選集合在緩存下一跳候選位置時必須執行結構化約束條件，以滿足緩存檢索結果的目的，所以候選集合僅能增加滿足x∈CP的向量。因此，每一跳的候選向量均需要滿足結構化約束。這會導致路由時近鄰圖的部分頂點不可達，索引的連通性下降。極端情況下，近鄰圖會形成多個不連通的子圖，容易產生檢索的局部性問題，從而降低檢索結果的精確度。如圖3（a）描述的場景中，由于候選集合僅包含向量x∈CP，導致搜索時僅能通過近鄰圖的少部分邊路由，容易陷入檢索的局部區域，致使無法召回最近鄰向量。圖3中，近鄰圖m=16 ，ef =5 ，由30個向量構成，每個向量xi∈[ 0,1]2(1≤i≤30)。五角星表示xq；紅色點屬于CP，滿足結構化約束，藍色方塊表示不滿足；黑色三角符號表示路由探索過的向量；黑色連線表示路由關鍵路徑，點右上角的數字表示路由跳數，從0開始計數。

4 基于容忍因子的過濾貪心搜索算法

基于上述思路，TF-FGS算法在FGS算法的基礎上將候選集合L 拆分為路由候選集合 ′L （為了避免歧義，用 ′L 表示TFFGS的候選集合，包含了服從容忍因子α個數約束且滿足的點）和結果候選集合R ，在搜索路由過程中采取不同的策略進行迭代更新，詳細過程見算法2和算法3。

算法2: TF-FGS. 基于容忍因子過濾貪心搜索算法.

輸入：近鄰圖G；導航點集合ep；查詢向量xq,路由候選集合大小ef；結構化約束條件c；容忍因子α

輸出：R 包含k個近似最近鄰點；V包含所有訪問過的節點

算法3: choose N Nearest With Tolerence. 改進的候選集合壓縮算法

輸入：候選集合 L′ ；查詢向量xq，路由候選集合大小ef；結構化約束條件c；不滿足結構化約束條件的容忍因子α

輸出：S 包含了ef 個距離xq的最近鄰，且滿足容忍因子α約束；

4.1 候選集合迭代更新策略

TF-FGS算法在每次路由迭代中，路由候選集合 ′L 會考慮所有新發現的點，然后使用基于容忍因子的n最近鄰算法（choose N Nearest With Tolerence）進行壓縮。與FGS算法不同的是，候選集合在壓縮時會依據容忍因子α選擇一定比例的滿足x∈·PC的向量。

當α=0 時，壓縮路由候選集合不會保留不滿足結構化約束的點，等同于FGS算法；當0＜α≤1時，壓縮路由候選集合會盡可能以比例α保留不滿足結構化約束的點。

在路由過程中，按照容忍因子α(0≤α≤1)來壓縮候選集合 ′L 。候選集合′L 按照與xq的距離升序排序，壓縮后的集合依次從排序集合中選擇候選點，直到集齊ef 個點；在選擇過程中，如果且，則忽略該點。因此最多可以有α×ef 個不滿足結構化約束條件的點參與路由。m)≈O(elogN)。特別地，當結構化約束評估的時間復雜度為O(e) ?O(1)時，FGS的時間復雜度為O(logN)。

FGS的空間復雜度由候選集合和訪問點集合兩部分構成。其中，候選集合空間復雜度為O(ef) =O(1)；訪問點集合最差的空間復雜度為O(N)，平均復雜度為O(h·m) =O(mlogN/m) ≈O(logN)。綜上所述，FGS的空間復雜度最差為O(N) ，平均復雜度為O(logN) 。

4.2 結果候選結合迭代更新策略

結果候選集合R 每次路由迭代增加滿足x∈CP的點，壓縮時直接選擇距離查詢點xq最近的前k個，迭代結束后作為結果返回。長度為k的結果集合R 記錄了搜索的最終結果，結果集合在增加元素時執行結構化約束條件。

5 復雜度分析

5.1 FGS算法的復雜度分析

FGS算法的時間復雜度由搜索過程中檢查的平均頂點個數、候選集合篩選、結構化約束計算3個部分組成。

假設圖索引中，頂點的最大度為m，結構化約束評估的時間復雜度為O(e) 。每次查詢平均會檢查O(h·o) 個向量，其中h表示平均每次查詢的路由跳數，期望值為logN/m；o(o≤m)表示每跳需要檢查的平均鄰居個數，期望值為m。篩選候選集合的時間復雜度取決于不同的實現方法，使用最大堆進行篩選，單個向量篩選的時間復雜度為 O (ef ·logef)。綜上所述，由于在大規模查詢場景下，m和ef 遠小于N，FGS的時間復雜度為

5.2 TF-FGS算法的復雜度分析

TF-FGS算法在FGS算法的基礎上改變了候選集合篩選的時間復雜度，增加了結果集合操作時間復雜度。

假設原始候選集合包含ef個元素，TF-FGS算法在實現候選集合篩選時，平均每跳增加元素o個，那么候選集合篩選的時間復雜度為 O (ef ·log(ef+o))。平均每跳增加元素o個，滿足結構化約束條件的點一般少于或等于o個，那么結果集合操作的時間復雜度為O(logo) 。綜上所述，由于在大規模查詢場景下，m和ef遠小于N，TF-FGS算法的時間復雜度為特別地，當結構化約束評估的時間復雜度為O(e) ?O(1)時，FGS的時間復雜度為O(logN) 。因此TF-FGS算法引入容忍因子后，時間復雜度與FGS算法在同一級別。

TF-FGS算法在FGS算法的基礎上增加了結果集合存儲，該部分的空間復雜度為O(k) ，為常量開銷。因此，TF-FGS算法的平均空間復雜度仍為O(logN) ，最差為O(N) 。

6 實驗與分析

本文對比了FGS算法和TF-FGS算法兩種搜索算法混合查詢時在不同索引、不同數據集上的性能表現，以驗證本文提出的TF-FGS算法的有效性。本文使用了3個公開數據集（GloVe.6B[26]、SIFT1M[29]和Deep1B[30]），并評估了本算法在數據上的準確率和查詢時間。通過實驗，旨在找到一種支持混合查詢的近鄰圖搜索算法，以滿足實際的應用需求。

6.1 實驗設置

本文選用了多樣化的ANNS 基準數據集進行實驗，包括GloVe.6B[26]、SIFT1M[29]和Deep1B[30]，數據集的詳細說明見表1。這些數據集在數據維度、向量來源類型等方面具有顯著差異，從而使實驗結果具有較強的代表性和普適性。

表1 數據集說明

GloVe.6B數據集來源于自然語言處理領域，它是一種基于全局詞向量表示的方法，用于捕捉詞匯之間的語義關系。SIFT1M數據集則是一個常用的計算機視覺數據集，包含了大量局部特征描述符，有助于理解圖像內容。Deep1B數據集來自深度學習領域，包含了海量的特征向量，用于描述復雜的數據結構。多元化的數據來源有助于確保實驗結果具有廣泛的普適性，從而為計算機信息檢索領域提供有價值的參考。

由于上述數據集中無結構化約束屬性，本文遵循前人的研究工作經驗[8,14]，對數據集模擬改造，模擬混合查詢場景數據。具體地，利用隨機數合成約束屬性，隨機數可以使用式（7）計算：

其中，U是一個取值在[ 0,1] 區間上的均勻分布隨機變量；N表示數據集的大??；表示向下取整函數。

本文中與檢索路由相關的參數主要有候選集合大小ef、容忍因子α。其中ef的取值為4、8、16、32、64；a取值為0、3、6、10。

本文使用了兩個主要的評估指標，分別是檢索精度和檢索效率。

對于檢索精度，本文使用precision@k作為評估指標。在每個數據集上，對于不同的實驗參數，選擇隨機的點作為查詢向量。每次將算法返回的前k個結果作為檢索結果，其中k的值為1、3、10。對于檢索效率，本文使用檢索時間作為評估指標。

6.2 TF-FGS算法與FGS算法效果對比

表2 TF-FGS 算法與FGS 算法搜索效果對比

從表2可觀察出，在所有數據集中，使用TF-FGS算法比FGS算法在相同的結構化約束強度下均有明顯提高。這表明本文提出的基于容忍因子的過濾貪心算法可以有效地克服結構化約束條件對檢索精度的負面影響。

在DEEP1B數據集中，當Q=30%時，使用TF-FGS比FGS精度提升了10%左右；當Q=90%時，精度提升了53.3%。這說明在數據集的結構化約束比較弱時，使用TFFGS算法比FGS算法提高的精度較??；而在數據集的結構化約束比較強時，使用TFFGS算法比FGS算法提高的精度就會更加明顯。在GloVe.6B和SIFT1M數據集中也存在類似的規律。

這表明在不同的數據集中，本文提出的算法都可以有效地提高精度，并且隨著結構化約束強度增加，相對FGS算法對檢索精度的提升越大。從表2可知，TF-FGS算法檢索結果的precision@10 相比FGS算法平均提升了30%。

6.3 容忍因子對混合查詢的影響

本實驗固定了檢索類型和數據類型，采用GloVe.6B數據集，使用HNSW的默認參數構建索引，并隨機選擇查詢向量進行實驗。在保持索引結構不變的條件下討論不同實驗超參數對TF-FGS檢索精確度的影響。在GloVe.6B數據集上檢索參數ef 、α和Q對precision@k的影響如圖4所示。同等參數條件下近鄰圖的連通性對檢索效率的影響如圖5所示。

圖4 GloVe.6B 上近鄰圖的連通性對檢索精確度的影響

圖5 GloVe.6B 上近鄰圖的連通性對檢索效率的影響

觀察圖4、圖5，可以發現以下結論。

● 參數ef 不變，容忍因子α=0 時（FGS算法），在滿足過濾條件的點占比逐漸下降時，檢索精確度會隨之下降，特別是在過濾掉85%以上的點時，精確度趨于0。但此時檢索效率會極大提升，這是由于近鄰圖不連通，導致提前結束查詢。

● 參數ef 不變，容忍因子α＞0 時，允許不滿足結構化約束的點參與路由，有效地緩解了檢索精確度隨滿足過濾條件的向量占比下降而逐漸降低的問題。而此時檢索耗時相對穩定。

● 容忍因子α不變時，候選集合大小ef 決定了檢索精確度的上限，且隨著ef 的增加，檢索精確度的提升越來越少。

● 在結構化約束強度Q較大時，引入容忍因子α對查詢精確度的提升越明顯。

綜上所述，在不改變索引結構的條件下，檢索參數ef 不變時，適當的容忍因子α可以在保持檢索效率不變的同時，顯著增強檢索的精確度，且在結構化約束強度Q較大時尤為顯著。

6.4 TF-FGS算法在不同索引上的有效性分析

本實驗驗證了TF-FGS算法在多種不同的近鄰圖索引上相對于FGS算法能夠獲得更好的檢索性能，兩者的效果對比如圖6所示。

圖6 不同索引中TF-FGS 算法和FGS 算法的效果對比

本實驗使用SIFT1M數據集，并使用HNSW、NSG、SSG 3種索引的默認參數建圖，設定容忍因子為0.3。在數據集和索引結構不變的條件下，比較了不同結構約束強度Q（取值范圍為31%～99%）下FGS算法和TF-FGS算法的檢索效果。

從結果可以觀察到，雖然在HNSW、NSG、SSG 3種索引上應用同一混合查詢方法時檢索精度有不同程度的差異，但是索引一定的條件下，當結構約束Q過強時，應用FGS算法查詢檢索精度會快速下降并趨近于0；而應用TF-FGS算法查詢，無論索引結構如何，檢索精度均能維持在較高水平。這表明在不同的近鄰圖索引上，TFFGS算法相對于FGS算法能夠獲得更優的檢索精確度。

6.5 TF-FGS算法在不同數據集的有效性分析

本實驗使用HNSW在DEEP1 B、GloVe.6B和SIFT1M數據集上分別構建近鄰圖索引，分析TF-FGS算法在不同數據集、不同的超參數取值時混合查詢的有效性。其中，超參數包括候選集合容量ef、容忍因子α、結構化約束強度Q。多數據集上近鄰圖的連通性對檢索精度和檢索效率的影響分別如圖7和圖8所示。

圖7 多數據集上近鄰圖的連通性對檢索精確度的影響

圖8 多數據集上近鄰圖的連通性對檢索效率的影響

從圖7、圖8可以看出，無論數據集和超參數設置如何，TF-FGS算法在保持近似相同的檢索效率的前提下均能夠獲得明顯更高的精確率。這證明了TF-FGS算法相較于FGS算法在不損耗效率的條件下可以提供更準確和更可靠的近似鄰域搜索結果。

如圖8所示，當參數ef 一定時，容忍因子α不宜過大。雖然過大的α不會降低檢索精確度，但是會導致檢索效率不穩定。因為過大的α會使更多不滿足結構化約束的點參與路由，當xq最近鄰附近有更多符合條件的點時，其會有較高的檢索效率；反之，則會搜索更多的無效分枝，進行更多的距離計算和對比，從而造成檢索效率降低。

綜上所述，實驗部分證明了TF-FGS算法在多種近鄰圖索引和多種數據集下均有較好的表現，具有一定的普適性，其可以在不影響檢索效率的前提下解決路由時的連通性問題，極大地降低了結構化約束強弱對檢索精確度的影響。

7 總結與展望

經過實驗驗證，本文改進的過濾貪心搜索算法能夠在不影響檢索效率的前提下提升近似最近鄰檢索的精確度，具有一定的有效性和普適性。然而，這種方法僅僅消除了結構化約束條件對檢索精確度的影響，如何在此基礎上利用結構化約束條件縮小檢索范圍、提升檢索效率仍然是一個值得探究的問題。未來可能的研究方向包括利用樹結構索引來加速搜索過程，提高檢索效率和精度；也可以考慮將本方法與其他近似最近鄰搜索算法相結合，探索出更加高效、準確的檢索方法?？傊?，本文提出的方法為近似最近鄰檢索領域的混合查詢研究提供了新思路，未來還有很多有意義的工作可以展開。