Method and server for searching for data stream dividing point based on server

• US 9,967,304 B2
• Filed: 08/12/2016
• Issued: 05/08/2018
• Est. Priority Date: 02/14/2014
• Status: Active Grant

• Current Assignee: Xfusion Digital Technologies Company Limited
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: Yu, Chuanshuai, Zhang, Chengwei, Xu, Linbo
• Primary Examiner(s): Tiv, Backhean
• Application Number:
  US15/235,407
• Publication Number:
  US 20160350026A1
• Time in Patent Office: 634 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 65/762 at the source reformatting of additional data in video distribution servers H04N21/2355

Abstract

Embodiments of the present invention provide a method for searching for a data stream dividing point based on a server. In the embodiments of the present invention, a data stream dividing point is searched for by determining whether at least a part of data in a window of M windows meets a preset condition, and when the at least a part of data in the window does not meet the preset condition, a length of N*U is skipped, so as to obtain a next potential dividing point, thereby improving efficiency of searching for a data stream dividing point.

Claims

1. A method performed by a processor configured to execute instructions stored in memory, the method for selecting for a data stream dividing point to break a large amount of data into a plurality of blocks of data according to a rule, wherein the rule comprising:

for a potential dividing point k, determining M points p_x, a window W_x[p_x−

A_x, p_x+B_x] corresponding to the point p_x, and a preset condition C_x corresponding to the window W_x[p_x−

A_x, p_x+B_x], wherein x indicates consecutive natural numbers from 1 to M, M≥

2, and A_x and B_x are integers, the method comprising;

(a) determining a point p_iz and a window W_iz[p_iz−

A_z, p_iz+B_z] corresponding to the point p_iz for a current potential dividing point k_i according to the rule, wherein i and z are integers, and 1≤

z≤

M;

(b) determining whether at least a part of data in the window W_iz[p_iz−

A_z, p_iz+B_z] meets a preset condition C_z; and

when the at least a part of data in the window W_iz[p_iz−

A_z, p_iz+B_z] does not meet the preset condition C_z, skipping N minimum units U for searching for a data stream dividing point from the point p_iz along a direction of searching for a data stream dividing point, wherein N*U is not greater than ∥

B_z∥

+max_x(∥

A_x∥

+∥

(k_i−

p_ix)∥

), so as to obtain a new potential dividing point, and performing step (a); and

(c) when at least a part of data in each window W_ix[p_ix−

A_x, p_ix+B_x] of M windows of the current potential dividing point k_i meets the preset condition C_x, selecting the current potential dividing point k_i as a data stream dividing point.

2. The method according to claim 1, wherein the rule further comprises that at least two points p_e and p_f meet conditions A_e=A_f, B_e=B_f, and C_e=C_f.

3. The method according to claim 2, wherein the rule further comprises:

relative to the potential dividing point k, the at least two points p_e and p_f are in a direction opposite to the direction of searching for a data stream dividing point.

4. The method according to claim 2, wherein the rule further comprises that a distance between the at least two points p_e and p_f is 1 U.

5. The method according to claim 1, wherein determining, by using a random function, whether the at least a part of data in the window W_iz[p_iz−

A_z, p_iz+B_z] meets the preset condition C_z.

6. The method according to claim 5, wherein determining, by using a hash function, whether the at least a part of data in the window W_iz[p_iz−

A_z, p_iz+B_z] meets the preset condition C_z.

7. The method according to claim 1, wherein when the at least a part of data in the window W_iz[p_iz−

A_z, p_iz+B_z] does not meet the preset condition C_z, the N minimum units U for searching for a data stream dividing point are skipped from the point p_iz along the direction of searching for a data stream dividing point, so as to obtain the new potential dividing point, and according to the rule, a left boundary of a window W_ic[p_ic−

A_c, p_ic+B_c] corresponding to a point p_ic that is determined for the new potential dividing point coincides with a right boundary of the window W_iz[p_iz−

A_z, p_iz+B_z] or a left boundary of a window W_ic[p_ic−

A_c, p_ic+B_c] corresponding to a point p_ic that is determined for the new potential dividing point falls within a range of the window W_iz[p_i−

A_z, p_iz+B_z], wherein the point p_ic determined for the new potential dividing point is a point ranking the first in a sequence, which is obtained according to the direction of searching for a data stream dividing point, of M points that are determined for the new potential dividing point according to the rule.

