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.

1 - 38 . (canceled)  
   
   
       39 . 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; and    when ready to write the one or more designated variable-size data objects to the to-be-filled packet, 
 writing data to 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.  
   
   
   
       40 . The method of  claim 39  wherein the tracking readiness comprises: 
 incrementing a total designated variable-size data objects count; and    updating 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.    
   
   
       41 . The method of  claim 39  further comprising determining when ready to write to the to-be-filled packet by: 
 comparing a cumulative size value for to-be-written designated variable-size data objects to a packet size threshold value, wherein the packet size threshold indicates available space in the to-be-filled packet to be filled; and    if the cumulative size value is greater than or equal to the packet size threshold, performing the writing acts.    
   
   
       42 . The method of  claim 39  wherein the writing the k references and the at least part of each of the one or more designated variable-size data objects to the to-be-filled packet comprises: 
 reserving space for the k references; and    for each of the one or more designated variable-size data objects, 
 writing a reference of the k references to the to-be-filled packet; and  
 writing the variable-size data object to the to-be-filled packet to the extent space allows in the to-be-filled packet.  
   
   
   
       43 . The method of  claim 39  further comprising: 
 preparing to fill a subsequent packet of the one or more packets.    
   
   
       44 - 47 . (canceled)  
   
   
       48 . 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.  
   
   
   
       49 . The computer-readable medium of  claim 48  wherein the tracking readiness comprises: 
 incrementing a total designated variable-size data objects count; and    updating 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.    
   
   
       50 . The computer-readable medium of  claim 48  wherein the method further comprises determining when ready to write to the to-be-filled packet by: 
 comparing a cumulative size value for to-be-written designated variable-size data objects to a packet size threshold value, wherein the packet size threshold indicates available space in the to-be-filled packet; and    if the cumulative size value is greater than or equal to the packet size threshold, performing the writing acts.    
   
   
       51 . The computer-readable medium of  claim 48  wherein the writing the k references and the at least part of each of the one or more designated variable-size data objects to the to-be-filled packet comprises: 
 reserving space for the k references; and    for each of the one or more designated variable-size data objects, 
 writing a reference of the k references to the to-be-filled packet; and  
 writing the variable-size data object to the to-be-filled packet to the extent space allows in the to-be-filled packet.  
   
   
   
       52 . The computer-readable medium of  claim 48  wherein the method further comprises preparing to fill a subsequent packet of the one or more packets.  
   
   
       53 . 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 parts 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;    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.  
   
   
   
       54 . The system of  claim 53  wherein the tracking readiness comprises: 
 incrementing a total designated variable-size data objects count; and    updating 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.    
   
   
       55 . The system of  claim 53  wherein the one or more modules are also for determining when ready to write to the to-be-filled packet by: 
 comparing a cumulative size value for to-be-written designated variable-size data objects to a packet size threshold value, wherein the packet size threshold indicates available space in the to-be-filled packet; and    if the cumulative size value is greater than or equal to the packet size threshold, performing the writing acts.    
   
   
       56 . The system of  claim 53  wherein the writing the k references and the at least part of each of the one or more designated variable-size data objects to the to-be-filled packet comprises: 
 reserving space for the k references; and    for each of the one or more designated variable-size data objects, 
 writing a reference of the k references to the to-be-filled packet; and  
 writing the variable-size data object to the to-be-filled packet to the extent space allows in the to-be-filled packet.  
   
   
   
       57 . The system of  claim 53  wherein the one or more modules are also for: 
 preparing to fill a subsequent packet of the one or more packets.