[發明專利]用于基數估計的方法、裝置、電子設備及存儲介質

在審

• 申請號: 202110263644.X
• 申請日: 2021-03-11
• 公開（公告）號: CN112966006A
• 公開（公告）日: 2021-06-15
• 發明（設計）人: 張貴川
• 申請（專利權）人: 北京明略昭輝科技有限公司
• 主分類號: G06F16/2455
• 分類號: G06F16/2455
• 代理公司: 北京康盛知識產權代理有限公司 11331
• 代理人: 李欣芮

本申請涉及計算機軟件技術領域，公開了一種用于基數估計的方法，接收由一個或多個初始規則組成的基數估計規則；調用所述基數估計規則中涉及的各所述初始規則關聯的計數器，所述計數器基于超對數計數HLLC算法生成，每個計數器對應數據為基于其對應的初始規則過濾后的數據；基于所述基數估計規則結合調用的所述計數器生成基數估計結果并執行基數估計結果輸出。在實時的、萬億級或無限量基數估計場景下，由于對需要進行基數估計的數據，預先使用HLLC算法進行初始基數估計，得到多個計數器，在接收到用戶輸入的查詢條件，需要進行基數估計時，可以根據基數估計規則調用預先生成的計數器進行計算，從而可以滿足計數量和實時性的需求。

技術領域

本申請涉及計算機軟件技術領域，例如涉及一種用于基數估計的方法、裝置、電子設備及存儲介質。

背景技術

在基數估計場景中，常常需要支持實時，即亞秒級別的基數估計。這樣的實時的基數估計場景下，目前所有的方法中普遍使用超對數計數(HyperLogLog Counting，HLLC)算法作為估計算法。但是基于HLLC算法實現的計數器對于少量的數據可以實現實時估算，對于億萬級或無限量基數估計場景，使用一個基于HLLC算法實現的計數器，很難及時的完成基數估計。

如何在實時的、萬億級或無限量基數估計場景下，解決基數估計問題，成為亟需解決的問題。

發明內容

為了對披露的實施例的一些方面有基本的理解，下面給出了簡單的概括。所述概括不是泛泛評述，也不是要確定關鍵/重要組成元素或描繪這些實施例的保護范圍，而是作為后面的詳細說明的序言。

本公開實施例提供一種用于基數估計的方法、裝置、電子設備及存儲介質，以解決在實時的、萬億級或無限量基數估計場景下，解決基數估計問題。

本公開實施例提供一種用于基數估計的方法，包括：

接收用戶輸入的查詢條件；

從所述查詢條件中提取基數估計規則，所述基數估計規則為N個初始規則之間的計算關系，N為正整數；

從預生成的W個基于超對數計數HLLC算法生成的計數器中，調用各初始規則對應的計數器，W為正整數；

基于所述基數估計規則結合調用的計數器生成基數估計結果；

將所述基數估計結果作為查詢結果輸出。

在一些實施方式中，所述計算關系中存在相交關系。

在一些實施方式中，基于所述基數估計規則結合調用的計數器生成基數估計結果，包括：

對所述基數估計規則進行等價轉換，轉換為所述計算關系中無相交關系的等價規則；

使用所述等價規則對調用的所述計數器進行基數估計生成基數估計結果。

在一些實施方式中，按下述方式對所述基數估計規則進行等價轉換：

其中，A為初始規則，n為大于1的整數，k為大于1的整數。

在一些實施方式中，所述將所述基數估計結果作為查詢結果輸出之前，還包括：

確定所述等價規則的計算關系中基數估計結果最大的第一合并關系；

獲取所述第一合并關系對應的誤差；

將所述第一合并關系對應的誤差作為當前基數估計規則的誤差，對所述基數估計結果進行誤差消減。

在一些實施方式中，所述第一合并關系對應的誤差err基于如下公式進行確定：

，其中∈為HLLC算法的誤差。