Bayesian visual interactive search

• US 10,102,277 B2
• Filed: 12/09/2016
• Issued: 10/16/2018
• Est. Priority Date: 05/15/2014
• Status: Active Grant

• Current Assignee: Sentient Technologies (Barbados) Limited
• Original Assignee: Sentient Technologies (Barbados) Limited
• Inventors: Legrand, Diego Guy M., Long, Philip M., Duffy, Nigel, Francon, Olivier
• Primary Examiner(s): WILLOUGHBY, ALICIA M
• Application Number:
  US15/373,897
• Publication Number:
  US 20170091319A1
• Time in Patent Office: 676 Days
• CPC Class Codes: G06F 16/3346 using probabilistic model
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06Q 30/00 Commerce

Abstract

A method for identifying a desired document is provided to include calculating a Prior probability score for each document of a candidate list including a portion of documents of an embedding space, the Prior probability score indicating a preliminary probability, for each document of the candidate list, that the document is the desired document, and identifying an initial (i=0) collection of N0>1 candidate documents from the candidate list in dependence on the calculated Prior probability scores, the initial collection of candidate documents having fewer documents than the candidate list. The method further includes, for each i'"'"'th iteration in a plurality of iterations, beginning with a first iteration (i=1) and in response to user selection of an i'"'"'th selected document from the (i−1)'"'"'th collection of candidate documents, identifying an i'"'"'th collection of Ni>1 candidate documents from the candidate list in dependence on Posterior probability scores.

Claims

1. A method for user identification of a desired document, comprising:

providing, accessibly to a computer system, a database identifying a catalog of documents in an embedding space;

calculating a Prior probability score for each document of a candidate list including at least a portion of the documents of the embedding space, the Prior probability score indicating a preliminary probability, for each particular document of the candidate list, that the particular document is the desired document;

a computer system identifying toward the user an initial (i=0) collection of N0>

1 candidate documents from the candidate list in dependence on the calculated Prior probability scores for the documents in the candidate list, the initial collection of candidate documents having fewer documents than the candidate list; and

for each i'"'"'th iteration in a plurality of iterations, beginning with a first iteration (i=1) and in response to user selection of an i'"'"'th selected document from the (i−

1)'"'"'th collection of candidate documents, identifying toward the user an i'"'"'th collection of Ni>

1 candidate documents from the candidate list in dependence on Posterior probability scores for at least a portion of the documents in the candidate list, Ni being smaller than the number of documents in the candidate list, the Posterior probability score for each given document D being given by P(C|D)P(D), where C is the sequence of documents c₁, . . . , c_i selected by the user up through the i'"'"'th iteration, where P(C|D) is the system'"'"'s view of the probability of C if the desired document is D and where P(D) is the calculated Prior probability score for document D.

2. The method of claim 1, further comprising, for each i'"'"'th iteration in the plurality of iterations, calculating the Posterior probability score for each document of the candidate list in dependence on the user selection of the i'"'"'th document from the (i−

1)'"'"'th collection of candidate documents.

3. The method of claim 1, further comprising taking an action in response to user behavior identifying as the desired document a selected document in one of the collections of documents.

4. The method of claim 1, wherein the Prior probability score is calculated for each document of the candidate list in dependence on previous experience, not specific to the user, regarding the documents of the candidate list.

5. The method of claim 4, wherein the documents in the candidate list represent products for sale,

and wherein the previous experience includes previous sales experience of products represented by at least one of the documents of the candidate list relative to products represented by other documents of the candidate list.

6. The method of claim 1, wherein the Prior probability scores are calculated in dependence on previous indications by the user of preferences among documents of the candidate list.

7. The method of claim 1, wherein one or more previous identifications of desired documents by the user are represented by a mean embedding vector of the user'"'"'s past identifications of desired documents,

and wherein calculating a Prior probability score for each document of a candidate list comprises calculating the Prior probability scores in dependence on a spherically symmetrical Gaussian centered at the mean embedding vector.

8. The method of claim 1, wherein the Prior probability scores are calculated in dependence on previous indications by one or more people other than the user, of preferences among documents of the candidate list.

