Determining documents that match a query

• US 9,442,929 B2
• Filed: 02/12/2013
• Issued: 09/13/2016
• Est. Priority Date: 02/12/2013
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Mehrotra, Sanjeev, Li, Jin, Shrivastava, Abhinav
• Primary Examiner(s): BROWN, SHEREE N
• Application Number:
  US13/764,788
• Publication Number:
  US 20140229473A1
• Time in Patent Office: 1,309 Days
• Field of Search: 707/728, 707/772
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: G06F 16/93 Document management systems

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.

Claims

1. A method for determining documents that are nearest to a query, the method comprising:

constructing, by a computer processor, a vantage point tree based on a plurality of document vectors;

searching, by a computer processor, 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;

removing any of the plurality of document vectors belonging to document clusters that do not intersect a hypersphere of the specified search radius centered about the query vector;

removing any of the plurality of document vectors that do not satisfy a triangle inequality condition for the specified search radius between one of the one or more vantage points, the document vector, and the query vector; and

adjusting the specified search radius such that only a specified number of nearest neighbor document vectors are remaining after document vectors that are outside the hypersphere of the specified search radius for the query vector and document vectors that do not satisfy the triangle inequality condition have been removed.

2. The method of claim 1, wherein determining the plurality of nearest neighbor document vectors to the query vector comprises determining a specified number of the plurality of document vectors that are nearest to the query vector.

3. The method of claim 1, comprising ranking documents corresponding to the plurality of nearest neighbor document vectors based on a relevance of each document to a query corresponding to the query vector.

4. The method of claim 1, wherein searching the vantage point tree to determine the plurality of nearest neighbor document vectors to the query vector comprises:

calculating a distance between each remaining document vector and the query vector;

sorting the calculated distances; and

determining the plurality of nearest neighbor document vectors to the query vector based on the distance between each remaining document vector and the query vector.

5. The method of claim 4, wherein removing a document vector that does not satisfy the triangle inequality condition comprises:

calculating a first distance range between the query vector and one of the one or more vantage points;

calculating a second distance range between the document vector and the one of the one or more vantage points;

determining whether an absolute value of a difference between the first distance range and the second distance range is greater than the specified search radius; and

if the absolute value is greater than the specified search radius, removing the document vector.

6. The method of claim 1, wherein the vantage point tree comprises a multi-vantage point tree comprising a plurality of vantage points for each node in the vantage point tree.

7. The method of claim 6, wherein constructing the multi-vantage point tree comprises, for each of the plurality of nodes, partitioning the plurality of document vectors in the node into clusters based on a distance of each of the plurality of document vector from the plurality of vantage points.

8. The method of claim 7, wherein a first vantage point of the plurality of vantage points is selected from a random node in a cluster, and wherein a second vantage point of the plurality of vantage points is selected from a node in the cluster that is the farthest from the random node.

9. The method of claim 8, wherein searching the vantage point tree to determine the specified number of nearest neighbor document vectors comprises removing any of the clusters that do not intersect the hypersphere of the specified search radius centered about the query vector.

10. The method of claim 7, wherein partitioning the plurality of document vectors into the clusters comprises:

calculating a distance of each document vector to one of the plurality of vantage points,

sorting the distances;

determining N−

1 radii that roughly partition the document vectors into N equally sized clusters; and

recording the N−

1 radii in a partitioning node to aid in traversal of the multi-vantage point tree.

20. The method of claim 1, wherein the vantage point tree comprises a multi-vantage point tree.

11. 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 remove any of the plurality of document vectors that do not satisfy a triangle inequality condition for the specified search radius between a vantage point, the document vector, and the query vector;

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; and

adjust the specified search radius such that only a specified number of nearest neighbor document vectors are remaining after document vectors that are outside the hypersphere of the specified search radius for the query vector and document vectors that do not satisfy the triangle inequality condition have been removed.

12. The system of claim 11, wherein the system memory comprises code configured to:

calculate a first distance range between the query vector and the vantage point;

calculate a second distance range between one of the plurality of document vectors and the vantage point;

determine whether an absolute value of a difference between the first distance range and the second distance range is greater than the specified search radius; and

if the absolute value is greater than the specified search radius, remove the one of the plurality of document vectors.

13. The system of claim 11, wherein the system comprises a plurality of computing devices;

wherein construction of child nodes for a vantage point tree node in upper levels of the vantage point tree is performed using a coordinating computing device randomly chosen from the plurality of computing devices which contain document vectors corresponding to the vantage point tree node; and

wherein the system memory of the coordinating computing device is configured to;

determine a vantage point; and

send the vantage point to each of the plurality of computing devices; and

wherein the system memory of each of the plurality of computing devices is configured to compute distances between the document vectors corresponding to the vantage point tree node that are stored on the computing device and the vantage point; and

wherein the system memory of the coordinating computing device is further configured to;

redistribute the document vectors stored on the plurality of computing devices according to the distances; and

partition the plurality of computing devices according to the distances to construct the child nodes; and

wherein the process is repeated until all the document vectors corresponding to the vantage point tree node reside on a single computing device, and wherein lower levels of the vantage point tree are constructed using document vectors on the single computing device and a vantage point for each node in the lower levels of the vantage point tree.

14. The system of claim 11, wherein the system comprises a plurality of computing devices;

wherein traversing the document vector search space using the vantage point tree comprises traversing a set of child nodes for a specified vantage point tree node by sending the query vector to a coordinating computing device chosen from the plurality of computing devices which contain document vectors corresponding to the specified vantage point tree node; and

wherein the system memory of the coordinating computing devices is configured to;

traverse the vantage point tree by removing child nodes of document vector clusters that are outside a hypersphere of the specified search radius centered about the query vector;

repeat until all document vectors for the given vantage point tree node reside on the coordinating computing device;

search lower levels of the vantage point tree using the query vector and the specified search radius to determine vantage point tree nodes that are to be searched; and

wherein the system memory of each of the plurality of computing devices corresponding to the vantage point tree nodes that are to be searched is configured to;

remove any of the document vectors that do not satisfy a triangle inequality condition for the specified search radius;

determine a distance between the query vector and each remaining document vector;

determine a specified number of nearest neighbor document vectors to the query vector based on the distance between the query vector and each remaining document vector; and

send the specified number of nearest neighbor document vectors to the coordinating computing device.

15. The system of claim 11, wherein the vantage point tree comprises a multi-vantage point tree comprising a plurality of vantage points for each node in the vantage point tree.

16. The system of claim 11, wherein the system memory comprises code configured to rank documents corresponding to the nearest neighbor document vectors based on a relevance of each document to a query corresponding to the query vector.

17. One or more computer-readable storage devices 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;

search the vantage point tree to determine a specified number of nearest neighbor document vectors to the query vector; and

remove a portion of the plurality of document vectors that are outside a hypersphere of the specified search radius for the query vector;

remove a portion of the plurality of document vectors that do not satisfy the triangle inequality condition; and

adjust the specified search radius such that only a specified number of nearest neighbor document vectors are remaining after document vectors that are outside the hypersphere of the specified search radius for the query vector and document vectors that do not satisfy the triangle inequality condition have been removed.

18. The one or more computer-readable storage devices of claim 17, wherein the computer-readable instructions comprise code configured to:

calculate a distance range between each remaining document vector and the query vector; and

determine the specified number of nearest neighbor document vectors to the query vector based on the distance between each remaining document vector and the query vector.

19. The one or more computer-readable storage devices of claim 17, wherein the computer-readable instructions comprise code configured to rank documents corresponding to the nearest neighbor document vectors based on a relevance of each document to a query corresponding to the query vector.