Visual interactive search

Abstract

Roughly described, a system and method for user identification of a desired document, in which a database is provided which identifies a collection of documents in an embedding space, the database identifying a distance between each pair of the documents in the embedding space corresponding to a predetermined measure of dissimilarity between the pair of documents. In dependence upon a user query, the system constrains the embedding space geometrically to develop a first candidate space, and identifies toward the user a first set of N1>1 candidate documents from the first candidate space, the first set of candidate documents being more discriminative than the average discriminativeness of set size N1 documents in the first candidate space. Preferably the placement of the documents as presented to the user is indicative of the placement of the documents in the embedding space, either in distance or in collinearity or both.

1 . A method for user identification of a desired document, comprising:
 providing, accessibly to a computer system, a database identifying a first plurality of documents in an embedding space, the database identifying a distance between each pair of the documents in the embedding space corresponding to a predetermined measure of dissimilarity between the pair of documents;   in dependence upon a user query:
 the computer system geometrically constraining the embedding space to develop a first candidate space, and 
 identifying toward the user a first set of N1>1 candidate documents from the first candidate space, the first set of candidate documents having fewer documents than the first candidate space and being more discriminative than the average discriminativeness of set size N1 documents in the first candidate space; and 
   taking action in response to user selection of a document identified toward the user.   
     
     
         2 . The method of  claim 1 , wherein the set of candidate documents is at least as discriminative as all other sets of size N1 documents in the first candidate space. 
     
     
         3 . The method of  claim 1 , wherein taking action comprises:
 the computer system geometrically constraining the first candidate space to develop a second candidate space, the second candidate space being a geometrically constrained portion of the first candidate space determined in dependence upon user selection of a subset of the documents in the first set of candidate documents;   identifying toward the user a second set of N2>1 candidate documents from the second candidate space, the second set of candidate documents having fewer documents than the second candidate space and being more discriminative than the average discriminativeness of set size N2 documents in the second candidate space; and   taking action in response to user selection of a document from the second set of candidate documents.   
     
     
         4 . The method of  claim 3 , wherein the second candidate space is determined so as to include more documents which are similar to the user selected subset of documents than the number of documents similar to the documents in the first set of candidate documents which are not in the user selected subset. 
     
     
         5 . The method of  claim 1 , wherein the embedding space comprises a multi-dimensional vector space, each of the dimensions in the vector space defining a different basis on which documents can differ from each other,
 and wherein the database identifies a position for each of the documents in the multi-dimensional vector space.   
     
     
         6 . The method of  claim 5 , wherein taking action comprises:
 a computer system identifying toward the user a second set of N2>1 candidate documents from the first candidate space, at least one pair of documents in the second set of candidate documents having different coordinates along a second dimension in the multi-dimensional vector space and being more discriminative than the average discriminativeness of set size N2 documents in the first candidate space, wherein the second dimension differs from all the dimensions of the multi-dimensional vector space along which documents in the first set of candidate documents differ from each other; and   taking action in response to user selection of a document from the second set of candidate documents.   
     
     
         7 . The method of  claim 5 , wherein identifying toward the user a first set of candidate documents from the first candidate space comprises presenting toward the user an M-dimensional layout, M>1, identifying the first set of candidate documents, the placement of candidate documents in the layout being indicative of dimensions in the first candidate space along which the candidate documents differ. 
     
     
         8 . The method of  claim 7 , wherein the placement of at least some candidate documents in the layout relative to each is further indicative of the distances among those candidate documents in the first candidate space. 
     
     
         9 . The method of  claim 5 , wherein providing a database comprises:
 determining, from the first plurality of documents, a first plurality of dimensions along which at least some of the documents in the first plurality of documents differ;   a computer system determining a position in each dimension in the first plurality of dimensions, for each of the documents in the first plurality of documents; and   a computer system associating in the database each document in the first plurality of documents with its position in each dimension in the first plurality of dimensions.   
     
     
         10 . The method of  claim 1 , wherein identifying toward the user a first set of candidate documents from the first candidate space comprises presenting toward the user an M-dimensional layout, M>1, identifying the first set of candidate documents, the placement of at least some candidate documents in the layout being indicative of the distances among the at least some candidate documents in the first candidate space. 
     
     
         11 . The method of  claim 10 , further comprising identifying toward the user a primary candidate document,
 wherein at least one pair of the documents in the set of candidate documents which are substantially collinear with the primary candidate document in the first candidate space appear in the layout collinearly with the primary candidate document.   
     
     
         12 . The method of  claim 1 , further comprising identifying toward the user a primary candidate document,
 wherein identifying toward the user a first set of candidate documents from the first candidate space comprises presenting toward the user an M-dimensional layout, M>1, identifying the first set of candidate documents,   and wherein the layout is such that collinearity with the primary candidate document of documents in the layout indicates substantial collinearity with the primary candidate document of documents in the embedding space.   
     
     
         13 . The method of  claim 1 , wherein identifying toward the user a first set of candidate documents from the first candidate space comprises presenting toward the user an M-dimensional layout, M>1, identifying the first plurality of candidate documents, the placement of at least some candidate documents in the layout relative to each other being indicative of the distances among the at least some candidate documents in the first candidate space. 
     
     
         14 . A system for user identification of a desired document, comprising:
 a processor; and   a computer readable medium coupled to the processor, the computer readable medium having stored thereon in a non-transitory manner a plurality of software code portions defining logic for:
 a first module to provide in a computer readable medium in a non-transitory manner a database identifying a first plurality of documents in an embedding space, the database identifying a distance between each pair of the documents in the embedding space corresponding to a predetermined measure of dissimilarity between the pair of documents, and 
 a second module to, in dependence upon a user query:
 geometrically constrain the embedding space to develop a first candidate space; and 
 identify toward the user a first set of N1>1 candidate documents from the first candidate space, the first set of candidate having fewer documents than the first candidate space and documents being more discriminative than the average discriminativeness of set size N1 documents in the first candidate space. 
 
   
     
     
         15 . The system of  claim 14 , wherein the set of candidate documents is at least as discriminative as all other sets of size N1 documents in the first candidate space. 
     
     
         16 . The system of  claim 14 , wherein the plurality of software code portions further define logic for:
 a module to geometrically constrain the first candidate space to develop a second candidate space, the second candidate space being a geometrically constrained portion of the first candidate space determined in dependence upon user selection of a subset of the documents in the first set of candidate documents; and   a module to identify toward the user a second set of N2>1 candidate documents from the second candidate space, the second set of candidate documents having fewer documents than the second candidate space and being more discriminative than the average discriminativeness of set size N2 documents in the second candidate space.   
     
     
         17 . The system of  claim 16 , wherein the second candidate space is determined so as to include more documents which are similar to the user selected subset of documents than the number of documents similar to the documents in the first set of candidate documents which are not in the user selected subset. 
     
     
         18 . The system of  claim 14 , wherein the embedding space comprises a multi-dimensional vector space, each of the dimensions in the vector space defining a different basis on which documents can differ from each other,
 and wherein the database identifies a position for each of the documents in the multi-dimensional vector space.   
     
     
         19 . The system of  claim 18 , wherein the plurality of software code portions further define logic for a module to identify toward the user a second set of N2>1 candidate documents from the first candidate space, at least one pair of documents in the second set of candidate documents having different coordinates along a second dimension in the multi-dimensional vector space and being more discriminative than the average discriminativeness of set size 2 documents in the first candidate space, wherein the second dimension differs from all the dimensions of the multi-dimensional vector space along which documents in the first set of candidate documents differ from each other. 
     
     
         20 . The system of  claim 18 , wherein identifying toward the user a first set of candidate documents from the first candidate space comprises presenting toward the user an M-dimensional layout, M>1, identifying the first set of candidate documents, the placement of candidate documents in the layout being indicative of dimensions in the first candidate space along which the candidate documents differ. 
     
     
         21 . The system of  claim 20 , wherein the placement of at least some candidate documents in the layout relative to each is further indicative of the distances among those candidate documents in the first candidate space. 
     
     
         22 . The system of  claim 18 , wherein the module to provide a database comprises a plurality of software code portions defining logic for:
 a module to determine, from the first plurality of documents, a first plurality of dimensions along which at least some of the documents in the first plurality of documents differ;   a module to determine a position in each dimension in the first plurality of dimensions, for each of the documents in the first plurality of documents; and   a module to associate in the database each document in the first plurality of documents with its position in each dimension in the first plurality of dimensions.   
     
     
         23 . The system of  claim 14 , wherein identifying toward the user a first set of candidate documents from the first candidate space comprises presenting toward the user an M-dimensional layout, M>1, identifying the first set of candidate documents, the placement of at least some candidate documents in the layout being indicative of the distances among the at least some candidate documents in the first candidate space. 
     
     
         24 . The system of  claim 23 , wherein the second module further identifies toward the user a primary candidate document,
 wherein at least one pair of the documents in the set of candidate documents which are substantially collinear with the primary candidate document in the first candidate space appear in the layout collinearly with the primary candidate document.   
     
     
         25 . The system of  claim 14 , wherein the second module further identifies toward the user a primary candidate document,
 wherein identifying toward the user a first set of candidate documents from the first candidate space comprises presenting toward the user an M-dimensional layout, M>1, identifying the first set of candidate documents,   and wherein the layout is such that collinearity with the primary candidate document of documents in the layout indicates substantial collinearity with the primary candidate document of documents in the embedding space.   
     
     
         26 . The system of  claim 1 , wherein identifying toward the user a first set of candidate documents from the first candidate space comprises presenting toward the user an M-dimensional layout, M>1, identifying the first plurality of candidate documents, the placement of at least some candidate documents in the layout relative to each other being indicative of the distances among the at least some candidate documents in the first candidate space. 
     
     
         27 . A computer readable medium, for use with a database identifying a first plurality of documents in an embedding space, the database identifying a distance between each pair of the documents in the embedding space corresponding to a predetermined measure of dissimilarity between the pair of documents, the computer readable medium having stored thereon in a non-transitory manner a plurality of software code portions defining logic for, in dependence upon a user query:
 geometrically constraining the embedding space to develop a first candidate space, and   identifying toward the user a first set of N1>1 candidate documents from the first candidate space, the first set of candidate documents having fewer documents than the first candidate space and being more discriminative than the average discriminativeness of set size N1 documents in the first candidate space.   
     
     
         28 . A system for user identification of a desired document, comprising:
 means providing access to a database identifying a first plurality of documents in an embedding space, the database identifying a distance between each pair of the documents in the embedding space corresponding to a predetermined measure of dissimilarity between the pair of documents; and   means for, in response to a user query:
 geometrically constraining the embedding space in dependence upon the query to develop a first candidate space, and 
 identifying toward the user a first set of N1>1 candidate documents from the first candidate space, the first set of candidate documents having fewer documents than the first candidate space and being more discriminative than the average discriminativeness of set size N1 documents in the first candidate space; and 
 means for receiving user input for further refinement of the set of candidate documents.