8. The method according to claim 5, wherein selecting F bytes in the window W_iz[p_iz−

A_z, p_iz+B_z], and using the F bytes repeatedly H times to obtain F*H bytes in total, wherein F≥

1, each byte is formed by 8 bits, which are denoted as a_m,1, . . . , and a_m,8, representing the 1st bit to the 8th bit of an mth byte in the F*H bytes, bits corresponding to the F*H bytes can be represented as;

9. A server for searching for a data stream dividing point according to a rule, wherein the rule comprising:

for a potential dividing point k, determining M points p_x, a window W_x[p_x−

A_x, p_x+B_x] corresponding to the point p_x, and a preset condition C_x corresponding to the window W_x[p_x−

A_x, p_x+B_x], wherein x indicates consecutive natural numbers from 1 to M, M≥

2, and A_x and B_x are integers, the server comprises a central processing unit and a memory for storing computer instructions, wherein the central processing unit communicates with the memory to retrieve and execute the computer instructions to perform the steps of;

(a) determining a point p_iz and a window W_iz[p_iz−

A_z, p_iz+B_z] corresponding to the point p_iz for a current potential dividing point k, according to the rule, wherein i and z are integers, and 1≤

z≤

M;

(b) determining whether at least a part of data in the window W_iz[p_iz−

A_z, p_iz+B_z] meets a preset condition C_z; and

when the at least a part of data in the window W_iz[p_iz−

A_z, p_iz+B_z] does not meet the preset condition C_z, skipping N minimum units U for searching for a data stream dividing point from the point p_iz along a direction of searching for a data stream dividing point, wherein N*U is not greater than ∥

B∥

+max_x(∥

A_x∥

+∥

(k_i−

p_ix)∥

), so as to obtain a new potential dividing point, and performing step (a); and

(c) when at least a part of data in each window W_ix[p_ix−

A_x, p_ix+B_x] of M windows of the current potential dividing point k_i meets the preset condition C_x, selecting the current potential dividing point k_i as a data stream dividing point.

10. The server according to claim 9, wherein the rule further comprises that at least two points p_e and p_f meet conditions A_e=A_f, B_e=B_f, and C_e=C_f.

11. The server according to claim 10, wherein the rule further comprises:

relative to the potential dividing point k, the at least two points p_e and p_f are in a direction opposite to the direction of searching for a data stream dividing point.

12. The server according to claim 10, wherein the rule further comprises that a distance between the at least two points p_e and p_f is 1 U.

13. The server according to claim 9, wherein the central processing unit is specifically configured to determine, by using a random function, whether the at least a part of data in the window W_iz[p_iz−

A_z, p_iz+B_z] meets the preset condition C_z.

14. The server according to claim 13, wherein the central processing unit is specifically configured to determine, by using a hash function, whether the at least a part of data in the window W_iz[p_iz−

A_z, p_iz+B_z] meets the preset condition C_z.

15. The server according to claim 9, wherein when the at least a part of data in the window W_iz[p_iz−

A_z, p_iz+B_z] does not meet the preset condition C_z, the N minimum units U for searching for a data stream dividing point are skipped from the point p_iz along the direction of searching for a data stream dividing point, so as to obtain the new potential dividing point, and according to the rule, a left boundary of a window W_ic [p_ic−

A_c, p_ic+B_c] corresponding to a point p_ic that is determined for the new potential dividing point coincides with a right boundary of the window W_iz[p_iz−

A_z, p_iz+B_z] or a left boundary of a window W_ic[p_ic−

A_c, p_ic+B_c] corresponding to a point p_ic that is determined for the new potential dividing point falls within a range of the window W_iz[p_iz−

A_z, p_iz+B_z], wherein the point p_ic determined for the new potential dividing point is a point ranking the first in a sequence, which is obtained according to the direction of searching for a data stream dividing point, of M points that are determined for the new potential dividing point according to the rule.

16. The server according to claim 13, wherein the determining, by the central processing unit by using a random function, whether the at least a part of data in the window W_iz[p_iz−

A_z, p_iz+B_z] meets the preset condition C_z specifically comprises;

selecting F bytes in the window W_iz[p_iz−

A_z, p_iz+B_z], and using the F bytes repeatedly H times to obtain F*H bytes in total, wherein F≥