9. The method of claim 8, wherein the one or more people are determined in dependence on criteria indicating similarity of the one or more people to the user.

10. The method of claim 1,

wherein the database identifies a distance between each pair of the documents in the embedding space and the distance corresponds to a predetermined measure of dissimilarity between the pair of documents,

wherein the method further includes, prior to the calculating of the Prior probability score for each document of the candidate list, identifying toward the user a preliminary collection of documents and receiving user selection of a seed document from the preliminary collection of documents,

and wherein calculating a Prior probability score for each document of a candidate list comprises calculating the Prior probability scores in dependence on a factor that decays as a function of distance from the seed document.

11. The method of claim 1, further comprising, after each i'"'"'th iteration of the plurality of iterations, removing a predetermined fraction of documents from the candidate list.

12. The method of claim 1, wherein P(C|D) is dependent upon probabilities determined with respect to the sequence of documents c₁, . . . , c_i selected by the user up through the i'"'"'th iteration.

13. The method of claim 1, wherein P(C|D) is given by Π

_j=1ⁱP(c_j|D), where each c_j is the document selected by the user in the j'"'"'th iteration.

14. The method of claim 1, wherein for an iteration i>

1, the system gives at least one of the documents c₁, . . . , c<sub>i−

1</sub> less influence on P(C|D) than the influence given by the system to document c_i on P(C|D).

15. The method of claim 1, wherein for each iteration i>

1, the system gives at least one of the documents c₁, . . . , c<sub>i−

1</sub> less influence on P(C|D) than the influence given by the system to document c_i on P(C|D).

16. The method of claim 1, wherein for an iteration i>

1, the system gives each of the documents c₁, . . . , c<sub>i−

1</sub> less influence on P(C|D) than the influence given by the system to document c_i on P(C|D).

17. The method of claim 1, wherein for each iteration i>

1, the system gives each of the documents c₁, . . . , c<sub>i−

1</sub> less influence on P(C|D) than the influence given by the system to document c_i on P(C|D).

18. The method of claim 1, wherein for an iteration i>

1, the system gives each document c_j, j=1, . . . , i, an influence on P(C|D) which is related monotonically the iteration number j in which document c_j was selected by the user.

19. The method of claim 1, wherein identifying toward the user an i'"'"'th collection of documents comprises:

calculating the Posterior probability scores for at least a subset of more than Ni of the candidate documents from the candidate list; and

identifying toward the user the candidate documents having the Ni highest calculated Posterior probability scores.

20. The method of claim 1, wherein identifying toward the user an i'"'"'th collection of candidate documents comprises selecting documents from the candidate list, to be included in the i'"'"'th collection of candidate documents, randomly according to a probability distribution that is weighted in dependence on the Posterior probability scores.

21. The method of claim 1, wherein identification of the initial collection of candidate documents toward the user comprises selecting documents from the candidate list, to be included in the initial collection of candidate documents, randomly according to a probability distribution that is weighted in dependence on the calculated Prior probability scores.

22. The method of claim 1, wherein for each i'"'"'th iteration in the plurality of iterations, identifying toward the user an i'"'"'th collection of documents comprises:

calculating the Posterior probability scores for at least a subset of the candidate documents from the candidate list; and

assigning zero as the Posterior probability score for each unselected document from the (i−

1)'"'"'th collection of documents.

23. The method of claim 1, further comprising:

initializing a neighbor graph G to include a corresponding vertex for each document of the candidate list; and

developing a plurality of tours each touching all the vertices in the neighbor graph G corresponding to documents of the candidate list, including, for each k'"'"'th tour of the plurality of tours, beginning with a first (k=1) tour;

determining a perpendicular projection of each document of the candidate list onto a k'"'"'th randomly oriented projection line that passes through an origin of the embedding space,

inserting into the neighbor graph G an edge from each particular vertex of G, to all vertices of the particular vertex whose projections onto the k'"'"'th line neighbor the projection of the particular vertex onto the k'"'"'th line, and

inserting into the neighbor graph G an edge between the vertices corresponding to two documents of the candidate list having the outermost projections onto the k'"'"'th line,

