[發(fā)明專利]用于在大索引樹中使用的劃分高維向量的方法和裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 200980136125.4
• 申請(qǐng)日: 2009-07-23
• 公開（公告）號(hào): CN102160034A
• 公開（公告）日: 2011-08-17
• 發(fā)明（設(shè)計(jì)）人: 羅素·托希奧·中野
• 申請(qǐng)（專利權(quán)）人: 那哈瓦有限公司
• 主分類號(hào): G06F9/44
• 分類號(hào): G06F9/44;G06F15/00;G06F17/16
• 代理公司: 北京安信方達(dá)知識(shí)產(chǎn)權(quán)代理有限公司 11262
• 代理人: 李冬梅;鄭霞

相關(guān)的申請(qǐng)

本專利申請(qǐng)要求2008年7月24日提交的、題目為“Method?And?Apparatus?For?Partitioning?High-Dimension?Vectors?For?Use?In?A?Massive?Index?Tree”的美國(guó)臨時(shí)申請(qǐng)序列號(hào)61/083404的優(yōu)先權(quán)，其與本申請(qǐng)是同一發(fā)明人，且由此其全部?jī)?nèi)容通過引用在此并入。本專利申請(qǐng)要求2009年7月22日提交的、題目為“Method?And?Apparatus?For?Partitioning?High-Dimension?Vectors?For?Use?In?A?Massive?Index?Tree”的美國(guó)申請(qǐng)序列號(hào)12/507271的優(yōu)先權(quán)，其與本申請(qǐng)是同一發(fā)明人，且由此其全部?jī)?nèi)容通過引用在此并入。

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

本發(fā)明涉及數(shù)據(jù)集。更具體地，本發(fā)明涉及用于在大索引樹中使用的劃分高維向量的方法和裝置。

背景技術(shù)

當(dāng)計(jì)算不能方便地由諸如數(shù)字或字母串的總排列表示的項(xiàng)的相似度時(shí)，產(chǎn)生了高維向量。這提出了問題。例如，在一種方法中，使用從諸如FFT和DCT的波譜技術(shù)得到的高維向量中獲取的“特征(signature)”，能夠計(jì)算圖像的相似度[Celentano?1997(@inproceedings{celentano97fftbased，author＝“Augusto?Celentano?and?Vincenzo?Di?Lecce”，title＝“{FFT}-Based?Technique?for?Image-Signature?Generation”，booktitle＝“Storage?and?Retrieval?for?Image?and?Video?Databases({SPIE})”，pages＝“457-466”，year＝“1997”，url＝“citeseer.ist.psu.edu/597114.html”})]。可以通過梅爾頻率聲譜系數(shù)(MFCC)計(jì)算歌曲或片段中的音樂(幀)的短節(jié)之間的匹配性[Logan?2001(@misc{logan01?contentbased，author＝“B.Logan?and?A.Salomon”，title＝“A?content-based?music?similarity?function”，text＝“B.Logan?and?A.Salomon.A?content-based?music?similarity?function.Technical?report，Compaq?Cambridge?Research?Laboratory，June?2001.”，year＝“2001”，url＝“citeseer.ist.psu.edu/logan01?contentbased.html”})]，其通過離散余弦變換(DCT)得到。存儲(chǔ)在基因組數(shù)據(jù)庫(kù)中的染色體之間的相似度能夠通過將核苷酸系列表示為從馬爾可夫轉(zhuǎn)換模型獲得的高維稀疏向量來計(jì)算[Nakano?2004(Russell?Nakano，“Method?and?apparatus?for?fundamental?operations?on?token?sequences：computing?similarity，extracting?terms?values，and?searching?efficiently”，U.S.Patent?Application，20040162827，August?19，2004.)]。

附圖說明

本發(fā)明通過實(shí)例進(jìn)行說明，且不限于附圖中的圖，附圖中；

圖1示出了其中可實(shí)現(xiàn)本發(fā)明的方法和裝置的網(wǎng)絡(luò)環(huán)境；

圖2是其中可實(shí)現(xiàn)本發(fā)明的某些實(shí)施方式和其中可使用本發(fā)明的某些實(shí)施方式的計(jì)算機(jī)系統(tǒng)的框圖；

圖3示出了本發(fā)明的一個(gè)實(shí)施方式，其示出了用于平衡二叉樹的術(shù)語(yǔ)；

圖4示出了具有兩個(gè)向量輸入和一個(gè)向量輸出的“優(yōu)化(majorize)”輔助函數(shù)的一個(gè)實(shí)施方式；

圖5示出了“initialGuess”方法的一個(gè)實(shí)施方式，其展示了作為向量集合的輸入和作為分裂向量猜測(cè)的輸出；

圖6示出了具有多個(gè)向量的輸入和一個(gè)分裂向量的輸出的計(jì)算分裂向量方法的一個(gè)實(shí)施方式。

具體實(shí)施方式