Information theory based result merging for searching hierarchical entities across heterogeneous data sources

Patent metadata

Field	Value
Publication number	US-10474686-B2
Application number	US-201615012415-A
Country	US
Kind code	B2
Filing date	Feb 1, 2016
Priority date	Oct 7, 2009
Publication date	Nov 12, 2019
Grant date	Nov 12, 2019

Abstract

A method, system, and computer program product are disclosed for merging search results. In one embodiment, the method comprises identifying a query, splitting the query into sub-queries, and calculating information content for each of the sub-queries. This method also comprises executing each of the sub-queries to obtain a plurality of search results, and combining the search results based on the information content calculated for the sub-queries. In an embodiment, the execution of each of the sub-queries includes identifying a multitude of search results for at least one of the sub-queries; and the combining includes grouping said multitude of search results into a plurality of clusters, and computing a relevance score for each of said clusters. In the embodiment the combining further includes merging the clusters based on the relevance scores computed for the clusters as well as the information content calculated for the sub-queries.

First claim

What is claimed is:

1. A computer-implemented method of merging search results from different data sources, the method comprising:
identifying, at a computer processor system, a query from a user;
splitting, at the computer processor system, the query into sub-queries;
for each of the sub-queries, determining, at the computer processor system, a relative importance of said each sub-query to the user relative to the importance of the others of the sub-queries to the user;
sending, by the computer processor system, each of the sub-queries to a respective one search engine on the computer processor system;
executing each of the sub-queries, on the respective one search engine on the computer processor system to which said each sub-query is sent, by using a respective one of the data sources to obtain a respective search result for said each sub-query;
collecting, by the computer processor system, the search results from the search engines;
using, at the computer processor system, the determined relative importance of said each sub-query to assign a weight to the respective search result obtained for said each sub-query; and
combining, at the computer processor system, the search results for the sub-queries based on the weights determined from the relative importance of the sub-queries and assigned to the search results to merge the search results for the sub-queries.

2. The method according to claim 1 , wherein:
the executing includes searching across heterogeneous indices, including structured, unstructured and semi-structured data sources; and
the combining includes merging the search results across said heterogeneous indices.

3. The method according to claim 1 , wherein:
the executing includes searching at an entity level, entities having a hierarchical structure; and
the combining includes merging the search results at the entity level.

4. The method according to claim 1 , wherein:
said sub-queries include a first sub-query and a second sub-query;
the execution of each of the sub-queries includes executing the first sub-query to identify a plurality of first class entities, and executing the second sub-query to identify multitude of second class entities, each of the second class entities being associated, according to a defined criteria, with one of the first class entities; and
the combining includes clustering the second class entities into a plurality of clusters based on the first class entity to which each of the second class entities belongs, and assigning a relevance score to each of the clusters.

5. The method according to claim 1 , wherein the execution of each of the sub-queries includes executing each of the sub-queries using a respective single search engine.

6. The method according to claim 1 , wherein:
the weight assigned to each of the search results is based on a determined probability that the respective search index used to obtain the search results for each sub-query has one or more items relevant to the each sub-query; and
the executing each sub-query on a search engine includes executing each sub-query on a meta search engine of the computer processor system.

7. The method according to claim 1 , wherein the combining the search results for the sub-queries based on the weights determined from the relative importance to the user of the sub-queries includes using the weights to compute data source independent scores for the search results for the sub-queries.

8. A method of merging search results, comprising:
identifying, at a computer processor system, a query from a user;
splitting, at the computer processor system, the query into sub-queries;
for each of the sub-queries, determining, at the computer processor system, a relative importance of said each sub-query to the user relative to the importance of the others of the sub-queries to the user,
sending, by the computer processor system, each of the sub-queried to a respective one search engine on the computer processor system;
executing each of the sub-queries, on the respective one search engine on the computer processor system to which said each sub-query is sent, by using a respective one of the data sources to obtain a respective search result for said each sub-query,
collecting, by the computer processor system, the search results from the search engines;
using, at the computer processor system, the determined relative importance of said each sub-query to the user to assign a weight to the respective search result obtained for said each sub-query; and
combining, at the computer processor system, the search results for the sub-queries based on the weights assigned to the search results to obtain merged search results; and wherein:
the execution of each of the sub-queries includes identifying a multitude of search results for at least one of the sub-queries;
the combining includes grouping said multitude of search results into a plurality of clusters, and computing a relevance score for each of said clusters, wherein each cluster represents a high level entity; and
the relevance score assigned to each of the search results is based on a determined probability that the respective search index used to obtain the search results for each sub-query has one or more items relevant to the each sub-query.

9. The method according to claim 8 , wherein:
the combining includes determining a cluster relevance score for each of the clusters based on the relevance scores of the search results which form the cluster.

10. The method according to claim 8 , wherein the combining further includes merging the clusters based on the cluster relevance scores computed for the clusters and the weights determined for the sub-queries.

11. An article of manufacture comprising:
at least one computer usable device having computer readable program code logic tangibly embodied therein to execute instructions in one or more processing units for merging search results from different data sources, said computer readable program code logic, when executing, performing the following:
identifying, at a computer processor system, a query from a user;
splitting, at the computer processor system, the query into sub-queries;
for each of the sub-queries, determining, at the computer processor system, a relative importance of said each sub-query to the user relative to the importance of the others of the sub-queries to the user,
sending, by the computer processor system, each of the sub-queries to a respective one search engine on the computer processor system;
executing each of the sub-queries, on the respective one search engine on the computer processor system to which said each sub-query is sent, by using a respective one of the data sources to obtain a respective search result for said each sub-query,
collecting, by the computer processor system, the search results from the search engines;
using, at the computer processor system, the determined relative importance of said each sub-query to the user to assign a weight to the respective search result obtained for said each sub-query; and
combining, at the computer processor system, the search results for the sub-queries based on the weights determined from the relative importance to the user of the sub-queries of the sub-queries and assigned to the search results to merge the search results for the sub-queries.

12. The article of manufacture according to claim 11 , wherein:
the execution of each of the sub-queries includes identifying a multitude of entities for at least one of the sub-queries; and
the combining includes grouping said multitude of entities into a plurality of clusters, computing a relevance score for each of said clusters, an

Assignees

• IBM

Inventors

• Deng Yu
• Devarakonda Murthy V
• Hosn Rafah A
• Mahindru Ruchi
• Rajamani Nithya
• Sarkar Soumitra

Classifications

• G06F16/285

  Clustering or classification · CPC title

• G06F16/24535 Primary

  of sub-queries or views · CPC title

• G06F16/9535

  Search customisation based on user profiles and personalisation · CPC title

• G06F16/24578 Primary

  using ranking · CPC title

• G06F16/838

  Presentation of query results · CPC title