一种大数据多区间查询条件下的基数估计方法及装置

摘要

本发明涉及一种大数据多区间查询条件下的基数估计方法及装置，包括以下步骤：按照数值属性对大数据预先划分成多个分区；建立树形索引结构，每个分区作为树形索引结构的一个节点；获取待写入树形索引结构的数据源，对支持区间查询条件的数据源进行倒排索引处理；将经过倒排索引处理的数据源写入树形索引结构中的节点内，将数据源的相应部分分别写入数据文件及基数估算器内；根据区间查询条件在树形索引结构中查询满足区间查询条件的节点，得到节点中的基数估算器，对基数估算器进行逻辑处理，得到基数估算值。本发明通过降低数据的计算精度提高基数统计效率，在任意多区间查询条件下，具备较高的查询效率，使用了大数据增量更新技术提高索引数据在线更新效率。

说明书

技术领域

本发明涉及大数据计算领域，特别涉及一种大数据多区间查询条件下的 基数估计方法及装置。

背景技术

随着移动互联网和Web2.0的发展，全球数据量正在惊人的增长：2008 年全球产生的数据量为0.49ZB（1ZB=1021字节），2009年为0.8ZB，2010 年为1.2ZB，2011年高达1.82ZB。IDC预计到2020年，全人类会产生超过 40ZB的数据。在大数据中一类重要的数据是结构化、半结构化数据，主要包 括：交易数据，日志数据等。据了解，淘宝网每日新增的交易数据达10TB， eBay分析平台日处理数据量高达100PB，沃尔玛每小时有大约2.5PB的数据 存入数据库。基于日志类数据进行挖掘、分析可以获得越来越多的有价值的 信息。如Google Trends对用户上网记录进行统计，成功预测流感在全球的 扩散范围，其准确度高达到97%以上。

多区间条件大数据基数估算是统计同时符合多个区间查询条件下的不 同的记录的个数，是聚合运算、统计分析的基础计算工具，在数据分析、网 络监控及数据库优化等领域都有广泛的相关需求。但是目前的大数据分析统 计系统本质是一种精确计算的方法，例如Hadoop为基础的大数据管理系统 Hive，pig等通过扫描原始数据获得准确的计算值，但是随着数据规模的增 大计算效率显著下降。近似查询是通过降低部分计算精度，来提高大数据的 计算效率。传统的基数估算算法，如Linear Counting、LogLog Counting、 HyperLogLog Counting、Adaptive Counting，以及Bloomfilter等能解决 简单的不同元素个数的统计，但是不支持区间查询条件下的基数统计。实现 多区间条件下的大数据高精度基数统计成为本发明需要解决的核心问题。

发明内容

本发明所要解决的技术问题是提供一种大数据多区间查询条件下的进 行高精度近似计算的基数估计方法及装置。

本发明解决上述技术问题的技术方案如下：一种大数据多区间查询条件 下的基数估计方法，包括以下步骤：

步骤1：按照数值属性对大数据预先划分成多个分区，每个分区内保存 所述大数据中的一段数据源，各个分区之间有序排列；

步骤2：建立树形索引结构，每个分区作为树形索引结构的一个节点， 每个节点用于记录对应的分区的最大值和最小值，每个节点中设置数据文件 和基数估算器；

步骤3：获取待写入树形索引结构的数据源，对支持区间查询条件的数 据源进行倒排索引处理；

步骤4：将经过倒排索引处理的数据源的相应部分分别写入数据文件及 基数估算器内；

步骤5：根据区间查询条件在树形索引结构中查询满足区间查询条件的 节点，得到节点中的基数估算器，对基数估算器中的数据源的相应部分进行 逻辑处理，得到基数估算值。

本发明的有益效果是：本发明针对大数据统计分析中通常使用的多区间 查询条件，提出一种近似查询方法，通过降低数据的计算精度提高基数统计 效率。本发明在每个分区内使用了HyperLogLog基数估算算法，公开的资料 和理论证明该算法可以在较小内存条件下（5KB），在10亿规模的数据中， 获得小于1.14%的计算误差，并且，估算器之间的合并不会降低计算误差， 因此本发明同样可以在任意的多区间条件下，提供较高计算精度；

