误差界限浮点数据压缩系统

摘要

一种系统包括：接收多个原始浮点值，将多个原始浮点值中的每一个舍入为相应的舍入浮点值，其中，每个舍入浮点值在其相应的原始浮点值的误差界限内，压缩多个舍入浮点值，以及将多个压缩舍入浮点值存储在数据存储系统中。

说明书

背景技术

现代计算部署生成大量数据。该数据的存储消耗了大量的计算资源。数据压缩技术可以用于减少存储的数据的量，并因此也减少存储数据所需的资源。

数据压缩可以是无损的，其中可以从压缩数据中准确地重现原始数据，数据压缩也可以是有损的，其中不能保证从压缩数据中准确地重现原始数据。与无损压缩相比，有损压缩通常展现出更高的压缩比和/或更快的处理。在特定情境中应用的压缩技术取决于情境的容错能力以及要压缩的数据类型。

诸如物联网(IoT)架构的系统可以生成浮点数据。例如，IoT传感器可以提供温度数据，该温度数据在从摄氏温度转换为华氏温度后，表示为64位双精度值。因此，需要在存储之前对该数据进行压缩。此外，由于IoT传感器的已知准确度限制，可能允许存储这些值以使得解压缩将导致每个值的最大误差界限为0.01。

例如，鉴于误差界限为0.01，将假设要存储值{1.241，1.240，1.239，1.241，1.253}。根据用于有损浮点压缩的已知方法，前四个值被识别为处于相同值(即1.24)的误差界限内，并因此这些值存储为{4x1.24，1x1.253}(例如，“游程(run)”数组{4，1}和“值”数组{1.24，1.253})。但是，如果连续值相对于误差界限有显著变化(例如{1.2348903，3.489345，-21.2344903，...}，则已知方法将数据存储为{1x1.2348903，1x3.489345，1x-21.2344903......}(例如，如“游程(run)”数组{1，1，1，...}和“值”数组{1.2348903，3.4489345，-21.2344903，...})，这无法提供令人满意的压缩。

期望对误差界限浮点压缩进行改进。

附图说明

图1图示了根据一些实施例的用于生成、压缩、存储和检索浮点值的架构。

图2是根据一些实施例的浮点传感器值的表格表示。

图3是根据一些实施例的图2传感器值的双精度版本的表格表示。

图4是根据一些实施例的基于误差界限来舍入浮点值的过程的流程图。

图5是根据一些实施例的图2传感器值的舍入版本的表格表示。

图6图示了根据一些实施例的用于压缩浮点值的处理流水线。

图7图示了根据一些实施例的用于压缩浮点值的处理流水线。

图8图示了根据一些实施例的用于压缩浮点值的处理流水线。

图9是根据一些实施例的基于误差界限和值的总和来舍入浮点值的过程的流程图。

图10是根据一些实施例的基于误差界限和值的总和来舍入浮点值的过程的流程图。

图11是根据一些实施例的计算系统的框图。

具体实施方式

提供以下描述以使本领域的任何技术人员能够进行和使用所描述的实施例，并且阐述了预期用于实施一些实施例的最佳模式。然而，各种修改对于本领域技术人员将是显而易见的。

实施例涉及将多个浮点值中的每一个舍入到特定数目的小数位。舍入值中的每一个都在其原始值的指定误差界限内。然后对舍入后的值进行进一步的浮点压缩，根据一些实施例，其又可以包括整数压缩。一些实施例进一步操作以减小或消除误差界限的舍入值的总和相对于对应的原始浮点值的总和的差。

因此，一些实施例可以提供输入浮点值的改进的误差界限压缩，其相对于误差界限展现出连续值中的显著数目的小数位和/或大的方差。

图1图示了根据一些实施例的架构100。架构100包括传感器110a-110d，每个传感器都将浮点值提供给流处理器120。传感器110a-110d可以包括任何类型和/或数目的传感器，并且可以根据请求，异步地和/或根据任何调度或标准向流处理器120提供数据。流处理器120可以包括能够接收IoT数据并根据需要对其进行处理的处理组件(例如，IoT集线器)。实施例不限于由传感器生成或由流处理器处理的浮点值。

根据图示的示例，流处理器120将接收到的浮点值发送到数据库平台130以进行存储。在发送到数据库平台之前，流处理器120可如本文所述压缩数据。

数据库平台130包括数据库管理系统(DBMS)132和数据存储134。DBMS 132可以在存储在数据存储134中之前如本文所述压缩数据，并在将数据提供给请求者之前解压缩由此存储的数据。DBMS 132还可以执行数据库平台130的管辖和管理功能。这样的功能可以包括快照和备份管理、索引、优化、垃圾收集和/或任何其它已知或将要知道的数据库功能。

数据存储134可以包括用于以已知的或变得已知的任何格式存储数据的任何存储系统。数据存储134可以包括数据库表的数据和描述数据结构的元数据，但是实施例不限于此。数据存储134的数据可以包括常规表格数据、基于行的数据、基于列的数据和基于对象的数据中的一个或多个。此外，可以在索引中对数据进行索引和/或选择性重复，以允许对其进行快速搜索和检索。

数据库平台130可以实现“存储器中(in-memory)”数据库，其中完整数据库存储在易失性(例如，非基于磁盘的)存储器(例如，随机存取存储器)中。完整数据库可以持久化在和/或备份到固定磁盘(未显示)中。实施例不限于存储器中的实现方式。例如，数据可以存储在随机存取存储器(例如，用于存储最近使用的数据的缓冲存储器)和一个或多个固定盘(例如，用于存储整个数据库的它们的相应部分的持久存储器)中。

查询服务器140可以处理从数据库应用(未示出)接收的结构化查询语言(SQL)和多维表达(MDX)语句。处理可以包括查询执行计划的生成和执行以从数据存储134检索数据。如上所述，DBMS 132可以在将数据发送到查询服务器140之前解压缩检索到的数据。

图2是根据一些实施例的可以被压缩的浮点传感器值200的表格表示。可以从任何合适的一个或多个源接收传感器值200，并且实施例不限于由传感器生成的值。出于比较的目的，图3是根据一些实施例的对应于传感器值200的双精度值300的表格表示。实施例可以尝试在维持指定的误差界限的情况下将诸如传感器值200的值压缩到每个值小于64位的存储空间。

图4是根据一些实施例的基于误差界限来舍入浮点值的过程400的流程图。在一些非穷举的实施例中，数据库系统的各种硬件元件执行程序代码以执行过程400。过程400和本文中提及的所有其它过程可以实施为从诸如硬盘驱动器、易失性或非易失性随机存取存储器、DVD-ROM、闪速驱动器和磁带的非暂时性计算机可读介质中的一个或多个读取的处理器可执行程序代码，并且然后以压缩、未编译和/或加密的格式存储。在一些实施例中，可以使用硬连线电路代替程序代码或与程序代码组合，以实现根据一些实施例的过程。实施例不限于硬件和软件的任何具体组合。

初始，在S405处接收多个原始浮点值。可以从任何已知的或变得已知的源接收或获取多个浮点值。多个原始浮点值中的每一个可以包括正值或负值，并且多个原始浮点值中的每一个可以包括任何数目的小数位。

根据一些实施例，在S405处还接收到误差界限或量化误差的指示。误差界限可以指示最大的每个值的误差，其可以由过程400所得到的值来展现。因此，S405可以包括鉴于特定的误差界限而接收压缩一组浮点值的命令。

在一些实施例中，执行过程400的组件了解适用的误差界限。例如，在架构100的情况下，DBMS 132可以在S405处接收命令以存储多个浮点值。然后，DBMS 132鉴于预定的误差界限，独立地确定执行过程400的其余部分以压缩和存储浮点值。

在S410处，将多个原始浮点值中的每一个舍入到特定数目(即，N)的小数位。根据当前描述的示例，N初始设置为小数目。实施例不限于此，下面将描述这些替代实施例。

更具体而言，将假设多个原始浮点值是图2的传感器值200，误差界限为0.01，并且N初始设置为零。在S410处，每个传感器值200被舍入到具有零小数位的值。因此，{1.24225，1.25121，1.2639，1.2692}舍入到{1，1，1，1}。根据一些实施例，可以使用“缩放因子”来执行该舍入，使得rounded_value＝round(original_value*scaling_factor)/缩放因子。在S410处使用初始缩放因子1(对应于N＝0)，rounded_value＝round(1.24225*1)/1＝1。

接下来，在S415处，确定每个舍入值是否在其对应的原始值的指定误差内。在数学上，对于每个原始值，S415评估|original_value-rounded_value|<0.01是否为真。参考本示例，S415确定|1.24225-1|<0.01，|1.25121-1|<0.01，|1.2639-1|<0.01，|1.2692-1|<0.01是否都为真。在其它实施例中，S415可以包括确定最大值(original_value-rounded_value)以及将最大值与误差界限进行比较。在任何一种情况下，并且由于以上不等式均不为真，因此在以上示例中的S415处的确定为否定。

如果在S415处的确定为否定，则流程继续进行到S420。在S420处，确定N是否已经达到最大预先指定值。在满足误差界限所需的小数位的数目大于期望的小数位的数目的情况下，或者如果一个或多个原始值使得无论值被舍入到小数位的数目(如Inf)都无法满足误差界限，则S420提供从过程400退出。

因此，如果在S420处的确定为肯定，则流程继续进行到S435以简单地输出原始浮点值。

如果N尚未达到最大预先指定值，则流程从S420继续进行到S425以递增N。然后，在S410处将多个原始浮点值中的每一个舍入到递增数目的小数位。

假设N现在等于1，则可以在S410处使用缩放因子10执行舍入。例如，rounded_value＝round(1.24225*10)/10＝1.2，rounded_value＝round(1.25121*10)/10＝1.3，rounded_value＝round(1.2639*10)/10＝1.3，以及rounded_value＝round(1.2692*10)/10＝1.3。每个舍入值的对应误差为{0.04225，0.04879，0.0361，0.0308}。由于所有这些值均大于0.01，因此在S415处的后续确定为否定，并且流程返回到S420。

N在S425处递增到2，对应于缩放因子100。因此，在S410处，rounded_value＝round(1.24225*100)/100＝1.24，rounded_value＝round(1.25121*100)/100＝1.25，rounded_value＝round(1.2639*100)/100＝1.26，以及rounded_value＝round(1.2692*100)/100＝1.27。每个舍入值的对应误差为{0.00225，0.00121，0.0039，0.0008}。因此，在S415处确定每个舍入值在其原始值的0.01以内。

流程从S415继续进行到S430以输出舍入值。参考上面的示例，输出值为{1.24，1.25，1.26，1.27}。图5是根据一些实施例的输出舍入值500的表格表示。

如上所述，S410的一些实施例对N使用较大的初始值(例如20)。因此，在S415处的肯定确定使得N递减，并且在S410处基于递减的值进行舍入。流程以这种方式继续，直到在S415的确定为否定，在这种情况下，输出舍入值是与N的先前值(和对应的缩放因子)相对应的值。

然后，可以对输出的舍入浮点值进行进一步的压缩。与其它有损浮点压缩技术相比，使用输出舍入浮点值而不是原始浮点值可能会导致更高的压缩比。

图6至图8图示了根据一些实施例的用于压缩浮点值的处理流水线。所图示的流水线可以在需要浮点值压缩的任何系统中实现。实施例不限于所图示的流水线。

流水线600包括误差界限舍入组件610以接收浮点值。组件610可以对接收到的浮点值执行过程400，以生成和输出舍入浮点值，如上所述。组件610还可以接收误差界限值以用于过程400。图6至图8的组件610和每个其它组件可以包括一个或多个执行程序代码的处理单元。

浮点压缩组件620从舍入组件610接收舍入浮点值，并执行压缩以生成和输出压缩浮点值。压缩浮点值可以根据需要被存储和/或发送。浮点压缩组件620可以执行已知的或变得已知的任何类型的无损或有损的浮点压缩。

根据一些实施例，图7的流水线700可以包括流水线600的具体实现方式。误差界限舍入组件710可以如上所述执行过程400。整数转换组件720和整数压缩组件730可以一起执行浮点压缩。例如，整数转换组件720可以将由舍入组件710输出的舍入值转换成整数值。由于舍入值可以各自展现相同数目的小数位N，因此整数转换组件720可以确定缩放因子10

整数压缩组件730接收多个整数值和缩放因子。组件730可以使用已知的或变得已知的任何整数压缩算法来压缩整数值。算法可以包括算法的组合，诸如但不限于压缩、游程压缩和增量压缩。如已知的，组合可以取决于被压缩的具体整数值和/或它们彼此之间的关系。

图8图示了包括误差界限舍入组件810的流水线800，该组件可以执行过程400以生成多个舍入浮点值。如以上背景技术中所描述的，可以由组件820对舍入浮点值进行适应性分段逼近。例如，如果组件810输出的舍入值是{1.241，1.240，1.239，1.241，1.253}，并且要由组件820进行误差界限为0.01的有损压缩，则值被输出为“游程”数组{4，1}和“值”数组{1.24，1.253}。然后，可以由整数压缩组件830对游程数组进行整数压缩，以生成压缩游程数组，并且由浮点压缩组件840对值数组进行浮点压缩，以生成压缩值数组。组件840的浮点压缩可以如以上关于组件720和730所述继续进行，但是实施例不限于此。

图9是根据一些实施例的基于误差界限和值的总和来舍入浮点值的过程900的流程图。在一些情境下，可以对由过程400输出的舍入值执行过程900。例如，上述组件610、710和810中的任何一个都可以执行过程400，然后执行过程900，以基于误差界限和压缩值的总和来压缩多个浮点值。

为了说明值的总和的相关性，考虑以下多个要压缩的值：{1.24，1.24，1.24，1.24，1.24，1.24，1.24，1.24，1.24，1.24}。平均值为1.24，这些值的总和为12.4。鉴于误差界限为0.1，使用过程400压缩值，则所得到的舍入值将为{1.2，1.2，1.2，1.2，1.2，1.2，1.2，1.2，1.2，1.2，1.2}，舍入值的平均值为1.2，总和为12。因此，如果舍入值代替原始值存储，则对存储数据的某些累积计算与对原始数据执行合计计算将导致不同的解。

以下舍入值也在原始值的0.1的误差界限内：{1.2，1.2，1.2，1.2，1.2，1.2，1.3，1.3，1.3，1.3}。与原始值的情况一样，这些值的平均值为1.24，总和为12.4。因此，在一些情境下，第二组舍入值可以被认为是原始值的更接近的表示。例如，对第二组舍入值的某些累积计算可能会导致解更相似于如果将计算应用于原始值时会生成的解。

假定在过程900之前，例如通过过程400，已经将多个原始浮点值压缩为具有N个小数位的多个舍入浮点值。过程900开始于S905，在S905处，将值M和sum_approx分别初始化为1和0。

接下来，在S910处，第M个(即，第一)舍入值的第N个小数位递增以生成递增舍入值，并递减以生成递减舍入值。例如，假设N＝2，并且第一舍入值为1.23，则第一递增值为1.24，第一递减值为1.22。

在S915处，选择第一舍入值、第一递增值和第一递减值中的一个。所选择的值是在第M个原始值的误差界限内的值，并且对于所选择的值，sum_approx+所选择的值最接近前M个原始浮点值的总和。在S915的第一迭代的情况下，所选择的值简单地是在误差界限内并且最接近第一原始值的值。返回到上面的示例，如果原始值为1.2349并且误差界限为0.01，则第一递增值1.24在误差界限内，而第一递减值1.22不在误差界限内。第一递增值(1.24)与原始值(1.2349)之间的差为.0051，第一舍入值(1.23)与原始值(1.2349)之间的差为.0049。因此，在S915处选择第一舍入值(1.23)。

所选择的值将被加到sum_approx，以生成所选择的值的新运行总和。S925确定是否存在多个舍入值的下一舍入值。如果存在，则在S930处将M递增1，并且流程返回到S910以递增第M个(即，第二)舍入值的第N个小数位以生成第二递增舍入值，并递减第M个(即，第二)舍入值的第N个小数位以生成第二递减舍入值。

关于第二舍入、递增和递减值，S915如上所述继续进行。选择这些值中的一个值，该所选择的一个值在第二原始值的误差界限内(第二舍入值将凭借过程400在误差界限内)，并且对于该所选择的一个值，新的sum_approx+所选择的值最接近于前两个原始浮点值的总和。然后流程如上所述继续进行到S920。

因此，流程从S910到S930循环，直到在S925处确定已经处理多个舍入值中的最后一个舍入值。接下来，在S935处，输出在S915的M次迭代期间所选择的M个值中的每一个。如上所述，输出值将在其对应的原始值的误差界限内，并且原始值的总和相较于输入到过程900的舍入值的总和可能更接近输出值的总和。

图10是根据一些实施例的基于误差界限和值的总和来舍入浮点值的过程1000的流程图。与过程900不同，过程1000的输出值的总和旨在等于原始的多个非舍入的浮点值的总和。

对于给定的多个舍入输入值V，对于第一至V-1值，过程1000在S1015处选择与在过程900的S915处选择的相同的值。然而，一旦在S1025处确定仍然需要处理最后一个舍入值V，则流程继续到S1035。在S1035处，确定值，对于该值，所有所选择的值的总和将等于多个原始浮点值的总和。换言之，确定的值是多个原始浮点值的总和与当时的sum_approx之间的差。在S1040处输出所选择的M个值和在S1035处确定的值。

在S1035处确定的值可以包括任何数目的小数位，并且可以被存储为与输出的所选择的M值不同的类型(例如，双精度)并且经历与输出的所选择的M值不同的压缩。在10,000个输入值的块上运行过程400+1000的情况下，每10,000个条目将存储一个这样的校正值。

图11是根据一些实施例的数据库系统1100的框图。数据库系统1100可以包括通用计算装置，并且可以执行程序代码以执行本文描述的任何功能。在一些实施例中，数据库系统1100可以包括数据库平台130的实现方式。根据一些实施例，数据库系统1100可以包括其它未示出的元件。

数据库系统1100包括可操作地耦接到I/O设备1120的(多个)处理单元1110、数据存储设备1130、一个或多个输入设备1140、一个或多个输出设备1150以及存储器1160。I/O设备1120可以促进与外部设备的通信，诸如流式集线器、客户端设备或数据存储设备。(多个)输入设备1140可以包括例如键盘、小键盘、鼠标或其它定点设备、麦克风、旋钮或开关、红外(IR)端口、扩展坞和/或触摸屏。(多个)输入设备1140可以例如用于将信息输入系统1100。(多个)输出设备1150可以包括例如显示器(例如，显示屏)、扬声器和/或打印机。

数据存储设备1130可以包括任何适当的持久性存储设备，包括磁存储设备(例如，磁带、硬盘驱动器和闪速存储器)、光存储设备、只读存储器(ROM)设备等的组合，而存储器1160可以包括随机存取存储器(RAM)。

数据存储设备的数据库应用、查询服务器和数据库管理系统可以各自包括由(多个)处理单元1110执行的程序代码，以使得系统1100执行本文所述的任何一个或多个过程。实施例不限于由单个计算设备执行这些过程。

设备1130中存储的数据可以包括已知的数据库表。数据库表(缓存的数据库或完整的数据库)可以存储在易失性存储器中，诸如易失性存储器1160。数据存储设备1130还可存储数据和其它程序代码，以提供附加功能和/或系统1100的操作所必需的功能，诸如设备驱动器、操作系统文件等。

前述图表示根据一些实施例的用于描述过程的逻辑架构，并且实际的实现方式可以包括以其它方式布置的更多或不同的组件。其它拓扑可以与其它实施例结合使用。此外，本文描述的每个组件或设备可以由经由任何数目的其它公共和/或私有网络通信的任何数目的设备来实现。两个或更多个这样的计算设备可以彼此远离放置，并且可以经由任何已知的(多个)网络方式和/或专用连接彼此通信。每个组件或设备可以包括适合于提供本文描述的功能以及任何其它功能的任何数目的硬件和/或软件元件。例如，在一些实施例的实现方式中使用的任何计算设备可以包括处理器以执行程序代码，使得计算设备如本文所述进行操作。

本文描述的实施例仅出于说明的目的。本领域技术人员将认识到，可以通过对上述实施例进行修改和替代来实践其它实施例。