wherein identifying toward the user an i'"'"'th collection of candidate documents comprises inserting documents into the i'"'"'th collection of candidate documents in dependence on a walk through the neighbor graph G beginning with the vertex in the graph corresponding to the i'"'"'th selected document and guided by Posterior probability scores calculated for documents corresponding to vertices encountered during the walk.

24. The method of claim 23, wherein, for each k'"'"'th tour, an edge is inserted from each vertex of the neighbor graph G to each of two other vertices of the neighbor graph G.

25. The method of claim 23, further comprising taking action in response to user behavior identifying, a selected document in one of the collections of documents, as the desired document.

26. The method of claim 23, further comprising, after each i'"'"'th iteration of the plurality of iterations, removing a predetermined fraction of vertices and connecting edges from the neighbor graph G.

27. The method of claim 23, wherein developing a plurality of tours further comprises removing redundant edges from the neighbor graph G belonging to different ones of the plurality of tours.

28. The method of claim 23, wherein the database identifies a distance between each pair of the documents in the embedding space and the distance corresponds to a predetermined measure of dissimilarity between the pair of documents, and

wherein developing a plurality of tours further comprises, for each k'"'"'th tour in the plurality of tours:

walking the vertices of the k'"'"'th tour for a plurality of laps; and

at each current vertex encountered in the walk, determining whether the document corresponding to the next vertex of the tour is farther away in the embedding space from the document corresponding to the current vertex than the document corresponding to a vertex further downstream in the tour is from the document corresponding to the current vertex, and if so then swapping the next vertex with the downstream vertex in the tour.

29. The method of claim 23,

wherein the database identifies a distance between each pair of the documents in the embedding space and the distance corresponds to a predetermined measure of dissimilarity between the pair of documents, and

wherein developing a plurality of tours further comprises, after inserting into neighbor graph G all the edges of each k'"'"'th tour in the plurality of tours:

walking the vertices of the k'"'"'th tour for a plurality of laps;

at each current vertex encountered in the walk, determining whether the document corresponding to the next vertex of the tour is farther away in the embedding space from the document corresponding to the current vertex than the document corresponding to a vertex further downstream in the tour is from the document corresponding to the current vertex, and if so then swapping the next vertex with the downstream vertex in the tour; and

removing edges from the neighbor graph G belonging to the k'"'"'th tour which are redundant with edges belonging to prior tours in the plurality of tours.

30. The method of claim 23, wherein identifying toward the user an i'"'"'th collection of candidate documents comprises, for each i'"'"'th iteration in the plurality of iterations:

beginning with the vertex that corresponds to the i'"'"'th selected document, walking a predetermined number of steps through vertices of the neighbor graph G not corresponding to documents already in the i'"'"'th collection, each step from a current vertex including, if the document corresponding to all neighbors of the current vertex are not already in the i'"'"'th collection of documents, choosing a next vertex in dependence upon the Posterior probability score of at least one neighbor of the current vertex; and

inserting into the i'"'"'th collection of documents the document corresponding to the last vertex encountered in the walk.

31. A method for user identification of a desired document, comprising:

providing, accessibly to a computer system, a database identifying a catalog of documents in an embedding space;

calculating a Prior probability score for each document of a candidate list including at least a portion of the documents of the embedding space, the Prior probability score indicating a preliminary probability, for each particular document of the candidate list, that the particular document is the desired document;

a computer system identifying toward the user an initial (i=0) collection of N0>

1 candidate documents from the candidate list in dependence on the calculated Prior probability scores for the documents of the candidate list, the initial collection of candidate documents having fewer documents than the candidate list; and

for each i'"'"'th iteration in a plurality of iterations, beginning with a first iteration (i=1);

in response to user selection of an i'"'"'th selected document from the (i−

1)'"'"'th collection of documents, calculating a Posterior probability score for each document of the candidate list, and

identifying toward the user an i'"'"'th collection of Ni>

1 candidate documents from the candidate list in dependence on the calculated Posterior probability scores for the documents in the candidate list, Ni being smaller than the number of documents of the candidate list,

wherein the calculated Posterior probability score for each given document D is given by P(C|D)P(D), where C is the sequence of documents c₁, . . . , c_i selected by the user up through the i'"'"'th iteration, where P(C|D) is the system'"'"'s view of the probability of C if the desired document is D and where P(D) is the calculated Prior probability score for document D.