本发明在任意多区间查询条件下，具备较高的查询效率，适用于大数据 的在线统计查询。本发明基于分区信息建立层次化的索引结构RC-Tree，在 执行具体的查询操作时仅在RC-Tree中进行检索，查询效率与RC-Tree的节 点数目相关与具体的数据量无关。在多个区间条件下的检索运算，都转化为 二进制或运算，因此都具有较高计算效率；

本发明使用了大数据增量更新技术提高索引数据在线更新效率。发明使 用临时表索引结构保存增量更新的数据，并对数据进行合并，当到达到一定 的数据规模后，把合并以后的数据批量更新到全局的索引结构中，并与全局 索引进行再次合并，提高大数据的更新效率。

在上述技术方案的基础上，本发明还可以做如下改进。

进一步，所述步骤3具体为：为每个待写入的数据源分配一个全局唯一 的ID,将每个数据源分别拆分为<value,ID>结构。

进一步，所述步骤4具体为：将<value,ID>结构中的value写入相应的 节点内的数据文件中，ID利用哈希算法写入节点内的基数估算器中。

进一步，所述步骤5具体为，当区间查询条件覆盖的区间为多个分区时， 返回该多个分区内所有基数估算器，将全部基数估算器利用哈希算法进行合 并，得到合并后的符合查询条件的全部基数值；

当区间查询条件覆盖的区间为部分分区，返回该部分分区所在的分区内 的数据文件，得到数据文件中的精确的value值。

进一步，所述步骤3和步骤4之间还包括：

步骤2-1：建立临时表结构，所述临时表结构与树形索引结构中各个节 点的结构相同；

步骤2-2：根据待写入的数据源，在临时表结构中利用二分法查找到对 应的节点，将待写入的数据源写入该临时表结构中的节点中；

步骤2-3：将临时表结构中每个节点中的数据文件存储于树形索引结构 中对应的数据文件的末尾，将临时表结构中每个基数估算器与树形索引结构 中对应的技术估算器进行合并。

进一步，一种大数据多区间查询条件下的基数估计装置，包括划分模块， 建立模块，倒排模块，写入模块和查询模块；

所述划分模块，用于按照数值属性对大数据预先划分成多个分区，每个 分区内保存所述大数据中的一段数据源，各个分区之间有序排列，将各个分 区的信息发送给建立模块；

所述建立模块，用于接收所有分区的信息，建立树形索引结构，每个分 区作为树形索引结构的一个节点，每个节点用于记录对应的分区的最大值和 最小值，每个节点中设置数据文件和基数估算器，将树形索引结构的信息、 数据文件和基数估算器的信息发送给写入模块；

所述倒排模块，用于获取待写入树形索引结构的数据源，对支持区间查 询条件的数据源进行倒排索引处理，将经过倒排索引处理的数据源发送给写 入模块；

所述写入模块，用于接收经过倒排索引处理的数据源，将经过倒排索引 处理的数据源的相应部分分别写入数据文件及基数估算器内，将写入数据源 后的树形索引结构的信息、数据文件和基数估算器的信息发送给查询模块；

所述查询模块，用于接收写入数据源后的树形索引结构的信息、数据文 件和基数估算器的信息，根据区间查询条件在树形索引结构中查询满足区间 查询条件的节点，得到节点中的基数估算器，根据基数估算器中的数据源的 相应部分，得到存储于数据文件中的基数估算值。

进一步，所述倒排模块具体用于：为每个待写入的数据源分配一个全局 唯一的ID,将每个数据源分别拆分为<value,ID>结构。

进一步，所述写入模块具体用于：将<value,ID>结构中的value写入相 应的节点内的数据文件中，ID利用哈希算法写入节点内的基数估算器中。

所述查询模块具体用于，当区间查询条件覆盖的区间为多个分区时，返 回该多个分区内所有基数估算器，将全部基数估算器利用哈希算法进行合 并，得到合并后的符合查询条件的全部基数值；当区间查询条件覆盖的区间 为部分分区，返回该部分分区所在的分区内的数据文件，得到数据文件中的 精确的value值。

