Determining documents that match a query
AssigneeMicrosoft Corporation
InventorsSanjeev Mehrotra, Jin Li, Abhinav Shrivastava
Life of this patent
Estimating the term…
Abstract
A computer-implemented method and system for determining documents that are nearest to a query are provided herein. The method includes constructing a vantage point tree based on a number of document vectors. The method also includes searching the vantage point tree to determine a number of nearest neighbor document vectors to a query vector by removing a portion of the document vectors from the vantage point tree based on one or more vantage points for each of a number of nodes in the vantage point tree and a specified search radius centered about the query vector.
Claims20
A method for determining documents that are nearest to a query, comprising:
- constructing a vantage point tree based on a plurality of document vectors;
- and
- searching the vantage point tree to determine a plurality of nearest neighbor document vectors to a query vector by removing a portion of the plurality of document vectors from the vantage point tree based on one or more vantage points for each of a plurality of nodes in the vantage point tree and a specified search radius centered about the query vector.
A computing system for determining documents that are nearest to a query, comprising:
- a processor that is adapted to execute stored instructions;
- and
- a system memory, wherein the system memory comprises code configured to:
- construct a vantage point tree based on a plurality of document vectors;
- traverse the vantage point tree using one or more vantage points for each of a plurality of nodes in the vantage point tree by removing any of the plurality of document vectors that are outside a hypersphere of a specified search radius centered about a query vector;
- and
- determine a plurality of nearest neighbor document vectors to the query vector based on a distance between each remaining document vector and the query vector.
One or more computer-readable storage media for storing computer-readable instructions, the computer-readable instructions providing a system for determining documents that are nearest to a query when executed by one or more processing devices, the computer-readable instructions comprising code configured to:
- construct a vantage point tree based on a plurality of document vectors;
- traverse the vantage point tree using one or more vantage points for each of a plurality of nodes in the vantage point tree by removing a portion of the plurality of document vectors from the vantage point tree based on a specified search radius centered about a query vector and a triangle inequality condition;
- and
- search the vantage point tree to determine a specified number of nearest neighbor document vectors to the query vector.
Dependencies are inferred from the claim text.