Browse Prior Art Database

Method for Providing Evaluation Metrics for Measuring Diversification in Search Assist Suggestions

IP.com Disclosure Number: IPCOM000240684D
Publication Date: 2015-Feb-18
Document File: 3 page(s) / 92K

Publishing Venue

The IP.com Prior Art Database

Related People

Amit Goyal: INVENTOR [+3]

Abstract

A method is disclosed for providing evaluation metrics for measuring diversification in search assist suggestions. The method proposes a novel evaluation metrics that improves auto-completion of queries by providing both relevant and diversified suggestions for better user experience.

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 53% of the total text.

Method for Providing Evaluation Metrics for Measuring Diversification in Search Assist Suggestions

Abstract

A method is disclosed for providing evaluation metrics for measuring diversification in search assist suggestions.  The method proposes a novel evaluation metrics that improves auto-completion of queries by providing both relevant and diversified suggestions for better user experience. 

Description

For any user-typed prefix in a search box, search assist needs to provide both relevant and diversified suggestions for reducing user efforts in formulating queries.  There is a need for metrics that are simple, easy to compute, and fast that can provide an automatic method to evaluate search assistance algorithms. 

Disclosed is a method for providing evaluation metrics for measuring diversification in search assist suggestions.  The method proposes a novel evaluation metrics for query auto-completion which measures and provides both relevant and diversification suggestions thereby easing user search experience.  The evaluation metrics works by evaluating one or more search assistance algorithms with respect to diversification and duplicity of search. 

In accordance with the method, the evaluation metrics are implemented in a sequence of steps.

Given a query qa=<w1 w2 ... wi> and qb=<w1 w2 ... wj>, Normalized Edit Distance (NED) can be measured, wherein

NED = editdist(qa,qb)/max(len(qa),len(qb)); where (a) refers to NED € [0,1] and (b) refers to a Higher value means more diverse. 

NED computes both at character and word level (or token level by stemming and removing stop words).  Length (len) is number of characters and terms in a query at character and word level respectively.

Average Normalized Edit Distance:

Given a query suggestion set Q=<q1, q2, ... ,qn>

There are n*(n-1)/2 all pairs and there are (n-1) Sequential pairs.

AVG_NED is the average normalized edit distance over all query pairs.  Hence, AVG_NED € [0,1]

AVG_NED can be computed over top K suggestions for given a prefix.  However, it is advantageous to have top K suggestions diverse due to position bias (that is more clicks on higher position suggestions).

For Sequential AVG_NED, suggestions are sorted lexicographically before computing it.  Further, AVG_NED is linear in number of suggestions compared to “All pairs” that is quadratic in number of suggestions....