32. A method for user identification of a desired document, comprising:

providing, accessibly to a computer system, a database identifying a catalog of documents in an embedding space;

calculating a Prior probability score for each document of a candidate list including at least a portion of the documents of the embedding space, the Prior probability score indicating a preliminary probability, for each particular document of the candidate list, that the particular document is the desired document;

initializing a neighbor graph G to include a corresponding vertex for each document of the candidate list;

developing a plurality of tours each touching all the vertices in the neighbor graph G corresponding to documents of the candidate list, including, for each k'"'"'th tour of the plurality of tours, beginning with a first (k=1) tour;

determining a perpendicular projection of each document of the candidate list onto a k'"'"'th randomly oriented projection line that passes through an origin of the embedding space,

inserting into the neighbor graph G an edge from each particular vertex of G, to all vertices of the particular vertex whose projections onto the k'"'"'th line neighbor the projection of the particular vertex onto the k'"'"'th line, and

inserting into the neighbor graph G an edge between the vertices corresponding to two documents of the candidate list having the outermost projections onto the k'"'"'th line,

a computer system identifying toward the user an initial (i=0) collection of N0>

1 candidate documents from the candidate list in dependence on the calculated Prior probability scores for the documents in the candidate list, the initial collection of candidate documents having fewer documents than the candidate list; and

for each i'"'"'th iteration in a plurality of iterations, beginning with a first iteration (i=1);

in response to user selection of an i'"'"'th selected document from the (i−

1)'"'"'th collection of candidate documents, inserting documents into an i'"'"'th collection of Ni>

1 candidate documents in dependence on a walk through the neighbor graph G beginning with the vertex in the graph corresponding to the it’

selected document and guided by Posterior probability scores calculated for documents corresponding to vertices encountered during the walk, Ni being smaller than the number of documents in the candidate list, and

identifying toward the user the i'"'"'th collection of candidate documents from the candidate list,

wherein the Posterior probability score for each given document D is given by P(C|D)P(D), where C is the sequence of documents c₁, . . . , c_i selected by the user up through the i'"'"'th iteration, where P(C|D) is the system'"'"'s view of the probability of C if the desired document is D and where P(D) is the calculated Prior probability score for document D.

33. A method for user identification of a desired document, comprising:

providing, accessibly to a computer system, a database identifying (i) a catalog of documents in an embedding space and (ii) a distance between each pair of the documents in the embedding space and the distance corresponds to a predetermined measure of dissimilarity between the pair of documents;

calculating a Prior probability score for each document of a candidate list including at least a portion of the documents of the embedding space, the Prior probability score indicating a preliminary probability, for each particular document of the candidate list, that the particular document is the desired document;

a computer system identifying toward the user an initial (i=0) collection of N0>

1 candidate documents from the candidate list in dependence on the calculated Prior probability scores for the documents in the candidate list, the initial collection of candidate documents having fewer documents than the candidate list; and

for each i'"'"'th iteration in a plurality of iterations, beginning with a first iteration (i=1);

in response to user selection of an i'"'"'th selected document from the (i−

1)'"'"'th collection of documents, assigning a weight w to each given document D in dependence on a Posterior probability score for each given document D, and

identifying toward the user an i'"'"'th collection of Ni>

1 candidate documents from the candidate list in dependence on the assigned weights w, the Posterior probability scores and a distance from each given document D to a closest document in the candidate list, such that i'"'"'th collection is a collection of Ni>

1 documents from the candidate list having a lowest weighted average of distances to closest documents that are weighted based on the corresponding weights w and Posterior probability scores, Ni being smaller than the number of documents of the candidate list,

wherein, the Posterior probability score for each given document D being given by P(C|D)P(D), where C is the sequence of documents c₁, . . . , c_i selected by the user up through the i'"'"'th iteration, where P(C|D) is the system'"'"'s view of the probability of C if the desired document is D and where P(D) is the calculated Prior probability score for document D.

34. A non-transitory computer-readable storage medium impressed with computer program instructions to provide user identification of a desired document, the instructions, when executed on a processor, implement a method comprising:

