[發明專利]經由基數估計的有效聯結路徑確定

有效

• 申請號: 201580070304.8
• 申請日: 2015-12-21
• 公開（公告）號: CN107251017B
• 公開（公告）日: 2020-09-25
• 發明（設計）人: 阿努拉格·溫德拉斯·古普塔;蒂莫西·安德魯·拉斯;斯里尼瓦桑·孫達爾·拉加萬;桑托什·凱克
• 申請（專利權）人: 亞馬遜技術有限公司
• 主分類號: G06F16/27
• 分類號: G06F16/27
• 代理公司: 中科專利商標代理有限責任公司 11021
• 代理人: 倪斌

1.一種用于識別事務數據中的分析關系的系統，所述系統包括：

一個或多個計算節點，其維持包括多個行的表格；

上面存儲有計算機可讀指令的一個或多個存儲器，所述計算機可讀指令當由計算設備執行時引起所述系統至少：

選擇所述多個行中的第一列和第二列，其中至少部分基于所述第一列與所述第二列之間的第一相關性估計選擇所述第一列和所述第二列；

至少部分基于所述多個行中的第一多個字段形成第一超級重對數，所述第一多個字段對應于所述第一列；

至少部分基于所述多個行中的第二多個字段形成第二超級重對數，所述第二多個字段對應于所述第二列；

計算所述第一超級重對數和所述第二超級重對數的交集；以及

至少部分基于所述第一多個字段中的字段與所述第二多個字段中的字段之間的第二重合估計識別所述第一列與所述第二列之間的聯結路徑，所述第二重合估計至少部分基于所述交集。

2.如權利要求1所述的系統，其進一步包括上面存儲有計算機可讀指令的一個或多個存儲器，所述計算機可讀指令當由所述一個或多個計算節點執行時引起所述系統至少：

基于所述第一列和所述第二列共同的數據類型形成所述第一相關性估計。

3.如權利要求1所述的系統，其進一步包括上面存儲有計算機可讀指令的一個或多個存儲器，所述計算機可讀指令當由所述一個或多個計算節點執行時引起所述系統至少：

通過至少將有關所述第一列和所述第二列的所述第二重合估計與有關兩個或多個額外列的額外重合估計進行比較來識別所述聯結路徑。

4.如權利要求1所述的系統，其進一步包括上面存儲有計算機可讀指令的一個或多個存儲器，所述計算機可讀指令當由所述一個或多個計算節點執行時引起所述系統至少：

通過至少從所述第一超級重對數和所述第二超級重對數的并集減去所述第一超級重對數和所述第二超級重對數的所述交集來形成所述第二重合估計。

5.如權利要求1所述的系統，其進一步包括上面存儲有計算機可讀指令的一個或多個存儲器，所述計算機可讀指令當由所述一個或多個計算節點執行時引起所述系統至少：

通過至少執行所述多個行的第一掃描來形成多個超級重對數；以及

通過至少執行所述多個行的第二掃描來形成所述第一超級重對數，其中所述第一超級重對數的大小大于在所述第一掃描期間形成的所述多個超級重對數中的超級重對數的大小。

6.一種用于識別事務數據中的分析關系的系統，其包括：

一個或多個處理器；以及

一個或多個存儲器，所述存儲器上存儲有指令，所述指令當由一個或多個計算設備執行時引起所述一個或多個計算設備至少：

至少部分基于多個行中的第一多個字段形成第一概率計數結構，所述第一多個字段對應于所述多個行中的第一列；

至少部分基于所述多個行中的第二多個字段形成第二概率計數結構，所述第二多個字段對應于所述多個行中的第二列；

計算所述第一概率計數結構和所述第二概率計數結構的交集；以及

至少部分基于所述第一多個字段中的字段與所述第二多個字段中的字段之間的重合估計識別所述第一列與所述第二列之間的聯結路徑，所述重合估計至少部分基于所述交集。

7.如權利要求6所述的系統，其包括進一步的指令，所述指令當由所述一個或多個計算設備執行時引起所述一個或多個計算設備至少：

至少部分基于所述第一列和所述第二列共同的數據類型選擇所述第一列和所述第二列以用于形成所述第一概率計數結構和所述第二概率計數結構。

8.如權利要求6所述的系統，其中所述第一概率計數結構和所述第二概率計數結構各自包括重對數、布隆過濾器或最小哈希中的至少一個。

9.如權利要求8所述的系統，其中所述重對數是超級重對數。