Multi-level nested open hashed data stores

• US 20060095458A1
• Filed: 10/29/2004
• Published: 05/04/2006
• Est. Priority Date: 10/29/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Strom, Clifford Paul, Evans, Brian Patrick, Siu, Michael Yiu-Kwan
• Granted Patent: US 7,464,103 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 21/10 Protecting distributed programs or content, e.g. vending or licensing of copyrighted material protection in video systems or pay television H04N7/16 ; Digital rights management [DRM]
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method for storing data. A method for storing data comprising arranging a plurality of data buckets in a logical inverted tree structure having a plurality of levels; and performing nested hashing at each level of the plurality of levels.

Claims

1. A method for storing data comprising:

arranging a plurality of data buckets in a logical inverted tree structure having a plurality of levels; and

performing nested hashing at each level of the plurality of levels.

2. The method of storing data of claim 1, in which the data buckets are of a fixed size.

3. The method of storing data of claim 1, in which the data buckets are stored in the memory of a CE device.

4. The method of storing data of claim 3, in which the CE device operates in a DRM system.

5. The method of storing data of claim 3, in which the data buckets store a plurality of licenses.

6. A method for storing data comprising:

forming a forest of name spaces for accessing a plurality of data stores; and

forming the plurality of data stores by multi-level nested open hashing.

7. The method for storing data of claim 6, in which one of the plurality of data stores, stores license information.

8. The method for storing data of claim 6, in which one of the plurality of data stores, stores media content.

9. The method for storing data of claim 6, in which the plurality of data stores by multi-level nested open hashing form a balanced tree structure.

10. The method for storing data of claim 6, in which the forest is formed by forming an index table to a plurality of data stores.

11. The method for storing data of claim 10, in which the index table is coupled to each of the plurality of data stores.

12. A method of forming a balanced memory tree comprising:

hashing a first hashkey and a bucket ID to produce a first evenly distributed n-state number;

using the first n-state number as an index to point to a storage bucket;

hashing a second hashkey and a bucket ID to produce a second evenly distributed n-state number;

using the second n-state number as an index to point to an overflow storage bucket.

13. The method of forming a balanced memory tree of claim 12, further comprising adding an un-hashed root bucket that is filled before the storage bucket.

14. A digital rights management system comprising:

a multi-level nested open hashed data store;

a CE device having the multi-level nested open hashed data store to store a data file;

a service provider coupled to the CE device to provide data files to the CE device.

15. The digital rights management system of claim 14, in which the data file includes licenses.

16. The digital rights management system of claim 14, in which the data file includes digital media.

17. The digital rights management system of claim 14, in which the CE device is coupled to the service provider through a PC.

18. The digital rights management system of claim 14, in which the CE device is coupled to the service provider through an internet connection.

19. A method of populating a multi-level nested open hashed data store comprising:

filling a current data bucket having a fixed size with a portion of data from a data record;

hashing a current bucket ID with a data hashkey;

creating a child bucket if one does not exist;

storing a portion of the data record in the child bucket repeating the process of populating a multi-level nested open hashed data store until all of the data from the data record has been stored in a plurality of child buckets.

20. The method of populating a multi-level nested open hashed data store of claim 19, in which the current bucket ID uniquely identifies a bucket associated with it.

21. The method of populating a multi-level nested open hashed data store of claim 19, in which the current bucket ID is a physical offset from the beginning of a file containing the bucket.