providing, accessibly to a computer system, a database identifying a catalog of documents in an embedding space;

calculating a Prior probability score for each document of a candidate list including at least a portion of the documents of the embedding space, the Prior probability score indicating a preliminary probability, for each particular document of the candidate list, that the particular document is the desired document;

a computer system identifying toward the user an initial (i=0) collection of N0>

1 candidate documents from the candidate list in dependence on the calculated Prior probability scores for the documents in the candidate list, the initial collection of candidate documents having fewer documents than the candidate list; and

for each i'"'"'th iteration in a plurality of iterations, beginning with a first iteration (i=1) and in response to user selection of an i'"'"'th selected document from the (i−

1)'"'"'th collection of candidate documents, identifying toward the user an i'"'"'th collection of Ni>

1 candidate documents from the candidate list in dependence on Posterior probability scores for at least a portion of the documents in the candidate list, Ni being smaller than the number of documents in the candidate list, the Posterior probability score for each given document D being given by P(C|D)P(D), where C is the sequence of documents c₁, . . . , c_i selected by the user up through the i'"'"'th iteration, where P(C|D) is the system'"'"'s view of the probability of C if the desired document is D and where P(D) is the calculated Prior probability score for document D.

35. The non-transitory computer-readable recording medium of claim 34, wherein the method further comprises, for each i'"'"'th iteration in the plurality of iterations, calculating the Posterior probability score for each document of the candidate list in dependence on the user selection of the i'"'"'th document from the (i−

1)'"'"'th collection of candidate documents.

36. The non-transitory computer-readable recording medium of claim 34, wherein the method further comprises:

initializing a neighbor graph G to include a corresponding vertex for each document of the candidate list; and

developing a plurality of tours each touching all the vertices in the neighbor graph G corresponding to documents of the candidate list, including, for each k'"'"'th tour of the plurality of tours, beginning with a first (k=1) tour;

determining a perpendicular projection of each document of the candidate list onto a k'"'"'th randomly oriented projection line that passes through an origin of the embedding space,

inserting into the neighbor graph G an edge from each particular vertex of G, to all vertices of the particular vertex whose projections onto the k'"'"'th line neighbor the projection of the particular vertex onto the k'"'"'th line, and

inserting into the neighbor graph G an edge between the vertices corresponding to two documents of the candidate list having the outermost projections onto the k'"'"'th line,

wherein identifying toward the user an i'"'"'th collection of candidate documents comprises inserting documents into the i'"'"'th collection of candidate documents in dependence on a walk through the neighbor graph G beginning with the vertex in the graph corresponding to the i'"'"'th selected document and guided by Posterior probability scores calculated for documents corresponding to vertices encountered during the walk.

37. A non-transitory computer-readable storage medium impressed with computer program instructions to provide user identification of a desired document, the instructions, when executed on a processor, implement a method comprising:

providing, accessibly to a computer system, a database identifying a catalog of documents in an embedding space;

calculating a Prior probability score for each document of a candidate list including at least a portion of the documents of the embedding space, the Prior probability score indicating a preliminary probability, for each particular document of the candidate list, that the particular document is the desired document;

a computer system identifying toward the user an initial (i=0) collection of N0>

1 candidate documents from the candidate list in dependence on the calculated Prior probability scores for the documents of the candidate list, the initial collection of candidate documents having fewer documents than the candidate list; and

for each i'"'"'th iteration in a plurality of iterations, beginning with a first iteration (i=1);

in response to user selection of an i'"'"'th selected document from the (i−

1)'"'"'th collection of documents, calculating a Posterior probability score for each document of the candidate list, and

identifying toward the user an i'"'"'th collection of Ni>

1 candidate documents from the candidate list in dependence on the calculated Posterior probability scores for the documents in the candidate list, Ni being smaller than the number of documents of the candidate list,

wherein the calculated Posterior probability score for each given document D is given by P(C|D)P(D), where C is the sequence of documents c₁, . . . , c_i selected by the user up through the i'"'"'th iteration, where P(C|D) is the system'"'"'s view of the probability of C if the desired document is D and where P(D) is the calculated Prior probability score for document D.