进一步，所述倒排模块和写入模块之间还包括建立临时表结构模块，二 分法查找模块和存储合并模块；

所述建立临时表结构模块，用于建立临时表结构，所述临时表结构与树 形索引结构中各个节点的结构相同；

所述二分法查找模块，用于根据待写入的数据源，在临时表结构中利用 二分法查找到对应的节点，将待写入的数据源写入该临时表结构中的节点 中；

所述存储合并模块，用于将临时表结构中每个节点中的数据文件存储于 树形索引结构中对应的数据文件的末尾，将临时表结构中每个基数估算器与 树形索引结构中对应的技术估算器进行合并。

附图说明

图1为本发明方法步骤流程图；

图2为本发明装置结构图；

图3为本发明树形索引结构示意图；

图4为本发明树形索引结构索引数据增量合并流程图；

图5为本发明多区间查询过程流程图。

附图中，各标号所代表的部件列表如下：

1、划分模块，2、建立模块，3、倒排模块，4、写入模块，5、查询模 块，6、建立临时表结构模块，7、二分法查找模块，8、存储合并模块。

具体实施方式

以下结合附图对本发明的原理和特征进行描述，所举实例只用于解释本 发明，并非用于限定本发明的范围。

如图1所示，为本发明方法步骤流程图；图2为本发明装置结构图；图 3为本发明树形索引结构示意图；图4为本发明树形索引结构索引数据增量 合并流程图；图5为本发明多区间查询过程流程图。

实施例1

一种大数据多区间查询条件下的基数估计方法，包括以下步骤：

步骤1：按照数值属性对大数据预先划分成多个分区，每个分区内保存 所述大数据中的一段数据源，各个分区之间有序排列；

步骤2：建立树形索引结构，每个分区作为树形索引结构的一个节点， 每个节点用于记录对应的分区的最大值和最小值，每个节点中设置数据文件 和基数估算器；

步骤3：获取待写入树形索引结构的数据源，对支持区间查询条件的数 据源进行倒排索引处理；

步骤4：将经过倒排索引处理的数据源的相应部分分别写入数据文件及 基数估算器内；

步骤5：根据区间查询条件在树形索引结构中查询满足区间查询条件的 节点，得到节点中的基数估算器，对基数估算器中的数据源的相应部分进行 逻辑处理，得到基数估算值。

所述步骤3具体为：为每个待写入的数据源分配一个全局唯一的ID,将 每个数据源分别拆分为<value,ID>结构。

所述步骤4具体为：将<value,ID>结构中的value写入相应的节点内的 数据文件中，ID利用哈希算法写入节点内的基数估算器中。

所述步骤5具体为，当区间查询条件覆盖的区间为多个分区时，返回该 多个分区内所有基数估算器，将全部基数估算器利用哈希算法进行合并，得 到合并后的符合查询条件的全部基数值；

当区间查询条件覆盖的区间为部分分区，返回该部分分区所在的分区内 的数据文件，得到数据文件中的精确的value值。

所述步骤3和步骤4之间还包括：

步骤2-1：建立临时表结构，所述临时表结构与树形索引结构中各个节 点的结构相同；

步骤2-2：根据待写入的数据源，在临时表结构中利用二分法查找到对 应的节点，将待写入的数据源写入该临时表结构中的节点中；

步骤2-3：将临时表结构中每个节点中的数据文件存储于树形索引结构 中对应的数据文件的末尾，将临时表结构中每个基数估算器与树形索引结构 中对应的技术估算器进行合并。

一种大数据多区间查询条件下的基数估计装置，包括划分模块1，建立 模块2，倒排模块3，写入模块4和查询模块5；

所述划分模块1，用于按照数值属性对大数据预先划分成多个分区，每 个分区内保存所述大数据中的一段数据源，各个分区之间有序排列，将各个 分区的信息发送给建立模块2；

所述建立模块2，用于接收所有分区的信息，建立树形索引结构，每个 分区作为树形索引结构的一个节点，每个节点用于记录对应的分区的最大值 和最小值，每个节点中设置数据文件和基数估算器，将树形索引结构的信息、 数据文件和基数估算器的信息发送给写入模块4；

