搜索資料庫的方法、生成索引結構的導航設備和方法

2023-05-26 11:54:01 1

專利名稱：搜索資料庫的方法、生成索引結構的導航設備和方法
技術領域：
本發明涉及在導航設備中使用的資料庫搜索方法和設備。本發明尤其涉及使用索引結構搜索導航設備資料庫的方法、生成索引結構的導航設備和方法。
背景技術：
眾所周知，導航設備執行諸如在兩個位置之間的路線搜索的功能。現代導航設備還可提供附加功能，諸如起到行程嚮導的作用，其根據需求輸出關於興趣點(POI)的信息。這樣的信息可包括街道或POI的名稱，而且還可包括附加文本或多媒體信息。例如，ー些導航設備可包括行程嚮導功能，以文本和/或多媒體的形式輸出關於對象的詳細解釋。鑑於在現代導航設備之中使用的資料庫的大小，在該資料庫中進行搜索是相當大 的挑戰。尤其是在執行對文本字符串、音位字符串(phoneme string)、多媒體對象,或在歐幾裡得(Euclidean)空間中未定義出的其它對象的搜索的時候。在2D或3D空間中定義的對象的幾何坐標可使得這些對象能夠基於它們的坐標被編入索引，用於基於坐標的搜索。這樣的編入索引對於諸如文本字符串、音位字符串、多媒體對象，或在歐幾裡得空間中未定義出的其它對象更具有挑戰性。進ー步地，當針對諸如文本字符串、音位字符串，或多媒體對象進行搜索時，用戶可能不僅對獲得準確的命中感興趣，用戶還可能會對獲得關於與查詢近似但不必相同的搜索結果的信息感興趣。對於許多應用，諸如輸入路線搜索的起始和終點位置、中間點或轉接點，或輸入POI時，用戶可能不知道對該名稱的正確文本表達。在資料庫中依據字符串首字母捜索準確匹配的常規技術在當這些首字母中出現拼寫錯誤時可能會失敗。進ー步地，在導航設備中，由於存儲空間限制所強加的約束和可用的運算時間的界限，使得實現高效的容錯(fault-tolerant)的搜索尤其具有挑戰性。

