一种用于计算海量数据的流式处理方法与流程

1.本发明属于数据处理技术领域，特别是涉及一种用于计算海量数据的流式处理方法，能够在有限的操作系统内存资源下可以高效地实现海量数据的处理计算。


背景技术：

2.随着现代各种技术手段的发展，海量数据的获取越来越便捷可行。这些数据通常以gb乃至tb为单位，远远超过普通计算机内存的容量。面对海量数据快速处理的强烈现实需求，目前的实现方法却有待突破。一方面由于计算机内存的局限性，对于海量数据没有很好的处理策略，空间性能较低，无法稳定实现海量数据的计算；另一方面现有很多处理算法效率不高，不能满足快速处理的实用需求。于是，要想充分利用好这些数据，发挥其海量的优势，传统的内存算法显然已经不再适用。
3.因此，研究基于外存的处理算法成为形势发展的当务之急。外存算法的基本思想是将计算机内存和外存(磁盘)看成一个连续的、巨大的存储空间，算法执行时不断的将需要处理的数据从外存读入内存，而将暂不处理的数据写入外存以空出必要的内存空间。然而由于数据的随机性，数据之间不具有空间关联，设计外存算法时内外存频繁交换，效率降低，算法的稳定性也不能保证。
4.基于此，本发明提出先根据数据的内在关联性，采用四叉树结构对海量数据进行分块，各块以morton码排序后再逐个进行处理计算。该处理方法虽然块内数据无序但块间有序，保证了数据的内在关联性，提高了数据处理过程搜索定位的效率。同时引入流计算模式，在处理的时候只读入一块点数据，每块数据处理完成后区分出稳定态和待定态，把稳定态的数据全部输出，只保留待定态数据在内存中参与后面的计算。这样内存占用大大降低，从而可以很好地处理海量数据。


技术实现要素：

