Scalable tree-based search of content descriptors

• US 8,352,483 B1
• Filed: 05/12/2010
• Issued: 01/08/2013
• Est. Priority Date: 05/12/2010
• Status: Active Grant

• Current Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Original Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Inventors: Ramesh, Sunil, Dhua, Arnab S., Delgadillo, Max, Manmatha, Raghavan
• Primary Examiner(s): MORRISON, JAY A
• Application Number:
  US12/778,957
• Time in Patent Office: 972 Days
• Field of Search: None
• US Class Current: 707/758
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures

Abstract

Multiple paths of an index tree may be traversed to discover a set of content descriptors that are match candidates for a set of query descriptors. A size of the set of candidate content descriptors may be optimized, for example, to reduce false positive matching errors, query latencies and/or index tree traversal times, at least in part by determining a number of child nodes to traverse based at least in part on current traverse level and/or traverse neighborhood thresholds. Index trees for large content descriptor sets may be built in resource constrained environments with approximation and/or refining build techniques.

Claims

1. A computer-implemented method for searching a collection of content, comprising:

under control of one or more computer systems configured with executable instructions,

receiving a search request corresponding to query content, the query content characterized by at least one query descriptor;

traversing an index tree including a plurality of levels that indexes a set of content descriptors characterizing the collection of content, the traversing including, at one or more of the plurality of levels of the index tree;

determining distances between child nodes of a distinguished node of the index tree and said at least one query descriptor based at least in part on index descriptors of the child nodes, each index descriptor representing a summarized characteristic for each child node;

determining a maximum number of child nodes to select for traversal based at least in part on the level of the distinguished node, the level of the distinguished node having a threshold relative to one or more other levels; and

selecting for traversal, in order of distance from said at least one query descriptor, at most the maximum number of child nodes, the maximum number being determined based at least in part on the level of the distinguished node;

selecting a subset of the content descriptors based at least in part on the traversing of the index tree; and

providing for presentation at least a reference to content in the collection characterized by at least one of the subset of content descriptors.

2. A computer-implemented method according to claim 1, wherein each of the descriptors includes a vector of a vector space.

3. A computer-implemented method according to claim 2, wherein determining the distance between each child node and each query descriptor includes determining an angle between the vector of the index descriptor of the child node and the vector of the query descriptor.

4. A computer-implemented method according to claim 1, wherein determining the distance between each child node and each query descriptor includes determining the distance between the index descriptor of the child node and the query descriptor with respect to a metric of a descriptor space.

5. A computer-implemented method according to claim 1, wherein selecting the subset of the content descriptors includes selecting content descriptors indexed by traversed nodes.

6. A computer-implemented method for searching a collection of content, comprising:

under control of one or more computer systems configured with executable instructions,

determining at least one query descriptor based at least in part on query content; and

determining a subset of a set of content descriptors characterizing the collection of content, the set of content descriptors being indexed by an index tree including a plurality of nodes at a plurality of node levels by, at least;

determining, for a parent node in at least one of the plurality of node levels, a number of child nodes to traverse, the number of child nodes to traverse based at least in part on the node level of the parent node, the node level of the parent node having a threshold relative to one or more other node levels; and

traversing at most the number of child nodes nearest in distance to said at least one query descriptor as part of identifying a set of lowest level nodes indexing the subset of the set of content descriptors, the number of child nodes nearest in distance being determined based at least in part on index descriptors of the child nodes, each index descriptor representing a summarized characteristic for each child node.

7. A computer-implemented method according to claim 6, further comprising providing for presentation at least a reference to content in the collection associated with at least one of the determined subset of the set of content descriptors.

8. A computer-implemented method according to claim 6, wherein:

the plurality of node levels of the index tree is classified into a plurality of level classes associated with a plurality of fan-out thresholds; and

determining the number of child nodes to select for traversal includes setting the number of child nodes to select for traversal based at least in part on at least one fan-out threshold associated with the level class of the node level.

9. A computer-implemented method according to claim 8, wherein the plurality of level classes comprises:

an upper level class classifying at least one node level of the index tree;

a middle level class classifying at least one node level of the index tree lower than said at least one node level in the upper level class; and

a lower level class classifying at least one node level of the index tree lower than said at least one level in the middle level class.

10. A computer-implemented method according to claim 9, wherein each fan-out threshold associated with the middle level class has a magnitude greater than or equal to a magnitude of each fan-out threshold associated with the lower level class.

11. A computer-implemented method according to claim 10, wherein the magnitude of each fan-out threshold associated with the middle level class is greater than or equal to a magnitude of each fan-out threshold associated with the upper level class.

12. A computer-implemented method according to claim 6, wherein selecting for traversal at most the number of child nodes includes:

