Method and device for compressing flow data

Patent metadata

Field	Value
Publication number	US-9768801-B1
Application number	US-201715597963-A
Country	US
Kind code	B1
Filing date	May 17, 2017
Priority date	Nov 17, 2014
Publication date	Sep 19, 2017
Grant date	Sep 19, 2017

Abstract

A method for compressing flow data, including: constructing multiple line segments according to flow data and a predefined maximum error that are acquired; obtaining a target piecewise linear function according to the multiple line segments, where the target piecewise linear function includes multiple linear functions, and an intersection set of value ranges of independent variables of every two linear functions among the multiple linear functions includes a maximum of one value; and outputting a reference data point according to the target piecewise linear function, where the reference data point includes a point of continuity and a point of discontinuity of the target piecewise linear function. In this way, a maximum error, a target piecewise linear function is further determined according to the multiple line segments, and a point of continuity and a point of discontinuity of the target piecewise linear function are used to represent compressed flow data.

First claim

What is claimed is:

1. A method for compressing flow data, comprising:
acquiring flow data, wherein the flow data comprises multiple data points, and each data point of the multiple data points comprises collection time of each data point and a data value collected at the collection time;
acquiring a maximum error that is predefined;
constructing multiple line segments according to the multiple data points and the maximum error, wherein the multiple line segments do not intersect with each other, each line segment of the multiple line segments represents a function with time as an independent variable, and when a value of the independent variable is the collection time, an absolute value of a difference between a function value of the function and the data value collected at the collection time is less than or equal to the maximum error;
obtaining a target piecewise linear function according to the multiple line segments, wherein the target piecewise linear function comprises multiple linear functions, and an intersection set of value ranges of independent variables of every two linear functions among the multiple linear functions comprises a maximum of one value; and
outputting a reference data point according to the target piecewise linear function, wherein the reference data point is used to represent compressed flow data, and the reference data point comprises a point of continuity and a point of discontinuity of the target piecewise linear function.

2. The method according to claim 1 , wherein the constructing the multiple line segments according to the multiple data points and the maximum error comprises:
creating an extended polygon according to the multiple data points and the maximum error, wherein the extended polygon is used to represent a region in which the multiple line segments are located; and
calculating a linked list based on the extended polygon, wherein the linked list comprises an information field C[k] and a pointer field pred[k], the information field C[k] is used to represent the multiple line segments, and the pointer field pred[k] is used to indicate that the information field C[k] points to an information field C[pred[k]], and wherein k is a non-negative integer that is not equal to 1, and C[k] corresponding to each value of k is used to represent one line segment of the multiple line segments.

3. The method according to claim 2 , wherein the information field C[k], is obtained by using the following expression:

C
⁡

[
k
]

=

{

cw
⁡

(

w
0

)

,

condition
⁢

⁢
1

cw
⁡

(

nw
⁡

(

C
⁡

[

k
-
3

]

)

)

,

condition
⁢

⁢
2

cw
⁡

(

C
⁡

[

k
-
2

]

)

,

others

,

wherein
wherein the condition 1 is: k=0,
the condition 2 is: k=3 or k≧5, and the cw(C[k−2]) is located on the left side of the cw(nw(C[k−3])),
wherein for k=0, pred[0] is null,
wherein for k≠0, if C[k]=cw(nw(C[k−3])), pred[k]=k−3,
if C[k]=cw (C[k−2]), pred[k]=k−2, and
wherein the w 0 is an initial window, cw(□) represents a closing window, and nw(□) represents a next window.

4. The method according to claim 2 , wherein the obtaining the target piecewise linear function according to the multiple line segments comprises:
obtaining the target piecewise linear function according to a direction relation between the multiple line segments.

5. The method according to any claim 2 , wherein the obtaining the target piecewise linear function according to the multiple line segments comprises:
pruning the linked list, so that for different values of k, values of pred[k] are unequal; and
obtaining the target piecewise linear function according to the pruned linked list.

6. The method according to claim 5 , wherein the linked list further comprises a count field ref[k], used to represent a quantity of information fields that point to the information field C[k], wherein
if pred[k+2]=k and pred[k+3]=k, ref[k]=2,
if pred[k+2]=k and pred[k+3]≠k, ref[k]=1,
if pred[k+2]≠k and pred[k+3]=k, ref[k]=1, and
if pred[k+2]≠k and pred[k+3]≠k, ref[k]=0.

7. The method according to claim 6 , wherein the pruning the linked list comprises:
deleting C[j], pred[j], ref[j] that correspond to ref[j]=0 from th

Assignees

• Huawei Tech Co Ltd

Inventors

• Li Zhenguo
• Luo Ge
• Yi Ke
• Fan Wei
• He Cheng

Classifications

• H03M7/30 Primary

  Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction · CPC title

• H03M7/3064

  Segmenting · CPC title