Storage and retrieval of compressed data in mixed mode

Methods of storing and retrieving compressed data and uncompressed data in a mixed mode are described. Generally, the method comprises the steps of compressing a fixed amount of input data within a sequence of frames to provide storage and retrieval in a sequential manner and random manner. The sequence of frames includes at least a first frame and a final frame. Each frame includes a first portion for storing uncompressed data and a second portion for storing compressed data. The uncompressed data is stored within a first portion of the first frame. The compressed data is stored within a second portion of the first frame.

Not applicable.

NAMES OF PARTIES TO A JOINT RESEARCH AGREEMENT

Not applicable.

REFERENCE TO A “SEQUENCE LISTING,” A TABLE, OR A COMPUTER PROGRAM LISTING APPENDIX SUBMITTED ON A COMPACT DISC AND AN INCORPORATION BY REFERENCE OF THE MATERIAL ON THE COMPACT DISC

Not applicable.

BACKGROUND

1. Field of the Invention

The present invention relates generally to the storage and retrieval of data in a mixed mode. More specifically, but not by way of limitation, the invention relates to the storage and retrieval of datasets having uncompressed and compressed data residing within the same frame or data space.

2. Brief Description of Related Art

It is well recognized within the art that there are several advantages in compressing vast amounts of data into small sets. Compressing data eases data storage, transmission, and retrieval applications. For example, compressing data aids in the reduction of consumption of expensive resources including storage space and/or transmission bandwidth.

There are many different encoding schemes for compressing data. For example, in one embodiment described in the Patent entitled “METHOD FOR ENCODING DATA,” the encoding scheme uses a compression process wherein an input stream is manipulated, encoded, and summarized to form entities that represent the input stream in a different form within the compressed sets. See U.S. Pat. No. 7,298,293, filed on May 18, 2006, the entire contents of which are hereby incorporated by reference in its entirety. In the alternative, in U.S. Provisional Patent No. 61/016,022 entitled METHOD FOR ENCODING & DECODING DATA, and the U.S. Provisional Patent No. 61/038,527 entitled METHOD FOR ENCODING & DECODING DATA, the subsequent decompression of data is described. See U.S. Provisional Patent No. 61/016,022, filed on Dec. 21, 2007, and U.S. Provisional Patent No. 61/038,527, filed on Mar. 21, 2008, the entire contents of which are hereby incorporated by reference in their entirety.

These references, and other similar encoding and decoding schemes, deal with what may be termed as “extreme” compression and decompression of data. Extreme compression, and also general compression and decompression of data, are useful in the storage and retrieval of data in a mixed mode as will be described in further detail herein.

Original data may be considered data in an uncompressed state. When the original data is compressed, this may be thought of as compression occurring at the “lowest level.” Data manipulation of the resulting compression dataset is at a “higher level” as will be described in further detail herein.

Retrieval of data, whether at a lower level or a higher level, is generally needed either on a sequential basis, or on a random basis. For example, a motion picture that digitizes frame by frame and stores the frames in a medium for retrieval and play back utilizes sequential access. Alternatively, data provided on an as needed basis, such as an employee name or business contact, utilizes random access. Thus, a storage and retrieval process that accounts for both sequential access and random access is also generally needed.

Throughout the discussion, terms are used that are commonly found in the Flora species such as trees, branches, leaves, blooms, buds, petals, cones, etc. Using these analogies, the inter relationships between the various data elements are described in a more intuitive manner.

BRIEF SUMMARY OF THE EMBODIMENTS

The present embodiments relate to an encoding scheme involving memory and/or storage of uncompressed data and compressed data in a mixed mode. In one embodiment, a fixed amount of input data is compressed within a sequence of frames using a forward freeze. The forward freeze allows for the storage and retrieval of data within a mixed mode. The mixed mode is a combination of an uncompressed dataset and a compressed dataset within a single or multiple frames. In general, frames are subdivided into two portions wherein one portion contains uncompressed data and a second portion contains the compressed data. A first frame is encoded and compressed to form a compressed dataset. The compressed dataset from the first frame is stored within the second portion of a second frame, which contains uncompressed data in its first portion. The second frame is encoded and compressed to form a second compressed dataset. The second compressed dataset is stored within the second portion of a third frame, which contains uncompressed data in its first portion. This process is repeated until the final frame is compressed. Compression of the final frame yields the final compressed dataset.

