[發(fā)明專利]基于歐氏距離的度量空間索引構(gòu)建方法、裝置及相關(guān)設(shè)備

在審

• 申請(qǐng)?zhí)枺?/td>: 202110689178.1
• 申請(qǐng)日: 2021-06-22
• 公開（公告）號(hào): CN113407786A
• 公開（公告）日: 2021-09-17
• 發(fā)明（設(shè)計(jì)）人: 毛睿;陳家穎;王毅;秦建斌;劉剛;陸克中;陸敏華;陳倩婷
• 申請(qǐng)（專利權(quán)）人: 深圳大學(xué)
• 主分類號(hào): G06F16/901
• 分類號(hào): G06F16/901;G06F16/9032;G06K9/62
• 代理公司: 深圳市精英專利事務(wù)所 44242
• 代理人: 馮筠

本發(fā)明公開了基于歐氏距離的度量空間索引構(gòu)建方法、裝置及相關(guān)設(shè)備，方法包括獲取原始數(shù)據(jù)集，根據(jù)原始數(shù)據(jù)集的類型，通過維度估計(jì)算法估算得到原始維度；根據(jù)原始維度，通過支撐點(diǎn)選取算法選取映射支撐點(diǎn)，映射支撐點(diǎn)的個(gè)數(shù)大于原始維度的數(shù)值；通過距離函數(shù)和映射支撐點(diǎn)將度量空間中的原始數(shù)據(jù)集映射到支撐點(diǎn)空間；通過降維算法對(duì)支撐點(diǎn)空間中的數(shù)據(jù)進(jìn)行降維；根據(jù)降維后的支撐點(diǎn)空間，通過歐氏距離近似最近鄰算法構(gòu)建索引。通過歐氏距離的近似最近鄰算法構(gòu)建基于歐氏距離的度量空間索引，在檢索的時(shí)候可通過該索引進(jìn)行檢索，將原本復(fù)雜的距離計(jì)算簡(jiǎn)化為了人們熟知且計(jì)算較為簡(jiǎn)單的歐氏距離的計(jì)算，提高了準(zhǔn)確度和查詢速度。

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)處理技術(shù)領(lǐng)域，尤其涉及一種基于歐氏距離的度量空間索引構(gòu)建方法、裝置及相關(guān)設(shè)備。

背景技術(shù)

在高維數(shù)據(jù)下，由于維數(shù)災(zāi)難問題，傳統(tǒng)的精確搜索方法如樹狀索引性能會(huì)急劇下降，甚至?xí)蝗缇€性掃描。因此，近似最近鄰查找的方法便誕生了，近似最近鄰查找方法的搜索結(jié)果并不一定是距離搜索點(diǎn)q最近的那個(gè)數(shù)據(jù)p，但一定離最近的數(shù)據(jù)p很近，即允許存在誤差。

在非度量空間的近似最近鄰算法中，這些算法大多只針對(duì)歐氏距離，在歐氏距離上有很好的性能，但無法擴(kuò)展到其它距離函數(shù)，因?yàn)檫@些搜索算法都是針對(duì)歐氏距離等特定的距離函數(shù)所涉及的。

度量空間的近似最近鄰算法的研究很少，目前了解到的有metric index，這種索引方法根據(jù)數(shù)據(jù)到支撐點(diǎn)的距離，為數(shù)據(jù)構(gòu)建基于支撐點(diǎn)距離大小順序的前綴樹進(jìn)行索引。但這種方法仍然無法避免傳統(tǒng)樹狀索引算法的弊端，在選取的支撐點(diǎn)數(shù)目比較多的情況下會(huì)不如線性掃描。

由此需要一種基于壓縮和歐氏距離的度量空間近似最近鄰查找方法，使數(shù)據(jù)在映射到支撐點(diǎn)空間后，用歐氏距離的近似最近鄰算法進(jìn)行查找，擴(kuò)展所有基于歐氏距離的算法的適用距離函數(shù)，提高準(zhǔn)確度和查詢速度。

發(fā)明內(nèi)容

本發(fā)明的目的是提供一種基于歐氏距離的度量空間索引構(gòu)建方法、裝置及相關(guān)設(shè)備，旨在解決現(xiàn)有技術(shù)中，查詢速度過慢且準(zhǔn)確度低的問題。

第一方面，本發(fā)明實(shí)施例提供了基于歐氏距離的度量空間索引構(gòu)建方法，包括：

獲取原始數(shù)據(jù)集，根據(jù)所述原始數(shù)據(jù)集的類型，通過維度估計(jì)算法估算得到原始維度；

根據(jù)所述原始維度，通過支撐點(diǎn)選取算法選取映射支撐點(diǎn)，所述映射支撐點(diǎn)的個(gè)數(shù)大于所述原始維度的數(shù)值；

通過距離函數(shù)和所述映射支撐點(diǎn)將原始數(shù)據(jù)集映射為支撐點(diǎn)空間；

通過降維算法對(duì)支撐點(diǎn)空間中的數(shù)據(jù)進(jìn)行降維；

根據(jù)降維后的支撐點(diǎn)空間，通過歐式距離計(jì)算映射到支撐點(diǎn)空間后數(shù)據(jù)之間的相似程度，并通過歐氏距離近似最近鄰算法構(gòu)建索引。

第二方面，本發(fā)明實(shí)施例提供了基于歐氏距離的度量空間索引構(gòu)建裝置，包括：

估算維度單元，用于獲取原始數(shù)據(jù)集，根據(jù)所述原始數(shù)據(jù)集的類型，通過維度估計(jì)算法估算得到原始維度；

支撐點(diǎn)選取單元，用于根據(jù)所述原始維度，通過支撐點(diǎn)選取算法選取映射支撐點(diǎn)，所述映射支撐點(diǎn)的個(gè)數(shù)大于所述原始維度的數(shù)值；

映射單元，用于通過距離函數(shù)和所述映射支撐點(diǎn)將原始數(shù)據(jù)集映射為支撐點(diǎn)空間；

降維單元，用于通過降維算法對(duì)支撐點(diǎn)空間中的數(shù)據(jù)進(jìn)行降維；

索引構(gòu)建單元，用于根據(jù)降維后的支撐點(diǎn)空間，通過歐式距離計(jì)算映射到支撐點(diǎn)空間后數(shù)據(jù)之間的相似程度，并通過歐氏距離近似最近鄰算法構(gòu)建索引。