5.本发明的目的在于提供一种用于计算海量数据的流式处理方法，通过预处理采用特定的编码方式及存储结构，结合流计算模式对海量数据进行优化处理，区分数据稳定态和待定态，并及时输出稳定态，只保留待定态数据在内存中参与后续计算，解决了现有的海量数据处理速度不佳、内容占用大的问题。
6.为解决上述技术问题，本发明是通过以下技术方案实现的：
7.本发明为一种用于计算海量数据的流式处理方法，按数据读入顺序进行处理，可以提早输出结果并释放内存；计算限定在内存，数据块之间无缝，无需考虑合并的问题，具体包括如下步骤：
8.步骤s1、数据预处理：根据数据的内在关联性，找到数据的特征包围盒，进行数据分块(块内有序，块间排序)，并按块将数据保存到外存文件；
9.步骤s2、分块读取数据：将每一块的数据从外存文件读取到内存处理；
10.步骤s3、区分数据块：每块数据按要求完成处理后，区分稳定态和待定态，将稳定
态数据输出，待定态数据保留在内存，继续参与后续计算；
11.步骤s4、处理结束：将所有块的数据处理完，输出最终结果。
12.作为一种优选的技术方案，所述步骤s1中，对数据进行预处理具体过程包括：
13.步骤s11：第一次读取数据，根据数据内在的关联性，找到数据的最值，确定数据的特征包围盒；
14.步骤s12：第二次读取数据，将全部数据划分为均匀数据格网块，根据格网块单元特征值，判断数据落在哪个格网单元内，据此统计出每个格网单元内数据的个数；
15.步骤s13：第三次读取数据，将格网单元采用z-order曲线顺序进行外部排序，对每个单元添加落入其内的所有数据，并将这些数据输出到临时文件。
16.作为一种优选的技术方案，所述数据预处理过程中，第一次读取数据时，遍历所有数据的特征值，找出其中的最大值和最小值来确定数据的特征包围盒；第二次读取数据时，利用四叉树结构进行剖分，数据量的大小决定剖分的层次，四叉树的叶节点即格网单元，并以morton码为键值key；统计每个格网内所包含的数据的个数，此步只是一个计数过程，数据本身并不保留在内存；第三次读取数据时，将新读取的数据添加到其所属格网单元内，当单元内数据的个数达到上限记录时，表明该单元已完成预处理，不会再有数据进入，于是将该单元内的所有数据输出到临时文件，同时释放内存。
17.作为一种优选的技术方案，所述步骤s2中，读取一块数据到内存中，在现存的特征值处理结果中，利用数据的特征值进行某种逻辑关系需求处理；首先在现存的特征值处理结果中，查找包含新进数据的特征值，然后搜索影响域，即找到所有与该特征值关联的结果影响域，对影响域重新进行逻辑关系需求处理，并删除原来的处理结果，将新得到的逻辑关系处理结果添加到现存结果集合中。
18.作为一种优选的技术方案，所述特征值的逻辑关系需求处理时，为了提高效率主要着眼于改进受影响结果域的搜索，本发明提出了两个优化策略。第一步特征值定位，即查找包含新进点的影响域，由于数据间具有特征值内在关联性，通过逆序排列新生成的影响域，从后向前查找，实现了快速定位。平均只需一个数量级的查找，即可完成定位过程。第二步邻接影响域搜索，我们把邻接关系表示为常数，用hash表存储，一方面加快了查找的速度，另一方面也避免了复杂数据结构的维护。
19.作为一种优选的技术方案，所述步骤s3中，每一单元块完成特征值需求处理后，用快速相交检测算法，识别出稳定态区域和待定态区域；所述稳定态，即数据特征处理结果完全落在已处理的单元区域内，表示需求结果已经确定，不再受后面计算过程的影响；所述稳定态数据需求结果提前输出到设备上，并释放内存；所述待定态，即数据特征处理结果与未处理区域相交，表示数据的需求结果会受后续计算过程的影响；所述待定态数据保留在内存，继续参与计算。
20.作为一种优选的技术方案，所述步骤s4中，当所有数据的格网单元块都读入内存，并完成特征值需求处理后，内存中仍然保留一部分的特征值需求结果，把这些结果全部输出，并把所计算的最终结果写到输出文件中，关闭文件，完成全部计算过程，算法结束。
21.本发明具有以下有益效果：
22.本发明通过预处理采用特定的编码方式及存储结构，结合流计算模式对海量数据进行优化处理，区分数据稳定态和待定态，并及时输出稳定态，只保留待定态数据在内存中
参与后续，提高了计算海量数据的处理速度、内容占用大，减少操作系统内存占用。
23.当然，实施本发明的任一产品并不一定需要同时达到以上所述的所有优点。
附图说明
24.为了更清楚地说明本发明实施例的技术方案，下面将对实施例描述所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
25.图1为本发明的一种用于计算海量数据的流式处理方法流程图；
26.图2为对数据进行预处理流程图。
具体实施方式
27.下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其它实施例，都属于本发明保护的范围。
28.实施例一
29.请参阅图1所示，本发明为按数据读入顺序进行处理，可以提早输出结果并释放内存；计算限定在内存，数据块之间无缝，无需考虑合并的问题，具体包括如下步骤：
30.步骤s1、数据预处理：根据数据的内在关联性，找到数据的特征包围盒，进行数据分块(块内有序，块间排序)，并按块将数据保存到外存文件；
31.请参阅图2所示，对数据进行预处理具体过程包括：
32.步骤s11：第一次读取数据，根据数据内在的关联性，找到数据的最值，确定数据的特征包围盒；
33.步骤s12：第二次读取数据，将全部数据划分为均匀数据格网块，根据格网块单元特征值，判断数据落在哪个格网单元内，据此统计出每个格网单元内数据的个数；
34.步骤s13：第三次读取数据，将格网单元采用z-order曲线顺序进行外部排序，对每个单元添加落入其内的所有数据，并将这些数据输出到临时
[0035][0036]
文件；z-order曲线排序如下表1所示，
[0037]
表1z-order曲线排序图
[0038]
数据预处理过程中，第一次读取数据时，遍历所有数据的特征值，找出其中的最大值和最小值来确定数据的特征包围盒；第二次读取数据时，利用四叉树结构进行剖分，数据量的大小决定剖分的层次，四叉树的叶节
[0039]
点即格网单元，并以morton码为键值key；统计每个格网内所包含的数据的个数，此步只是一个计数过程，数据本身并不保留在内存；第三次读取数据时，将新读取的数据添加到其所属格网单元内，当单元内数据的个数达到上限记录时，表明该单元已完成预处理，不会再有数据进入，于是将该单元内的所有数据输出到临时文件，同时释放内存。
[0040]
如下表2，对数据进行两次遍历实现负载平衡后，在确定特征包围盒的同时，对余下的各子区域分别构建四叉树进行格网划分，并对四叉树叶子节点进行morton编码；
[0041][0042]
表2数据进行morton编码
[0043]
步骤s2、分块读取数据：将每一块的数据从外存文件读取到内存处理；
[0044]
读取一块数据到内存中，在现存的特征值处理结果中，利用数据的特征值进行某种逻辑关系需求处理；首先在现存的特征值处理结果中，查找包含新进数据的特征值，然后搜索影响域，即找到所有与该特征值关联的结果影响域，对影响域重新进行逻辑关系需求处理，并删除原来的处理结果，将新得到的逻辑关系处理结果添加到现存结果集合中。
[0045]
特征值的逻辑关系需求处理时，为了提高效率主要着眼于改进受影响结果域的搜索，本发明提出了两个优化策略。第一步特征值定位，即查找包含新进点的影响域，由于数据间具有特征值内在关联性，通过逆序排列新生成的影响域，从后向前查找，实现了快速定位。平均只需一个数量级的查找，即可完成定位过程。第二步邻接影响域搜索，我们把邻接关系表示为常数，用hash表存储，一方面加快了查找的速度，另一方面也避免了复杂数据结构的维护。
[0046]
步骤s3、区分数据块：每块数据按要求完成处理后，区分稳定态和待定态，将稳定态数据输出，待定态数据保留在内存，继续参与后续计算；
[0047]
每一单元块完成特征值需求处理后，用快速相交检测算法，识别出稳定态区域和待定态区域；稳定态，即数据特征处理结果完全落在已处理的单元区域内，表示需求结果已经确定，不再受后面计算过程的影响；稳定态数据需求结果提前输出到设备上，并释放内存；待定态，即数据特征处理结果与未处理区域相交，表示数据的需求结果会受后续计算过程的影响；待定态数据保留在内存，继续参与计算。
[0048]
步骤s4、处理结束：将所有块的数据处理完，输出最终结果；
[0049]
当所有数据的格网单元块都读入内存，并完成特征值需求处理后，内存中仍然保留一部分的特征值需求结果，把这些结果全部输出，并把所计算的最终结果写到输出文件中，关闭文件，完成全部计算过程，算法结束。
[0050]
实施例二
[0051]
以下为构建四叉树的代码：
[0052]
[0053]
[0054][0055]
值得注意的是，上述系统实施例中，所包括的各个单元只是按照功能逻辑进行划分的，但并不局限于上述的划分，只要能够实现相应的功能即可；另外，各功能单元的具体名称也只是为了便于相互区分，并不用于限制本发明的保护范围。
[0056]
另外，本领域普通技术人员可以理解实现上述各实施例方法中的全部或部分步骤是可以通过程序来指令相关的硬件来完成，相应的程序可以存储于一计算机可读取存储介质中。
[0057]
以上公开的本发明优选实施例只是用于帮助阐述本发明。优选实施例并没有详尽叙述所有的细节，也不限制该发明仅为所述的具体实施方式。显然，根据本说明书的内容，可作很多的修改和变化。本说明书选取并具体描述这些实施例，是为了更好地解释本发明的原理和实际应用，从而使所属技术领域技术人员能很好地理解和利用本发明。本发明仅受权利要求书及其全部范围和等效物的限制。