In another embodiment, a fixed amount of input data is compressed within a sequence of frames using a reverse freeze. In a reverse freeze, the final frame is encoded and compressed to form a first compressed dataset. The first compressed dataset from the final frame is stored within the second portion of a preceding frame, which contains uncompressed data in its first portion. The preceding frame is encoded and compressed to form a second compressed dataset. This process is repeated until the first frame is compressed. Compression of the first frame yields the final compressed dataset.

DETAILED DESCRIPTION OF THE EMBODIMENTS

Present embodiments of the invention are shown in the above-identified figures and described in detail below. In describing the embodiments, like or identical reference numerals are used to identify common or similar elements. The figures are not necessarily to scale and certain features in certain views of the figures may be shown exaggerated in scale or in schematic in the interest of clarity and conciseness.

Referring now to the figures, and in particular toFIGS. 1 and 2, shown therein and designated by reference numeral10is a petal having an arbitrary, but fixed amount of memory space. Throughout the specification, the petal10may also be referred to herein as a frame10.

The size of the petal10may be related to the use and cost of the application, and as such, multiple petals10may be used. Additionally, in certain situations, it is advantageous to standardize the petal10size in order to facilitate exchange of information. For example, as illustrated inFIG. 2, if each petal10comprises one megabyte, and the application requires 9.5 megabytes, ten petals10may be needed in order to standardize the petal10size. In this situation, nine petals10(1.1-1.9)are able to hold nine megabytes of data and one petal10(1.10)holds 0.5 megabytes of data. Multiple sets of petals10are generally referred to as a petal row12or a frame row12.

Petals10are identified by a two-part number known as the “Petal Tag” or “Frame Tag.” The first number is the petal row number (PRN) and the second number is the petal number (PN) within the petal row12, i.e. the sequence number of the petal10. The Petal Tag is generally shown within round brackets as (PRN. PN). For example, the petal row12inFIG. 2is a single row (PRN=1). Thus the petal tags for the petal row12inFIG. 2are: (1.1), (1.2), (1.3), (1.4), (1.5), (1.6), (1.7), (1.8), (1.9), and (1.10).

A sequence having 3 petal rows (not shown), a first row with 6 petals, the second row with 3 petals, and a third row with 3 petals, the following petal tags would be used:For Row1, the petal tags are: (1.1), (1.2), (1.3), (1.4), (1.5) and (1.6);For Row2, the petal tags are: (2.1), (2.2), and (2.3); and,For Row3, the petal tags are: (3.1), (3.2), and (3.3).

FIG. 3illustrates a flow chart of one embodiment of a method for forming a mixed frame. The petal10represents information at the lowest level, that is, the petal represents information in the greatest expanded state (e.g. having uncompressed data). Data within the petal10is compressed through any suitable means to form the frozen petal16. For example, compression of the data within the petal10may be through the super cooling process as described in U.S. Pat. No. 7,298,293, filed on May 18, 2006, entitled METHOD FOR ENCODING DATA, the entire contents of which are hereby incorporated by reference in its entirety. Although the reference discloses “extreme” compression, it will be apparent to one skilled in the art, the techniques described herein are not limited to “extreme” compression, but are relevant as long as compression results in a data set that is a percentage of the original size.

The formed frozen petal16may then be directed into the original petal10or a separate petal10a. The frozen petal16is placed in a subset of the petal10and/or petal10areferred to as a freezer18. In the embodiment illustrated inFIG. 3, the petal10is compressed forming the frozen petal16and placed within the freezer18aof the separate petal10a. Petals10ahaving both compressed data and uncompressed data are referred to as being in a mixed mode.

The freezer18may exist in any space within the petal10. Preferably, in multiple sets of petals10, each freezer18within each petal10is located in substantially the same location. For purposes of clarity and conciseness within the following description, each freezer18is illustrated within the figures in a fixed location within each petal10.

The petal10generally contains two types of data: the compressed data and uncompressed data. As such, the petal10can exist in a mixed mode of compressed data and uncompressed data. As previously described, the compressed data is located within the freezer18. As one skilled in the art will appreciate, compressed data is only generally useful once uncompressed.

The uncompressed data is located within the remaining space of the petal10external to the freezer18. Examples of uncompressed data include text, sound, video, and other similar data. For example, the uncompressed data may contain sound data useful in electronic applications.

In general, access to data is primarily needed on either a sequential basis or random basis. Thus, the storage and retrieval process for a mixed mode must provide for both sequential access and random access in order to access the uncompressed data. In sequential access, there are primarily two techniques: forward freezing (also referred to as forward compression) and reverse freezing (also referred to as reverse compression).

