DATA STORAGE STRUCTURE

• US 20090222408A1
• Filed: 02/28/2008
• Published: 09/03/2009
• 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.
• Granted Patent: US 8,028,000 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 storing a functional relationship between elements of a source set and elements of a query result set using an indexing structure comprising an indexing array, the method comprising:

choosing at least two hash functions that generate hash values corresponding to mapped positions in the indexing array;

for respective elements of the source set, generating at least one equation representing a functional relationship with an element of the query result set;

solving the equations for variables, respective variables for an element of the source set combining to represent an element of the query result set according to the functional relationship; and

storing the variables at the mapped positions in the indexing array.

2. The method of claim 1, the elements of the source set representing strings.

3. The method of claim 1, choosing at least two hash functions comprising:

determining whether a graph, representing the positions in the indexing array mapped by the at least two hash functions, is acyclic.

4. The method of claim 3, comprising:

upon determining that the graph is not acyclic, storing the functional relationship between the elements of the source set and the elements of the query set using at least one new hash function replacing one of the at least two hash functions.

5. The method of claim 1, the generating at least one equation comprising generating at least one parity hash value using at least one parity hash function for elements of the source set.

6. The method of claim 1:

the indexing structure comprising a modulus, and

the solving of equations comprising;

selecting variables at the mapped positions in the array that combine with the parity hash value to a value that, moduloed by the modulus, equals the corresponding element in the query results set defined by the functional relationship.

7. The method of claim 6, the modulus comprising a number at least about the range size of the parity hash values.

8. The method of claim 1, the indexing array having a size at least about twice the number of elements in the source set.

9. A method of resolving a query comprising a functional relationship of an element of a source set to an element of a query result set using an indexing structure comprising an indexing array, at least two hash functions and a parity hash function, and the method comprising:

combining at least two variables stored in at least two positions of the indexing array, identified by the two hash functions, of an indexing array;

generating a parity hash value for the query using the parity hash function; and

combining the parity hash value with the combination of the at least two variables stored at the at least two positions of the indexing array identified by the at least two hash functions to identify the element of the query result set.

10. The method of claim 9, the query result moduloed by the modulus comprising a number at least about the range size of the parity hash values to obtain a paritied query result.

11. The method of claim 10, the paritied query result comprising one of:

a valid output of the query comprising an output mapping to an element of the query result set, and

an invalid output of the query comprising an output not mapping to an element of the query result set.

12. The method of claim 11 comprising:

if the paritied query result is valid, outputting the identified element of the query result set; and

if the paritied query result is invalid, outputting an indicator that the query is invalid.

13. The method of claim 9, at least one of:

the combining of the at least the variables comprises summing; and

the combining of the parity hash value with the combination of the at least two variables comprises summing.

14. A method for adapting an indexing structure comprising an indexing array and at least two hash functions to accommodate a changed functional relationship between an element of a source set and an element of a query result set, the method comprising:

identifying positions in the indexing array of variables to be updated by using at least two hash functions that generate hash values for affected elements of the source set corresponding to mapped positions in the indexing array;

for the identified positions, identifying elements of the source set represented by at least one of the identified positions;

for respective identified elements and the element of the changed functional relationship, generating at least one equation for the affected elements of the source set using the changed functional relationship to the elements of the query result set;

solving the at least one equation for at least one changed function variable representing the changed functional relationship with the element of the query result set; and

storing the at least one changed variable in respective identified positions in the indexing array.

15. The method of claim 14, the variables connected comprising variables in positions of the indexing array connected by at least one edge in a graphical representation of the indexing array.

16. The method of claim 14, the variables connected comprising, the variables in the positions of the indexing array connected by at least one hash function in the array mapping representation of the indexing array.

17. The method of claim 14, the solving of equations comprising:

setting variables at the mapped positions in the indexing array such that a sum of the variables is equal to a corresponding element in the query results set.

18. The method of claim 14, the generating of at least one equation for the elements of the source set comprising generating at least one parity hash value using at least one parity hash function for the elements of the source set.

19. The method of claim 14:

the indexing structure comprising a modulus, and the solving of equations comprising;

selecting variables at the mapped positions in the array that combine with the parity hash value to a value that, moduloed by the modulus, equals the corresponding element in the query results set defined by the functional relationship.

20. The method of claim 18, the modulus comprising a number at least about a range size of the parity hash values.