所述倒排模块3，用于获取待写入树形索引结构的数据源，对支持区间 查询条件的数据源进行倒排索引处理，将经过倒排索引处理的数据源发送给 写入模块4；

所述写入模块4，用于接收经过倒排索引处理的数据源，将经过倒排索 引处理的数据源的相应部分分别写入数据文件及基数估算器内，将写入数据 源后的树形索引结构的信息、数据文件和基数估算器的信息发送给查询模块 5；

所述查询模块5，用于接收写入数据源后的树形索引结构的信息、数据 文件和基数估算器的信息，根据区间查询条件在树形索引结构中查询满足区 间查询条件的节点，得到节点中的基数估算器，根据基数估算器中的数据源 的相应部分，得到存储于数据文件中的基数估算值。

所述倒排模块3具体用于：为每个待写入的数据源分配一个全局唯一的 ID,将每个数据源分别拆分为<value,ID>结构。

所述写入模块4具体用于：将<value,ID>结构中的value写入相应的节 点内的数据文件中，ID利用哈希算法写入节点内的基数估算器中。

所述查询模块5具体用于，当区间查询条件覆盖的区间为多个分区时， 返回该多个分区内所有基数估算器，将全部基数估算器利用哈希算法进行合 并，得到合并后的符合查询条件的全部基数值；当区间查询条件覆盖的区间 为部分分区，返回该部分分区所在的分区内的数据文件，得到数据文件中的 精确的value值。

所述倒排模块3和写入模块4之间还包括建立临时表结构模块6，二分 法查找模块7和存储合并模块8；

所述建立临时表结构模块6，用于建立临时表结构，所述临时表结构与 树形索引结构中各个节点的结构相同；

所述二分法查找模块7，用于根据待写入的数据源，在临时表结构中利 用二分法查找到对应的节点，将待写入的数据源写入该临时表结构中的节点 中；

所述存储合并模块8，用于将临时表结构中每个节点中的数据文件存储 于树形索引结构中对应的数据文件的末尾，将临时表结构中每个基数估算器 与树形索引结构中对应的技术估算器进行合并。

在具体实施中，本发明具体包括以下步骤：

步骤1：大数据预分区处理：

本发明首先对大数据进行预分区处理。在分布式大数据系统中，分区是 常用的技术方法。本发明对大数据源根据数值属性划分为多个相互独立的N 分区，每个分区表示一定范围，例如对(-∞,+∞)之间，可以划分为：(-∞, key₁),[key₁,key₂),[key₂,key₃)，…,[key_N-1,+∞)共N个区间。其中key₁， key₂，…,key_N有序且递增。在给定区间个数N，如何确定分区key的序列本 发明首先转化为大数（Big Integer）运算，然后利用大数除法，确定每个 分区范围。

步骤2：建立RC-Tree：

根据步骤1产生的分区，建立RC-Tree索引结构。RC-Tree在基本的B Tree基础上修改而来。RC-Tree每个节点记录是一个区间信息，记为 <[start-key,end-key],CE,otherInfo>结构，其中：[start-key,end-key) 表示一个分区内的最大和最小值；CE是本区间内的基数估算器，建立时初始 化为空，otherInfo是本区间内对应的数据文件存储位置以及其他的一些元 数据信息。RC-Tree的内节点是叶节点合并以后的结果，区间范围是所有叶 节点的区间范围。利用RC-Tree可以有效组织有步骤1生成的元数据信息， 其中的每个区间直接使用RC-Tree的一个叶节点来管理，例如对于RC-Tree 的第一个节点可以表示为：start-key=-∞,end-key=key1。

步骤3：倒排加载的结构化数据源：

本发明对于写入的数据源要进行倒排处理。首先针对写入的日志类数据 和其他半结构化数据需要区分哪些字段支持区间查询条件。默认的所有的字 段全部支持区间条件查询。对于支持区间条件查询的字段要进行倒排处理。 倒排的方法是对每条记录引入一个全局唯一的ID，本发明中使用UINT64表 示。把多个字段分别拆分为<value,ID>结构，拆分以后的字段当ID相同时 表示是来自同一条记录。例如对于一条网络访问日志记录为：“en， dbinfo，…”网络访问日志，其中en是页面语言类型，dbinfo是页面类型， 倒排以后的结构为<en,0001>，<dbinfo,0001>。

