一种具有多维信息的海量数据查询方法

暂无

一种具有多维信息的海量数据查询方法\n技术领域\n[0001] 发明涉及数据挖掘领域，特别涉及一种具有多维信息的海量数据查询方法。\n背景技术\n[0002] 随着大数据时代的到来，对传统的数据管理、查询等传统数据分析领域造成了极大的挑战。为了应对海量数据所带来对挑战，在学术界和工业界广泛采用MapReduce编程模型和分布式文件系统来应对这种挑战。OLAP(On-LineAnalytical Processing联机分析处理)是传统数据分析领域中非常重要的分析手段和方法。在大数据领域对OLAP分析也提出了新的要求。\n[0003] OLAP可以按照其实现方式不同分为ROLAP(Relational OLAP面向关系的联机数据分析处理)、MOLAP(Multidimensional OLAP面向多维的联机分析处理)和HOLAP(Hybrid OLAP混合型联机分析处理)3种。其中ROLAP采用关系表存储维信息和事实数据，MOLAP则采用多维数据结构存储维信息和事实数据，而HOLAP称之为混合OLAP，该方法结合了ROLAP和MOLAP技术。无论是何种OLAP，都需要存储和计算平台的支持，尤其是在大数据环境下。为了解决大数据所带来的诸多挑战，学界和业界涌现出许多新技术，如分布式文件系统、NoSQL(Not Only Structured Query Language不仅仅是基于结构化查询语言的)数据库系统，MapReduce编程模型以及相关的优化方法，这些技术都被广泛地运用到大数据分析中。\n[0004] 在大数据环境中常用的OLAP优化方法有以下两种：利用预计算和浓缩数据立方的结果优化OLAP性能和通过优化存储结构和算法来优化OLAP性能。但是前者将会生成大量的数据，无法适用于海量数据环境，而后者的优化措施大多基于ROLAP，对OLAP的性能没有质的提升。有研究提出了OLAP查询中的SPAJG-OLAP子集，在存储、查询、数据分布、网络传输和分布式缓存等方面研究海量数据大规模并行处理框架的优化策略和实现技术。该研究基于并行数据库技术优化ROLAP性能，通过对OLAP查询以及存储的优化达到加速OLAP的目的，但是由于ROLAP是基于关系数据库技术，会产生大量的连接操作，当数据量非常庞大的情况下其优化效果并不明显。\n[0005] 就分布式的OLAP系统而言，一些基于Hadoop的云数据库系统，例如Hive、HadoopDB、HBase等，都支持OLAP。在当前对海量数据分布式OLAP领域中，广泛采用数据索引、分片等方法对ROLAP进行优化。但是ROLAP需要采用关系模型以及耗费资源的连接操作，当数据量增加时，索引及分片的优化作用急剧下降。此外还有通过对查询条件进行优化ROLAP的方法。但是同样由于不可避免连接操作，其优化作用不是非常明显。MOLAP将数据作为数据立方进行存储，但需要对维进行管理和优化，导致当前对MOLAP的研究以及系统并没有权威的报道。\n发明内容\n[0006] 针对现有发明存在的不足，本发明的目的是提供一种具有多维信息的海量数据查询方法，以达到在海量数据环境中数据查询、聚集计算的目的。\n[0007] 本发明的技术方案是这样实现的：一种具有多维信息的海量数据查询方法，包括以下步骤：\n[0008] 步骤1：对具有多维信息的海量数据的维信息进行装载，具体包括如下步骤：\n[0009] 步骤1.1：对海量数据的维信息进行鉴别，判断海量数据的每一个维信息是否同时满足如下三个约束：\n[0010] 约束1：维由一个且仅一个维层次构成，即维是所有维级别组成的全序关系；\n[0011] 约束2：在维的任意维级别中，仅包含一个维属性，该维属性包含若干个维值；\n[0012] 约束3：在所有维值所组成的维值树中，兄弟节点包含相同个数的子节点；\n[0013] 若全部满足，则执行步骤1.3，否则，执行步骤1.2；\n[0014] 步骤1.2：对维信息进行处理，使得每一个维都形成符合约束的维值树结构，处理过程如下：\n[0015] 针对约束1：若有多个维层次，则根据需要对维层次进行舍弃，仅保留一个维层次即可；\n[0016] 针对约束2：若某一维级别包含多个维属性，则根据需要对维属性进行舍弃，仅保留一个维属性即可；\n[0017] 针对约束3：若兄弟节点包含的子节点个数不同，则添加空值，使兄弟节点的子节点个数相同；\n[0018] 步骤1.3：对维信息进行编码；\n[0019] 针对维值树中每一维级别的维值，从左到右以十进制数依次编码，当所有的维值均有对应的编码后编码工作结束；\n[0020] 步骤1.4：对维信息的编码进行存储；\n[0021] 对于海量数据的任意一个维信息，存储每一维级别名称以及在该级别中兄弟节点的个数，最终形成海量数据所有维信息的文件，存储于分布式文件系统中；\n[0022] 步骤2：对海量数据进行装载；\n[0023] 步骤2.1：用户根据需要确立海量数据的维信息的实际意义与其维信息的编码的对应关系，即将海量数据中的任意一条数据用维信息的编码进行表示；\n[0024] 步骤2.2：所有的最细粒度的多维海量数据形成数据立方结构，海量数据的任意一条数据作为该数据立方中的一个单元格，该单元格的信息包括：该单元格位于立方体内的坐标，以及单元格所表示的事实数据值；其中，单元格的坐标表示为：\n[0025] <一个维信息的编码，另一个维信息的编码，...，最后一个维信息的编码>；\n[0026] 所述的最细粒度是指：最低层维级别所指向的数据；\n[0027] 步骤2.3：对数据立方进行切割：\n[0028] 根据用户的查询需求，在保证查询时间最短的条件下，对数据立方进行切割，形成数据块，确定数据块的边长；\n[0029] 步骤2.4：对步骤2.3划分好的数据块进行编码，方法为：数据块内任意单元格的坐标除以数据块的边长，将所得数据向上取整后得到的值作为数据块的编码；\n[0030] 步骤2.5：步骤2.3切割好的数据块存储于分布式文件系统中，将步骤2.4确立的编码作为数据块文件的名称；\n[0031] 步骤3：采用联机数据分析OLAP的方法对海量数据进行查询；\n[0032] 步骤3.1：用户设置查询条件，包括：\n[0033] 查询目标：是指确定针对哪个数据立方进行查询，即目标立方；\n[0034] 查询范围：在已确立的查询目标中，针对哪部分数据进行查询；\n[0035] 结果的维信息：是指结果数据立方的维信息；\n[0036] 聚集方法：对查询范围内的数据进行聚集的操作；\n[0037] 步骤3.2：判断步骤3.1设置好的查询条件是否满足如下约束条件：\n[0038] 约束1：查询目标已存在，且查询范围应小于或等于查询目标的数据范围；\n[0039] 约束2：结果数据立方的维数量应小于或等于查询目标的维数量；\n[0040] 约束3：结果数据立方的任意维的最低维级别应高于查询目标对应维的最低维级别；\n[0041] 约束4：聚集方法必须是分布式的或代数式的；\n[0042] 若同时满足约束1、约束2和约束4，则执行步骤3.3；\n[0043] 若同时满足约束1～约束4则执行步骤3.4；\n[0044] 若不满足上面的任何一个条件，则查询失败，结束；\n[0045] 步骤3.3：对查询目标进行转换，寻找当前查询目标的上一级立方，判断上一级立方是否满足约束3，若不满足，再继续查询该上一级立方的上一级立方，若始终无法满足，则查询失败，结束查询过程；若找到了满足约束3的上一级立方，则将该立方替换为目标立方；\n[0046] 步骤3.4：数据的粗筛：根据查询范围确定查询所需的最小数据块的范围；\n[0047] 步骤3.5：数据的精筛；扫描步骤3.4所筛选出的数据块文件，根据查询范围对所有位于数据块内的单元格进行筛选，若单元格位于查询范围内，执行步骤3.6；否则，则舍弃该单元格；\n[0048] 步骤3.6：利用维的编码改变单元格的维级别，对比结果数据立方的维信息与目标立方的维信息，确定发生改变的维信息，对单元格坐标上表示该维的坐标进行修改；\n[0049] 步骤3.7：对具有相同坐标的单元格，根据所设定的聚集方法对单元格内的事实数据值进行聚集操作；\n[0050] 步骤3.8：经步骤3.7聚集之后的数据，形成结果数据立方，将该结果数据立方的信息返回给用户，并将该结果立方作为新的数据立方存储，使之可以作为下一轮查询的查询目标。\n[0051] 本发明的有益效果：本发明一种具有多维信息的海量数据查询方法，具有如下优点：\n[0052] 1、通过维编码的方法来组织具有多维信息的海量数据\n[0053] 2、利用数据分块存储的方法简化了数据块的寻址。\n[0054] 3、利用维的编码，快速地实现维层级的转化。\n[0055] 4、通过了基于数据块选择的方法进行数据的筛选，仅针对实际参与的数据进行计算和处理。\n附图说明\n[0056] 图1为本发明一种实施方式海洋科学数据集中的维结构示意图；\n[0057] 图2为本发明一种实施方式时间维编码示意图；\n[0058] 图3为本发明一种实施方式地区维编码示意图；\n[0059] 图4为本发明一种实施方式深度维编码示意图；\n[0060] 图5为本发明一种实施方式不符合约束1的时间维示意图；\n[0061] 图6为本发明一种实施方式多维海量数据立方结构示意图；\n[0062] 图7为本发明一种实施方式多维海量数据立方分块示意图；\n[0063] 图8为本发明一种实施方式数据粗筛示意图；\n[0064] 图9为本发明一种实施方式MapReduce实现海量数据查询方法示意图；\n[0065] 图10为本发明一种实施方式改变维编码示意图；\n[0066] 图11为本发明一种实施方式在MapReduce中改变维编码示例图；\n[0067] 图12为本发明一种实施方式具有多维信息的海量数据查询方法的流程图。\n具体实施方式\n[0068] 下面以某海洋科学数据为例，结合附图和具体实施方式对本发明作进一步的详细说明。\n[0069] 本实施方式以某海洋科学数据作为研究对象，该海洋数据为具有三维信息的海量数据。包括：时间维、区域维和深度维，对应分别用Time、Area和Depth表示，其维结构如图1所示。其中，Time共有4个级别：分别为年(Year)、月(Month)、日(Day)、次(Slot)。其中，Slot指一天的三个时间段分别进行一次测试，其维值分别是“上午”、“下午”和“晚上”，其维值树结构如图2所示。在图2中，若共有3年(2010年1月1日～2012年12月31日)的数据，则在Year维级别上，对应有3个维值，分别为2010、2011、2012，在Month维级别上，对应有36个维值，分别是2010年1月、2010年2月、......、2012年12月，在Day维级别上，我们假设每个月均有31天，则对应1116个维值，分别为2010年1月1日、2010年1月2日、......、2012年12月31日，在Slot维级别上则对应有3348个维值，分别是2010年1月1日上午、2010年1月1日中\n午、......、2012年12月31日下午。Area共有7个维级别：1°、1/2°、1/4°、1/8°、1/16°、1/32°和1/64°。其中1°指由1°经度和1°纬度所组成的方形区域，地球表面可以划分为360×180个\n1°方区，其维值树结构如图3所示。在图3中包含2°区域的数据，在1°的维级别上包含2个维值，分别是1°、2°，在1/2°维级别上包含4个维值，分别是1/2°、1°、3/2°、2°，以此类推，在1/\n64°的维级别上包含128个维值，分别是1/64°、1/32°、......、2°。Depth共有3个维级别：\n1OOm、50m、1Om，其中，1OOm指的是“海洋的深度以100米的间隔进行划分”，其维值树结构如图4所示。在图4中若水深有500m，则在1OOm的维级别上，对应有5个维值，分别为1OOm、\n200m、......、500m，在50m的维级别上，对应有10个维值，分别为50m、1OOm、......、500m，在\n1Om的维级别上，对应有50个维值，分别为1Om、20m、......、500m。在海洋数据集的立方中，每一个单元格内仅有一个事实数据，即海洋的温度数据，该数据的数据类型为双精度浮点数。\n[0070] 本实施方式，对上述具有3维信息的海洋数据进行查询的方法，其流程如图12所示，包括以下步骤：\n[0071] 步骤1：对具有3维信息的海量数据的维信息进行装载，具体包括如下步骤：\n[0072] 步骤1.1：对海量数据的维信息进行鉴别，判断海量数据的每一个维信息是否同时满足如下三个约束：\n[0073] 约束1：维由一个且仅一个维层次构成，即维是所有维级别组成的全序关系。\n[0074] 本实施方式中，对于海洋数据而言，若时间维中包含星期这个维级别时(如，2010年1月1日星期五上午)，由于月中不能包含完整的星期(如，2010年1月1日作为1月的开始，但是这一天是星期五，不是一个完整星期的开始)，因此将会产生两个维层次，分别是年(year)-星期(week)-日(day)-次(slot)、年(year)-月(month)-日(day)-次(slot)，这种维不符合约束，其示意图如图5所示。本实施方式中限定的全序关系，对于海洋数据的时间维而言，应该满足年包含季、季包含月、月包含日、日包含次，如果不满足这样的关系则不满足约束。\n[0075] 约束2：在维的任意维级别中，仅包含一个维属性，该维属性包含若干个维值。\n[0076] 考虑一个假设的城市维，其维层次为：省-市-区(例如，辽宁省-沈阳市-和平区)。\n在市维级别中，包含2个维属性，分别是城市名称、城市区号，(例如：沈阳/024)。这种维是不符合约束的。\n[0077] 约束3：在所有维值所组成对维值树中，兄弟节点包含相同个数的子节点；\n[0078] 在本实施方案中，对于海洋数据而言，在真实的情况下，在时间维中每个月包含不同的天数(如，2010年1月包含31天，2010年2月包含28天等)，反应到维值树中，则同一年内月互为兄弟节点，如2010年1月和2010年2月是兄弟节点，其父节点为2010年。则对于2010年\n1月而言，其子节点个数为31(2010年1月包含31天)，对于2010年2月而言，其子节点个数为\n28(2010年2月包含28天)。那么时间维不符合约束。\n[0079] 若满足，则执行步骤1.3，否则，执行步骤1.2；\n[0080] 步骤1.2：对维信息进行处理，使得每一个维都形成符合约束的维值树结构，处理过程如下：\n[0081] 针对约束1：若有多个维层次，则根据需要对维层次进行舍弃，仅保留一个维层次即可；\n[0082] 例如，对于2010年1月1日星期五这个时间维而言，由于存在2个维层次，所以需要将星期维级别舍弃。最终形成了如图1中所示的时间维。\n[0083] 针对约束2：若某一维级别包括多个维属性，则根据需要对维属性进行舍弃，仅保留一个维属性即可；\n[0084] 在假设的城市维中，在市的维级别中包含2个维属性，城市名称和城市编号。为了符合约束2，将维属性城市名称删除，仅保留城市编号，使得城市维符合约束2.\n[0085] 针对约束3：若兄弟节点包含的子节点个数不同，则添加空值，使兄弟节点的子节点个数相同。\n[0086] 例如，本实施方式中假设海洋数据的时间维信息是：全年有12个月，每个月固定有\n31天，这个假设中，存在与实际情况不符的情况，例如，图2中在时间维中存在有数据2010年\n2月31日，该日期并不存在，本实施方式通过设定空值的方式，对时间维进行修订，如，若为闰年，则将29日-31日设置为空值，若为非闰年，则将30日-31日设置为空值。对于仅有30天的月份，将31日设定为空值。最终形成的时间维的维值树如图2所示。在图2中，展示了时间维的维值树结构。其中固定了每个月均有31天，若遇到不足31天的情况，则使用空值补足。\n[0087] 步骤1.3：对维信息进行编码；\n[0088] 针对维值树中每一级别的维值，从左到右以十进制数依次编码，当所有的维值均有对应的编码后编码工作结束；\n[0089] 在本实施方案中，对时间维编码后的结果如图2所示。对于时间维而言，不符合本专利中维的假设，所以固定每个月为31天，遇到不足31天的情况则使用空值补足。2010年2月实际只有28天，所以使用3个空值补足31天。在图2中，仅显示一个空值，即2010年2月31日。在本实施方案中，海洋科学数据集共包含3年的海洋海水温度数据，所以在年维级别上共有3个维值，从左到右编码，其编码为0、1、2；在月维级别上共有36个维值(2010年1月至\n2013年12月)，其编码为0、1、......、35；在日维级别上共有1116个维值，编码分别为0、\n1、......、1115；在次维级别上共有3348个维值，编码分别为0、1、......、3347。区域维的编码如图3所示。在本实施方案中，海洋科学数据集共包含涉及2°方区的数据，在1°维级别中共包含2个维值，其编码为0、1，以此类推，在最低维级别(1/64°)中共有128个维值，编码分别为0、1、......、127。深度维的编码如图4所示，在本实施方案中，海洋科学数据集共包含涉及500米层深的数据。在1OOm维级别上共有5个维值，其编码分别是0、1、......、4；在50m维级别上共有10个维值，其编码分别是0、1、......、9；在10m维级别上共有50个维值，其编码分别是0、1、......、49。\n[0090] 步骤1.4：对维信息的编码进行存储；\n[0091] 对于海量数据的任意一个维信息，存储每一维级别名称以及在该级别中兄弟节点的个数，最终形成海量数据所有维信息的文件，存储于分布式文件系统中。\n[0092] 在本实施方案中，对于时间维编码后的结果如图2所示。在时间维的维值树中，年维级别共包含3个维值，且3个维值互为兄弟节点，其父节点为ALL即全部数据，兄弟节点数量为3；月级别共包含36个节点，其中在同一年的下的节点互为兄弟节点，其父节点为该年的节点，如2010年下共有2010年1月～2010年12月12个子节点，则在级别下兄弟节点的个数为12；日级别共包含1116个节点，其中在同一月下的节点互为兄弟节点，其父节点为该月的节点，如2010年1月下共有2010年1月1日～2010年1月31日共31个节点，则在该级别中兄弟节点数量为31；同理在次级别中，兄弟节点的数目为3。在本实施方案中，使用XML文件对时间维进行存储，其存储文件如表1所示。在该文件中包含了时间维的名称Time，以及各个维基本的名称和其兄弟节点的数目，例如对于年维级别而言，名称为Year，兄弟节点的数目为\n3。\n[0093] 表1为以XML形式存储的时间维\n[0094]\n[0095] 步骤2：对海量数据进行装载；\n[0096] 步骤2.1：用户根据需要确立海量数据的维信息的实际意义与其维信息的编码的对应关系，即将海量数据中的任意一条数据用维信息的编码进行表示；\n[0097] 维编码与维值的意义的翻译器由用户根据自己的需要实现。例如在本实施方案中，时间维上2010年1月1日上午，通过翻译器可以获得其在次维层级上的编码是0，地区维上1/64°通过翻译器可以获得其在1/64°维层级上的编码是0。翻译器常用的实现方法如下：\n当数据量较大时，采用数据库进行存储和查找。例如在数据库中创建一张表，在表中仅有2列，分别存储维值的意义和维值的对应编码；当维值数量较少时，采用分布式内存进行存储和查找。例如在分布式内存中创建一个哈希表，存储维值的意义和维值的对应编码；当编码与维值有数学上的对应关系时，采用编码直接计算。例如，对于深度维而言，可以通过当前层深除以当前维级别的层深划分步长后取整的方法获得。如：45m层深在10m维级别上的编码为45/10取整后为4，4即为45m层深在10m维级别上的编码。\n[0098] 步骤2.2：所有的最细粒度的多维海量数据形成数据立方结构，海量数据的任意一条数据作为该数据立方中的一个单元格，该单元格的信息包括：该单元格位于立方体内的坐标，以及单元格所表示的事实数据值；其中，单元格的坐标表示为：\n[0099] <一个维信息的编码，另一个维信息的编码，...，最后一个维信息的编码>；\n[0100] 所述的最细粒度是指：最低层维级别所指向的数据；\n[0101] 在本实施方案中，多维海量数据形成数据立方结构，其结构如图6所示。海量数据的任意一条数据作为该数据立方中的一个单元格，该单元格的信息包括：该单元格位于立方体内的坐标，以及单元格所表示的事实数据值。对于海洋数据：2010年1月1日上午在1/\n64°区内10m水深的温度数据为18℃而言，该条海洋数据作为数据立方中的一个单元格，在分布式文件系统中保存该单元的信息，包括坐标<0，0，0>，其中，第一个0表示时间维上的编码，即2010年1月1日上午在的次级别上编码为0，第2个0表示区域维上的编码，即1/64°在1/\n64°维级别上编码为0，第3个0表示深度维上的编码为0，即10m在10m维级别中的编码为0，以及事实数据18℃。\n[0102] 步骤2.3：对数据立方进行切割：\n[0103] 根据用户的查询需求，在保证查询时间最短的条件下，对数据立方进行切割，形成数据块，确定数据块的边长；\n[0104] 用户的查询需求：是指用户常用的查询条件以及其出现的概率。以用户的查询需求为对象对我们来说会有以下好处：保证查询效率，系统对于用户的查询可以快速的响应；\n保证了系统并行性和调度代价间的平衡。\n[0105] 在本实施方案中，使用MapReduce编程模型对海量数据查询方法进行实现。海量数据查询方法中MapReduce的输入是数据块文件，整个查询方法的性能与块的大小密切相关。\n块文件取值越小，并行性越好，实际参与运算的数量越少，但此时调度代价变高，如何折中的确定块文件的取值将变的十分关键。由于难以穷举所有查询条件及其出现概率，所以在本实施方案中采用随机抽样，抽取一些查询条件及其出现概率。除此之外，在本实施方案中，块文件大小的取值还考虑查询方法的运行环境。本实施方式中的海量数据查询方法利用MapReduce实现，所以块文件大小的取值还需考虑MapReduce的一些特性，例如文件寻址时间、数据处理时间等。表2列出了相关符号的定义，其中λi为变量，T和Na是计算结果，其它为已知常量。\n[0106] 表2相关符号定义\n[0107]\n[0108] 平均一个查询命中的块个数Na可以通过每个查询条件出现的概率得到，如公式1所示。\n[0109]\n[0110] 考虑MapReduce相关的一些影响因素之后，可以得到一个OLAP操作消耗的平均时间，如公式2所示。\n[0111]\n[0112] 通过公式2可以计算出T取最小值时的λi，也就得到了块大小。\n[0113] 在本实施方案中，假设计算出的块在各个维上的取值个数分别为6、4、5，即块的边长分别为558、32、10，即在时间维上按照步长为558进行划分，在地区维上按照步长为32进行划分，在深度维上按照步长为10进行划分。最终的划分结果如图7所示。在图7中较小的方格为单元格，较大的方格为数据块(如，数据块5、数据块11、数据块18、数据块19、数据块20、数据块21、数据块22、数据块23、数据块42、数据块43和数据块44)。为了绘图方便在图中每个数据块仅包含9个单元格，但是在实际操作中，数据块包含的方格数量为558*32*10，即为\n178560。在本实施方案中共包含6*4*5＝120个数据块。\n[0114] 当出现计算出的维上的块取值个数无法整除的情况时，例如假设在本实施方案中计算出的块在各个维上的取值个数分别为7、4、5时，则在时间维上无法进行整除，即3348/7不是整数时，通过向上取整的方法获得在该维上的划分步长，即此时在时间维上的划分步长为479。此时，对于数据块而言，要通过加入一些空值的方法进行补足。\n[0115] 步骤2.4：对步骤2.3划分好的数据块进行编码，方法为：数据块内任意单元格的坐标除以数据块的边长，将所得数据向上取整后得到的值作为数据块的编码。\n[0116] 从逻辑角度来看，数据块可以视作一个小立方，包含了数据立方中的一部分单元格，而数据立方也可以看作由数据块构成。在本实施方案中，假设有一条数据为2012年6月1日上午1/32°方区40m层深的海水温度为15℃，则其对应的坐标为<2697，1，4>，若块的边长分别为558、32、10，其所属的数据块坐标为<4，0，0>。其中4是由该条数据在时间维上的编码\n2697除以数据块在时间维的上长度558，并向上取整后获得的；第一个0是由该条数据在地区维上的编码1除以数据块在地区维上长度32获得；第二个0是有该条数据在深度维上的编码4除以数据块在深度维上长度10所获得的。\n[0117] 步骤2.5：步骤2.3切割好的数据块存储于分布式文件系统中，将步骤2.4确立的编码作为数据块文件的名称。\n[0118] 为了将数据块以及数据块内的单元格存储于分布式文件系统中，本实施方案首先对其编码进行了序列化。逻辑上，“立方和其单元格”或是“立方和其块”的数据结构均可以类比为“多维数组和其元素”的数据结构。物理上，块是立方的存储单元，将块内的单元格线性化后，块可以作为独立文件进行存储。为了便于寻址，块和单元格都需要支持线性化和反线性化运算，且该运算与多维数组的线性化和反线性化运算是一致的。设存在一个n维数组，其维规模记作，多维数组中的元素X在多维空间中的坐标记作(X1，X2，...，Xn)，其线性化后的坐标记作index(X)，则其线性化方法如公式3所示，反线性化方法如公式4所示。\n[0119] index(X)＝(...((Xn×An-1+Xn-1)×An-2+...+X3)×A2+X2)×A1+X1     (3)\n[0120] temp1＝index\n[0121]\n[0122]\n[0123] Xn＝tempn％An\n[0124] 对于单元格和数据块编码的线性化和反线性化的方法，与上述多维数组的线性化和反线性化方法是相同的。在对数据块线性化和反线性化时，维规模指的是数据块在各个维的取值个数，对单元格进行线性化和反线性化时，维规模指的是数据立方的各个维的长度，即组成数据立方的各个维最低层维级别中维值的取值个数。\n[0125] 假设有数据2012年6月1日上午1/32°方区40m层深的海水温度为15℃，则其对应的坐标为<2697，1，4>，且数据立方的边长分别为3348、128、50，其中3348是时间维最低层维层次，次维层次包含的维值数量，128是地区维最低维层次，1/64°维层次包含的维值数量，50是层深维最低维层次，1Om维层次包含的维值数量。直接使用公式(3)即可计算得到该条数据线性化的坐标为(4*128+1)*3348+2697＝1720221。反线性化时使用公式(4)，初始化时temp1＝1720221；X1＝1720221％3348＝2679， ；X2＝513％128\n＝1， X3＝4％128＝4，则最终反线性化后的坐标为<2679，1，4>。\n[0126] 假设有一个数据块的坐标为<4，0，0>，其中，块在各个维上的取值个数分别为6、4、\n5。则这个块线性化后的坐标为((0*4+0)*6)+4＝4；反线性化时使用公式(4)，初始化时temp1＝4；X1＝4％3348＝4， X2＝0％128＝0， X3＝\n0％128＝0则最终反线性化后的该块的坐标为<4，0，0>。\n[0127] 若当前载入数据块的坐标为<4，0，0>，则块内单元格的坐标范围是<2232，0，0>至<\n2769，31，9>。其中起始范围2232，是在时间维上编码的起始范围，通过4*558计算得来。而在时间为上的结束范围2769则是由2232+558-1计算得来。若当前载入的数据坐标为<2769，\n31，9>，对应的数据为2012年6月24日上午32/64°方区90m深度的海水温度。假设该数据的数值为20℃则新生成的记录为<3961241，20>，其中3961241＝(((9*128)+31)*3348+557)。在数据块文件中添加一条记录<3961241，20>，此时整个块文件导入完毕，其文件名为数据块序列化后的坐标，即为4。\n[0128] 按照上述方法，将块文件全部装载完毕。将当前载入的数据立方命名为原始立方，至此数据装载工作完成。\n[0129] 步骤3：采用联机数据分析OLAP的方法对海量数据进行查询；\n[0130] 步骤3.1：用户设置查询条件，包括：\n[0131] 查询目标：是指确定针对哪个数据立方进行查询，即目标立方。\n[0132] 对于一个初始的查询来说，将海量数据所形成的数据立方称之为原始的数据立方，经过初始查询之后，会产生该原始数据立方的下一级立方，在经过多次查询之后，还会产生该下一级立方的下一级立方，或者原始立方的另外的下一级立方，这些新产生的数据立方均可以作为下一次查询的基础来进行选择。\n[0133] 查询范围：在已确立的查询目标中，针对哪部分数据进行查询。\n[0134] 客户端给出想要分析的数据范围。通过用户自定义的翻译方法，将数据范围中维值的实际意义翻译为维值的编码信息。若用户要查询原始立方中的2012年4月20日下午4/\n64°方区1m至2012年6月25日上午32/64°方区90m水深的温度数据，则通过翻译后对应的数据编码范围是<2570，4，0>至<2769，31，9>。\n[0135] 结果的维信息：是指结果数据立方的维信息。\n[0136] 若我们要查看所选数据范围内的所有数据每天的海水温度的平均值，则结果数据的维信息如下：时间维，年-月-日；地区维与目标立方相同；深度维与目标立方相同。\n[0137] 聚集方法：对查询范围内的数据进行聚集的操作\n[0138] 例如，若用户要查询原始立方中的2012年4月20日下午4/64°方区1m至2012年6月\n25日上午32/64°方区90m水深，这一范围内每日的平均数，则该聚集方法就是求平均数。常用的聚集方法还有：求和、最大值、最小值等。\n[0139] 步骤3.2：判断步骤3.1设置好的查询条件是否满足如下约束条件：\n[0140] 约束1：查询目标已存在，且查询范围应小于或等于查询目标的数据范围；\n[0141] 用户所指定的查询目标必须是在系统中已经存在的。例如在系统初始化阶段，用户装载了所有的海量数据并命名为原始立方。若用户在初次查询时候指定了其他立方，则不符合约束1。若用户载入的数据为2010年至2012年、2°方区、500m层深的数据且在该原始立方中查询，但查询内容涉及到了2013年的数据，则查询范围大于了查询目标的范围，不符合约束1。实际上，对于多维数据而言，任何一维不在查询目标的数据范围内都不符合约束\n1。\n[0142] 约束2：结果数据立方的维数量应小于或等于查询目标的维数量；\n[0143] 若用户给出的查询目标是原始立方，原始立方的维是时间维、地区维、层深维，但是用户设定的结果数据立方中涉及到了其他维，例如记录人员维，此时是不符合约束2的。\n当用户仅仅指定了时间维而没有指定地区维和层深维时，是符合约束2的。此时意味着，用户不改变地区维和层深维的粒度或者说在地区维和层深维上结果数据立方和查询目标保持一致。\n[0144] 约束3：结果数据立方的任意维的最低维级别应高于查询目标对应维的最低维级别；\n[0145] 在本实施方案中，结果数据立方与查询目标在地区维和层深维上没有发生改变，仅仅在时间为上，结果数据立方的维层次为年-月-日，原始数据立方的维层次是年-月-日-次。意味着结果数据立方较查询目标在时间维上上升了一个级别。这是符合约束3的，若我们假设查询立方和结果数据立方的维信息对调，则意味着结果数据立方较查询目标在时间维上下降了一个级别，这是不符合约束3的。\n[0146] 约束4：聚集方法必须是分布式的或代数式的；\n[0147] 一个聚集函数是分布的，如果它能以如下分布方式进行计算：设数据被划分为n个集合，函数在每一部分上的计算得到一个聚集值。如果将函数用于n个聚集值得到的结果，与将函数用于所有数据得到的结果一样，则该函数可以用户分布式计算。常见的分布式聚集方法有：求和、最大值、最小值、计数等。\n[0148] 一个函数是代数的，如果它能够由一个具有若干参数的代数函数计算，而每个参数都可以用一个分布式聚集函数求得。常见的代数式聚集方法有：求平均值。\n[0149] 在本实施方案中使用平均值作为聚集方法，是符合约束4的。如果使用求中位数作为聚集方法，则不符合约束4。\n[0150] 若同时满足约束1、约束2和约束4，则执行步骤3.3；\n[0151] 若同时满足约束1～约束4则执行步骤3.4；\n[0152] 若不满足上面的任何一个条件，则查询失败，结束；\n[0153] 步骤3.3：对查询目标进行转换，寻找当前查询目标的上一级立方，判断上一级立方是否满足约束3，若不满足，再继续查询该上一级立方的上一级立方，若始终无法满足，则查询失败，结束查询过程；若找到了满足约束3的上一级立方，则将该立方替换为目标立方；\n[0154] 在不满足约束3的情况下，可以通过对目标立方进行转换的方法，使之满足约束3。\n但是无法通过转换方法满足约束3的查询，则该查询失败。\n[0155] 若有立方一，各个维层级为：年-月-日-次、1°-1/2°-1/4°-1/8°-1/16°-1/32°-1/\n64°、1OOm-50m-1Om；立方二，各个维层级为：年-月-日、1°-1/2°-1/4°-1/8°-1/16°-1/32°-\n1/64°、1OOm-50m-1Om；立方三，年-月-日-次、1°-1/2°-1/4°-1/8°-1/16°-1/32°-1/64°、\n100m-50m-10m，同时我们保证在数据范围方面，立方一包含立方二，立方二包含立方三。我们假设立方二是由立方一查询得出，此时我们计划通过查询得到立方三，且查询目标为立方二。但是这一查询不符合约束3，则进行目标立方的转化。立方二是通过在立方一上建立查询得到，则我们说立方一是立方二的上一级立方。则我们将目标立方转变为立方一，此时查询变成结果数据立方为立方三，目标立方是立方一，再次检测约束3，满足，则转换成功。\n若通过转换后，直到目标数据立方是原始立方，仍然无法满足约束3，则查询失败。\n[0156] 步骤3.4：数据的粗筛：根据查询范围确定查询所需的最小数据块的范围；\n[0157] 数据粗筛的过程示意图如图8所示。在本实施方案中，我们将针对原始立方进行查询，数据范围为的2012年4月20日下午4/64°方区1m至2012年6月25日上午32/64°方区90m水深的温度数据，对应的编码范围是<2570，4，0>至<2769，31，9>。则反映到图8中，点B的坐标为<2570，4，0>，点H为<2769，31，9>，则立方体ABCD-EFGH即为所要查询的数据范围。为了确定最小数据块的范围，我们将B点和H点的坐标分别转换成其所在的块的坐标，转换方法与步骤2.4是相同的。在本实施方案中，数据块的边长为558，32，10。通过转换后，获得最小数据块的范围是<4，0，0>至<4，0，0>。所以在本实施方案中，仅仅需要扫描1个块文件的数据。\n反映到图8中，对应的A’B’C’D’-E’F’G’H’即为块<4，0，0>内包含的数据。本实施方案，一共包含有6*4*5＝120个数据块。则通过数据粗筛的方法，我们仅仅对需要查询的数据进行处理，从而去掉了其他119个数据块参与计算。\n[0158] 步骤3.5：数据的精筛；扫描步骤3.4所筛选出的数据块文件，根据查询范围对所有位于数据块内的单元格进行筛选，若单元格位于查询范围内，执行步骤3.6；否则，则舍弃该单元格；\n[0159] 在本实施方案中使用MapReduce编程模型对多维信息海量数据查询方法进行了实现。MapReduce由四个部分组成：InputFormatter、Mapper、Reducer和OutputFormatter，分别对应数据的精晒，改变维级别，聚集和输出结果集的四个步骤。其运行流程如图9所示。\n[0160] 在本实施方案中，通过数据粗筛的数据块的坐标为<4，0，0>，则对应的数据块名称为4，其中4是由数据块坐标线性化而来。InputFormatter是文件级别的数据读入，所以InputFormatter读取通过粗筛后的数据块文件，也就是数据块文件4。InputFormatter依次读取到数据块4中的所有记录，每一条记录均是格式的，其中key是当前读取到的单元格线性化后的坐标，value是当前单元格中数据的取值。之后InputFormatter将key反线性化，后得到数据在数据立方中的坐标，与查询范围进行对比，如果符合查询范围则保留该条数据，否则就舍弃该数据。例如InputFormatter读取到一条数据为<3961241，20>，对其中线性化后的坐标3961241进行反线性化后得到坐标<2570，4，0>，其中在本实施方案中查询数据的范围是<2570，4，0>至<2769，31，9>，则该条数据符合查询范围，进入到下一步改变单元格维级别的操作。否则，则舍弃该数据。\n[0161] 步骤3.6：改变单元格的维级别，对比结果数据立方的维信息与目标立方的维信息，确定发生改变的维信息，对单元格坐标上表示该维的坐标进行修改；\n[0162] 图9展示了在本实施方案中，基于MapReduce实现的海量数据查询方法的全过程。\n若我们将块文件中的记录抽象为其中key是单元格线性化后的坐标，value是指单元格内数据的取值。通过InputFormatter读取所需的块文件，对key进行反序列化，得到的数据格式为<(a1，a2，...，an)，value>其中(a1，a2，...，an)是单元格的实际坐标，通过和查询条件检测后，所有符合条件的数据将进入到Mapper中进行改变维级别的操作。在Mapper中数据由<(a1，a2，...，an)，value>变化为<(b1，b2，...，bn)，value>其中(b1，b2，...，bn)是改变维级别后单元格的坐标。最终该坐标会被线性化后传递给Reducer处理。所有Mapper的输出为格式。在处理过程中value值始终不会发生改变。在Reducer中，相同的index的记录会进入到同一个Reducer中进行处理，Reducer使用指定的聚集方法对所有的value进行聚集后输出到OutputFormatter。最后OutputFormatter负责块文件的生成。在整个计算过程中在Mapper中单元格坐标的维级别的改变是非常重要的操作。\n[0163] 为了改变单元格的维编码，在本实施方案中我们引入分析路径的概念。图10展示了一个改变维层次的示意图，其维层次为年-月-日。在年维级别共有4个维值分别是2010、\n2011、2012、2013，在月维级别共有48个取值，分别是2010年1月、2010年2月、......、2013年\n12月；在日维级别，我们固定每个月有31天，则共有1488个取值。此时我们针对2010年2月2日这个维值进行举例。若我们当前知道2010年2月2日的维编码是2，而此时需要将该维值改变至月级别，即要计算出2010年2月的维编码。为了便于计算，本实施方式中引入分析路径\n1 2 3 1\n的概念，同时为了简述，我们将维值2010年2月2日记做<2010 ，2 ，2>，其中2010表示在时间维的第1个维级别中，即年维级别中，维值的取值是2010，其他的几项亦然。同时称维值在兄弟节点间的所处的位置(该位置从左到右计数，从0开始)为该维值的分析路径。例如对于<20101，22，23>而言其分析路径为<0，1，1>，2010在年维级别中与其他所有维值互为兄弟节点，且处于开始的维值，所以其分析路径为0，在月维级别中，2010年2月与其他2010内各月的维值互为兄弟节点，其父节点为2010年，则其所处第2个维值，但是由于分析路径从0开始计数，则其分析路径为1，2010年2月2日的分析路径的计算方法与2010年2月的分析路径计算方法相同。当前已知<20101，22，23>编码为32，需要求得<20101，22>的编码。在本实施方案中，引入分析路径与编码的转换关系如公式(5)和公式(6)所示。其中，编码记作code()，例如code(20101)为2010年的编码即code(20101)＝0；分析路径记作order()，例如order()为\n1\n2010年的分析路径即order(2010 )＝0。|li|表示第i个维级别中，任意维值的兄弟节点的个数。例如在年维级别中|l1|＝4，各个年份互为兄弟节点，在月的维级别中|l2|＝12，同一年内的各个月互为兄弟节点，在日的维级别中|l3|＝31，同一个月内的天互为兄弟节点。\n[0164] code(vi)＝(...((0+order(v1))×|l2|+order(v2))×|l3|+order(v3)...)×|li|i\n+order(v )\n[0165]                                   (5)\n[0166] tempi＝code(vi)\n[0167]\n[0168]\n[0169] order(v1)＝temp1％|l1|\n[0170] 当前已知code(20101，2223)＝32。根据公式(6)，则temp3＝32，order(20101，2223)＝32％31＝1， ，order(20101，22)＝1％12＝1， order\n(20101)＝0％4＝0。从而求得对于<20101，22，23>而言分析路径为<0，1，1>，那么显然的由于节点的相对位置不会发生改变，所以对于<20101，22>而言分析路径为<0，1>。通过公式(5)，计算得到code(20101，22)＝(0+0)*48+1＝1。从而求得对于2010年2月而言，编码为2。至此完成了编码2010年2月2日向2010年2月的转化。\n[0171] 在本实施方案中对于海量数据的查询方法，使用MapReduce进行实现，其中实现关键是单元格坐标的更新以及单元格内度量的聚集操作。为了便于叙述，我们使用2维立方对该过程进行阐述，图11中展示了查询方法执行过程中单元格坐标及其取值的变化过程，其中d1，d2是2个维，分别被分为4份。对于d1而言，其维层次为l11-l21-l31，对于d2而言，其维层次为l12-l22-l32-l42其对应的参数见如表格3所示。|l|指的是维级别l中任意节点的兄弟节点的数量。\n[0172] 表格3为OLAP算法执行相关参数\n[0173]\n[0174] 假设被处理的单元坐标为126，事实数据为67，其对应的块的坐标为6。若该单元符合查询条件，则交予Mapper进行处理，输入为<126，67>。在Mapper中，首先126会被反线性化，得出(10，6)。若在查询过程中，对应的新维层次是l12，l22。则通过公式5和公式6分别对2个维编码进行更新，结果为(1，0)，再次线性化后的得出index为1。最终该Mapper输出结果为<1，67>。当所有的输入数据的编码被改变后，本步骤结束。\n[0175] 步骤3.7：对具有相同坐标的单元格，根据所设定的聚集方法对单元格内的事实数据值进行聚集操作；\n[0176] 继续以图11为例。如其它Mapper输出以下数据<1，57>，<1，43>，则图11中Reducer的输入数据是<1，{67，57，43})。假设在本实施方案中，使用求和作为聚集方法，则Reducer的输出为<1，167>。上述Reducer的输出以记录的形式存储在OutputFormatter生成的块文件中。\n[0177] 步骤3.8：经步骤3.7聚集之后的数据，形成结果数据立方，将该结果数据立方的信息返回给用户，并将该结果立方作为新的数据立方存储，使之可以作为下一轮查询的查询目标。\n[0178] 在所有MapReduce任务完成之后，返回客户端成功信息。且将该结果立方作为新的数据立方存储，使之可以作为下一轮查询的查询目标。\n[0179] 虽然以上描述了本发明的具体实施方式，但是本领域内的熟练的技术人员应当理解，这些仅是举例说明，可以对这些实施方式做出多种变更或修改，而不背离本发明的原理和实质。本发明的范围仅由所附权利要求书限定。