Forward freezing provides access to data on a sequential basis. Sequential access is useful in many applications such as the retrieval during motion picture storage and use. For example, a motion picture that digitizes each movie frame by frame and stores the movie frames in a medium for retrieval and play back, generally uses sequential access in retrieval. The forward freezing process as described herein allows for sequential access by retrieving the data in reverse order of its original ordering.

FIG. 4is a block diagram illustrating one embodiment of a method for forward freezing. Generally, each of the petals10initially contains uncompressed data in a first portion designated for uncompressed data. Data is compressed within each petal10using an encoding scheme to form the frozen petal16. In a preferred embodiment, the petals10are compressed using the super cooling process as described in the Patent entitled “METHOD FOR ENCODING DATA.” See U.S. Pat. No. 7,298,293, filed on May 18, 2006, the entire contents of which are hereby incorporated by reference in its entirety. It should be noted that any other compression method known in the art may also be used to compress the data. In the super freezing process, an input stream of data is manipulated, encoded, and summarized to form entities that represent the input stream in a different form within the compressed sets. Super freezing allows for the unlimited compression of data. Compressing forms the frozen petal16, which is inserted into the freezer18of a subsequent petal10.

FIG. 4illustrates forward freezing using six petals10. The six petals10are within one petal row12. Thus, the petal tags for each petal10are (1.1), (1.2), (1.3), (1.4), (1.5), and (1.6). It should be noted that any number of petals10within the petal row12may be used without deviating from the methods of forward freezing as described herein.

The first petal10(1.1)includes a termination code22within the freezer18(1.1). The termination code22provides a mechanism to signify a termination point during the decompression process. Initially, petal10(1.1)is compressed, and the resulting frozen petal16(1.1)is inserted into the freezer18(1.2)of the petal10(1.2). Petal10(1.2)is then compressed, and the resulting frozen petal16(1.2)is inserted into the freezer18(1.3)of petal10(1.3). This process continues through petal10(1.6)resulting in the freezer18(1.6)of the final petal10(1.6)holding all of the frozen petals16(1.1)-(1.5)in addition to uncompressed data external to the freezer18(1.6). Compression of the final petal10(1.6)results in the formation of a bud24[1], also referred to herein as a final compressed dataset.

Buds24are generally the same as a frozen petal16. The distinction between buds24and frozen petals16is that a frozen petal16contains the compressed information of single petals10, a bud24contains compressed information of a row of petals12. In order to distinguish the additional information carried by the bud24, the bud24is shown as a box with line drawn in the middle. For example, as illustrated inFIG. 4, a first half26of the bud24[1]represents the first petal10(1.1)and a second half28of the bud24represents the final petal10(1.6). In the first half26of the bud24[1], the first petal10(1.1)is numerically represented within a first box30aand the content of the freezer18(1.1)is illustrated within a second box32a. Similarly, in the second half28of the bud24[1], the final petal10(1.6)is numerically represented within a first box30band a second box32bis blank.

Bud tags identify the path by which the bud24[1]is derived. The bud tag indicates the petal10and petal row12to which the bud24is attached to (PAand PRArespectively), and also includes the petal row from which it was formed (PF). Bud tags are odd number of digits enclosed within square bracket represented as: [PA. PRA. PF]. If the bud24does not attach to a separate petal row12, the bud tag is represented solely as [PF] For example, the bud24[1]inFIG. 4is derived through a single petal row12and is not attached to a separate petal row. The bud tag, [1], thus indicates a single petal row was used in deriving the bud24. Bud tags become extremely useful in describing buds24derived and attaching to multiple petal rows12, as will be discussed in further detail herein below.

Decompression extracts data within the bud24[1]. Decompression may be through any decompression process known in the art, such as, for example, the decompression process described in U.S. Provisional Patent No. 61/016,022 entitled METHOD FOR ENCODING & DECODING DATA, and the U.S. Provisional Patent No. 61/038,527 entitled METHOD FOR ENCODING & DECODING DATA. See U.S. Provisional Patent No. 61/016,022, filed on Dec. 21, 2007, and U.S. Provisional Patent No. 61/038,527, filed on Mar. 21, 2008, the entire contents of which are hereby incorporated by reference in their entirety. Decompression of the bud24[1]begins with the final petal10(1.6). The freezer18(1.6)of the final petal10(1.6)holds the data in petals10(1.1)-(1.5)in a compressed form. Decompression of the data within each petal10(1.1)-(1.5)is in a sequential manner in the reverse order in which the petals10(1.1)-(1.6)were compressed. The contents of the freezer18(1.6)of the final petal10(1.6)is the same as the frozen petal16(1.5). Decompressing frozen petal16(1.5)yields petal10(1.5). This process is repeated until reaching the termination code22within the first petal10(1.1). The termination code22signals the end of the decompressing process.

