Browse Prior Art Database

Method and System for Searching a Collection of Objects based on Similarity and Ranking

IP.com Disclosure Number: IPCOM000198735D
Publication Date: 2010-Aug-13
Document File: 6 page(s) / 835K

Publishing Venue

The IP.com Prior Art Database

Related People

Alexander Smola: INVENTOR [+3]

Abstract

A method and system for searching a collection of objects based on similarity and ranking is disclosed. The method enables the image returned results obtained from a keyword-based search engine to be presented systematically to the user based on the content of the returned images. The highly query relevant image is placed at a specific position for example, a top-left corner.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 51% of the total text.

Method and System for Searching a Collection of Objects based on Similarity and Ranking

Abstract

A method and system for searching a collection of objects based on similarity and ranking is disclosed.  The method enables the image returned results obtained from a keyword-based search engine to be presented systematically to the user based on the content of the returned images.  The highly query relevant image is placed at a specific position for example, a top-left corner.

Description

Disclosed is a method and system for searching a collection of objects based on similarity and ranking.  The method disclosed herein bridges the gap between keyword- based and content-based search by returning keyword-based query relevant objects in a set of pages.  In the set of pages, each page contains several objects with similar content objects are placed at proximal locations.  In this method, image returned results obtained from a keyword-based search engine are presented systematically to the user based on the content of the returned images.  The highly query relevant image is placed at a specific position for example, a top-left corner.

The method utilizes a kernel sorting algorithm to perform matching between pairs of objects from different domains that requires a similarity measure within each of the two domains.  For example, consider two sets of objects namely,   and .  Here  denotes the size of each set.  To find correspondences between the two sets of objects, the algorithm finds a permutation  that maps  by maximizing the dependence between the two sets of objects under a Hilbert Schmidt Independence Criterion.  A dependency measure technique is used by the algorithm to maximize over the permutation group to identify good matches.  Hence, the resulting optimization problem of kernel sorting algorithm is given as:

In the above equation,  are the kernel metrics for the set  and the set , respectively, i.e.,  and .  Kernel  measures the pair wise similarity between objects in set  and the likewise kernel  for the set .  Thereafter, centering matrix  with  centers the observations of set  and set  in feature space.  The centered versions of  and  are then denoted as  and , respectively.

The kernel algorithm in the equation 1 may be NP hard.  Therefore, first order lower bound of equation (1) over a relaxed constraint set  is successively maximized instead.  Now referring to Algorithm 1 (shown below) for a summarization of the kernel sorting algorithm with ranking constraint.  The constraint set  admits total modularity.

Now assuming that a specific ranking preference on a subset of objects,  for ) .  To solve this, the method adds additional constraints associated with the ranking to the original optimization problem in equation (1) as follows:

The above problem can be solved by succession of linear programming instead of linear assignment.  However, instead of solving equation (2), the method focuses on the fo...