System and method for organizing, compressing and structuring data for data mining readiness

• US 20030009467A1
• Filed: 09/20/2001
• Published: 01/09/2003
• Est. Priority Date: 09/20/2000
• Status: Active Grant

• Current Assignee: Ndsu-Research Foundation
• Original Assignee: Ndsu-Research Foundation
• Inventors: Perrizo, William K.
• Granted Patent: US 6,941,303 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A system and method to take data, which is in the form of an n-dimensional array of binary data where the binary data is comprised of bits that are identified by a bit position within the n-dimensional array, and create one file for each bit position of the binary data while maintaining the bit position identification and to store the bit with the corresponding bit position identification from the binary data within the created filed. Once this bit-sequential format of the data is achieved, the formatted data is structured into a tree format that is data-mining-ready. The formatted data is structured by dividing each of the files containing the binary data into quadrants according to the bit position identification and recording the count of 1-bits for each quadrant on a first level. Then, recursively dividing each of the quadrants into further quadrants and recording the count of 1-bits for each quadrant until all quadrants comprise a pure-1 quadrant or a pure-0 quadrant to form a basic tree structure.

Claims

1. A method of structuring data in a data-mining-ready format, wherein said data has been previously organized in a bit-Sequential (bSQ) format that comprises a plurality of binary files identified by a bit position, said method comprising the steps of:

dividing each of said plurality of binary files into first quadrants;

recording the count of 1-bits for each first quadrant on a first level;

dividing each of said first quadrants into new quadrants;

recording the count of 1-bits for each of said new quadrants on a new level; and

repeating the two steps immediately above until all of said new quadrants comprise a pure-1 quadrant or a pure-0 quadrant to form a basic tree structure.

2. The method of claim 1, wherein said basic tree structure has a complement that provides the 0-bit counts for each of said first quadrants and said new quadrants.

3. The method of claim 1, further comprising the step of masking said basic tree structure.

4. The method of claim 3, wherein said step of masking comprises using a 3-value logic to represent said pure-1 quadrants, said pure-0 quadrants, and a non-pure quadrant.

5. The method of claim 1, further comprising constructing a value tree structure from said basic tree structure.

6. The method of claim 5, further comprising constructing a tuple tree structure from said value tree structure.

7. The method of claim 1, wherein said data comprises two-dimensional spatial data.

8. The method of claim 7, wherein said basic tree structure comprises a lossless format of said two-dimensional spatial data.

9. The method of claim 1, wherein said data comprises bioinformatics data.

10. The method of claim 9, wherein said bioinformatics data comprises microarray data.

11. The method of claim 1, wherein said data comprises nanotechnology data.

12. The method of claim 1, wherein said data comprises data representing an integrated circuit.

14. The system of claim 13, wherein said set of instructions further include directing said computer system to determine a complement of said basic tree structure that provides the 0-bit counts for each of said first quadrants and said new quadrants.

15. The system of claim 13, wherein said set of instructions further include directing said computer system to mask said basic tree structure.

16. The system of claim 15, wherein the masking of said basic tree structure comprises using a 3-value logic to represent said pure-1 quadrants, said pure-0 quadrants, and a non-pure quadrant.

17. The system of claim 13, wherein said set of instructions further include directing said computer system to construct a value tree structure from said basic tree structure.

18. The system of claim 17, wherein said set of instructions further include directing said computer system to construct a tuple tree structure from said basic tree structure.

19. The system of claim 13, wherein said data comprises two-dimensional spatial data.

20. The system of claim 19, wherein said basic tree structure comprises a lossless format of said two-dimensional spatial data.

21. The system of claim 19, wherein said data comprises bioinformatics data.

22. The system of claim 21, wherein said data comprises microarray data.

23. The system of claim 13, wherein said data comprises nanotechnology data.

24. The system of claim 23, wherein said data comprises data representing an integrated circuit.

26. The system of claim 25, wherein said data comprises two-dimensional spatial data.

27. The system of claim 25, wherein said data comprises bioinformatics data.

28. The system of claim 27, wherein said bioinformatics data comprises microarray data.

29. The system of claim 25, wherein said data comprises nanotechnology data.

30. The system of claim 25, wherein said data comprises data representing an integrated circuit.

36. The method of claim 1, wherein said data comprises data representing an integrated circuit.

13. A system for structuring data in a data-mining-ready format, wherein said data has been previously organized in a bit-Sequential (bSQ) format that comprises a plurality of binary files identified by a bit position, said system comprising:

a computer system and a set of computer readable instructions, wherein said set of instructions include directing said computer to system to;

divide each of said plurality of binary files into first quadrants;

record the count of 1-bits for each first quadrant on a first level;

divide each of said first quadrants into new quadrants;

record the count of 1-bits for each of said new quadrants on a new level; and

repeat recursively until all of said new quadrants comprise a pure-1 or pure-0 quadrant to form a basic tree structure.

25. A system for formatting data, wherein said data is in the form of an n-dimensional array of binary data, said binary data comprising a plurality of bits that are identified by a bit position within the n-dimensional array, the system comprising:

a computer system and a set of computer readable instructions, wherein said set of instructions include directing said computer to system to;

create one file for each bit position of said binary data wherein the bit position identification is maintained; and

store the bit with the corresponding bit position identification from said binary data within the created file.

31. A method of formatting data, wherein said data is in the form of an n-dimensional array of binary data, said binary data comprising a plurality of bits that are identified by a bit position within the n-dimensional array, said method comprising the steps of

creating one file for each bit position of said binary data while maintaining the bit position identification;

and

storing the bit with the corresponding bit position identification from said binary data within the created file.

32. The method of claim 31, wherein said data comprises two-dimensional spatial data.

33. The method of claim 31, wherein said data comprises bioinformatics data.

34. The method of claim 33, wherein said bioinformatics data comprises microarray data.

35. The method of claim 31, wherein said data comprises nanotechnology data.