Method for using dual indices to support query expansion, relevance/non-relevance models, blind/relevance feedback and an intelligent search interface

• US 8,775,410 B2
• Filed: 12/20/2013
• Issued: 07/08/2014
• Est. Priority Date: 02/09/2009
• Status: Active Grant

• Current Assignee: Hong Kong Polytechnic University
• Original Assignee: Hong Kong Polytechnic University
• Inventors: Luk, Robert Wing Pong
• Primary Examiner(s): VU, BAI DUC
• Application Number:
  US14/137,150
• Publication Number:
  US 20140114944A1
• Time in Patent Office: 200 Days
• Field of Search: None
• US Class Current: 707/715
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence

Abstract

A method for using dual indices to support query expansion, relevance/non-relevance models, blind/relevance feedback and an intelligent search interface, the method comprising: accessing an inverted index to obtain an initial retrieval of results in response to a query, and to generate a rank list of the results, the results referring to information units (IUs) where the query occurs; and determining a number of “N” IUs in the results that are assumed to be relevant by accessing a forward index; wherein the forward index and inverted index have pointers to locations in the IUs where terms of the query occur, and the forward index retrieves a term frequency vector of the IU or a set of contexts of the IU.

Claims

1. A method for using dual indices to support query expansion, the method comprising:

accessing an inverted index to obtain an initial retrieval of results in response to a query using a computing device;

generating a rank list of the results using the computing device, where the results referring to information units (IUs) where terms of the query occur;

determining a number of “

N”

IUs in the results that are regarded as relevant by accessing a forward index using the computing device;

computing query expansion weights for a portion of the relevant determined number of “

N”

IUs using the computing device;

computing query expansion terms based on the initial retrieval of results and the computed query expansion weights using the computing device;

formulating a new search query comprising the computed query expansion terms using the computing device; and

re-ranking the rank list of the results based on the new search query using the computing device.

2. The method of claim 1, further comprising:

determining at least one non-relevant IU in the results that are regarded by the computing device as not relevant by accessing the forward index using the computing device;

wherein the forward index and inverted index have pointers to locations in the IUs where terms of the query occur more than once, and a forward index and inverted index pointer storage stores the locations in the IUs where the query term occurs only once in the IUs, and the forward index retrieves a term frequency vector of the IU or a set of contexts of the IU; and

wherein computing query expansion weights for the top “

N”

retrieved IUs utilizes the forward index to compute query expansion by;

computing at least one relevance query expansion term weight based on the top “

N”

retrieved IUs in the results and the forward index using the computing device;

computing at least one non-relevance query expansion term weight based on the at least one non-relevant IU in the results and the forward index using the computing device; and

selecting query expansion terms based on the results, the at least one relevance query expansion term weight, and the at least one non-relevance query expansion term weight using the computing device.

3. The method of claim 2, wherein re-ranking the rank list of the results is based on the original query, the forward index, a portion of the relevant number of “

N”

IUs in the results, and the at least one non-relevant IU in the results.

4. The method according to claim 1, wherein “

N”

is from 1 to 10000.

5. The method according to claim 1, wherein “

N”

is query-dependent, and the forward index is accessed one-by-one to determine the number “

N.”

6. The method of claim 5, further comprising:

storing the frequencies of the query terms in the forward index using the computing device; and

storing the pointers to word locations in the forward index using the computing device.

7. The method according to claim 1, wherein the forward index is searched by an information unit identifier (IID) of the IU, and is searched by terms of the query, and the frequencies of the query terms are collected.

8. The method according to claim 1, wherein the forward index is a set of frequency vectors for the IUs.

9. The method according to claim 1, wherein the inverted index and forward index are compressed.

10. The method according to claim 1, wherein the forward index is any one from the group consisting of:

variable bit-block compression signature, superimposed coding signature, vocabulary index, trie, B-tree, heap B-tree, red-black tree, suffix arrays, suffix tree, PATRICIA trie, string B-tree, and DAWGs.

11. The method of claim 1, wherein generating the ranked list of results is based on the forward index.

12. A system for supporting query expansion using dual indices, the system comprising:

a processor; and

memory configured to store a search processing application;

wherein the search processing application configures the processor to;

access an inverted index to obtain an initial retrieval of results in response to a query;

generate a rank list of the results, where the results referring to information units (IUs) where terms of the query occur;

determine a number of “

N”

IUs in the results that are regarded as relevant by accessing a forward index;

compute query expansion weights for a portion of the relevant determined number of “

N”

IUs;

compute query expansion terms based on the initial retrieval of results and the computed query expansion weights;

formulate a new search query comprising the computed query expansion terms; and

re-rank the rank list of the results based on the new search query.

13. The system of claim 12, wherein:

the search processing application further configures the processor to determine at least one non-relevant IU in the results that are regarded by the computing device by accessing the forward index;

the forward index and inverted index have pointers to locations in the IUs where terms of the query occur more than once, and a forward index and inverted index pointer storage stores the locations in the IUs where the query term occurs only once in the IUs, and the forward index retrieves a term frequency vector of the IU or a set of contexts of the IU; and

computing query expansion weights for the top “

N”

retrieved IUs utilizes the forward index to compute query expansion terms by;

computing at least one relevance query expansion term weight using the top “

N”

retrieved IUs in the results and the forward index;

computing at least one non-relevance query expansion term weight using the at least one non-relevant IU in the results and the forward index; and

selecting query expansion terms using the results, the at least one relevance query expansion term weight, and the at least one non-relevance query expansion term weight.

14. The system of claim 13, wherein re-ranking the rank list of the results is based on the original query, the forward index, a portion of the relevant number of “

N”

IUs in the results, and the at least one non-relevant IU in the results.

15. The system of claim 12, further comprising solid state disk drives to store the inverted index and forward index.

16. The system of claim 12, wherein the search processing application further configures the processor to generate the ranked list of the results based on the forward index.

17. The system of claim 12, wherein “

N”

is query-dependent, and the forward index is accessed one-by-one to determine the number “

N.”

18. The system of claim 17, wherein the search processing application further configures the processor to:

store the frequencies of the query terms in the forward index; and

store the pointers to word locations in the forward index.

19. The system of claim 12, wherein the forward index is searched by an information unit identifier (IID) of the IU, and is searched by terms of the query, and the frequencies of the query terms are collected.

20. The system of claim 12, wherein the forward index is a set of frequency vectors for the IUs.

21. The system of claim 12, wherein the inverted index and forward index are compressed.

22. The system of claim 12, wherein the forward index is any one from the group consisting of:

variable bit-block compression signature, superimposed coding signature, vocabulary index, trie, B-tree, heap B-tree, red-black tree, suffix arrays, suffix tree, PATRICIA trie, string B-tree, and DAWGs.

23. The system of claim 12, wherein:

the system is configured to operate as a search engine; and

wherein the search processing application configures the processor to obtain a query comprising one or more search terms.