Reverse freezing, similar to forward freezing, provides access to data on a sequential basis.FIG. 5illustrates a block diagram of one embodiment of a method for reverse freezing using petals10(1.1)-(1.6). Although six petals10are illustrated in this embodiment, it should be noted that any number of petals10may be used without deviating from the scope of the reverse freeze process.

In the reverse freeze, the final petal10(1.6)includes the termination code22within the freezer18(1.6). The termination code22provides a mechanism to signify a termination point during decompression. Similar to the forward freeze, each petal10adds the frozen petal16of the previous petals10. For example, petal10(1.6)is compressed, and the resulting frozen petal16(1.6)is inserted into the freezer18(1.5)of the petal10(1.5). Petal10(1.5)is then compressed, and the resulting frozen petal16(1.5)is inserted into the freezer18(1.4)of the petal10(1.4). This process continues through petal10(1.1). The petal10(1.1)contains uncompressed data in addition to the frozen petals16(1.2)-(1.6). Compression of the petal10(1.1)results in the formation of a bud24[1].

Decompression extracts data within the bud24[1]. Decompression may be through any decompression process known in the art, such as, for example, the decompression process described in U.S. Provisional Patent No. 61/016,022 entitled METHOD FOR ENCODING & DECODING DATA, and the U.S. Provisional Patent No. 61/038,527 entitled METHOD FOR ENCODING & DECODING DATA. See U.S. Provisional Patent No. 61/016,022, filed on Dec. 21, 2007, and U.S. Provisional Patent No. 61/038,527, filed on Mar. 21, 2008, the entire contents of which are hereby incorporated by reference in their entirety. Decompression of the bud24[1]yields petal10(1.1). The freezer18(1.1)of the petal10(1.1)holds the data of petals10(1.2)-(1.6)in a compressed form. Decompression of the data within each petal10(1.2)-(1.6)is in a sequential manner in the reverse order in which the petals10(1.2)-(1.6)were compressed. The contents of the freezer18(1.1)of the petal10(1.1), is the same as the frozen petal16(1.2). Decompressing frozen petal16(1.2)yields the petal10(1.2). This process is repeated until reaching the termination code22within the petal10(1.6). The termination code22signals the end of the decompressing process.

In the embodiments of forward freezing and reverse freezing illustrated above, the petals10(1.1)-(1.6)have a sequential formation, e.g. petal10(1.2)follows petal10(1.1), petal10(1.3)follows petal10(1.2). For petals10in sequential formations, there is generally only one freezer18within each petal referred to as a primary freezer.

Compression and decompression of the data, either in forward freezing or reverse freezing, may include multiple petal rows12referred to as blooms. There are two main classifications of blooms: open blooms34aand closed blooms34b. In general, open blooms34aand closed blooms34bare well suited to describe life or biological forms. Blooms necessitate the use of multiple freezers18within each petal: one primary freezer18aand one or more secondary freezers18b. The primary freezer18awithin each petal10stores data associated that particular petal row12. The secondary freezer18bstores data associated with other petal rows12.

Generally, in the open bloom34a, there are two types of petal rows12: donor rows and receiver rows. In the open bloom34a, frozen petals16and buds24of donor petal rows may only be stored in receiver petal rows. For example,FIG. 6illustrates one embodiment of an open bloom34ahaving three petal rows12comprised of one receiver row121and two donor rows122and123. The frozen petals16and buds24of donor petal rows122and123may only be stored in the receiver row121. It should be noted that althoughFIG. 6illustrates two donor rows122and123, and one receiver row121, any number of donor rows and/or receiver rows may be used.

In the embodiment illustrated inFIG. 6, compression of donor petal row123begins with petal10(3.1)and proceeds toward petal10(3.3). The bud24[1.3.3]formed by donor petal row123is stored in the secondary freezer18b(1.3)of petal10(1.3).

As previously described, the bud tag indicates the path of the bud formation. Specifically, the bud tag indicates the petal row12and petal10to which the bud24is attached (PRAand PArespectively), and also includes the petal row from which it was formed (PF). The bud tag is represented as: [PRA.PA.PF]. The bud24[1.3.3]was formed in123(PF=3), and attaches to petal10(1.3)of petal row121(PRA=1 and PA=3). As such, the bud tag for the bud formed in petal row123is [1.3.3].

