Multidimensional data object searching using bit vector indices
AssigneeMicrosoft Corporation
InventorsJonathan Goldstein, John Platt, Christopher Burges
Life of this patent
Estimating the term…
Abstract
Prior to searching a multidimensional feature space populated with data objects, each dimension in the feature space is divided into a number of intervals. When a query is received, a single interval that is overlapped by the query is selected from each dimension. A reduced set of data objects is then selected that includes only those data objects that overlap the selected intervals. This reduced set of data objects, rather than the entire set of data objects in the feature space, is then used to determine matches for the query.
Claims16
A method comprising:
- partitioning each dimension in a multidimensional (MD) feature space into a plurality of intervals;
- identifying an interval in each dimension that overlaps a query point;
- finding one or more MD data objects coupled to the MD feature space that match all of the identified intervals;
- and
- evaluating a first MD data object that matches all of the identified intervals to determine whether the first MD data object overlaps the query point.
A system comprising:
- a data store containing a plurality of data items;
- a computer readable medium having defined therein a multidimensional (MD) feature space coupled to a plurality of MD data objects, each MD data object being associated with a data item;
- and
- a search module operable to:
- partition each dimension in the MD feature space into a plurality of intervals;
- select an interval in each dimension that overlaps a query point;
- determine a subset of the plurality of MD data objects that matches all of the selected intervals;
- and
- select a data item based on the query point and the determined subset of MD data objects.
A computer-readable medium having computer-executable instructions for performing acts comprising:
- partitioning each dimension in a multidimensional (MD) feature space into a plurality of intervals, the feature space coupled to a plurality of MD data objects, each MD data object being associated with a data item;
- identifying an interval in each dimension that includes a query point;
- identifying one or more MD data objects coupled to the feature space that match all of the identified intervals;
- and
- identifying a data item that matches the query point using the query point and the identified one or more MD data objects.
Dependencies are inferred from the claim text.