1, each byte is formed by 8 bits, which are denoted as a_m,1, . . . , and a_m,8, representing the 1st bit to the 8th bit of an mth byte in the F*H bytes, bits corresponding to the F*H bytes can be represented as;

17. A non-transitory computer-readable storage medium, wherein the computer-readable storage medium is configured to store executable instructions that, when executed by a processors, prompts the processor to search for a data stream dividing point according to a rule, wherein the rule comprising:

for a potential dividing point k, determining M points p_x, a window W_x[p_x−

A_x, p_x+B_x] corresponding to the point p_x, and a preset condition C_x corresponding to the window W_x[p_x−

A_x, p_x+B_x], wherein x indicates consecutive natural numbers from 1 to M, M≥

2, and A_x and B_x are integers, and;

(a) determining p_iz and a window W_iz[p_iz−

A_z, p_iz+B_z] corresponding to p_iz for a current potential dividing point k_i according to the rule, wherein i and z are integers, and 1≤

z≤

M;

(b) determining whether at least a part of data in the window W_iz[p_i−

A_z, A_iz+B_z] meets a preset condition C_z; and

when the at least a part of data in the window W_iz[p_iz−

A_z, p_iz+B_z] does not meet the preset condition C_z, skipping N minimum units U for searching for a data stream dividing point from the point p_iz along a direction of searching for a data stream dividing point, wherein N*U is not greater than ∥

B_z∥

+max_x(∥

A_x∥

+∥

(k_i−

p_ix)∥

), so as to obtain a new potential dividing point, and performing step (a); and

(c) when at least a part of data in each window W_ix[p_ix−

A_x, p_ix+B_x] of M windows of the current potential dividing point k_i meets the preset condition C_x, selecting the current potential dividing point k_i as a data stream dividing point.

18. The non-transitory computer-readable storage medium according to claim 17, wherein the rule further comprises that at least two points p_e and p_f meet conditions A_e=A_f, B_e=B_f, and C_e=C_f.

19. The non-transitory computer-readable storage medium according to claim 18, wherein the rule further comprises:

relative to the potential dividing point k, the at least two points p_e and p_f are in a direction opposite to the direction of searching for a data stream dividing point.

20. The non-transitory computer-readable storage medium according to claim 18, wherein the rule further comprises that a distance between the at least two points p_e and p_f is 1 U.

21. The non-transitory computer-readable storage medium according to claim 17, wherein determining, by the server by using a random function, whether the at least a part of data in the window W_iz[A_z, p_iz+B_z] meets the preset condition C_z.

22. The non-transitory computer-readable storage medium according to claim 21, wherein determining, by the server by using a hash function, whether the at least a part of data in the window W_iz[A_z, p_iz+B_z] meets the preset condition C_z.

23. The non-transitory computer-readable storage medium according to claim 17, wherein when the at least a part of data in the window W_iz[p_iz−

A_z, p_iz+B_z] does not meet the preset condition C_z, the N minimum units U for searching for a data stream dividing point are skipped from the point p_iz along the direction of searching for a data stream dividing point, so as to obtain the new potential dividing point, and according to the rule, a left boundary of a window W_ic[p_ic−

A_c, p_ic+B_c] corresponding to a point p_ic that is determined for the new potential dividing point coincides with a right boundary of the window W_z[p_iz−

A_z, p_iz+B_z] or a left boundary of a window W_ic[p_ic−

A_c, p_ic+B_c] corresponding to a point p_ic that is determined for the new potential dividing point falls within a range of the window W_iz[p_iz−

A_z, p_iz+B_z], wherein the point p_ic determined for the new potential dividing point is a point ranking the first in a sequence, which is obtained according to the direction of searching for a data stream dividing point, of M points that are determined for the new potential dividing point according to the rule.

24. The non-transitory computer-readable storage medium according to claim 21, wherein selecting F bytes in the window W_iz[p_iz−

A_z, p_iz+B_z], and using the F bytes repeatedly H times to obtain F*H bytes in total, wherein F≥

1, each byte is formed by 8 bits, which are denoted as a_m,1, . . . , and a_m,8, representing the 1st bit to the 8th bit of an mth byte in the F*H bytes, bits corresponding to the F*H bytes can be represented as;