Compression of donor petal row122begins at petal10(2.3)and proceeds to petal10(2.1)in the donor petal row122. The bud24[1.4.2]formed from the donor petal row122(PF=2) is stored in the secondary freezer18b(1.4)of petal10(1.4)in the receiver row121(PA=4 and PRA=1). As such, the bud tag for the bud formed in petal row122is [1.4.2].

The receiver row121undergoes forward freezing starting at petal10(1.1)and ends at petal10(1.6). The bud24[1]formed by the receiver row121is not attached to either donor petal row122or123. As such, the bud tag for the bud formed in petal row121is [1]. The bud[1]is the final compressed set. In the preferred embodiment, the final compressed set is a super frozen dataset.

In this example, there are three petal rows121,122, and123, and each petal row can be expanded in a similar manner as described above. Decompression extracts data within the buds24[1],24[1.4.2], and/or24[1.3.3]. Decompression may be through any decompression process known in the art, such as, for example, the decompression process described in U.S. Provisional Patent No. 61/016,022 entitled METHOD FOR ENCODING & DECODING DATA, and the U.S. Provisional Patent No. 61/038,527 entitled METHOD FOR ENCODING & DECODING DATA. See U.S. Provisional Patent No. 61/016,022, filed on Dec. 21, 2007, and U.S. Provisional Patent No. 61/038,527, filed on Mar. 21, 2008, the entire contents of which are hereby incorporated by reference in their entirety. Decompression of the petal row121yields petals10(1.1)-(1.6). The freezers18b(1.4)and18b(1.3)of the petals10(1.4)and10(1.3)hold the data of petals10(2.3-2.1)and petals10(3.1-3.3)respectively in a compressed form. Decompression of the data within each petal10(2.3-2.1)and10(3.1-3.3)is in a sequential manner in the reverse order in which the petals10(2.3-2.1)and10(3.1-3.3)were compressed. This process is repeated until reaching the termination code22within the each petal row12. The termination code22signals the end of the decompressing process of the petal row12.

Similar to the open bloom34a, in the closed bloom34bthere are two types of petal rows12: donor rows and receiver rows. In the closed bloom34b, however, frozen petals16and buds24of donor petal rows may be stored in either donor petal rows, receiver petal rows, and/or both.

FIG. 7illustrates one embodiment of a closed bloom34bhaving three petal rows121,122, and123designated as either donor and/or receiver rows depending upon whether data from the rows121,122, and123are provided to or received from the other rows121,122, and123. Similar to the open bloom34a, in the closed bloom34bthe frozen petals16and buds24of donor petal rows122and123may be stored in the receiver row121. Additionally, in the closed bloom34b, the frozen petals16and buds of the receiver row121may also be stored within the donor petal rows122and123. The donor petal rows122and123and/or receiver petal row121may store their frozen petals16and/or buds24at any stage of compression. It should be noted that althoughFIG. 7illustrates two donor rows122and123, and one receiver row121, any number of donor rows and/or receiver rows may be used.

In the embodiment illustrated inFIG. 7, compression begins at the receiver petal row121at petal10(1.1)and proceeds toward petal10(1.2). The frozen petal16(1.2)at this point is placed in the secondary freezer18b(3.1)of petal10(3.1)in donor row123, as well as in the primary freezer18a(1.3)of petal10(1.3). Petal10(1.3)of receiver petal row121is compressed, and the frozen petal16(1.3)is placed in the secondary freezer18b(2.2)of petal10(2.2)of the donor row122, as well as in the primary freezer18a(1.4)of petal10(1.4)of the receiver row121.

Compression of the donor row123, begins at petal10(3.1)and proceeds towards petal10(3.3). The bud24[1.4.3], produced by the compression of donor row123(PF=3), is placed in the secondary freezer18b(1.4)of receiver row121(PRA=1, PA=4). As such, the bud tag of donor row123is [1.4.3].

In the next step, petal10(1.4)of the receiver row121undergoes compression, and the frozen petal16(1.4)produced is placed in the primary freezer18a(1.5)of petal10(1.5). At this point, compression at petal10(2.3)of the donor row122proceeds to10(2.1). The resulting bud24[1.5.2]formed from donor row122(PF=2) is stored in the secondary freezer18b(1.5)of the donor row121(PRA=1, PA=5). As such, the bud tag of the donor row122is [1.5.2].

Once the bud24[1.5.2]is formed, compression begins for frames10(1.5)and10(1.6)of the receiver row121to form the bud24[1]. The bud24[1]does not attach to either donor row122or123. As such, the bud tag of the receiver row121is [1]. The bud24[1]represents the super frozen set of the entire closed bloom34b.

