US 7,065,530 B2 · Data structure for efficient access to variable-size data objects

Abstract

A data structure includes variable-size data objects [“VSDOs”] and enables selective and efficient retrieval of data in particular VSDOs. The data structure includes multiple packets. Each packet includes a reference count field, a references field, and an objects field. The references field stores references to VSDOs within the data structure. The reference count field indicates the number of references stored in the references field. The objects field stores the-actual VSDOs. To access a particular VSDO, an accessing unit traverses the reference count fields of the multiple packets until the accessing unit finds a packet that includes the reference to the particular VSDO. The accessing unit accesses the particular VSDO based upon the reference. To further improve the efficiency of an access operation, packets form metapackets. A metapacket header sums the reference count fields of the packets within the metapacket. To access a particular VSDO, an accessing unit traverses the metapacket headers until the accessing unit finds a metapacket that includes a packet having the reference to the particular VSDO. Based upon the reference, the accessing unit accesses the particular VSDO. Storing light field information in VSDOs using the data structure facilitates efficient light field operations and light field operations at selective levels of refinement.

Claims12

Dependent claims

A method for filling a data structure with a plurality of variable-size data objects, the data structure comprising one or more packets, wherein each packet of the one or more packets comprises a reference count k, k references to variable-size data objects, and at least parts of one or more of the plurality of variable-size data objects, the method comprising for each of the plurality of variable-size data objects, iteratively repeating:

designating the variable-size data object;
tracking readiness to write one or more designated variable-size data objects to a to-be-filled packet of the one or more packets;
when ready to write the one or more designated variable-size data objects to the to-be-filled packet,
writing the reference count k to the to-be-filled packet, for the one or more designated variable-size data objects, writing the k references and at least part of each of the one or more designated variable-size data objects to the to-be-filled packet, and
preparing to fill a subsequent packet of the one or more packets, wherein the preparing comprises:
adjusting a cumulative size value, wherein the cumulative size value measures cumulative size of to-be-written designated variable-size data objects and cumulative size of references to the to-be-written designated variable-size data objects,
initializing a total designated variable-size data objects count;
and
selecting the subsequent packet as the to-be-filled packet.

6 more elements

A computer-readable medium storing computer-executable instructions for causing a computer system programmed thereby to perform a method of filling a data structure with a plurality of variable-size data objects, the data structure comprising one or more packets, wherein each packet of the one or more packets comprises a reference count k, k references to variable-size data objects, and at least parts of one or more of the plurality of variable-size data objects, the method comprising, for each of the plurality of variable-size data objects, iteratively repeating:

designating the variable-size data object;
tracking readiness to write one or more designated variable-size data objects to a to-be-filled packet of the one or more packets;
when ready to write the one or more designated variable-size data objects to the to-be-filled packet,
writing the reference count k to the to-be-filled packet,
for the one or more designated variable-size data objects, writing the k references and at least part of each of the one or more designated variable-size data objects to the to-be-filled packet, and
preparing to fill a subsequent packet of the one or more packets, wherein the preparing comprises:
adjusting a cumulative size value, wherein the cumulative size value measures cumulative size of to-be-written designated variable-size data objects and cumulative size of references to the to-be-written designated variable-size data objects,
initializing a total designated variable-size data objects count;
and
selecting the subsequent packet as the to-be-filled packet.

7 more elements

A system for filling a data structure with a plurality of variable-size data objects, the data structure comprising one or more packets, wherein each packet of the one or more packets comprises a reference count k, k references to variable-size data objects, and at least pans of one or more of the plurality of variable-size data objects, the system including one or more modules for iteratively repeating, for each of the plurality of variable-size data objects:

designating the variable-size data object;
tracking readiness to write one or more designated variable-size data objects to a to-be-filled packet of the one or more packets;
and
when ready to write the one or more designated variable-size data objects to the to-be-filled packet,
writing the reference count k to the to-be-filled packet,
for the one or more designated variable-size data objects, writing the k references and at least part of each of the one or more designated variable-size data objects to the to-be-filled packet, and
preparing to fill a subsequent packet of the one or more packets, wherein the preparing comprises:
adjusting a cumulative size value, wherein the cumulative size value measures cumulative size of to-be-written designated variable-size data objects and cumulative size of references to the to-be-written designated variable-size data objects,
initializing a total designated variable-size data objects count;
and
selecting the subsequent nacket as the to-be-filled packet.

8 more elements

Dependencies are inferred from the claim text.

Data structure for efficient access to variable-size data objects

Life of this patent

Data structure for efficient access to variable-size data objects

Life of this patent

Abstract

Claims12