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

• US 10,264,045 B2
• Filed: 03/28/2018
• Issued: 04/16/2019
• 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/938,845
• Publication Number:
  US 20180219930A1
• Time in Patent Office: 384 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 server processor for searching for a data stream dividing point and for dividing data into a plurality of portions the method comprising:

determining a window W_x[k−

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

A_x, k+B_x] based on a dividing rule, wherein x indicates consecutive natural numbers from 1 to M, M≥

2, and A_x and B_x are integers for establishing a potential dividing point k,

determining a corresponding window W_iz[k_i−

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

z≤

M;

determining whether at least a part of data in the window W_iz[k_i−

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

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

A_z, k_i+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 current potential dividing point k_i along a direction of searching for a data stream dividing point, wherein N*U is not greater than ∥

B_z∥

+max_x(∥

A_x∥

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

when at least a part of data in each window W_ix[k_i−

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

2. The method according to claim 1, wherein the dividing rule further comprises that at least two windows W_ie[k_i−

A_e, k_i+B_e] and W_if[k_i−

A_f, k_i+B_f] meet conditions |A_e+B_e|=|A_f+B_f| and C_e=C_f.

3. The method according to claim 2, wherein the dividing rule further comprises that A_e and A_f are positive integers.

4. The method according to claim 2, wherein the dividing rule further comprises A_e−

1=A_f and B_e+1=B_f.

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[k_i−

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

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

A_z, k_i+B_z] meets the preset condition C_z is specifically;

determining, by using a hash function, whether the at least a part of data in W_iz[k_i−

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

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

A_z, k_i+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;

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

A_z, k_i+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 current potential dividing point k_i along the direction of searching for a data stream dividing point, so as to obtain the new potential dividing point, and based on the dividing rule, a left boundary of a window W_ic[k_i−

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

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

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

A_z, k_i+B_z], wherein the window W_ic[k_i−

A_c, k_i+B_c] determined for the new potential dividing point is a window ranking the first in a sequence, which is obtained according to the direction of searching for a data stream dividing point, of M windows that are determined for the new potential dividing point based on the dividing rule.

9. A server for searching for a data stream dividing point for dividing data into a plurality of portions, comprising:

a central processing unit and a primary memory, the central processing unit communicates with the primary memory to execute computer instructions stored therein to perform the steps of;

determining a window W_x[k−

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

A_x, k+B_x] based on a dividing rule, wherein x indicates consecutive natural numbers from 1 to M, M≥

2, and A_x and B_x are integers for establishing a potential dividing point k;

determining a corresponding window W_iz[k_i−

A_z, k_i+B_z] for a current potential dividing point k_i based on the dividing rule, wherein i and z are integers, and 1≤

z≤

M;

determining whether at least a part of data in the window W_iz[k_i−

A_z, k_i+B_z] meets a preset condition C_z;

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

A_z, k_i+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 current potential dividing point k_i along a direction of searching for a data stream dividing point, wherein N*U is not greater than ∥

B_z∥

+max_x(∥

A_x∥

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

when at least a part of data in each window W_ix[k_i−

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

10. The server according to claim 9, wherein the dividing rule further comprises that at least two windows W_ie[k_i−

A_e, k_i+B_e] and W_if[k_i−

A_f, k_i+B_f] meet conditions |A_e+B_e|=|A_f+B_f| and C_e=C_f.

11. The server according to claim 10, wherein the dividing rule further comprises that A_e and A_f are positive integers.

12. The server according to claim 10, wherein the dividing rule further comprises A_e−

1=A_f and B_e+1=B_f.

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[k_i−

A_z, k_i+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[k_i−

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

15. The server according to claim 14, 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[k_i−

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

selecting F bytes in the window W_iz[k_i−

A_z, k_i+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;

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

A_z, k_i+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 current potential dividing point k_i along the direction of searching for a data stream dividing point, so as to obtain the new potential dividing point, and based on the dividing rule, a left boundary of a window W_ic[k_i−

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

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

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

A_z, k_i+B_z], wherein the window W_ic[k_i−

A_c, k_i+B_c] determined for the new potential dividing point is a window ranking the first in a sequence, which is obtained according to the direction of searching for a data stream dividing point, of M windows that are determined for the new potential dividing point based on the dividing rule.

17. A non-transitory computer-readable storage medium, wherein the computer-readable storage medium is configured to store executable computer instructions for execution by a processor that prompts the processor to determine a potential dividing point k for dividing data into a plurality of portions by:

determining a window W_x[k−

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

A_x, k+B_x] based on a dividing rule, wherein x indicates consecutive natural numbers from 1 to M, M≥

2, and A_x and B_x are integers;

determining a corresponding window W_iz[k_i−

A_z, k_i+B_z] for a current potential dividing point k_i based on the dividing rule, wherein i and z are integers, and 1≤

z≤

M;

determining whether at least a part of data in the window W_iz[k_i−

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

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

A_z, k_i+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 current potential dividing point k_i along a direction of searching for a data stream dividing point, wherein N*U is not greater than ∥

B_z∥

+max_x(∥

A_x∥

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

when at least a part of data in each window W_ix[k_i−

A_x, k_i+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 dividing rule further comprises that at least two windows W_ie[k_i−

A_e, k_i+B_e] and W_if[k_i−

A_f, k_i+B_f] meet conditions |A_e+B_e|=|A_f+B_f| and C_e=C_f.

19. The non-transitory computer-readable storage medium according to claim 18, wherein the dividing rule further comprises that A_e and A_f are positive integers.

20. The non-transitory computer-readable storage medium according to claim 18, wherein the dividing rule further comprises A_e−

1=A_f and B_e+1=B_f.

21. The non-transitory computer-readable storage medium according to claim 17, wherein:

determining, by using a random function, whether the at least a part of data in the window W_iz[k_i−

A_z, k_i+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[k_i−

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

23. The non-transitory computer-readable storage medium according to claim 21, wherein the determining, by using a random function, whether the at least a part of data in the window W_iz[k_i−

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

selecting F bytes in the window W_iz[k_i−

A_z, k_i+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;

24. 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[k_i−

A_z, k_i+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 current potential dividing point k_i along the direction of searching for a data stream dividing point, so as to obtain the new potential dividing point, and based on the dividing rule, a left boundary of a window W_ic[k_i−

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

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

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

A_z, k_i+B_z], wherein the window W_ic[k_i−

A_c, k_i+B_c] determined for the new potential dividing point is a window ranking the first in a sequence, which is obtained according to the direction of searching for a data stream dividing point, of M windows that are determined for the new potential dividing point based on the dividing rule.