[發明專利]一種高維數據快速搜索方法

在審

• 申請號: 201910361033.1
• 申請日: 2019-04-30
• 公開（公告）號: CN111858578A
• 公開（公告）日: 2020-10-30
• 發明（設計）人: 趙風光
• 申請（專利權）人: 上海聞通信息科技有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/245;G06F16/28
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明提供一種高維數據快速搜索方法，包括如下步驟：1）從根開始計算，根節點作為父節點，棧清空，DIST取最大值，記數器CNT置為0；2).取出父節點指向的當前向量對應的分類維s和中間値MEAN,計算Y(s)跟MEAN差的平方SQRT；3).比較DIST與SQRT的大?。?).比較Y(s)與MEAN的大?。?)．按照先進后出FILO方式進行出棧操作，生成新的父節點；6).判斷棧是否為空；7).搜索中止，獲得搜索結果。本發明所給出這種能夠自動生成優先序列的查找模型和方法，解決了BBF方式存在的最優排序耗時的問題，可以獲得更高的計算性價比，為大數據高維搜索提供了全新的更有效的解決方案。

技術領域

本發明屬于大數據，計算機軟件和信息技術處理領域，對高維數據搜索計算提供快速計算模型，以實現數據的快速計算搜索的方法。

背景技術

對一個規模為n的一維數組，遍歷型數據查找的計算量是O(n)，通過排序，可以獲得O（log(n)）規模的查找計算量，因此稱為快速查找。一旦數組維數超過1，一維情況的快速查找就無法實現了。不過，人們按照一維快速查找思路，提出了KD樹的多維建模方法，也可以實現類似一維的查找算法，有時也能接近O（log(n)）的計算量。遺憾的是，這種方法對于數據規模巨大的數據集是有效的，而且數據規模是維數的指數冪次量級，但大部分應用往往到不了這個規模，計算效率也就變得低效了，甚至比遍歷計算還差。

如果使用大寫字母X，Y表示一個維數為d的數組，也稱向量。兩個向量的距離用歐氏距離定義為

D(X,Y)= （1）

其中 X=(x₁,x₂,...,x_d)，Y=(y₁,y₂,...,y_d)。

對于一個向量集，我們用X₁,X₂,...,X_n表示n個數據的d維向量數組，高維數據搜索的目標是對一個目標向量Y尋找一個向量集中最近的數，也即滿足

（2）

這個問題的求解很簡單，就是逐一計算Y與每個向量X_i的距離，取最小的那個。這種遍歷型計算也稱為暴力計算，其計算量是O(n)級的。當維數d和集合數目n很大時，計算量是很可觀的。為了降低計算量，加快搜索速度，人們提出了KD樹的平衡二叉樹數據結構。把向量集X₁,X₂,...,X_n存貯為二叉樹的節點，然后通過尋求二叉樹的葉節點，對（2）實現快速計算，這種計算，不需要比較向量集的所有點，從而實現數據的快速查找。

二叉樹的構造，通過計算各維向量的均方差，找出方差最大的那個子維數，作為當前維，按這個子維排序找到最中間向量，作為根節點，然后把向量集從中間向量分成左右兩個子集，再把每個子集當成集合各自繼續按上述方法劃分，形成下級節點，直到子集只剩一個元素，成為葉節點。最終形成平衡二叉樹。

上述二叉樹的經典搜索方法，對于查詢向量Y，從樹的根節點開始，根據當前節點的子維數s判斷，如果Y(s)大于中間變量，走左分支，否則走右分支，直到葉節點結束。然后從葉節點開始向上回溯，并根據回溯結果，進入其他分支。這種經典計算，通過分維比較，找到一個接近最優的解，表面看省去很多距離計算，但它浪費了中間部分的很多關鍵信息。當數據向量集數目不大，效率很差，甚至比暴力計算還慢。為此，LOWE提出了一種搜索算法，稱為BBF，改進了這種經典回溯法，在從根到葉的回溯過程中構造一個優先序列，每次回溯都不斷調整這個優先序列，由于豐富了中間信息，效果比經典方法更快，特別對于中等數據集，BBF搜索成為最好的搜索技術之一，但是盡管BBF對優先序列的排序用了快速堆棧技術，但維護一個堆棧優先級也是很耗計算成本的，限制了它在某些方面的應用。

發明內容