selecting a first nearest child node to said at least one query descriptor for traversal;

determining a relative distance of at least a second nearest child node from said at least one query descriptor with respect to the first nearest child node; and

selecting said at least the second nearest child node for traversal if the relative distance is less than a traversal neighborhood threshold.

13. A computer-implemented method for searching a collection of content, comprising:

under control of one or more computer systems configured with executable instructions,

determining at least one query descriptor based at least in part on query content;

determining a subset of a set of content descriptors indexed by an index tree at least in part by traversing the index tree to identify a set of lowest level nodes indexing the subset, the traversing including;

selecting a first nearest child node to said at least one query descriptor for traversal;

determining a relative distance of at least a second nearest child node from said at least one query descriptor with respect to the first nearest child node, the distance being determined based at least in part on index descriptors of the first and second nearest child nodes, each index descriptor representing a summarized characteristic for each child node; and

selecting said at least the second nearest child node for traversal if the relative distance is less than a traversal neighborhood threshold; and

providing for presentation at least a reference to content in the collection associated with at least one of the set of content descriptors.

14. A computer-implemented method according to claim 13, wherein determining the relative distance includes normalizing a distance between said at least one query descriptor and said at least the second nearest child node with respect to a distance between said at least one query descriptor and the first nearest child node.

15. A computer-implemented method according to claim 13, wherein the traversing further includes bounding the number of selected child nodes based at least in part on traversal level in the index tree.

16. A computer-implemented method according to claim 13, wherein:

the traversing further includes determining a maximum number of child nodes to select for traversal based at least in part on traversal level; and

said at least the second nearest child node is selected for traversal if the relative distance is less than the traversal neighborhood threshold and if doing so does not exceed the determined maximum.

17. A computerized system for searching a collection of content, comprising:

a data store storing at least;

a set of content descriptors characterizing the collection of content; and

an index tree indexing the set of content descriptors; and

a processor; and

a memory device including instructions that, when executed by the processor, cause the processor to;

determine at least one query descriptor based at least in part on query content;

determine a subset of the set of content descriptors at least in part by traversing the index tree, the traversing including;

determining a number of child nodes to select for traversal based at least in part on traversal level; and

selecting for traversal at most the number of child nodes nearest in distance to said at least one query descriptor, the number of child nodes nearest in distance being determined based at least in part on index descriptors of the first and second nearest child nodes, each index descriptor representing a summarized characteristic for each child node; and

provide for presentation at least a reference to content in the collection characterized by at least one of the subset of the set of content descriptors.

18. A computerized system according to claim 17, wherein the number of child nodes to select for traversal is determined for each of a plurality of levels of the index tree.

19. A computerized system according to claim 17, wherein the instructions further cause the processor to provide a search user interface least configured to perform the providing for presentation responsive to a search request at least referencing the query content.

20. A computerized system according to claim 19, wherein the providing for presentation includes specifying the presentation with a presentation specification language.

21. A computerized system according to claim 17, wherein the determined number of child nodes to select for traversal at middle levels of the index tree is greater than the determined number of child nodes to select for traversal at lower levels of the index tree.

22. One or more non-transitory computer-readable media having collectively thereon computer-executable instructions that configure one or more computers to collectively, at least:

determine at least one query descriptor based at least in part on query content;

determine a subset of content descriptors indexed by an index tree at least in part by traversing the index tree, the traversing including;

(a) selecting for traversal a first child node nearest to said at least one query descriptor;

(b) determining a first distance of a second child node from said at least one query descriptor; and

(c) selecting the second child node for traversal if the first distance is less than a traversal neighborhood threshold, the distance being determined based at least in part on an index descriptor of the second child node, the index descriptor representing a summarized characteristic for the second child node; and

provide for presentation at least a reference to content characterized by at least one of the subset of content descriptors.

23. One or more non-transitory computer-readable media according to claim 22, wherein the content descriptors characterize a collection of content and said at least one query descriptor similarly characterizes the query content.

24. One or more non-transitory computer-readable media according to claim 22, wherein:

the first distance includes a relative distance normalized with respect to a second distance between the first child node and said at least one query descriptor; and

the traversal neighborhood threshold includes a relative distance threshold.

25. One or more non-transitory computer-readable media according to claim 22, wherein the traversing further includes:

determining a second distance of a third child node from said at least one query descriptor; and

selecting the third child node for traversal if the second distance is less than the traversal neighborhood threshold.

26. One or more non-transitory computer-readable media according to claim 22, wherein the traversing further includes:

initially selecting a root node of the index tree for traversal; and

performing steps (a), (b) and (c) for each node of the index tree selected for traversal.