Data structure for efficient access to variable-size data objects
First Claim
1. A computer-readable medium having stored thereon a data structure for storing variable-size data objects, the data structure comprising one or more packets, a packet comprising:
- a references data field containing data representing references to locations of variable-size data objects;
an objects data field containing data representing at least parts of one or more variable-size data objects; and
a reference count data field containing data representing a number k related to a number of references in the references data field, wherein during an access operation for a particular variable-size data object in the data structure, the number k in the reference count data field is examined to determine whether the references data field of the packet includes a reference to the location of the particular variable-size data object.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
35 Claims
-
1. A computer-readable medium having stored thereon a data structure for storing variable-size data objects, the data structure comprising one or more packets, a packet comprising:
-
a references data field containing data representing references to locations of variable-size data objects;
an objects data field containing data representing at least parts of one or more variable-size data objects; and
a reference count data field containing data representing a number k related to a number of references in the references data field, wherein during an access operation for a particular variable-size data object in the data structure, the number k in the reference count data field is examined to determine whether the references data field of the packet includes a reference to the location of the particular variable-size data object. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 27, 28, 29, 30, 31, 32, 33, 34, 35)
at least two packets; and
a header data field containing data representing a number j related to a total number of references within the references data fields of the packets of the metapacket.
-
-
23. The computer-readable medium of claim 1 wherein a composite data structure includes the data structure for storing variable-size data objects.
-
27. A method for accessing the particular variable-size data object stored in the data structure of claim 1, the method comprising:
-
receiving a numerical selection m, wherein m corresponds to the particular variable-size data object to be accessed;
retrieving the mth reference of the data structure; and
accessing the particular variable-size data object based upon the retrieved reference.
-
-
28. A method for accessing the particular variable-size data object stored in the data structure of claim 1, the method comprising:
-
a) receiving a numerical selection m, wherein m corresponds to the reference to the particular variable-size data object to be accessed;
b) based at least in part upon the number k of the reference count data field of the packet, determining whether the packet contains the reference to the particular variable-size data object, and if so, accessing the particular variable-size data object based upon the reference;
and if not, repeating act (b) using a next packet in the data structure as the packet.
-
-
29. The method of claim 28 wherein the determining comprises:
-
adding k to a cumulative reference count;
comparing m to the cumulative reference count;
if m is less than or equal to the cumulative reference count, retrieving the reference to the particular variable-size data object within the packet.
-
-
30. The method of claim 28 wherein the determining comprises:
-
comparing m to k;
if m is less than or equal to k, retrieving the reference to the particular variable-size data object within the packet;
wherein if m is greater than k, act (b) further comprises, before the repeating, setting m to equal m minus k.
-
-
31. A method for accessing the particular variable-size data object stored in the data structure of claim 22, the method comprising:
-
a) receiving a numerical selection m, wherein m corresponds to the reference to the particular variable-size data object to be accessed;
b) based at least in part upon the number of the header data field of the metapacket, determining whether the metapacket contains the reference to the particular variable-size data object, and if so, accessing the particular variable-size data object based upon the reference;
and if not, repeating act (b) using a next metapacket in the data structure as the metapacket.
-
-
32. The method of claim 31 wherein the determining comprises:
-
adding j to a cumulative metapacket reference count;
comparing m to the cumulative metapacket reference count;
if m is less than or equal to the cumulative metapacket reference count, retrieving the reference to the particular variable-size data object within a references data field of a packet of the metapacket.
-
-
33. The method of claim 31 wherein the determining comprises:
-
comparing m to j;
if m is less than or equal to j, retrieving the reference to the particular variable-size data object within a references data field of a packet of the metapacket;
wherein if m is greater than j, act (b) further comprises, before the repeating, setting m to equal m minus j.
-
-
34. A method for filling the data structure of claim 1, the method comprising,
for each of the variable-size data objects, iteratively writing to the reference count data field, the references data field, and the objects data field. -
35. A method of communicating the data structure of claim 1, the method comprising
formatting the variable-size data objects into the one or more packets in a transmitter, and transmitting the one or more packets by the transmitter.
-
24. A computer-readable medium having stored thereon a data structure for storing variable-size data objects, the variable-size data objects including information for spatially related views of an object or scene, the data structure comprising one or more packets, a packet comprising:
-
a references data field containing data representing references to locations of variable-size data objects;
an objects data field containing data representing at least parts of one or more variable-size data objects, wherein the variable-size data objects include information for spatially related views of an object or scene; and
a reference count data field containing data representing a number k related to a number of references in the references data field, wherein during an access operation for a particular variable-size data object in the data structure, the number k in the reference count data field is examined to determine whether the references data field of the packet includes a reference to the location of the particular variable-size data object. - View Dependent Claims (25, 26)
-
Specification