步骤4：更新RC-Tree：

把倒排以后的多个<value,ID>结构写入到RC-Tree中，写入的方法是首 先在RC-Tree中查找满足value∈[start-key,end-key)条件的区间,value 写入到分区内的数据文件中，ID利用hash算法写入节点的CE中。

由于大数据面临吞吐率高的应用特点。本发明利用临时链表作为缓存结 构进行增量大数据合并提高数据的更新效率。临时表的结构与RC-Tree节点 的结构相同，也是记录不同分区的索引数据。当有更新数据到来时，首先在 临时表中利用二分法查找到对应的分区节点，然后把value写到临时文件中， ID写入到临时节点的估算器中。由于临时表的数据量较少，写入效率较高。 当临时表达到一定的规模，不20万个节点时，把临时表批量写入到RC-Tree 中。写入的过程是依次把临时表中每个临时节点对应的数据文件直接追加到 RC-Tree数据文件的末尾，每个临时节点的估算器利用二进制或操作与 RC-Tree节点的估算器进行合并。由于此时主要是由整个文件的追加写，以 及二进制运算操作，因此提高了RC-Tree吞吐率。RC-Tree在实验条件下， 可以达到平均20MB/s的实时加载速率，具体的RC-Tree更新过程见附图3.

步骤5：多区间条件近似基数查询：

多区间条件基数查询是统计满足多个区间条件下的不同的记录个数，可 以通过类sql语句表示其语法规则：

Select distinct count(*)from tablename where

l₁<p₁<l₂ opr

l_i<p₂<l_j…;

其中：tablename表示SQL语句中的表名；opr是逻辑运算符，一般包 含AND，OR等逻辑运算。pi表示查询字段名称；l_i，l_j，表示一个区间范围。

区间条件是常用的过滤类查询条件，其涵盖的数据量大。在多条件区间 查询中，可以针对不同的字段列构造区间查询条件，因此目前的大数据系统， No-SQLDB等精确计算方法，都无法高效的获得计算结果。本发明针对上述检 索模式，基于RC-Tree提供高效的近似查询。

本发明针对多区间查询条件分为两个步骤实现，首先针对每个区间查询 条件在RC-Tree中进行查询满足条件的估算器；然后根据逻辑运算符进行多 区间逻辑运算，最后获得计算结果。

1）单区间条件查询：

RC-Tree的各个节点记录了所有分区信息。当一个区间条件覆盖多个节 点所包含的区间时，按序返回所有节点的估算器，然后进行估算器的merge， 生成一个能够表示多个区间基数的单一估算器。但是对于查询条件开始和结 束两个端点会存在部分覆盖RC-Tree节点的情况，此时本发明可以扫描数据 文件获得本区间内的精确查询结果，但是由于本方法是一个近似查询方法， 可以直接返回查询条件所涉及的所有节点的估算器，作为查询结果，尽管会 增大部分查询误差，但是会先显著提高查询效率。当有多个区间检索条件时， 一次针对每个区间查询条件返回一个合并以后的估算器。估算器的合并方法 是采用Hash值的二进制或运算实现。

2）逻辑条件下的基数查询：

多个区间查询条件是通过逻辑运算符连接实现的，一般有AND，OR等集 合运算关系。本发明针对OR运算本发明对每个区间查询条件返回的估算器 进一步对其Hash值进行或运算，即可获得由多个OR运算符连接的多区间条 件的基数估算值。对于AND运算而言本发明采用集合运算的 inclusive-exclusive principle，即|A|∩|B|=|A|+|B|-|A|∪|B|。首先利用 1）结果中每个区间条件的估算器计算其基数估算值，然后再利用逻辑或方 法获得基数估算器以及其基数值。结合inclusive-exclusive principle即 可获得由逻辑AND连接的多个查询条件。

由于数据分布在RC-Tree和临时表中，在查询过程中需要针对RC-Tree 和临时表分别进行查找，然后再结合1）或2）的合并规则进行合并即可。

关于多区间查询条件见附图5所示。

以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明 的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发 明的保护范围之内。