Data storage structure
AssigneeMicrosoft Corporation
InventorsDenis X. Charles, Kumar H. Chellapilla
Life of this patent
Estimating the term…
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.
Claims20
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.
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.
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.
Dependencies are inferred from the claim text.