Information embedding based on user relevance feedback for object retrieval

• US 6,347,313 B1
• Filed: 03/01/1999
• Issued: 02/12/2002
• Est. Priority Date: 03/01/1999
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Zhang, HongJiang, Lee, Catherine S., Ma, Wei-Ying
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US09/260,215
• Time in Patent Office: 1,079 Days
• Field of Search: 707/2, 707/3, 707/4, 707/5, 707/6
• US Class Current: 707/711
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 18/2178 based on feedback of a supervisor
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06F 18/2414 Smoothing the distance, e.g. radial basis function networks [RBFN]
• CPC Class Codes: G06F 18/40 Software arrangements specially adapted for pattern recognition, e.g. user interfaces or toolboxes therefor
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method and system for indexing and retrieving database objects, such as images, include a database manager which initializes database objects based on vectors for values of quantified features associated with the database objects. Similar database objects are grouped into common clusters that are based on system-perceived relationships among the objects. For each search session, a vector for a search query is calculated and database objects from the closest cluster within feature space are selected for presentation at a user device. The user indicates which of the selected objects are relevant to the search session and which of the objects are irrelevant. If one of the clusters includes both relevant and irrelevant objects, the cluster is split into two clusters, so that one of the resulting clusters includes the relevant objects and the other cluster includes irrelevant objects. The correlation matrix is updated to indicate that the resulting clusters have a weak correlation. If two of the clusters include database objects which were indicated to be relevant to the search session, the correlation matrix is updated to indicate that the two clusters have a strong correlation. To avoid an excessive proliferation of database clusters, mergers are performed on clusters which are closely located within the feature space and share a strong correlation within the correlation matrix. Following continued use, the groupings of objects into clusters and the cluster-to-cluster correlations will reflect user-perceived relationships.

Claims

1. A method of managing objects of a database comprising steps of:

presenting first database objects in response to a search query of a first search session;

enabling a user to designate a first subset of said first database objects as being relevant to said first search session and to designate a second subset of said first database objects as being irrelevant to said first search session;

at least partially based upon designations of said first and second subsets, organizing said objects of said database into multi-object groups and defining correlations among said groups, organization of a plurality of said objects into a specific said group being indicative of content similarities among said objects, said correlations being indicative of user-perceived similarities among said groups; and

storing said organization of said groups and said defined correlations among said groups for access during a second search session following completion of said first search session.

2. The method of claim 1 further comprising a step of indexing said objects of said database prior to said first search session, including forming a preliminary organization of said objects into initial groups, wherein said step of organizing said objects reconfigures said preliminary organization based on said designations of first and second subsets.

3. The method of claim 2 further comprising a step of presenting a second iteration of second database objects during said first search session, said second database objects including said first subset of first database objects that were designated as being relevant, said second database objects further including objects from a group having a predefined correlation with said first subset.

4. The method of claim 1 wherein said step of presenting said first database objects includes randomly selecting objects from a plurality of groups.

5. The method of claim 2 wherein said step of indexing includes quantifying a plurality of attributes for each object and determining an attribute vector for said each object based on said quantifications, said preliminary organization being based on said attribute vectors for said objects.

6. The method of claim 5 further comprising a step of reconfiguring said correlations and said groups during each search session subsequent to said first search session, said reconfiguring being based on user designations of relevant and irrelevant objects during said each search session, said reconfiguring including forming a correlation matrix that links said groups and quantifies similarity correlations among said groups.

7. The method of claim 6 wherein said step of reconfiguring said correlations and said objects includes a step of formulating membership functions for an object such that said object has a different membership function for said each group, each membership function describing a membership of said object within one of said groups.

8. The method of claim 7 wherein said reconfiguring step further includes formulating membership functions for a query object included in said search query, each query object membership function describing a degree of membership of said query object within one of said groups.

9. The method of claim 7 wherein said step of reconfiguring said correlations includes integrating attribute information associated with said object into said each membership function to describe degrees of membership of said object within each of said groups.

