Multi-level nested open hashed data stores

• US 7,464,103 B2
• Filed: 10/29/2004
• Issued: 12/09/2008
• 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
• Primary Examiner(s): Alam; Shahid A
• Assistant Examiner(s): NGUYEN, PHONG H
• Application Number:
  US10/976,463
• Publication Number:
  US 20060095458A1
• Time in Patent Office: 1,502 Days
• Field of Search: 707/2, 707/101, 707/102
• 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 records in a tree structure comprising a root bucket and a plurality of levels comprising buckets, the buckets comprising leaf and non-leaf buckets, each bucket having a unique bucket identifier, the buckets storing the data records, each data record having a corresponding key, the method comprising:

providing a hash function that maps different pairs of values to respective single hash values;

receiving a new key for a new data record to be stored in the tree structure;

responsive to determining that the root bucket does not have sufficient available space to store the new data record, using the hash function to map the identifier of the root bucket and the key of the new data record to a hash value, the hash value being computed as a function of the key combined with the identifier of the root bucket such that the key and the identifier of the root bucket are mapped to the hash value according to the hash function;

identifying an identifier of a child bucket of the root bucket in the tree structure, where the identifier of the child bucket is identified based on the hash table value;

responsive to determining that the child bucket does not have sufficient available space to store the new data record, hashing the identifier of the child bucket and the key of the new data record to compute a second hash value which is used to identify a child bucket at a third level in the tree structure; and

responsive to determining that the child bucket does have sufficient available space to store the new data record, storing the new data record in the child bucket.

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

3. The method of storing data of claim 1, in which the root bucket and the child 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 root bucket and the child buckets store a plurality of licenses.

6. A method of forming a memory tree comprising:

providing a hash function that maps different pairs of values to respective single hash values;

using the hash function to hash both a first key and a first bucket ID to produce, as a function of both the first key and the first bucket ID, a first n-state number, where the value of the n-state number depends on the values of both the first key and the first bucket ID, and obtaining a second bucket ID using the n-state number, the second bucket ID corresponding to a second memory bucket which is a child of the first memory bucket;

using the hash function to hash both a second key and the second bucket ID to produce, as a function of both the second key and second bucket ID, a second n-state number, the second key corresponding to a second data record and the second bucket ID identifying the second memory bucket, and using the second n-state number to identify an overflow storage bucket that is a child of the second memory bucket;

determining whether the first memory location is full; and

if it is determined that the first memory bucket is full, storing at least a portion of the second data record in the overflow storage bucket.

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

8. A method of populating a multilevel nested hash store comprising a tree of buckets and a hash function, each bucket having a unique bucket ID, the tree being formed by linking the buckets with bucket IDs, where the buckets are for storing data chunks, and the data chunks having respective keys, the method comprising:

providing a hash function that maps different pairs of values to respective single hash values;

receiving new keys of respective new data chunks to be stored in the hash store;

identifying target buckets for the new keys, and determining if the target buckets have sufficient space to store the new data chunks;

when a new key'"'"'s target bucket is determined to have sufficient available space to store the new key'"'"'s data chunk, storing the new key'"'"'s data chunk in the new key'"'"'s target bucket; and

when a new key'"'"'s target bucket is determined to not have sufficient available space to store the new key'"'"'s data chunk;

using the hash function to compute a single first hash value of both the new key and the bucket ID of the new key'"'"'s target bucket, the first hash value being computed as a function of both the new key and the bucket ID of the target bucket such that the value of new key and the value of the bucket ID map to the first hash value according to the hash function;

selecting a bucket ID of one of the target bucket'"'"'s children buckets based on the first hash value;

storing the new key'"'"'s data chunk in the bucket of the selected bucket ID if the bucket of the selected bucket ID has sufficient available space; and

using the hash function to compute a single second hash value of the new key combined with the selected bucket ID, the second hash value being computed as a function of the new key combined with the bucket ID of the selected bucket such that the value of the new key and the value of the bucket ID of the selected bucket map to the second hash value according to the hash function, and using the second hash value to select a child bucket of the selected bucket as a bucket for storing the new data chunk.

9. A method according to claim 8, wherein the data chunks comprise digital media rights license data.

10. A method according to claim 8, further comprising forming a new child bucket when a selected bucket does not exist.