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

有效

• 申請號: 200980136125.4
• 申請日: 2009-07-23
• 公開（公告）號: CN102160034A
• 公開（公告）日: 2011-08-17
• 發明（設計）人: 羅素·托希奧·中野
• 申請（專利權）人: 那哈瓦有限公司
• 主分類號: G06F9/44
• 分類號: G06F9/44;G06F15/00;G06F17/16
• 代理公司: 北京安信方達知識產權代理有限公司 11262
• 代理人: 李冬梅;鄭霞

1.一種計算機實現的方法，包括：

(a)輸入向量x；

(b)輸入向量y；

(c)確定是否所述向量x＝0和所述向量y＝0；及

(d)如果是，則

(d1)返回零向量作為結果；

(d2)將所述結果存儲在所述計算機上的硬件中；

(d3)將所述存儲結果變換為圖形化的表示；及

(d4)將所述圖形化的表示顯示給用戶；

(e)如果否，則

(f)確定是否所述向量x＝0；及

(g)如果是，則

(g1)返回向量y作為結果；

(g2)將所述結果存儲在所述計算機上的硬件中；

(g3)將所述存儲結果變換為圖形化的表示；及

(g4)將所述圖形化的表示顯示給用戶；

(h)如果否，則

(i)確定是否所述向量y＝0；及

(j)如果是，則

(j1)返回向量x作為結果；

(j2)將所述結果存儲在所述計算機上的硬件中；

(j3)將所述存儲結果變換為圖形化的表示；及

(j4)將所述圖形化的表示顯示給用戶；

(k)如果否，則

(l)計算單側Jacobi變換：

(l1)u＝c*x-s*y

(l2)v＝s*x+c*y

其中

g＝<x，y>

a＝<x，x>

b＝<y，y>

w＝(b-a)/(2*g)

t＝sign(q)/(abs(q)+sqrt(1+w^2))

c＝1/sqrt(t^2+1)

s＝c*t

(m)確定是否((b-a)*((s*s)-(c*c)))-4*c*s*g＞0；及

(n)如果是，則

(n1)返回向量u作為結果；

(n2)將所述結果存儲在所述計算機上的硬件中；

(n3)將所述存儲結果變換為圖形化的表示；以及

(n4)將所述圖形化的表示顯示給用戶；

(o)如果否，則

(o1)返回向量v作為結果；

(o2)將所述結果存儲在所述計算機上的硬件中；

(o3)將所述存儲結果變換為圖形化的表示；及

(o4)將所述圖形化的表示顯示給用戶。

2.一種計算機實現的用“initialGuess”表示的方法，包括

(a)輸入用S表示的向量集合；

(b)確定所述S是否為空；及

(c)如果是，則

(c1)返回null作為結果；

(c2)將所述結果存儲在所述計算機上的硬件中；

(c3)將所述存儲結果變換為圖形化的表示；及

(c4)將所述圖形化的表示顯示給用戶；

(d)如果否，則

(e)確定所述S是否含有一個向量；及

(f)如果是，則

(f1)返回所述一個向量作為結果；

(f2)將所述結果存儲在所述計算機上的硬件中；

(f3)將所述存儲結果變換為圖形化的表示；及

(f4)將所述圖形化的表示顯示給用戶；

(g)如果否，則

(h)確定所述S是否含有兩個向量；及

(i)如果是，則

(i1)將所述兩個向量變換為優化結果；

(i2)將所述結果存儲在所述計算機上的硬件中；

(i3)將所述存儲結果變換為圖形化的表示；及

(i4)將所述圖形化的表示顯示給用戶；

(j)如果否，則

(k)將S中的向量任意分成兩半，H1和H2；

(l)使用所述H1作為輸入向量S來調用“initialGuess”的另一個實例并返回結果r1；

(m)使用所述H2作為輸入向量S來調用“initialGuess”的另一個實例并返回結果r2；

(n)將所述結果r1和所述結果r2變換為優化結果；及

(o)將所述結果存儲在所述計算機上的硬件中；

(p)將所述存儲結果變換為圖形化的表示；及

(q)將所述圖形化的表示顯示給用戶。

3.一種計算機實現的方法，包括：

(a)輸入m個不同的非零向量，該m個不同的非零向量表示為集合S；

(b)在所述集合S上調用InitialGuess程序，并將返回的結果表示為u.0；

(c)定義矩陣A，其中第i列是來自所述S的第i個向量；

(d)初始化表示為k的迭代計數器為0值；

(e)計算表示為d的分裂值，其中d＝A.transpose*A*u.k；

(f)確定是否所述分裂值d給出了S的可接受的劃分；及

(g)如果是，則

(g1)將所述分裂值d存儲在所述計算機上的硬件中；

(g2)將所述存儲的分裂值d變換為一個或多個圖形化的表示；及

(g3)將所述一個或多個圖形化的表示顯示給用戶；

(h)如果否，則

(h1)計算u.k+1＝d/sqrt(<d，d>)；

(h2)將k的所述值增加1；及

(h3)回到(e)。