Type path indexing
AssigneeMicrosoft Corporation
InventorsConor Cunningham, Ramachandran Venkatesh, Eric Hanson
Life of this patent
Estimating the term…
Abstract
Efficient hierarchical searching is based on object type. By pre-computing additional information and storing it in a fast-lookup structure, it is possible to quickly identify objects that satisfy an object retrieval request. Furthermore, it is also possible to use this technique to avoid object hydration for operations in the store. Moreover, it is possible to leverage database statistical structures such as histograms to estimate the number of qualifying objects without having to examine each object.
Claims24
A computer system comprising:
- a data store comprising a plurality of objects, each object having an associated type, each type having an identifier;
- and
- a hardware/software interface system for manipulating the plurality of objects.
A hardware/software interface system capable of manipulating a plurality of objects, each object having an associated type, each type having an identifier.
A computer-readable medium having stored thereon a data structure, comprising:
- a first data field containing an object;
- and
- a second data field containing a data type associated with the object, the data type having an identifier.
A method of generating a selectivity estimate of a query over a plurality of objects, each object having a type with identifier, comprising:
- encoding each object with a type path derived from the identifier;
- for each object, determining if its type path will satisfy the query;
- and
- determining the ratio of objects having a type path that will satisfy the query to the total number of objects.
Dependencies are inferred from the claim text.