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

在審

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

1.一種高維數據快速搜索方法，其特征在于：該方法采用如下步驟實現：

1).從根開始計算，根節點作為父節點，棧清空，DIST取最大值，記數器CNT 置為 0，其中DIST表示兩個向量的距離平方；

2). 取出父節點指向的當前向量對應的分類維s和中間値MEAN, 計算Y(s)跟MEAN差的平方SQRT，其中Y表示查詢向量，s為當前節點的子維數；

3). 比較DIST與SQRT的大小，如果DIST大于SQRT，則進入以下步驟：

3.1).計算Y(s)與當前向量的距離平方TMP，如果TMP小于DIST，則DIST= TMP；

3.2).計數器CNT加1，如果超過指定數，跳轉至步驟7)；

4). 比較Y(s)與MEAN的大小，

4.1).如果Y(s)大于MEAN， 則進入以下步驟：

4.1a).判斷右孩子是否為空，如果右孩子非空，同時DIST大于SQRT，則右孩子進棧；

4.1b).判斷左孩子是否為空，如果左孩子非空，則左孩子進棧，否則跳轉至步驟5)；

4.2).所述步驟4.1)中如果條件不滿足則進入以下步驟：

4.2a).判斷左孩子是否為空，如果左孩子非空，同時DIST大于SQRT，則左孩子進棧；

4.2b).判斷右孩子是否為空，如果右孩子非空，則右孩子進棧，否則跳轉至步驟5)；

5)．按照先進后出FILO方式進行出棧操作，生成新的父節點；

6). 判斷棧是否為空，如果棧空則跳轉至步驟7)，否則跳轉至步驟2)；

7). 搜索中止，獲得搜索結果。

2.根據權利要求1所述的一種高維數據快速搜索方法，其特征在于所述步驟4.1)和步驟4.2)順序不可改變。

3.根據權利要求1所述的一種高維數據快速搜索方法，其特征在于：從步驟1)到步驟7)適用于KD樹左分支大，右分支小的情況，如果右分支比左分支大，只要在步驟4.1)包含的步驟和步驟4.2)包含的步驟中，左孩子與右孩子互換即可。

4.根據權利要求1所述的一種高維數據快速搜索方法，其特征在于所述計數器CNT可以設置為任何固定值作為終止條件。