Data Segmentation Algorithm Using a Decrementing Sliding Walker Chunking Approach

• US 20080016060A1
• Filed: 07/11/2006
• Published: 01/17/2008
• Est. Priority Date: 07/11/2006
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Hall, Michael David
• Granted Patent: US 7,765,170 B2
• Time in Patent Office: Days
• US Class Current: 707/6
• CPC Class Codes: G06F 16/90344 by using string matching techniques

Abstract

A method for segmenting a data set is disclosed. The method consists of setting a maximum walker size and setting a walker size. Then, a first segment of data from the data set is obtained, wherein the first segment of data is the size of the walker. Then, a second segment of data from the data set is obtained, wherein the second segment of data is not greater than the maximum walker size.

Claims

1. A method for segmenting a data set comprising:

setting a maximum walker size;

setting a walker size;

obtaining a first segment of data from the data set, the first segment of data the size of the walker; and

obtaining a second segment of data from the data set the second segment of data not greater than the maximum walker size.

2. The method of claim 1, further comprising adjusting the size of the walker, and after adjusting the size of the walker:

obtaining a third segment of data from the data set, the third segment of data the adjusted walker size, and

obtaining a fourth segment of data from the data set, the fourth segment of data not greater than the maximum walker size, the first and third segments of data being at least partially different segments of data, and the second and fourth segments of data being at least partially different segments of data.

3. The method of claim 2, further comprising:

analyzing the first and second segments of data for a pattern; and

analyzing the second and third segments of data for a pattern.

4. The method of claim 2, further comprising:

comparing the first segment of data with the second segment of data for a pattern; and

comparing the third segment of data with the fourth segment of data for a pattern.

5. The method of claim 1, wherein the maximum walker size is not more than half the length of the data set.

6. The method of claim 1, wherein the maximum walker size is substantially about half the length of the data set.

7. The method of claim 1, further comprising when additional data remains after obtaining the first and second segments of data, obtaining when available additional data segments not greater than the maximum walker size, and when data segments not greater than the maximum walker size are not available then obtaining the remaining data into a remaining segment.

8. The method of claim 1, further comprising when additional data remains after obtaining the first and second segments of data, obtaining when available additional data segments not greater than the maximum walker size, and when data segments not greater than the maximum walker size are not available then obtaining the remaining data into a minimum number of remaining segments.

9. The method of claim 1, further comprising:

analyzing the first and second segments of data;

moving the walker to obtain a third segment of data from the data set, the third segment of data the adjusted walker size;

obtaining a fourth segment of data from the data set, the fourth segment of data not greater than the maximum walker size, the first and third segments of data being at least partially different segments of data, and the second and fourth segments of data being at least partially different segments of data; and

analyzing the third and fourth segments of data.

10. The method of claim 9, further comprising one of increasing or decreasing the size of the walker.

11. A method for segmenting a data set, comprising:

setting a maximum walker size;

setting a walker size;

setting a walk offset to zero;

creating a first segment of data of the walker size at the walk offset from the data set;

from a portion of the data set remaining after the creation of the walker size segment, creating a maximum number of contiguous segments of data of maximum walker size; and

if the creation of the maximum number of contiguous segments of maximum walker size leaves additional data, grouping the additional data into a minimum number of remaining segments.

12. The method of claim 11 further comprising after the grouping of the additional data of less than the maximum walker size, determining whether the walker is at an end of the data set.

13. The method of claim 12, further comprising, when the walker is not at the end of the data set:

incrementing the walk offset by one; and

using the incremented walk offset, repeating the creating of the first segment, creating a maximum number of contiguous segments, grouping the additional data into a minimum number of remaining segments

14. The method of claim 12, further comprising, when the walker is at the end of the data set, decrementing the walker size by one and determining whether the walker size equals zero.

15. The method of claim 14, further comprising, when the walker size does not equal zero:

setting the walk offset to zero;

creating a next segment of data of walker size at the walk offset in the data set;

from the data set remaining after the creation of the next segment of data of the walker size, creating the maximum number of contiguous segments of maximum walker size;

if the creation of the maximum number of contiguous segments of maximum walker size leaves additional data, grouping the additional data into a minimum number of remaining segments.

16. The method of claim 14, further comprising, when the walker size does equal zero, stopping.

17. The method of claim 14, wherein the first and contiguous segments are sent to a pattern identification module.

18. The method of claim 14, wherein the maximum walker size is set equal to one half a size of the data set.

19. The method of claim 14, wherein the maximum walker size is set equal to a size of a largest pattern likely to be found in the data set.

20. The method of claim 14, wherein the data set includes data derived from at least one of:

an intelligent operations, administration, and management (OAM) application for a telecommunications network,

an intelligent operations, administration, and management (OAM) application for a computer network;

an image recognition application;

a biometrics application; and

a cognitive radio spectrum management application.