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

有效

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

諸如超級重對數等概率計數結構可以在有關選擇的一組列中的每一個的表格掃描期間形成。所述列可以基于初始相關性估計選擇，所述初始相關性估計可能基于所述各自列的數據類型。列的交集或并集的估計的基數可以基于所述概率數據結構的交集形成。聯結路徑可以基于所述列的交集或并集的所述估計的基數確定。

相關申請的交叉引用

本申請要求于2014年12月22日提交的美國專利申請No.14/578,841的利益，所述美國專利申請的公開內容以引用的方式整體并入本文中。

背景技術

數據倉庫和在線分析處理(“OLAP”)系統可能包括允許分析查詢的自動生成的各種工具。在一些情況下，這些工具可能依賴于用戶提供有關將分析的數據的結構的各種細節。然而，提供該信息可能是參與的過程。在其它情況下，工具可以使用明確定義的模式信息諸如主鍵和外鍵關系自動地生成分析查詢。然而，即使未明確定義，在分析上有用的關系可能仍然存在。可能還存在分析工具的用戶不知道的分析上有用的關系。

附圖說明

當結合附圖進行閱讀時，以下詳述可以更好地理解。出于說明的目的，附圖中示出本公開的方面的各種示例，然而本發明并不限于公開的特定方法和手段。

圖1是描繪用于通過使用概率計數結構以估計兩個列內的字段重合從而識別聯結關系的系統和過程的實施方案的框圖。

圖2是描繪基于使用基數估計計算的估計的字段重合對兩個列之間的聯結路徑進行識別的框圖。

圖3描繪用于計算概率計數結構的交集和并集的過程。

圖4描繪用于使用概率計數結構識別聯結路徑的過程的實施方案。

圖5描繪用于識別多個列中的兩個之間的聯結路徑的過程的實施方案。

圖6是描繪可以實踐本公開的方面的計算環境的實施方案的框圖。

圖7是描繪可以實踐本公開的方面的計算系統的實施方案的框圖。

具體實施方式

本公開的方面可以被采用以識別可以用于在事務數據上執行分析操作的聯結關系。聯結關系可以用于各種目的，諸如用于生成分析查詢。在一些情況下，聯結關系可以用于生成可用于執行分析的分層。

本公開的實施方案可以利用諸如超級重對數(hyperloglog)等概率數據結構來識別列之間的聯結關系。實施方案可以為每一潛在相關的列生成概率數據結構，其中初始相關性估計可能基于諸如共同的數據類型等因素。實施方案可以基于兩個或多個概率數據結構的交集或基于交集的并集估計列值之間的重合。然后可以將列值之間的重合用作用于識別列之間的聯結關系的依據。

概率數據結構可能包括與諸如近似法或隨機化等各種統計技術有關的那些結構，以估計集合的基數。數據集的基數可能指代集合內的截然不同的值的數量。概率數據結構的示例包括與超級重對數、重對數(loglog)以及布隆過濾器技術有關的那些。術語超級重對數、重對數、最小哈希以及布隆過濾器可以用于指代對應于所述技術的結構。

概率數據結構可能包括若干桶。每一桶可能對應于數據流的細分并且可能包含有關細分內的估計的基數的信息。所述數據流可以基于多種準則進行細分。在一些情況下，所述細分可能是基本上隨機的，在這種情況下桶可能對應于數據集的基本上隨機的部分。這例如當數據流使用某些哈希函數進行細分時可能是如此情況。在其它情況下，細分可能基于諸如鍵范圍等非隨機準則。

通常來說，可以通過掃描大的(且在一些情況下非常大的)數據集獲得數據流。概率數據結構可以被用于以存儲器使用高效的方式估計大數據集的基數。然而，基數估計的準確度可能取決于數據流中的細分的數量和概率數據結構中的對應桶的數量。