In this example, there are three petal rows121,122, and123, and each petal row can be expanded in a similar manner as described above. Decompression extracts data within the buds24[1],24[1.5.2], and/or24[1.4.3]. Decompression may be through any decompression process known in the art, such as, for example, the decompression process described in U.S. Provisional Patent No. 61/016,022 entitled METHOD FOR ENCODING & DECODING DATA, and the U.S. Provisional Patent No. 61/038,527 entitled METHOD FOR ENCODING & DECODING DATA. See U.S. Provisional Patent No. 61/016,022, filed on Dec. 21, 2007, and U.S. Provisional Patent No. 61/038,527, filed on Mar. 21, 2008, the entire contents of which are hereby incorporated by reference in their entirety. Decompression of the petal row121yields petals10(1.1)-(1.6). The freezers18b(1.4)and18b(1.5)of the petals10(1.4)and10(1.5)hold the data of petals10(2.3-2.1)and petals10(3.1-3.3)respectively in a compressed form. Decompression of the data within each petal10(2.3-2.1)and10(3.1-3.3)is in a sequential manner in the reverse order in which the petals10(2.3-2.1)and10(3.1-3.3)were compressed. This process is repeated until reaching the termination code22within each petal row12. The termination code22signals the end of the decompressing process of the petal row12.

Generally, each petal10contains information about a single entity. For example, a single entity could be an individual. The information on the particular individual may be in photographic form having multiple viewing angles, fingerprints, mug shots, address, and or similar types of information. This information may be stored within a single petal10. If information on the specific entity cannot be stored within the single petal10, an auxiliary petal may be used and the compressed information of the auxiliary petal placed within an auxiliary freezer within the single petal10. In this situation, the single petal10is generally referred to as a host petal. For example, if information on the host petal cannot be stored entirely within the host petal, the auxiliary petal may be used. The auxiliary petal would contain the overflow of information from the host petal. The auxiliary petal is compressed to form an auxiliary frozen petal. The auxiliary frozen petal is placed in the auxiliary freezer of the host petal.

If all of the information for an entity can be contained in the uncompressed portion of a single petal10, then the auxiliary freezer within the single petal10may be filled with special data. For example, the auxiliary freezer may be filled with all zeros indicating that there is no auxiliary petal for the petal10.

The auxiliary petal may only contain one freezer, the primary freezer. If information on the entity overflows from the first auxiliary petal, a second auxiliary petal is created. The second auxiliary petal contains the information overflow from the first auxiliary petal. The second auxiliary petal is compressed to form a second auxiliary frozen petal. The second auxiliary frozen petal is placed in the primary freezer of the first auxiliary petal's freezer. The first auxiliary petal is then compressed to form the auxiliary frozen petal that is placed in the auxiliary freezer of the host petal.

This process is repeated until all of the data for a single entity is accommodated. The primary freezer of the last auxiliary freezer may be filled with special data indicating that there are no additional auxiliary petals in the chain.

6. Static Data Access

A leaf40provides the ability to store and retrieve large amounts of information that is relatively static. Leaves40are petals10that contain a significant portion of compressed datasets. As previously discussed, petals10contain information at “Level0,” that is petals10have information in useable form within the uncompressed portion. Leaves40are a higher level compared to petals10. That is, leaves40are structured to store compressed datasets, and thus contain information at “Level1.” Similar to petals10, a leaf40consists of an arbitrary, but fixed, amount of storage space.

FIG. 8illustrates one embodiment of a leaf40. The leaf40is divided into cells42. In this embodiment, each cell42is substantially similar in storage space to the related cells42. Generally, cells42should be large enough to hold at least one compressed dataset, e.g. frozen petals16and/or buds24.

Alternatively, the leaf40may be divided into cells42of varying sizes for the storage of compressed datasets, e.g. frozen petals16and/or buds24. Leaves40having cells42of varying sizes will generally contain at least one cell42designated to store a table identifying each cell by its size, location, and/or other similar information. In an effort for clarity and conciseness, the following discussion relates to leaves40having cells42of similar sizes; however, as one skilled in the art will appreciate, the methods discussed herein may include leaves40having cells42of varying sizes.

As the size of the leaf40is generally fixed, only a certain number of compressed datasets (e.g. frozen petals16and/or buds24) may be stored within the leaf40. If additional storage is required, a second leaf40may be created and the additional compressed datasets may be stored within the second leaf. Additional leaves40may be added until all of the information to be stored is accommodated with a row of leaves. A row of leaves40that contain related information are referred to as a leaf cluster43(illustrated inFIG. 9).