技术特征：
1.一种用于计算海量数据的流式处理方法，其特征在于，包括如下步骤：步骤s1、数据预处理：根据数据的内在关联性，找到数据的特征包围盒，进行数据分块，并按块将数据保存到外存文件；步骤s2、分块读取数据：将每一块的数据从外存文件读取到内存处理；步骤s3、区分数据块：每块数据按要求完成处理后，区分稳定态和待定态，将稳定态数据输出，待定态数据保留在内存，继续参与后续计算；步骤s4、处理结束：将所有块的数据处理完，输出最终结果。2.根据权利要求1所述的一种用于计算海量数据的流式处理方法，其特征在于，所述步骤s1中，对数据进行预处理具体过程包括：步骤s11：第一次读取数据，根据数据内在的关联性，找到数据的最值，确定数据的特征包围盒；步骤s12：第二次读取数据，将全部数据划分为均匀数据格网块，根据格网块单元特征值，判断数据落在哪个格网单元内，据此统计出每个格网单元内数据的个数；步骤s13：第三次读取数据，将格网单元采用z-order曲线顺序进行外部排序，对每个单元添加落入其内的所有数据，并将这些数据输出到临时文件。3.根据权利要求2所述的一种用于计算海量数据的流式处理方法，其特征在于，所述数据预处理过程中，第一次读取数据时，遍历所有数据的特征值，找出其中的最大值和最小值来确定数据的特征包围盒；第二次读取数据时，利用四叉树结构进行剖分，四叉树的叶节点即格网单元，并以morton码为键值key；第三次读取数据时，将新读取的数据添加到其所属格网单元内，当单元内数据的个数达到上限记录时，表明该单元已完成预处理，将该单元内的所有数据输出到临时文件，同时释放内存。4.根据权利要求1所述的一种用于计算海量数据的流式处理方法，其特征在于，所述步骤s2中，读取一块数据到内存中，在现存的特征值处理结果中，查找包含新进数据的特征值，然后搜索影响域，即找到所有与该特征值关联的结果影响域，对影响域重新进行逻辑关系需求处理，并删除原来的处理结果，将新得到的逻辑关系处理结果添加到现存结果集合中。5.根据权利要求4所述的一种用于计算海量数据的流式处理方法，其特征在于，所述特征值的逻辑关系需求处理时，进行特征值定位，即查找包含新进点的影响域，通过逆序排列新生成的影响域，从后向前查找。6.根据权利要求5所述的一种用于计算海量数据的流式处理方法，其特征在于，邻接所述影响域搜索时，将邻接关系表示为常数，用hash表存储。7.根据权利要求1所述的一种用于计算海量数据的流式处理方法，其特征在于，所述步骤s3中，每一单元块完成特征值需求处理后，用快速相交检测算法，识别出稳定态区域和待定态区域；所述稳定态，即数据特征处理结果完全落在已处理的单元区域内，表示需求结果已经确定，不再受后面计算过程的影响；所述稳定态数据需求结果提前输出到设备上，并释放内存；所述待定态，即数据特征处理结果与未处理区域相交，表示数据的需求结果会受后续计算过程的影响；所述待定态数据保留在内存，继续参与计算。8.根据权利要求1所述的一种用于计算海量数据的流式处理方法，其特征在于，所述步骤s4中，当所有数据的格网单元块都读入内存，并完成特征值需求处理后，内存中仍然保留
一部分的特征值需求结果，把结果全部输出，并把所计算的最终结果写到输出文件中，关闭文件，完成全部计算过程，算法结束。

技术总结
本发明公开了一种用于计算海量数据的流式处理方法，涉及数据处理技术领域。本发明包括如下步骤：数据预处理：根据数据的内在关联性，找到数据的特征包围盒，进行数据分块；分块读取数据：将每一块的数据从外存文件读取到内存处理；区分数据块：每块数据完成处理后，区分稳定态和待定态，将稳定态数据输出，待定态数据保留在内存，继续参与后续计算；处理结束：将所有块的数据处理完，输出最终结果。本发明通过预处理采用特定的编码方式及存储结构，结合流计算模式对海量数据进行优化处理，区分数据稳定态和待定态，并及时输出稳定态，只保留待定态数据在内存中参与后续，提高了计算海量数据的处理速度、内容占用大，减少操作系统内存占用。占用。占用。


技术研发人员：张英
受保护的技术使用者：劳弗尔视觉科技有限公司
技术研发日：2023.07.03
技术公布日：2023/10/6