[發明專利]用于近似查詢的長序列數據降維方法

無效

• 申請號: 200710303987.4
• 申請日: 2007-12-24
• 公開（公告）號: CN101196921A
• 公開（公告）日: 2008-06-11
• 發明（設計）人: 宋國杰;謝昆青
• 申請（專利權）人: 北京大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京市商泰律師事務所
• 代理人: 毛燕生

1.一種面向近似性查詢的長序列數據降維方法，其特征是：包括如下步驟：

步驟一、利用序列嵌入技術，把一個輸入的長序列數據轉化為一棵序列嵌入樹；

步驟二、從序列嵌入樹中，從每一層抽取出由字符序列所組成的字符多集集合，并利用所提出的距離收斂性質，構造多集空間所對應的主成份；

步驟三、在所提出的多集主成份和距離收斂性質的基礎上，構造一個與多集主成份對應的索引結構；

步驟四、基于所提出索引結構基礎上，提出序列距離的雙邊界距離上界和下界原理，并提出相應的近似性查詢算法，完成基于序列降維的長序列高效查詢。

2.根據權利要求1所述的一種面向近似性查詢的長序列數據降維方法，其特征是：對于一個序列S，標記為ET₁(S)，通過一次迭代可以被分解為6個塊，每個塊由2到3個字符組成，標記為ET₁(S)[cs，ce]，cs和ce分別表示該塊的開始和結束字符；每個塊ET₁(S)[cs，ce]通過一個一對一的Karp-Miller哈希函數映射為一個元素；因此，在ET₁(S)中所有塊經哈希映射所得到的元素所組成的序列得到一個新的序列，標記為ET₂(S)；利用同樣的原理，重復上述過程，可以得到最終的序列嵌入樹。

3.根據權利要求1所述的一種面向近似性查詢的長序列數據降維方法，其特征是：所述步驟二，包括如下步驟：

步驟21、把序列嵌入樹中的所有字符組成一個多集集合，標記為T(S)；

步驟22、把多集集合T(S)按照其元素在嵌入樹中所述的層次，分拆成為h(h為嵌入樹的高度)個子多集集合T_i(S)，T_i(S)中的每個元素與嵌入樹中第i層的每個元素一一對應，表示為{T_i(S)|T_i(S)T(S)，i≤h}；每個T_i(S)構成序列S的第i個主成份；

步驟23、利用得到的多集主成份，構造出支持序列降維的距離收斂性質。

4.根據權利要求3所述的一種面向近似性查詢的長序列數據降維方法，其特征是：所述步驟23，包括：

基于多集主成份的距離收斂性質定義如下：對于任意給定的兩個序列S₁和S₂，和任意兩個整數i和j，i≤j，滿足如下性質：

d^e(Ti(S1),Ti(S2))≤d^e(Ti(S1),Ti(S2))]]>

其中，Ti(S)=Uk=1iTi(S),]]>d^e(Ti(S1),Ti(S2))card(Ti(S1)eTi(S2))card(Ti(S1)UTi(S2)).]]>