10. The method of claim 6 wherein said step of reconfiguring includes dividing a first group into two separate groups in response to designations that both relevant objects and irrelevant objects reside in said first group.

11. The method of claim 10 wherein said step of reconfiguring further includes merging at least two of said groups into a merged group at least in part in response to determining that a correlation value that is representative of similarities between said groups exceeds a predetermined threshold.

12. The method of claim 11 wherein said step of reconfiguring further includes assigning correlation weights based upon designations of relevant and irrelevant objects.

13. A system for organizing and retrieving database objects comprising:

a database of objects, each object having an assigned value for each of a plurality of object features, said objects being organized into a plurality of groups, said groups having group-to-group correlations partially based on similarities among said assigned values and partially based on group-to-group correlation values that are representative of perceived similarities among said groups;

an object selection subsystem responsive to receiving search queries of search sessions to select objects for display based on said groups and said correlations;

a user device for enabling a user to designate a first subset of selected objects as being relevant to a search session and a second subset of said selected objects as being irrelevant to said search session; and

a configuration module responsive to designations of said first and second subsets via said user device to manage said objects with respect to at least one of assigning said objects into groups and assigning said correlations, said assigned groups and said assigned correlations thereby being at least partially based on said designations of said first and second subsets.

14. The system of claim 13 wherein said configuration module is responsive to designations of relevant and irrelevant objects in a single group to divide said single group into first and second groups such that said first group includes first objects designated to be relevant and said second group includes second objects designated to be irrelevant.

15. The system of claim 14 wherein said configuration module is responsive to said division of said single group to assign a low correlation of similarity to an association between said first and said second groups.

16. The system of claim 13 wherein said configuration module is configured to assign a high correlation of similarity to an association between a first object group and a third object group which both include database objects that have been determined to be relevant to a first search query object.

17. The system of claim 16 wherein said object selection subsystem is configured to select objects from said first group and said third group during an iteration of an object retrieval session which includes a second query object, said selection of said objects from said first and said third groups being based at least partially upon said high correlation of similarity between said first and said third object groups.

18. The system of claim 13 wherein said object selection subsystem is configured to include random objects among said objects selected for display.

19. A method of managing objects within a database utilizing user feedback comprising steps of:

configuring said objects into a network of clusters based on values of quantified features of said objects and based on correlations among said clusters;

detecting a first search query of a search session;

selecting a first set of objects determined to be responsive to said first search query, including basing said selecting upon said values and said correlations, said first set including objects from each of first and second clusters;

embedding user feedback into a correlation matrix that defines said correlations among said clusters in said network, including;

(a) assigning a high correlation to linking said first and said second clusters if objects within each of said first and second clusters are designated by a user to be relevant to said search session; and

(b) splitting said first cluster into a third and fourth cluster if said first cluster is designated by said user to include both relevant and irrelevant objects with respect to said search session; and

storing said correlation matrix after embedding said user feedback for use in subsequent search sessions.

20. The method of claim 19 further comprising a step of merging said first cluster with a fifth cluster if it is determined that (1) said values of quantified features for objects in said first cluster are within a similarity threshold with respect to said values of quantified features for objects in said fifth cluster and (2) said first and said fifth clusters are assigned a correlation above a threshold correlation value.

21. The method of claim 19 wherein said step of selecting said first set of database objects includes randomly selecting a plurality of objects to diminish the probability of selecting only irrelevant objects during consecutive iterations of said search session.

22. The method of claim 19 further comprising the steps of:

selecting a second set of objects in response to receiving a second query, said selecting being based at least in part on said stored correlation matrix; and

updating said correlation matrix based on user feedback which includes user-generated determinations of relevance for a first portion of said second set of objects and user-generated determinations of irrelevance for a second portion of said second set of objects.

23. The method of claim 19 further comprising the step of decreasing a correlation assigned to said first and said second clusters if objects from one of said first and said second cluster are designated as being relevant to said search and objects from the other of said first and said second cluster are designated as being irrelevant to said search.