Similar to petals10, leaves40contain freezers known as leaf freezers44. At least one cell42within the leaf40is designated as the leaf freezer44. Additionally, similar to petals10, each leaf40may contain a primary leaf freezer44aand a secondary leaf freezer44b. The leaf freezer44may be placed in any arbitrary location within the leaf40. This location may vary between leaves40. In the preferred embodiment, the location of the leaf freezer44within multiple leaves is at a fixed location. In an effort for clarity and conciseness, the leaf freezers44within the following discussion are described as positioned in a fixed location.

As illustrated inFIG. 9, representations and notations of leaves40are similar to petals10, and representations and notations of branches48are similar to buds24with one exception: petals10and buds24are represented by a box having separating portions of the box, while leaves40and branches48are shown as quadrants.

Frozen leaves46are leaves40containing compressed information. When a leaf cluster43is repeatedly compressed (e.g. frozen), the final compressed dataset entity that results is referred to as a branch48. The branch48is similar to the bud24discussed herein, however, as the branch48contains compressed datasets (e.g. frozen leaves46and/or buds24) at Level1, the branch48may be thought of as being at Level2.

A tree stores a cluster of branches44. The tree holds information at Level3and higher. Trees are not discussed further herein as it will be apparent to one skilled in the art that trees may be readily derived.

FIG. 9illustrates one embodiment of the interrelation between three separate leaf clusters431,432, and433. The leaf cluster431contains six leaves40(1.1)-(1.6), the leaf cluster432contains three leaves40(2.1)-(2.3), and the leaf cluster433contains three leaves40(3.1)-(3.3).

The branch48[1.3.3]of leaf cluster433is stored in the secondary freezer44b(1.3)of leaf40(1.3)in leaf cluster431. Likewise, the branch48[1.4.2]is stored in the secondary freezer44b(1.4)of leaf40(1.4)in leaf cluster431. The entire leaf cluster431is compressed into the branch48[1]shown inFIG. 9.

Retrieval of information from leaf clusters43follows the same pattern as the retrieval of information from petal rows12. The retrieval of information from leaf clusters43is therefore not discussed further as it will be apparent to one skilled in the art how to derive the information based on the description of the retrieval of information from petal rows12provided herein.

Referring now toFIG. 10, in general, a cone leaf50provides a mechanism for the storage and retrieval of volatile information on a random basis. The cone leaf50follows the same scheme as leaves40with one exception. Generally, the cone leaf50does not contain freezers, and instead contains cone cells52providing for the storage of compressed information.

Generally, the cone leaf50is formed from a collection of leaves40at different levels. For example, if an entity has data that overflows the petal10, then all of the auxiliary petals that contain data relating to the entity are compressed as previously described herein. The final auxiliary frozen petal is placed in the auxiliary freezer of the host petal. The host petal is then compressed to obtain the frozen petal16. This frozen petal16is then placed in at least one cell52of the cone leaf50. These steps are repeated until the petals for every entity are converted and stored within the cells52of the cone leaf50. The cone leaf50is then compressed to produce a frozen cone leaf54(FroC). This results in at least one cone leaf50at Level1set. It should be noted that if the cone leaf50does not accommodate the frozen petals of all of the entities needed, then additional cone leaves50may be created.

Each of the cone leaves50within the Level1set is further compressed and placed within the cell52of another cone leaf. This results in at least one cone leaf50at a Level2. Cone leaves50are provided in order to accommodate all of the frozen cones of Level1. This process is repeated to form a single cone at the highest level referred to as an apex leaf58. The apex leaf58is then frozen to provide a kernel60.

The apex leaf58contains a special cell referred to as a seed pod62. The seed pod62contains a table of storing references for identifying the location of each petal10stored within the apex leaf. For example, the table may contain entity IDs, level numbers, cone leaf identification, cell location, and/or other similar identifying factors.

FIG. 10illustrates a flow chart of one embodiment of a method for producing a kernel60from cone leaves50. Row1is the petal row12containing a series of petals10(1.1)-(1.96)from 1 through 96. The petals10(1.1)-(1.96)are considered to be at Level0. Each petal10(1.1)-(1.96)is compressed to produce frozen petals16(1.1)-(1.96)as illustrated in row2. The frozen petals16(1.1)-(1.96)are considered to be at Level1. The frozen petals16(1.1)-(1.96)are stored in cells52aof cone leaves50a1-11as illustrated in row3. Each cone leaf50a1-11is segmented into nine cells. Thus, in the embodiment illustrated, eleven cone leaves50a1-11are needed in order to store the frozen petals16(1.1)-(1.96)of the 96 petals10(1.1)-(1.96).