38. A non-transitory computer-readable storage medium impressed with computer program instructions to provide user identification of a desired document, the instructions, when executed on a processor, implement a method comprising:

providing, accessibly to a computer system, a database identifying a catalog of documents in an embedding space;

calculating a Prior probability score for each document of a candidate list including at least a portion of the documents of the embedding space, the Prior probability score indicating a preliminary probability, for each particular document of the candidate list, that the particular document is the desired document;

initializing a neighbor graph G to include a corresponding vertex for each document of the candidate list;

developing a plurality of tours each touching all the vertices in the neighbor graph G corresponding to documents of the candidate list, including, for each k'"'"'th tour of the plurality of tours, beginning with a first (k=1) tour;

determining a perpendicular projection of each document of the candidate list onto a k'"'"'th randomly oriented projection line that passes through an origin of the embedding space,

inserting into the neighbor graph G an edge from each particular vertex of G, to all vertices of the particular vertex whose projections onto the k'"'"'th line neighbor the projection of the particular vertex onto the k'"'"'th line, and

inserting into the neighbor graph G an edge between the vertices corresponding to two documents of the candidate list having the outermost projections onto the k'"'"'th line,

a computer system identifying toward the user an initial (i=0) collection of N0>

1 candidate documents from the candidate list in dependence on the calculated Prior probability scores for the documents in the candidate list, the initial collection of candidate documents having fewer documents than the candidate list; and

for each i'"'"'th iteration in a plurality of iterations, beginning with a first iteration (i=1);

in response to user selection of an i'"'"'th selected document from the (i−

1)'"'"'th collection of candidate documents, inserting documents into an i'"'"'th collection of Ni>

1 candidate documents in dependence on a walk through the neighbor graph G beginning with the vertex in the graph corresponding to the it’

selected document and guided by Posterior probability scores calculated for documents corresponding to vertices encountered during the walk, Ni being smaller than the number of documents in the candidate list, and

identifying toward the user the i'"'"'th collection of candidate documents from the candidate list,

wherein the Posterior probability score for each given document D is given by P(C|D)P(D), where C is the sequence of documents c₁, . . . , c_i selected by the user up through the i'"'"'th iteration, where P(C|D) is the system'"'"'s view of the probability of C if the desired document is D and where P(D) is the calculated Prior probability score for document D.

39. A non-transitory computer-readable storage medium impressed with computer program instructions to provide user identification of a desired document, the instructions, when executed on a processor, implement a method comprising:

providing, accessibly to a computer system, a database identifying (i) a catalog of documents in an embedding space and (ii) a distance between each pair of the documents in the embedding space and the distance corresponds to a predetermined measure of dissimilarity between the pair of documents;

calculating a Prior probability score for each document of a candidate list including at least a portion of the documents of the embedding space, the Prior probability score indicating a preliminary probability, for each particular document of the candidate list, that the particular document is the desired document;

a computer system identifying toward the user an initial (i=0) collection of N0>

1 candidate documents from the candidate list in dependence on the calculated Prior probability scores for the documents in the candidate list, the initial collection of candidate documents having fewer documents than the candidate list; and

for each i'"'"'th iteration in a plurality of iterations, beginning with a first iteration (i=1);

in response to user selection of an i'"'"'th selected document from the (i−

1)'"'"'th collection of documents, assigning a weight w to each given document D in dependence on a Posterior probability score for each given document D, and

identifying toward the user an i'"'"'th collection of Ni>

1 candidate documents from the candidate list in dependence on the assigned weights w, the Posterior probability scores and a distance from each given document D to a closest document in the candidate list, such that i'"'"'th collection is a collection of Ni>

1 documents from the candidate list having a lowest weighted average of distances to closest documents that are weighted based on the corresponding weights w and Posterior probability scores, Ni being smaller than the number of documents of the candidate list,

wherein, the Posterior probability score for each given document D being given by P(C|D)P(D), where C is the sequence of documents c₁, . . . , c_i selected by the user up through the i'"'"'th iteration, where P(C|D) is the system'"'"'s view of the probability of C if the desired document is D and where P(D) is the calculated Prior probability score for document D.

