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.
Claims5
1-20. (canceled)
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.