The cone leaves50a1-11in row3are further compressed to form frozen cone54a1-11as illustrated in row4. The frozen cones54a1-11in row4are considered to be at Level2and stored in the cells of cone leaves50b1and50b2illustrated in row5. There are nine cells52bin the cone leaves50b1and50b2that hold data. As such, only two cone leaves50b1and50b2are needed in order to store the frozen cones54a1-11of row4.

The cone leaves50b1and50b2in row5are then frozen to produce frozen cones54b1and54b2in row6. These frozen cones54b1and54b2are considered to be at Level3. The frozen cones54b1and54b2are stored in the cone leaf50cin row7. The cone leaf50cin row7is then frozen and stored in the kernel60.

Through selectively decompressing the levels of information, random access to a specific entity is provided. For example, in order to access an entity stored in the petal10numbered93, first the kernel60is decompressed (e.g. Super Heated) to get the cone leaf50c. From this, the seed pod62is obtained. The seed pod62is then decompressed (e.g. Super Heated). Information in the table illustrated inFIG. 11is stored within the seed pod62. Generally, the seed pod62contains information on how to retrieve information stored in the cone leaves50a-cof the entity of interest.

In this embodiment, the seed pod62, reveals the information relating to the entity stored within the petals. Each of the rows1-8can be expanded as described above. For example, in order to retrieve the entity stored in petal10(1.93), first the kernel60is decompressed (e.g. super heated) to provide the apex cone leaf50c. The seed pod62within the apex cone leaf50cis then decompressed (e.g. super heated). The seed pod62reveals information relating to the entity stored within petal10(1.93). Specifically, the seed pod62provides information that petal10(1.93)lies within the range82-96(as illustrated inFIG. 11). The table inFIG. 11indicates the range82-96is located in cell2of the apex cone leaf50c

Cell2of the apex cone leaf50cis decompressed (e.g. super heated) to obtain the cone leaf50b2at Level2. The seed pod62(FIG. 11) indicates the petal10(1.93)lies within the range91-96in cell11of the cone leaf50b2. The seed pod62(FIG. 11) also indicates that the petal10(1.93)lies within cell93of the cone leaf50a11at Level1.

Cell11of the cone leaf50b2is decompressed (e.g. super heated) to obtain the cone leaf50a11. Cell93of the cone leaf50a11is the same as the frozen petal16(1.93). Frozen petal16(1.93)is decompressed to obtain the uncompressed data of the entity stored in petal10(1.93).

The cone leaves50a-c, and associated kernel60as described, are well suited in applications without complex relationships between entities among the petals10. Examples of such application include main memory management and communication applications. Additionally, the cone leaves50a-cand kernel60structures may be used in entertainment applications wherein the majority of access is on a sequential basis, but also involves the need to fast forward and/or rewind to a specific frame on a random basis.

It should be noted that the concept of cone leaves50may be extended to the storing of buds24within the cells52of the cone leaves50. The structure resulting from the storing of buds24within cone leaves50is referred to as a cascade. Cascades may be well suited for database applications wherein the storage, retrieval, and management of large amounts of data with complex structural relationships are needed. Generally, the buds24within the cells52of the cone leaves50allow complex structures to be stored and randomly accessed. As one skilled in the art will be readily able to carry out the extension of cascades using the methods described herein, the process is not described in detail.

FIG. 12illustrates one embodiment of a system100for storing and retrieving highly compressed data in mixed mode. In this embodiment, the system100includes a control unit102. The control unit102may be any computational device capable of executing the methods of storing and retrieving the highly compressed data as described herein. In one embodiment, the control unit102executes a process for compressing the data and provides the highly compressed data into stored components (e.g. petals, buds, and/or the like) contained in a storage device104. The storage device104stores the program code and commands required for operation by the control unit102in performing the storage and retrieval of the uncompressed and compressed data. Alternatively, the program code may be incorporated into the control unit102itself.

From the above description, it is clear that the present invention is well adapted to carry out the objects and to attain the advantages mentioned herein, as well as those inherent in the invention. Although the foregoing invention has been described in some detail by way of illustration and example, it will be apparent to those skilled in the art that certain changes and modifications may be practiced without departing from the spirit and scope of the present invention, as described herein. Thus, the present invention is not intended to be limited to the embodiments shown but is to be accorded the widest scope consistent with the principles and features described herein.