40. A system including one or more processors coupled to memory, the memory loaded with computer instructions to provide for user identification of a desired document, the instructions, when executed on the processors, implement actions comprising:

providing, accessibly to a computer system, a database identifying a catalog of documents in an embedding space;

calculating a Prior probability score for each document of a candidate list including at least a portion of the documents of the embedding space, the Prior probability score indicating a preliminary probability, for each particular document of the candidate list, that the particular document is the desired document;

a computer system identifying toward the user an initial (i=0) collection of N0>

1 candidate documents from the candidate list in dependence on the calculated Prior probability scores for the documents in the candidate list, the initial collection of candidate documents having fewer documents than the candidate list; and

for each i'"'"'th iteration in a plurality of iterations, beginning with a first iteration (i=1) and in response to user selection of an i'"'"'th selected document from the (i−

1)'"'"'th collection of candidate documents, identifying toward the user an i'"'"'th collection of Ni>

1 candidate documents from the candidate list in dependence on Posterior probability scores for at least a portion of the documents in the candidate list, Ni being smaller than the number of documents in the candidate list, the Posterior probability score for each given document D being given by P(C|D)P(D), where C is the sequence of documents c₁, . . . , c_i selected by the user up through the i'"'"'th iteration, where P(C|D) is the system'"'"'s view of the probability of C if the desired document is D and where P(D) is the calculated Prior probability score for document D.

41. The system of claim 40, further comprising, for each i'"'"'th iteration in the plurality of iterations, calculating the Posterior probability score for each document of the candidate list in dependence on the user selection of the i'"'"'th document from the (i−

1)'"'"'th collection of candidate documents.

42. The system of claim 40, further comprising:

initializing a neighbor graph G to include a corresponding vertex for each document of the candidate list; and

developing a plurality of tours each touching all the vertices in the neighbor graph G corresponding to documents of the candidate list, including, for each k'"'"'th tour of the plurality of tours, beginning with a first (k=1) tour;

determining a perpendicular projection of each document of the candidate list onto a k'"'"'th randomly oriented projection line that passes through an origin of the embedding space,

inserting into the neighbor graph G an edge from each particular vertex of G, to all vertices of the particular vertex whose projections onto the k'"'"'th line neighbor the projection of the particular vertex onto the k'"'"'th line, and

inserting into the neighbor graph G an edge between the vertices corresponding to two documents of the candidate list having the outermost projections onto the k'"'"'th line,

wherein identifying toward the user an i'"'"'th collection of candidate documents comprises inserting documents into the i'"'"'th collection of candidate documents in dependence on a walk through the neighbor graph G beginning with the vertex in the graph corresponding to the i'"'"'th selected document and guided by Posterior probability scores calculated for documents corresponding to vertices encountered during the walk.

43. A system including one or more processors coupled to memory, the memory loaded with computer instructions to provide for user identification of a desired document, the instructions, when executed on the processors, implement actions comprising:

providing, accessibly to a computer system, a database identifying a catalog of documents in an embedding space;

calculating a Prior probability score for each document of a candidate list including at least a portion of the documents of the embedding space, the Prior probability score indicating a preliminary probability, for each particular document of the candidate list, that the particular document is the desired document;

a computer system identifying toward the user an initial (i=0) collection of N0>

1 candidate documents from the candidate list in dependence on the calculated Prior probability scores for the documents of the candidate list, the initial collection of candidate documents having fewer documents than the candidate list; and

for each i'"'"'th iteration in a plurality of iterations, beginning with a first iteration (i=1);

in response to user selection of an i'"'"'th selected document from the (i−

1)'"'"'th collection of documents, calculating a Posterior probability score for each document of the candidate list, and

identifying toward the user an i'"'"'th collection of Ni>

1 candidate documents from the candidate list in dependence on the calculated Posterior probability scores for the documents in the candidate list, Ni being smaller than the number of documents of the candidate list,

wherein the calculated Posterior probability score for each given document D is given by P(C|D)P(D), where C is the sequence of documents c₁, . . . , c_i selected by the user up through the i'"'"'th iteration, where P(C|D) is the system'"'"'s view of the probability of C if the desired document is D and where P(D) is the calculated Prior probability score for document D.