發明內容
據此，存在對提供能夠進行容錯搜索的方法和導航設備的需求。尤其是對使容錯捜索能夠被高效地執行的這樣的方法和導航設備的需求。這種需求通過獨立權利要求中所述的設備和方法來解決。從屬權利要求定義了各種實施方式。依據ー個方面，提供了一種在導航設備資料庫中執行相似性捜索的方法。該相似性搜索是使用ー種索引結構執行的。該資料庫包括多個對象，並且該索引結構包括多個節點。接收查詢對象。訪問與多個對象中的至少ー個對象相關聯的索引結構的節點。對於所訪問節點中的至少ー個對象，依據距離度量(distance metric)確定在查詢對象和該對象之間的距離。基於所確定的距離，選擇性地訪問索引結構的另ー節點。該方法使用相似性捜索。這使得模糊捜索能夠被實現成，模糊捜索不僅提供關於準確匹配的信息，而且還在資料庫中檢索出了關於最相似對象的信息。在該方法中，確定出在查詢對象和索引結構的節點中的對象之間的距離，以識別出將要訪問哪個(些)其它的節點。這使得該搜索能夠被高效地執行。不需要訪問既不包括也不指向距查詢對象的距離大於閾值的對象的節點。通過使用依據距離度量確定的距離，定量地評估出查詢對象和在索引結構中包括的對象之間的相似性或非相似性。該索引結構可被存儲在導航設備的存儲設備中。該索引結構可以是度量索引結構。依據常規術語，度量索引結構是僅考慮對象之間(而非它們在多維空間中的坐標之間)的相對距離的索引，以對該索引進行分割。該索引結構可尤其是M樹(M-tree)、優勢點樹(vantage-point tree),或依據距離度量組織的任意其它的樹結構。該索引結構是按照距離函數組織的，其與用於確定查詢對象和執行搜索的對象之間距離的距離相同。
使用常規術語，「距離度量」或「度量」在此被理解為指示滿足自反性、対稱性和三角不等性的基本條件的距離函數。使用常規術語，術語「相似性捜索」在此被用於指示對對象的捜索，這些對象滿足關於相對於查詢對象的相似性或非相似性的給定準則。例子包括，捜索具有非相似性的對象，該非相似性是作為依據小於固定閾值的距離度量的距離而被測量的，或者，捜索具有最小非相似性的對象，該最小非相似性是作為依據被索引的對象當中距查詢對象的距離度量的距離而被測量的。可以但不必確定出在查詢對象和由該搜索中訪問的節點表示的所有對象之間的準確距離。針對沿著穿過該索引結構的路徑的節點中的至少ー些，可足以確定出該查詢對象和該索引結構中相應的對象之間距離的下界。這些對象可以是字符串，尤其是音位字符串或文本字符串，相應地，查詢對象可以是音位字符串或文本字符串。這使得能夠執行對音位字符串或文本字符串的容錯搜索。當輸入起始和終點位置時、當在資料庫中搜索POI時、當搜索被存儲在該資料庫中的文本或多媒體數據時，或者在類似情況下，這樣的捜索可能是有用的。用於字符串對象的距離度量可從多個可用的字符串度量中的任意ー種中被選定。例如，該距離度量可以是基於Levenshtein距離的。該距離函數還可以是Damerau-Levenshtein 距離、Jaro-Winkler 距離、漢明(Hamming)距離、按照 Soundex 距離度量所確定的距離、Needleman-Wunsch 距離、Gotoh 距離、Smith-Waterman-Gotoh 距離、P ^ I的Lp距離，或者遵守自反性、対稱性和三角不等性的基本條件的任意其它字符串度量中的任意ー種。可接收文本輸入並執行文本到音位的轉換，以由該文本輸入生成查詢對象。備選地或額外地，該查詢對象可以是由語音輸入生成的音位字符串。該索引結構可進ー步包括關於在被訪問的節點中包括的至少ー個對象和該索引結構中其它對象之間距離的距離信息。對於具有父對象的任意節點，該距離信息可包括在該節點中的該對象與其父對象之間的距離。該距離信息可被存儲在該索引結構中。備選地或額外地，對於指向另ー個節點的任意對象，即，其不在葉節點中，該距離信息可包括該對象和在與該對象相關聯的索引結構的子樹中包括的任意對象之間距離的上界。該距離上界還可被稱為覆蓋半徑，因為其表示了該對象周圍的距離，在其子樹中的所有對象位於該距離之內。通過將這樣的距離信息包括到該索引結構中，該距離信息可在運行時被使用，而不需要在相似性捜索中對其進行計算。因此可增強搜索的性能。
基於查詢對象和被訪問的節點中包括的對象之間的距離，並且基於距離信息，可選擇性地執行對另ー個節點的訪問。可執行閾值比較。基於該閾值比較，可確定是否必須捜索索引的子樹。備選地或附加地，基於閾值比較，可確定是否需要計算查詢對象和在該索引結構中的對象之間的準確距離。可將查詢對象與在該節點中包括的對象之間的距離和覆蓋半徑與捜索半徑之和相比較。如果該閾值比較表明查詢對象和在節點中包括的對象之間的距離大於求和值，則不需要訪問該對象所指向的索引結構的子樹。捜索半徑可以是固定的，或者可以使其隨著相似性捜索的進行而變化。節點可包括若干個對象。針對若干個對象中的每ー個，索引結構可包括在相應的對象與在該相應的對象指向的索引結構的子樹中包括的任意對象之間的距離上界。基於所確定的距離，可從相似性搜索中選擇性地剪除對象。剪除可基於查詢對象和在節點中的對象之間所確定出的距離，並基於對象的覆蓋半徑來執行。
可以迭代的方式重複確定距離和選擇性地訪問另一個節點的步驟。在重複這些步驟時，不需要針對節點中的對象中的每ー個都計算查詢對象和該節點中包括的對象之間的距離。查詢對象和節點中包括的對象之間的距離可基於某種準則選擇性地計算，這種準則不需要計算新的距離。確定距離和選擇性地訪問另一個節點可在當該另ー個節點是該索引結構的葉節點時終止。當所訪問的其它節點是葉節點時，該方法可進ー步包括，根據閾值比較的結果，選擇性地確定該葉節點中的對象與查詢對象之間的距離。根據閾值比較的結果，可選擇性地確定出在該葉節點中給定的對象和查詢對象之間的距離。該閾值比較可包括將第一距離和第二距離之間的差異的模數與閾值進行比較。該第一距離可以是查詢對象和該葉節點的父對象之間的距離。該第二距離可以是該葉節點的父對象與該葉節點中相應的給定對象之間距離。對於在該葉節點中的任意給定的對象，可根據這樣的閾值對比的結果，選擇性地計算出相應的給定對象和查詢對象之間的距離。從而，可進ー步減少搜索時間。在該搜索中，可識別出位於距查詢對象在預確定距離之內的所有對象。該距離是按照距離度量定義的。這使得與未超出給定閾值的查詢對象具有非相似性的所有對象能夠被識別出並被輸出給用戶。備選地或額外地，可識別出整數k > I個對象，其表示依照距離度量確定出的在該索引結構中查詢對象的k個最接近的鄰居，這使得在距離度量方面與查詢對象最相似的k個對象可被識別出並輸出給用戶。基於查詢對象和相應的被識別出的對象之間的距離，可輸出被識別出的對象。在輸出這些識別出的對象時，可依照查詢對象和相應的識別出的對象之間的距離對這些對象進行分揀。例如，為了經由光學輸出單元輸出，距查詢對象距離最近的對象可在頂部或最左位置處輸出，並且其它對象可按照距查詢對象的距離増大的順序輸出。類似地，為了經由音頻輸出單元輸出，距查詢對象距離最近的對象可被首先輸出，並且此後其它對象可按照距查詢對象的距離增大的順序繼續輸出。依據另一方面，提供了導航設備，該導航設備包括存儲設備和處理設備。存儲設備存儲了用於資料庫的索引結構，該資料庫包括多個對象，該索引結構包括多個節點。處理設備被耦接到存儲設備。為了執行對查詢對象的相似性捜索，該處理設備被配置成訪問與多個對象中的至少ー個對象相關聯的索引結構的節點。該處理設備被進ー步配置成，依照距離度量，確定查詢對象和至少ー個對象之間的距離。該處理設備被進ー步配置成，基於所確定出的距離，選擇性地訪問索引結構的另ー個節點。這樣的導航設備使得模糊捜索能夠被實現成，不僅提供關於準確匹配的信息，而且在該資料庫中檢索關於最相似對象的信息。在該導航設備中，確定在查詢對象和索引結構的節點中的對象之間的距離，以識別出將要訪問其它的哪個(些)節點。這使得捜索能夠被高效地執行。不需要訪問既不包括也不指向具有距查詢對象的距離大於閾值的對象的節點。通過使用按照距離度量確定的距離，定量地評估查詢對象和索引結構中的對象之間的相似性或非相似性。這些對象可以是音位和/或文本字符串。該索引結構可以是度量索引結構。該導航設備可包括輸入單元。處理設備可被耦接到該輸入単元，以從其中接收查詢對象，或者基於在輸入單元處接收的輸入生成查詢對象。該處理設備可被配置成執行文本到音位轉換，以生成查詢對象。該導航設備可包括輸出單元。處理設備可被配置成控制該輸出單元，使得在相似性捜索中找到的多個對象經由輸出單元輸出。處理設備可被配置成控制該輸出單元，使得按照查詢對象和相應的輸出對象之間的距離，對這些輸出對象進行分揀。該處理設備可被配置成識別出具有距查詢對象的距離小於固定捜索半徑的所有對象，該距離是依照距離度量確定的。該處理設備可備選地或額外地被配置成識別出k >I個對象，這些k > I個對象是查詢對象的k個最接近的鄰居。該處理設備可被配置成依照任意ー個方面或任ー實施例執行相似性捜索方法。依據另ー個方面，提供了ー種生成導航設備資料庫的度量索引結構的方法。該資料庫包括多個對象。在該方法中，生成索引結構的目錄節點，其包括指向該索引結構的其它節點和該索引結構的葉節點的指針。生成節點包括，針對多對對象，分別確定出該對對象的對象之間的距離，從而確定出多個距離。這些距離按照距離度量被分別地確定出。基於該多個距離，識別出將要被包括在目錄節點中的對象和將要被包括在葉節點中的對象。使用這種方法，索引結構被生成，其可被用於相似性搜索方法，也可以用於任意一方面或任ー實施例的導航設備中。依照所確定出的多個距離來組織所生成的度量索引結構，該多個距離是對象之間的相對距離。這使得度量索引結構也能夠針對並非通過在多維空間中的坐標定義的對象來設置。這些對象可以是音位字符串，或者字母數字字符串。在生成索引結構時，可從用於字符串度量的多個距離定義中的任意ー個中選擇出距離度量。例如，距離度量可以是基於Levenshtein距離的。該距離函數還可以是Damerau-Levenshtein 距離、Jaro-Winkler 距離、漢明(Hamming)距離、按照 Soundex 距離度量所確定的距離、Needleman-Wunsch 距離、Gotoh 距離、Smith-Waterman-Gotoh 距離、P ^ I的Lp距離，或者遵守自反性、対稱性和三角不等性的基本條件的任意其它字符串度量中的任意ー種。針對在目錄節點中包括的對象，該方法可包括存儲關於相應的對象和在該對象所 指向的索引結構的子樹中包括的任意對象之間的距離的上界。該上界，或覆蓋半徑，可被存儲在該索引結構中。針對在節點中包括的具有父對象的對象,該方法可備選地或額外地包括存儲相應的對象與其父對象之間的距離。在該方法中，索引結構可以迭代的方式生長。該方法可包括將額外的對象插入節點中。為了這種目的，可識別出將要被插入對象所在的節點。識別節點可包括確定將要插入的對象和該索引結構的目錄節點中的對象之間的距離。該方法可進ー步包括分裂節點。為了這種目的，在插入對象之後，可確定出在該節點中的對象的個數是否大於對象的固定的最大個數。如果該個數超過最大個數，則節點分裂。分裂節點可包括，從將要被包括在新目錄節點中的節點中選擇出對象，以及將對象指派給兩個新的葉節點中的ー個。可進行分裂節點，使得在新的目錄節點中的兩個對象的兩個覆蓋區域之間的重疊減小到閾值以下，或者被最小化。依據另ー個方面，提供了用於導航設備資料庫的度量索引結構。該度量索引結構 包括目錄節點，其包括指向該索引結構的其它節點和葉節點的指針。這些節點中的至少ー些節點可包括距離信息，其代表關於該索引結構的對象之間依據度量確定的距離的信息。至少目錄節點可包括該目錄節點中的對象和相應的對象的索引結構的子樹中包括的任意對象之間的距離的上界。應該理解，以上所提及的和那些將要在下面解釋的特徵不僅可被用於所指示出的各個組合中，而且還可以用在其它組合中，或単獨使用。


