Data storage structure

• US 8,028,000 B2
• Filed: 02/28/2008
• Issued: 09/27/2011
• Est. Priority Date: 02/28/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chellapilla, Kumar H., Charles, Denis X.
• Primary Examiner(s): Stevens; Robert
• Application Number:
  US12/038,813
• Publication Number:
  US 20090222408A1
• Time in Patent Office: 1,307 Days
• Field of Search: 707/741, 707/802, 707/999.3
• US Class Current: 707/802
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/245 Query processing

Abstract

Efficient data storage and retrieval (e.g., in terms of time and space requirements) is facilitated by implementing an indexing structure comprising an indexing array. That is, a functional relationship between elements of a source set and elements of a query result set can be stored in the indexing structure. This allows, for example, a query regarding whether an element is a member of a set (e.g., whether a particular website or Uniform Resource Locator (URL)) has been visited before) as well as a relationship between the member set and the query (e.g., the number of hyperlinks in the website the last time it was visited) to be resolved efficiently.

Claims

1. A method for efficiently retrieving data, embodied in instructions in a storage apparatus and executed with a processing apparatus, the method comprising:

storing a source set array of elements and a query set array of elements, the

source set array comprising a functional relationship with the query set array;

choosing at least two hash functions to map respective elements of the source set array to an indexing array such that a map of the indexing array is acyclic;

calculating at least two hash function arrays for the at least two hash functions based at least in part on the source set array; and

populating the indexing array based at least in part on at least one of the mapped hash functions, the hash function arrays, a parity hash function, the source set array, the query set array, the functional relationship, or a modulus.

2. The method of claim 1, populating the indexing array comprising solving an equation f(x)=[g(h₁(x))+g(h₂(x))+h₃(x)] mod m, where:

f(x) represents the functional relationship;

h₁(x) and h₂(x) represent the hash functions;

g(h₁(x)) and g(h₂(x)) represent one or more values of the indexing array based at least in part on the respective hash functions and a position in the indexing array;

h₃(x) represents the parity hash function;

mod represents a modulo operation; and

m represents the modulus.

3. The method of claim 1, the functional relationship supporting an input query which returns at least one of an output indicating the input query belongs to the source set or an output indicating the input query does not belong to the source set.

4. The method of claim 3, the output indicating the input query belongs to the source set comprising an output demonstrating the functional relationship.

5. The method of claim 1, the choosing comprising replacing at least one of the hash functions with a new hash function based at least in part on a condition where the map of the indexing array is cyclical.

6. The method of claim 1, a size of the indexing array greater than twice the size of the source set array.

7. The method of claim 1, a size of at least one of the hash function arrays greater than twice the size of the source array.

8. The method of claim 1, the modulus greater than a size of the parity hash function of the source set array.

9. A method for efficiently retrieving data, embodied in instructions in a storage apparatus and executed with a processing apparatus, the method comprising:

storing a source set array of elements and a query set array of elements, the

source set array comprising a functional relationship with the query set array;

storing at least two hash value arrays for respective source set elements;

creating a graphical representation based at least in part on at least one of the

hash value arrays or the source set array; and

populating an indexing array based at least in part on the graphical representation.

10. The method of claim 9, the graphical representation based at least in part on respective elements in the source set array mapped to two positions in the indexing array.

11. The method of claim 9, the graphical representation based at least in part on respective elements of the hash value arrays representing one or more respective nodes connected based at least in part on a common input.

12. The method of claim 9, the graphical representation is acyclic.

13. The method of claim 9, comprising receiving an input as one of the query elements.

14. The method of claim 9, comprising:

comparing at least one of the elements of one or more of the arrays to a cardinal set; and

determining a membership of a set based at least in part on a match between the compared at least one element and the cardinal set.

15. A computer-readable storage device comprising computer-executable instructions, which when executed via a processor on a computer perform acts, comprising:

storing a source set array of elements and a query set array of elements, the source set array comprising a functional relationship with the query set array;

choosing at least two hash functions to map respective elements of the source set array to an indexing array such that a map of the indexing array is acyclic;

calculating at least two hash function arrays for the at least two hash functions, the calculating based at least in part on the source set array; and

populating the indexing array based at least in part on at least one of the mapped hash functions, the hash function arrays, a parity hash function, the source set array, the query set array, the functional relationship, or a modulus.

16. The computer-readable storage device of claim 15, populating the indexing array comprising solving an equation f(x)=[g(h₁(x))+g(h₂(x))+h₃(x)] mod m, where:

f(x) represents the functional relationship;

h₁(x) and h₂(x) represent the hash functions;

g(h₁(x)) and g(h₂(x)) represent one or more values of the indexing array based at least in part on the respective hash functions and a position in the indexing array;

h₃(x) represents the parity hash function;

mod represents a modulo operation; and

m represents the modulus.

17. The computer-readable storage device of claim 15, the functional relationship supporting an input query which returns at least one of an output indicating the input query belongs to the source set or an output indicating the input query does not belong to the source set.

18. The computer-readable storage device of claim 15, the choosing comprising replacing at least one of the hash functions with a new hash function based at least in part on a condition where the map of the indexing array is cyclical.

19. The computer-readable storage device of claim 15, a size of at least one of the hash function arrays greater than twice the size of the source array.

20. The computer-readable storage device of claim 15, the modulus greater than a size of the parity hash function of the source set array.