44. A system including one or more processors coupled to memory, the memory loaded with computer instructions to provide for user identification of a desired document, the instructions, when executed on the processors, implement actions comprising:

providing, accessibly to a computer system, a database identifying a catalog of documents in an embedding space;

calculating a Prior probability score for each document of a candidate list including at least a portion of the documents of the embedding space, the Prior probability score indicating a preliminary probability, for each particular document of the candidate list, that the particular document is the desired document;

initializing a neighbor graph G to include a corresponding vertex for each document of the candidate list;

developing a plurality of tours each touching all the vertices in the neighbor graph G corresponding to documents of the candidate list, including, for each k'"'"'th tour of the plurality of tours, beginning with a first (k=1) tour;

determining a perpendicular projection of each document of the candidate list onto a k'"'"'th randomly oriented projection line that passes through an origin of the embedding space,

inserting into the neighbor graph G an edge from each particular vertex of G, to all vertices of the particular vertex whose projections onto the k'"'"'th line neighbor the projection of the particular vertex onto the k'"'"'th line, and

inserting into the neighbor graph G an edge between the vertices corresponding to two documents of the candidate list having the outermost projections onto the k'"'"'th line,

a computer system identifying toward the user an initial (i=0) collection of N0>

1 candidate documents from the candidate list in dependence on the calculated Prior probability scores for the documents in the candidate list, the initial collection of candidate documents having fewer documents than the candidate list; and

for each i'"'"'th iteration in a plurality of iterations, beginning with a first iteration (i=1);

in response to user selection of an i'"'"'th selected document from the (i−

1)'"'"'th collection of candidate documents, inserting documents into an i'"'"'th collection of Ni>

1 candidate documents in dependence on a walk through the neighbor graph G beginning with the vertex in the graph corresponding to the it’

selected document and guided by Posterior probability scores calculated for documents corresponding to vertices encountered during the walk, Ni being smaller than the number of documents in the candidate list, and

identifying toward the user the i'"'"'th collection of candidate documents from the candidate list,

wherein the Posterior probability score for each given document D is given by P(C|D)P(D), where C is the sequence of documents c₁, . . . , c_i selected by the user up through the i'"'"'th iteration, where P(C|D) is the system'"'"'s view of the probability of C if the desired document is D and where P(D) is the calculated Prior probability score for document D.

45. A system including one or more processors coupled to memory, the memory loaded with computer instructions to provide for user identification of a desired document, the instructions, when executed on the processors, implement actions comprising:

providing, accessibly to a computer system, a database identifying (i) a catalog of documents in an embedding space and (ii) a distance between each pair of the documents in the embedding space and the distance corresponds to a predetermined measure of dissimilarity between the pair of documents;

calculating a Prior probability score for each document of a candidate list including at least a portion of the documents of the embedding space, the Prior probability score indicating a preliminary probability, for each particular document of the candidate list, that the particular document is the desired document;

a computer system identifying toward the user an initial (i=0) collection of N0>

1 candidate documents from the candidate list in dependence on the calculated Prior probability scores for the documents in the candidate list, the initial collection of candidate documents having fewer documents than the candidate list; and

for each i'"'"'th iteration in a plurality of iterations, beginning with a first iteration (i=1);

in response to user selection of an i'"'"'th selected document from the (i−

1)'"'"'th collection of documents, assigning a weight w to each given document D in dependence on a Posterior probability score for each given document D, and

identifying toward the user an i'"'"'th collection of Ni>

1 candidate documents from the candidate list in dependence on the assigned weights w, the Posterior probability scores and a distance from each given document D to a closest document in the candidate list, such that i'"'"'th collection is a collection of Ni>

1 documents from the candidate list having a lowest weighted average of distances to closest documents that are weighted based on the corresponding weights w and Posterior probability scores, Ni being smaller than the number of documents of the candidate list,

wherein, the Posterior probability score for each given document D being given by P(C|D)P(D), where C is the sequence of documents c₁, . . . , c_i selected by the user up through the i'"'"'th iteration, where P(C|D) is the system'"'"'s view of the probability of C if the desired document is D and where P(D) is the calculated Prior probability score for document D.