在結合附圖閱讀以下實施方式的詳細描述時，各實施方式的前述和其它特徵將會變得更加清楚。在附圖中，用相同的附圖標記表示相同的元件。圖I是導航設備的示意性框圖；圖2是索引結構的示意性表達；圖3和圖4是在索引結構的節點中的數據條目的示意性表達；圖5是使用相似性搜索的方法的流程圖；圖6是執行相似性捜索的方法的流程圖；圖7是對用於解釋圖6的方法的資料庫對象的示意性表達；圖8是對用於解釋圖6的方法的索引結構的示意性表達；圖9是使用相似性搜索的方法的流程圖；圖10是生成索引結構的方法的流程圖；圖11和圖12是用於解釋圖10的方法的索引結構的示意性表達。
具體實施例方式圖I示意性地說明了依據ー個實施例的車輛導航設備I。該導航設備I包括依據例如存儲在存儲器中的控制指令來控制該導航設備I的操作的處理設備2。該處理設備2可包括例如具有ー個或多個微處理器、數位訊號處理器或者專用集成電路形式的中央處理単元。導航設備I進ー步包括存儲設備3，其可以是可擦除或不可擦除存儲介質或者存儲器。該存儲設備3可包括諸如隨機訪問存儲器、快閃記憶體或硬碟的不同類型的存儲器或存儲介質中的任意ー種或任意組合，還可以包括諸如高密度磁碟(CD)、DVD、存儲卡等可移除存儲器。導航設備I還可包括用於將信息輸出給用戶的輸出接ロ 4。該輸出接ロ 4可包括光學輸出設備、音頻輸出設備或者其組合。該導航設備I還包括輸入接ロ 5，其使得用戶能夠輸入信息。尤其是，該輸入接ロ 5可使得用戶能夠輸入文本信息或者語音信息。導航設備可包括附加組件，諸如位置傳感器和/或無線接收機和/或車輛接ロ。位置傳感器可適用於確定車輛的當前位置，在該車輛上安裝有導航設備I。該位置傳感器可包括GPS(全球定位系統)傳感器、伽利略(Galileo)傳感器、基於移動通信網絡的位置傳感器，以及類似傳感器。無線接收機可被配置成接收用於更新存儲在存儲設備3中的資料庫的信息。車輛接ロ可使得處理設備2能夠從其它車輛系統中獲得信息，或者經由該車輛接ロ獲得車輛狀態信息。該車輛接ロ可包括，例如，CAN(控制器區域網)接ロ或MOST(媒體定向設備傳輸)接ロ。存儲設備3存儲了包括多個對象的資料庫。該多個對象可包括文本或音位字符串。例如，該資料庫可包括代表道路名稱的對象、代表興趣點(POI)名稱的對象，和/或代 表關於道路或POI的附加信息的對象。這樣的信息可具有文本或音位字符串或多媒體對象的形式，或可包括文本或音位字符串或多媒體對象。存儲設備3存儲了該資料庫的索引結構。在導航設備I的應用中，處理器2使用該索引結構執行相似性捜索。該處理器2可使用在輸入接ロ 5接收的輸入作為查詢對象，或可執行關於輸入的附加操作，以生成查詢對象。然後處理器2使用該索引結構，執行對查詢對象的相似性搜索。該相似性搜索包含計算該查詢對象和存儲在該資料庫中的對象之間的距離。在此所使用的「計算」可以不同方式實現，包括查表操作。該距離提供了對查詢對象和索引結構中的對象的非相似性的定量測量。在該搜索中找到的若干個最相似對象經由輸出接ロ 4被輸出給用戶。例如，處理器2可生成關於光學輸出接ロ 4的列表，其中，在具有距查詢對象距離最近的索引結構中的對象按照通過它們距查詢對象的距離所確定出的順序列出。 在邏輯上該索引結構可與資料庫分開。備選地，該資料庫可與索引結構合併。該索引結構可使用任意適當的技術來實現。為了說明而非構成限制，該索引結構可使用SQ Lite來實現。該索引結構可被實現成在資料庫系統中，尤其是在相關資料庫系統中，由用戶定義的索引結構。該相關資料庫可包括用於文本字符串或音位字符串的表格，以及用於多對文本字符串或多對音位字符串之間的距離的另ー個表格。該資料庫的索引結構可被組織成索引樹。該索引結構可包括多個節點，這些節點中的至少ー些為目錄節點，其包括指向其它節點的指針，並且至少ー些其它節點為葉節點，其不包括指向其它節點的指針。這些節點中的每ー個節點可與至少ー個對象並且典型的是若干個對象相關聯。針對在目錄節點中包括的對象，該目錄節點可存儲指向與這些對象中的每ー個對象相關聯的相應的根部的指針。存儲在存儲設備3中的索引結構是度量索引結構，其可使用距離度量被搜索出來。而且，該索引結構也是依照距離度量組織的。即，該索引結構基於資料庫的對象之間的相對距離被分割成子樹，資料庫的對象之間的相對距離是根據距離度量確定的。依據通用的術語，「距離度量」或者「度量」在此是指針對非空集合M的對象定義的距離測量，該非空集合M滿足以下條件
自反性(也稱為對不可辨別性的識別):Vx,少 eM :d(x，y) = O 若且唯若 X = y 時； (I)対稱性Vx,少 eM : d (X, y) =d(y,x)(2)三角不等性/x,y,z eM d (x, z) ≤ d (x, y) +d (y, z)(3)當滿足以上基本條件(I)至(3)時，緊跟著，距離函數也滿足正性基本條件Vx,ysM d(x, y)(4)集合M和度量d的重數(M，d)也稱為度量空間。組織索引結構所依據的並且還被用於在索引結構中執行搜索的度量可以從各種定義中選出，尤其取決於資料庫中的對象。例如，對於文本字符串或語音字符串的對象，Levenshtein距離定義了度量，並且可在建立索引結構時以及在索引結構中執行相似性搜索時使用。Levenshtein距離也被稱為編輯距離。在兩個字符串之間的Levenshtein距離被定義成，通過對單個字符進行插入、刪除或者替換的可允許的編輯操作，將ー個字符串變換成另一個所需的最小編輯次數。其它度量也可被用於組織索引結構和在索引結構中執行相似性搜索時計算距離。也可使用其它度量。例如，距離函數可被選擇為Damerau-Levenshtein距離、Jaro-Winkler距離、漢明距離、依據Sondex距離度量確定的距離、Needleman-Wunsch距離、Gotoh距離、Smith-Waterman-Gotoh距離、p彡I的Lp距離，或遵守自反性、對稱性和三角不等性的基本條件的任意其它字符串度量中的任意ー種。存儲在存儲媒介3中的索引結構不僅可包括對象和指向定義了搜索樹的其它節點的指針，而且還可額外地包括指示索引結構中對象之間距離的距離信息。在執行搜索吋，這樣的距離信息可從索引結構中檢索出來。這樣的距離信息可尤其被用於從相似性捜索中剪除對象或節點，正如在下面將詳細描述的那樣。圖2是索引結構10的示意性表達。雖然在圖2中被示出為類似樹的結構，但是索引結構通常可以任意適當的格式存儲，例如，作為相關資料庫中的用戶定義的索引結構。該索引結構包括目錄節點11-13以及葉節點14-17。目錄節點11_13中的每ー個節點包括指向其它節點的指針。每ー個指針可分別與在相應的節點中包括的對象相關聯。例如，根節點11可包括與第一對象相關聯的數據條目21和與第二對象相關聯的數據條目
22。數據條目21可包括指向目錄節點12的指針，其為第一對象的子樹的根部。數據條目22可包括指向目錄節點13的指針，其為第二對象的子樹的根部。目錄節點12可包括與該資料庫的其它對象相關聯的數據條目23、24。數據條目
23、24可分別包括指向另ー個節點的指針。在圖2所示的結構中，數據條目23、24分別包括指向葉節點14和15的指針。可實現目錄節點的較大分層。類似地，目錄節點13可包括與資料庫的其它對象相關聯的數據條目25、26。數據條目25、26可分別包括指向另ー個節點的指針，諸如，分別指向葉節點16和17的指針。葉節點14-17可分別包括與資料庫的一個或多個對象相關聯的數據條目。例如，葉節點14被示出為包括與資料庫的三個對象相關聯的數據條目27-29。在索引結構中，搜索樹按照距離度量被分割。為了這種目的，可選出由數據21代表的第一對象和由數據22代表的第二對象，使得在具有根節點12的第一子樹中包括的所有對象位於圍繞第一對象具有第一覆蓋半徑的覆蓋區域之內，並且在具有根節點13的第ニ子樹中包括的所有對象位於圍繞第二對象具有第二覆蓋半徑的覆蓋區域之內。換句話說，該第一覆蓋半徑可以是節點12、14和15中的任意一個節點所代表的任意對象與數據條目21代表的對象之間距離的最大值，數據條目21是該子樹的父對象。第二覆蓋區域半徑可以是節點13、16和17中任意一個節點所代表的任意對象與數據條目22代表的對象之間距離的最大值，數據條目22是該子樹的父對象。在根節點11中的第一對象和第二対象，以及相關聯的子樹中的對象，被選擇為使得第一和第二覆蓋區域具有重疊，該重疊優選地儘量小。進ー步，在根節點11中的第一對象和第二對象以及在相關聯的子樹中的對象可被選擇為 ，使得在第一對象和具有根部12的子樹中包括的任意對象之間的第一最大距離，以及在第二對象和具有根部13的子樹中包括的任意對象之間的第二最大距離保持儘量小。這樣，該索引結構按照對象之間依據距離度量確定的接近程度被分割。用於組織以上索引結構所列出的準則不僅適用於根節點11，而且還適用於任意目錄節點12、13。即，將對象組織到目錄節點和葉節點中，g在減小目錄節點中不同對象的覆蓋區域的重疊，並進一歩g在減小覆蓋區域尺寸。在下面參考圖10至圖12將描述用於生成這樣的索引結構的系統性方法。在一些實施例中，索引結構的目錄節點可包括關於在該索弓I結構中包括的對象之間距離的信息。在目錄節點中的數據條目21-26可分別包括對象與該對象指向的子樹中包括的任意對象之間的距離的上界。該上界可以是這些距離的最大值。例如，數據條目21可包括數據條目21所代表的第一對象和節點12、14和15中的任意對象之間的距離的上界。數據條目22可包括數據條目22所代表的第二對象和節點13、16和17中的任意對象之間的距離的上界。數據條目23可包括數據23所代表的對象和節點14中的對象中任意ー個對象之間距離的上界，等等。基於該上界，可在相似性捜索中執行剪除。對於在相應的節點中的任意對象，所有具有父對象的節點中的數據可進ー步包括，關於該對象和其父對象之間的距離的信息。這種信息還可在相似性捜索中被用於估計距離。該索引結構可尤其被組織成由P. Ciaccia、M. Patella和P. Zezula所開發的M樹(M-tree) 0也可以使用按照距離度量組織的其它索引結構。例如，該索引結構可以是優勢點樹。圖3示出了用幹與目錄節點中包括的對象相關聯的數據條目31的示範性數據結構。該圖所示出的是，例如，在M樹中使用的示範性數據條目。數據條目31包括對象0パ備選地，在數據31中可包括該對象的特徵值。備選地，在數據31中可包括該對象的標識符。數據條目31還包括指向該對象( 子樹的根節點的指針ptr (T (Or))。如果目錄節點不是該索引結構的根節點，則數據條目31可進ー步包括對象和其父對象P(0J之間的距離(1執；P(0J)。通過將這樣的距離包括在索引結構中，值(1執；P(Or))可被用於估計距離和/或用於剪除捜索。在運行時可提高相似性捜索的效率。數據條目31可進ー步包括半徑r (Or)，其是對象Or和具有根節點T (Or)的子樹中任意對象之間的距離的上界。半徑r(0j可被定義為這樣的距離的最大值
r (Or) = maxj d(0j ；0r)(5)其中，該最大值是在指針ptr(T(0j)指向的子樹的所有對象Oj之中確定出來的。圖4示出了用幹與在索引結構的葉節點中包括的對象相關聯的數據條目32的示範性數據結構。所說明的是在M樹中使用的示範性數據條目。數據條目32包括對象(V備選地，在數據32中可包括該對象的特徵值。備選地，在數據32中可包括該對象的標識符。數據條目32可進ー步包括相應的對象Oj和其父對象P(Oj)之間的距離d(0パP(Oj)).通過將這樣的距離包括在該索引結構中，值CKOyP(Oj))可被用於估計距離和/或用於剪除捜索，而不需要在搜索過程中計算距離。可使用其它數據結構。例如，在數據條目31或數據條目32中指示的不同欄位條目不必以彼此接近的方式存儲。在相關資料庫中用戶定義的索引結構可被用於存儲索引結構。
圖5是方法33的流程圖，其可由處理器2使用該索引結構來執行。在34，接收輸入。該輸入可以是經由輸入接ロ 4接收的用戶輸入。備選地，該輸入可通過該車輛的其它系統或設備被提供給處理器2，或者可從該車輛的外部接收。該輸入可以是文本字符串。在35，執行文本到音位的轉換。所獲得的音位字符串作為查詢對象。在36，使用索引結構執行相似性搜索。該索引結構是按照距離度量組織的度量索引結構。該索引結構可被配置成如參考以上圖2至圖4描述的那樣。為執行相似性捜索，可依據距離度量確定出查詢對象和在索引結構中的對象之間的距離。在37，輸出在搜索中找出的最相關對象。這些最相關對象可以是查詢對象的k >I個最接近的鄰居，即，在被索引的對象當中距該查詢對象距離最小的k個對象，這些距離是依據距離度量確定的。備選地，這些最相關對象可以是在索引結構中距查詢對象距離小於預定閾值的所有対象。在37，可執行輸出，使得多個對象被輸出。這些對象可以按照所確定的它們各自距查詢對象的距離順序被輸出。圖5是用於執行相似性捜索的方法40的流程圖。該方法40可通過處理器2執行。該相似性搜索是使用按照距離度量d(· ； ·)組織的索引結構執行的。如上所述，取決於對象類型，可選擇出不同距離度量中的任意ー個。該索引結構可以被配置成如圖2至圖4所描述的那樣。在41，接收查詢對象。接收查詢對象可包括對輸入進行處理，諸如執行文本到音位轉換。在42，訪問索引結構的節點N。方法40的步驟可沿著樹的路徑被迭代地重複。在第一迭代中，節點N可以是索引結構的根節點。在後續迭代中，節點N可以是索引結構的目錄節點。在43，選擇出在節點N中的對象O,。不同對象O,可按照這些O,被包括在節點N中的順序被選擇出。在44，確定出查詢對象Q和在節點N中被選擇出的對象Or之間的距離(1執；Q)。對於文本或音位字符串，確定距離可包括計算Levenshtein距離或者依據任意其它字符串度量的距離。在44中是使用分割索引結構所依據的距離度量來確定距離的。
在45，確定出距離d(0, ；Q)是否大於對象O,的覆蓋半徑r (O,)與搜索半徑R的和。該搜索半徑R可以是固定的半徑。備選地，該搜索半徑R還可以隨著相似性捜索的繼續被動態地調節。例如，該搜索半徑R可在k個最接近的鄰居的捜索中被調節，使得R對應於查詢對象與到目前為止檢索的第k個最接近的鄰居之間的距離。如果確定出，距離d((^ ；Q)大於覆蓋半徑r(0j與捜索半徑R的求和值，則該方法從45前進到46。在46，從搜索中剪除在對象Or的子樹中的所有對象。通過將覆蓋半徑r(0r)定義成該子樹中的任意對象和對象Or之間的距離的上界，如果距離d((^ ；Q)大於r(0j與R的求和值，在對象Or的子樹中的對象距查詢對象Q的距離不可能小於或等於搜索半徑R。通過剪除該搜索，可避免假性(spurious)搜索步驟。如果確定出距離d((^;Q)不大於覆蓋半徑r(0j與R的求和值，則該方法從45前進到47。 在47，在對象Or的子樹中繼續搜索。為了這種目的，訪問對象Or的子樹的根節點T(Or)0基於在45的條件測試，選擇性地訪問該根節點。為了繼續在該子樹中的捜索，在該子樹中可重複步驟42-48，直到達到葉節點為止。只有沿著從索引結構的根部到葉節點的路徑，沿著該路徑所貫穿的任意對象Or不滿足在45所檢查的條件，才能達到葉節點。如果在47達到了葉節點，則可確定出在該葉節點中的對象Oj和查詢對象Q之間的距離d (OyQ)。如果d(0j ；Q) < R,(6)則在相關的被索引對象的列表中可包括對象Op用於後續輸出。如果執行k個最接近的鄰居搜索，則可更新捜索半徑R，即，如果滿足等式(6)且在索引結構中識別出的相關對象的列表中包括對象(V則搜索半徑R可被減少。如果在葉節點中沒有找到滿足等式
(6)的對象，則該方法前進到48。在48，確定出在節點N中是否存在另ー個對象0パ如果存在另ー個對象，則該方法返回43，選擇這些對象Or中的另ー個。如果確定出在節點N中沒有其它對象，則該方法前進到49。在49，輸出所識別出的對象。執行該輸出可使得多個對象被輸出。在相似性捜索中找出的這些對象可按照通過它們各自距查詢對象Q的距離確定的順序被輸出，由於該距離在前面的步驟44或步驟47已經被確定出，該距離可被用於將所識別出的對象組織到按順序整理的列表中，用於後續輸出。備選地，在搜索過程中確定的距離可被登記，用於後續按照它們距查詢對象Q的距離對這些對象進行分揀。在方法40中，基於查詢對象和被索引的對象之間的距離，執行相似性搜索。這使得，甚至在歐幾裡得(Euclidean)空間中未定義該查詢對象和被索引的對象時，也能夠執行該搜索。相似性捜索40還可針對在多維矢量空間中所定義的對象執行。使用在度量索引結構中的相似性捜索實現了容錯搜索。在該方法中，基於查詢對象和索引結構的對象之間的距離，可選擇性地剪除捜索。剪除可基於在方法40的步驟45中驗證的條件進行，或者基於在下面描述的備選的或額外的條件進行。為了進一步說明，參考圖7和圖8。圖7是對對象的不意性表達50,而圖8是對索引結構70的示意性表達。在圖7中示出的對象包括對象52和55，其被包括在索引結構的根節點中。位於對象52的子樹中的對象位於距對象52小於或等於覆蓋半徑53的距離處。位於對象53的子樹中的對象位於距對象55小於或等於覆蓋半徑56的距離處。正如示意性地說明的，在對象52的子樹中的對象位於第一覆蓋區域54中。在對象55的子樹中的對象位於第二覆蓋區域57中。該索引結構被組織成，使得覆蓋區域54和57具有較小的重疊。在與對象52相關聯的子樹中的對象被聚合在對象52周圍，而在與對象55相關聯的子樹中的對象被聚合在對象55周圍。對象52的子樹的根節點包括對象59和60。包括對象59和60的節點是目錄節點。與對象59相關聯的指針指向包括接近於對象59的對象(如，對象61)的葉節點。與對象60相關聯的指針指向包括接近於對象60的對象(如，對象62 )的葉節點。在與對象55相關聯的子樹中包括對象63、64。圖8示出了索引結構70，其對應於圖7的表達。在圖8中，對象被標記為A、B、C、D、E、F、G、H、I、J。該索引結構包括具有對象A和B的根節點71。在該根節點71中的對象A對應於例如在圖7中的52所指示的對象。在根節點71中的對象B對應於例如在圖7中的55所指示的對象。該索引結構包括目錄節點72，其是用於與對象A相關聯的子樹的根節點。節點72包括對象C和D。在節點72中的對象C對應於例如在圖7中的59所指示的對象。在節點72中的對象D對應於例如在圖7中的60所指示的對象。該索引結構包括葉節點74，其以對象C作為父對象。該節點74包括對象G和H。在節點74中的對象G對應於例如在圖7中的61所指示的對象。該索引結構包括葉節點75，其以對象D作為父對象。節點75包括對象I和J，在節點75中的對象I對應於例如在圖7中的62所指示的對象。該索引結構包括在與對象B相關聯的子樹中的附加節點73。假設針對查詢對象51執行了鄰近搜索，可使用查詢對象和索引中各個對象A-J之間的距離，結合在索引結構中包括的距離信息，剪除該搜索。在圖7中的58示意性地指示了捜索半徑R。當搜索方法40開始時，訪問索引結構的根節點71。在66示出的查詢對象Q和對象B之間的距離d(Q;B)大於搜索半徑58和覆蓋半徑56的求和值。因此，在對象B的子樹中不執行搜索。在65示出的查詢對象Q和對象A之間的距離d(Q ；A)小於在58指示的搜索半徑和在53所指示的對象A的覆蓋半徑的求和值。因此，在對象A的子樹中繼續搜索。通過對具有根節點72的子樹重複方法40的步驟42-49，對象G (圖7中由符號61表示)和I (圖7中由符號62表示)被識別為位於距查詢對象51小於或等於搜索半徑的距離處。通過識別這些對象，實現了容錯搜索，該搜索依據距離度量返回所測量出的與查詢對象具有最小非相似性性的対象。可通過基於覆蓋半徑剪除搜索而高效地執行相似性捜索。在索引結構中包括的附加數據可被用於進ー步增強搜索效率。例如，如果在索引結構中存儲了對象和它們各自的父對象之間的距離，則該信息可被用於減少在運行時需要執行的距離運算次數。例如，當在方法40的步驟42中所訪問的節點N是目錄節點，而不是索引結構的根節點吋，只有滿足以下條件吋，步驟44至47可被選擇性地執行I d (Q ；P (Or)) -d (Or ；P (Or)) I ( r (0r+R)，(7)在此P機)表示節點對象ル的父節點。使用作為度量的距離d(，)，如果不滿足等式(7)，則三角不等性確保了在對象Or的子樹中的對象都不具有距查詢對象Q為R或更少的距離。如果不滿足等式(7)，則可剪除對象ル的子樹。可驗證等式(7)而不需要任何額外的距離運算。對於父節點，在方法40的前面的迭代中確定出了 d(Q;P((U)的量。i^d(Q5P(Qr))的量可從索引結構中讀出。通過取決於是否滿足等式(7)的條件，選擇性地執行在方法40的步驟44的運算，可減少在運行時運算 量繁重的距離確定。為了進ー步說明，當在方法40的步驟47中訪問葉節點時，只有當滿足以下條件時，才可選擇性地確定在葉節點中的對象Oj和查詢對象Q之間的距離d(Q；P(Oj))-d(Oj ；P(Oj)) | ( R(8) 其中p(op表示該葉節點的父節點，該父節點中包括對象(V由於d(，)是度量，如果不滿足等式(8)，則三角不等性確保Oj和查詢對象Q不可能具有R或更小的距離。如果不滿足等式(8)，則不需要確定d(Q，Oj)。可驗證等式(8)而不需要任何額外的距離運算。對於父節點，在方法40前面的步驟中確定出了 (KQ5P(Oj))的量。^cKQ5P(Oj))的量可從索引結構中讀出。通過只有在滿足等式(8)的條件時，選擇性地計算(KQ5P(Oj)),可減少在運行時運算量繁重的距離確定。依據以上參考圖I至圖8所描述的實施例，用於執行相似性捜索的設備和方法可尤其被用於當對象是文本字符串、音位字符串或多媒體對象吋。這些設備和方法可被用於識別在索引結構中與音位字符串具有最小非相似性的対象。該索引結構可被用作音位字符串的過濾器。圖9是方法80的流程圖表達,其中可使用相似性搜索。在81，識別器基於輸入確定出音位字符串。該輸入可以是文本字符串。向音位字符串的轉換可以基於與彼此相似的音位相對應的不同音位簇，使得使用距離度量確定的簇中的音位之間的距離在閾值以下。在82，使用索引結構過濾音位字符串。該音位字符串可通過在索引結構中執行相似性捜索來進行過濾，正如以上參考圖I至圖8中的任意ー個附圖描述的。在一些實現中，可確定出距查詢對象的距離小於或等於閾值的對象。在備選實現中，可確定出查詢對象的k個最接近的鄰居對象。在83，對音位進行過濾的結果被提供給拼寫匹配器。在用於執行相似性搜索的這些方法中的任意ー個和以上描述的導航設備中，索引結構可以是度量索引結構。在用於執行相似性捜索的方法中的任意ー個和以上描述的導航設備中，索引結構可對應於平衡的搜索樹。在用於執行相似性搜索的這些方法中的任意一個和以上描述的導航設備中，索引結構可被配置成使得每個目錄節點和每個葉節點的條目的個數是固定的。現將參考圖10至圖12解釋生成具有這些屬性的索引結構的方法。
圖10是用於生成索引結構的方法90的流程圖。該方法90可與相似性搜索分開地執行。尤其是，在預處理用於導航設備的數據時，可執行方法90。該索引結構可由伺服器計算機在中心地點構建，然後可被部署到多個導航設備中。方法90可通過將附加對象後續添加到索引結構，以自下至上的方式構建索弓I結構。該索引結構可使用距離度量構建，隨後該距離度量還將在執行相似性搜索時被使用。被插入的對象可以是字符串，尤其是音位字符串或者文本字符串。在方法90中，當在節點中出現溢出狀況時，可通過插入對象和通過分裂節點來構建索引結構。當節點被分裂時，生成新的目錄節點。在91，檢索出將要被插入索引結構的對象Oi。該對象可以是音位字符串或文本字符串。 在92，訪問索引結構的節點N。如果只存在ー個節點，則訪問該節點。如果索引結構已經包括目錄節點，則訪問最高目錄節點，即，該結構的根節點。在93，確定出節點N是否是葉節點。如果該節點是葉節點，則該方法在98繼續。否則，該方法在94繼續。在94，確定出在將要被插入的對象Oi和在該節點中包括的所有對象Ok之間的距離d(0k ；0i)。該距離是依據距離度量分別地確定出的。在95，確定出在節點N中包括的對象0k，對於該對象0k，d(0k ；0j)為最小。在96，選擇出新的節點N，其為對象Ok的子樹的根節點。訪問該節點N。在97，確定出節點N是否是葉節點。如果該節點N不是葉節點，則該方法返回94。否則，該方法在98繼續。在98，確定出在插入對象之後節點N的大小是否將超過閾值，該閾值對應於所允許的節點的最大條目個數。如果確定出不會超過所允許的最大條目個數，則在99將對象Oi插入該節點。然後該方法返回91。如果在98確定出，節點N已經具有允許的最大條目個數，則該方法在99繼續。在99,節點N被分裂成ー對節點。通過分裂節點N,生成兩個新的葉節點。同時，生成目錄節點，其包括具有指向這兩個新的葉節點的指針的兩個對象。對象Oi可被插入這兩個新葉節點中的ー個，或者被插入新的目錄節點。然後該方法返回91。圖11和圖12說明了，在達到在節點中所允許的最大條目個數時葉節點的分裂。圖11示出了索引結構110，其包括具有對象A和B的目錄節點11、具有對象C、D、G的葉節點112，以及具有對象E和F的另ー個葉節點113。假設插入新的對象I，對於該對象I，d(A ;I) < d(B ;1)，則方法90確定該對象將要被插入從節點A開始可到達的葉節點。如果對於節點所準許的條目最大數量對應於三個對象，則不能將對象簡單地插入節點112。在這種情況下，節點112分裂。圖12示出了節點112分裂之後的索引結構110。生成了兩個新的葉節點115和116。進ー步地，生成新的目錄節點114。在葉節點112中包括的對象C和D被晉升為目錄節點中的對象。在M樹術語中，對象C和D被晉升為路線設定(routing)對象。對象G被添加到以對象C作為父對象的葉節點115。對象I被添加到以對象D作為父對象的葉節點116。當在方法90的步驟100處節點被分裂時，可使用不同的技木，以選擇出被晉升為目錄節點的對象。例如，對於M樹，可使用以下實現在一種實現中，可隨機選擇出被晉升到目錄節點的對象。在另ー種實現中，對被晉升到目錄節點的多對對象進行取樣。對於多個對中的任意ー對，在該節點中包括的另一對對象被分割成兩個新的葉節點。可將對象分配給新的葉節點中的ー個，對於該葉節點，該對象和該葉節點的父對象之間的距離較小。當完成分割時，確定出得到的覆蓋半徑。該覆蓋半徑依據等式(5)來確定。對於被晉升到目錄節點的不同對對象，得到不同的覆蓋半徑。然後可分裂該節點，使得經取樣的對象對中的一對被添加到目錄節點，對於該對象對，兩個覆蓋半徑的最大值具有經取樣的被晉升的對象對當中的最小值。在另ー種實現中，對在該節點中包括並且原則上可被添加到目錄節點中的所有可能的對象對O1和O2進行取樣。在分裂前的節點中包括的另ー對對象被分割，如上所述。即，這些對象可被分配給新的葉節點中的ー個，對於該節點，該對象和該葉節點的父對象之間 的距離較小。對於可能的對象對中的任意ー對，確定出覆蓋半徑T(O1Hr(O2)的求和值。然後，導致覆蓋半徑的求和值最小的對象對可被添加到目錄節點中。其它對象可分別被分配給新的葉節點中的ー個，對於該節點，該對象和該葉節點的父對象之間的距離較小。在另ー種實現中，對在該節點中包括的並且原則上可被添加到目錄節點的所有對可能的對象O1和O2進行取樣。在該節點中包括的其它對象在分裂之前如上所述地被分割。即，這些對象可被分配給新的葉節點中的ー個，對於該葉節點，該對象和該葉節點的父對象之間的距離較小。對於要被晉升的可能的對象對中的任意ー對，確定出兩個覆蓋半徑之中的最大值max (!"(O1)，r (O2))。然後，使得覆蓋半徑的最大值最小的對象對可被添加到目錄節點中。其它對象可被分別地分配給新的葉節點中的ー個，對於該葉節點，該對象和該葉節點的父對象之間的距離相應地較小。在另ー種實現中，確定出在葉節點中距要被插入的對象具有最大距離d(0k ；0,)的對象0k。然後該對象Ok和新的對象Oi可被晉升到目錄節點。其它對象可分別被分配到新的葉節點中的ー個中，對於該葉節點，該對象和該葉節點的父對象之間的距離較小。雖然以上參考圖10至圖12已經描述了生成被配置成M樹的索引結構的方法，但是在其它實施例中可使用其它度量索引結構和用於構建相同方式的方法。例如，可使用優勢點樹(,vantage-point tree) 雖然已經詳細描述了依據實施例的設備和方法，但是在其它實施例中可實現變形。例如，雖然諸如覆蓋半徑或父對象和子對象之間距離的距離信息可被存儲在索引數據中，但是這樣的數據也可在運行時被計算出來。為了進ー步說明，雖然已經解釋了索引樹和它們的節點的示範性結構，但是任意適當的數據結構可被用於實現該索引樹。例如，在相關資料庫中該索引樹可被存儲成用戶定義的索引結構。在這種情況下，可提供表格，其包括文本字符串或音位字符串。可提供另一表格，其包括文本字符串對或音位字符串對之間的距離。為了進ー步說明，雖然使用諸如「在該索引結構中的對象」這樣的措辭已經描述了索引結構，但是像這樣的對象並不需要被結合到索引結構中。相反，該索引結構可包括指向該對象的標識符或指針，而不是該對象本身。為了進ー步說明，雖然在對位於距查詢對象固定捜索半徑內的對象的捜索的上下文中，或者在對k個最接近的鄰居的捜索的上下文中已經描述了相似性捜索，但是也可使用度量索引結構實現其它的相似性捜索。雖然在特定距離度量或特定應用的上下文中已經 描述了ー些搜索，諸如，對音位或文本字符串的捜索，但是本發明的實施例並不限於此。本發明的實施例可被用於車輛導航設備中。
權利要求
1.ー種使用索引結構(10 ；70)在導航設備資料庫中執行相似性捜索的方法，所述資料庫包括多個對象，所述索引結構(10 ；70)包括多個節點(11-17 ;71-75)， 所述方法包括 接收查詢對象(51)， 訪問所述索引結構(10;70)的節點(11-13 ;71-73)，所述節點與所述多個對象中的至少ー個對象(52，55，59，60)相關聯， 對於與所述節點(11-13 ；71-73)相關聯的所述至少一個對象(52，55，59，60)中的每個對象，分別確定所述查詢對象(51)和所述對象之間的距離(65，66)，所述距離(65，66)按照距離度量被分別確定，以及 基於所確定的距離(65，66)，選擇性地訪問所述索引結構(10;70)中的另ー個節點(12-17 ；72-75)。
2.如權利要求I所述的方法， 其中所述查詢對象(51)為音位字符串或文本字符串。
3.如權利要求2所述的方法， 其中所述接收所述查詢對象(51)包括接收文本輸入和執行文本到音位的轉換。
4.如權利要求I所述的方法， 所述索引結構(10 ；70)進ー步包括關於所述至少一個對象(52，55，59，60)和所述索引結構(10 ；70)中的其它對象之間距離的距離信息， 基於所述距離信息和所確定的距離(65 ;66)，選擇性地訪問所述其它節點(12-17;.72-75)。
5.如權利要求4所述的方法， 所述節點(11-13 ；71-73)與若干個對象(52，55)相關聯， 對於所述若干個對象(52，55)中的每ー個，所述距離信息包括，相應的對象(52，55)和與所述相應的對象(52 ；55)相關聯的所述索引結構(10 ；70)的子樹中包括的任意對象(59-64)之間的距離的上界(53, 56) ο
6.如權利要求4所述的方法， 其中所述查詢對象(51)為音位字符串或文本字符串，並且 其中所述接收所述查詢對象(51)包括接收文本輸入和執行文本到音位的轉換。
7.如權利要求I至6中的任一項所述的方法， 其中，基於所確定的距離￠5 ;66)，從所述相似性捜索中選擇性地剪除對象。
8.如權利要求I至6中的任一項所述的方法， 其中，所述確定距離出5;66)和選擇性地訪問另ー節點(12-17 ;72-75)，在其它節點(12-17 ；72-75)是所述索引結構(10 ；70)的葉節點(14-17 ;74，75)時終止。
9.如權利要求I至6中的任一項所述的方法， 其中，識別出根據所述距離度量確定的位於距所述查詢對象(51)預定的距離(58)內的所有對象。
10.如權利要求I至6中的任一項所述的方法， 其中，識別出整數k> I個對象，其代表根據所述距離度量確定的所述查詢對象(51)的k個最接近鄰居。
11.如權利要求10所述的方法， 其中，以基於所述查詢對象(51)和相應的被識別的對象之間的距離所確定的順序，輸出所述被識別的對象。
12.—種導航設備，包括 存儲設備(3)，其存儲用於包括多個對象的資料庫的索引結構(10;70)，所述索引結構(10 ；70)包括多個節點(11-17 ；71-75);以及 處理設備(2)，其被耦接到所述存儲設備(3)，所述處理設備(2)被配置成執行以下步驟，以執行對查詢對象(51)的相似性搜索， 訪問與所述多個對象中的至少ー個對象(52，55，59，60)相關聯的所述索引結構(10;70)的節點(11-13 ;71-73)， 根據距離度量，確定所述查詢對象(51)和所述至少一個對象(52，55，59，60)之間的距離(65,66)，以及 基於所確定的距離(65 ;66)，選擇性地訪問所述索引結構(10;70)的另ー個節點(12-17 ；72-75)。
13.如權利要求12所述的導航設備， 其中，所述處理設備(2)被配置成執行權利要求I至6中的任一項所述的方法。
14.ー種生成用於導航設備資料庫的度量索引結構(10;70;110)的方法，所述導航設備資料庫包括多個對象，所述方法包括生成所述索引結構的目錄節點(11-13 ；71-73 ;111，114)和生成所述索引結構的葉節點(14-17 ;74，75 ; 113，115，116)，所述目錄節點包括指向所述索引結構(10 ；70 ；110)的其它節點的指針。
其中，所述生成目錄節點(11-13 ；71-73 ;111，114)和葉節點(14-17 ;74，75 ;113，115，116)包括 對於多對所述對象，分別確定所述對象對的對象之間的距離，從而確定多個距離，所述距離是根據距離度量分別確定的，以及 基於所述多個距離，識別出將被包括在目錄節點(11-13 ;71-73 ;111，114)中的對象，和將被包括在葉節點(14-17 ;74 ;75 ;113，115，116)中的對象。
15.如權利要求14所述的方法， 其中，所述對象為音位字符串或文本字符串。
16.如權利要求14或15所述的方法，包括 將從所述多個距離中得出的距離信息存儲在所述目錄節點和/或葉節點中。
全文摘要
本發明提供了一種在導航設備資料庫中執行相似性搜索的方法，其使用了度量索引結構。該索引結構包括多個節點。當接收到查詢對象(51)時，訪問與至少一個對象(52，55，59，60)相關聯的索引結構的節點。按照距離度量確定查詢對象(51)和至少一個對象(52，55，59，60)之間的距離(65，66)。基於所確定的距離，選擇性地訪問該索引結構中的另一個節點。
文檔編號G06F17/30GK102693266SQ20121004314
公開日2012年9月26日 申請日期2012年2月23日 優先權日2011年2月23日
發明者A.普裡雅克欣, J.威爾舍, P.庫納斯 申請人:哈曼貝克自動系統股份有限公司