Multifaceted search

• US 9,535,979 B2
• Filed: 06/21/2013
• Issued: 01/03/2017
• Est. Priority Date: 06/21/2013
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ambasta, Rohan A., Ganesh, Bharath, Gokhale, Parag S., Jain, Chandrashekhar
• Primary Examiner(s): Rostami, Mohammad S
• Application Number:
  US13/923,406
• Publication Number:
  US 20140379728A1
• Time in Patent Office: 1,292 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A query is received that includes two or more facets of a multidimensional inverted index for a collection of documents. Each document is associated with at least one facet. Generation of the multidimensional inverted index includes creating one or more entries. Each entry includes a combination of two or more facets and a posting list of indications for the documents associated with respective facets of each entry. Each indication identifies a document. Generation of the index also includes determining documents associated with respective facets of the combination of each entry. The multidimensional inverted index is searched for an entry having the combination of two or more facets included in the query and a search result is returned. An indication for a document may be included in a posting list if it is determined that the document is associated with each facet of the combination of facets of the entry.

Claims

1. A computer-implemented method of searching, comprising:

receiving a query including two or more facets of a single multidimensional inverted index for a collection of documents, each document being associated with at least one facet, wherein the query further includes one or more non-index terms;

wherein the single multidimensional inverted index is generated by;

creating one or more entries, each entry including a combination of two or more facets, wherein each of the two or more facets is not a sub-category of any other facet of the two or more facets,

determining documents associated with respective facets of the combination of two or more facets of each entry, and

creating a posting list of indications for the documents associated with respective facets of each entry, each indication identifying a document;

determining a format of the single multidimensional inverted index, wherein the format includes an order of the two or more facets in the single multidimensional inverted index;

normalizing the query to conform to the format of the single multidimensional inverted index, wherein the normalizing includes reordering the two or more facets in the query, the reordered two or more facets having the same order as the two or more facets in the single multidimensional inverted index;

searching the single multidimensional inverted index for an entry having the combination of two or more facets included in the query;

identifying, based on the searching the single multidimensional inverted index, a set of documents having the combination of two or more facets included in the query;

searching the set of documents for the one or more non-index terms;

generating a search result, wherein the search result includes only documents of the set of documents that include the one or more non-index terms; and

returning the search result.

2. The method of claim 1, wherein the determining of documents associated with respective facets of the combination of two or more facets of each entry includes determining that a first document is associated with each facet of the two or more facets.

3. The method of claim 1, wherein the determining of documents associated with respective facets of the combination of two or more facets of each entry includes determining that a first document is associated with at least one facet of the two or more facets.

4. The method of claim 1, wherein the determining of documents associated with respective facets of the combination of two or more facets of each entry includes determining that a first document is associated with only one facet of the two or more facets.

5. The method of claim 1, further comprising selecting the single multidimensional inverted index for the collection of documents from first and second multidimensional inverted indices for the collection of documents based on the two or more facets included in the query.

6. The method of claim 1, wherein at least one of the one of more entries of the single multidimensional inverted index is generated prior to receiving the query.

13. The method of claim 1, wherein the two or more facets of the query are selected by a user checking boxes in a user interface.

14. The method of claim 1, wherein the single multidimensional array includes a field having a number of documents for each facet.

15. The method of claim 1, wherein the single multidimensional array includes a field having a frequency of the two or more facets in the document.

16. The method of claim 1, the method further comprising:

adding a new document to the collection of documents; and

generating a document record for the new document, the document record including an identifier and values for each facet associated with the new document.

17. The method of claim 1, wherein the single multidimensional inverted index further includes:

a first field for each entry, the first field listing quantitative aggregations for each entry; and

a second field for each entry, the second field listing qualitative aggregations for each entry.

7. A computer program product for searching, the computer program product comprising a non-transitory computer readable storage medium having program code embodied therewith, the program code comprising computer readable program code configured to:

receive a query including two or more facets of a single multidimensional inverted index for a collection of documents, each document being associated with at least one facet, wherein the query further includes one or more non-index terms;

wherein the single multidimensional inverted index is generated by;

creating one or more entries, each entry including a combination of two or more facets, wherein each of the two or more facets is not a sub-category of any other facet of the two or more facets,

determining documents associated with respective facets of the combination of two or more facets of each entry, and

creating a posting list of indications for the documents associated with respective facets of each entry, each indication identifying a document;

determine a format of the single multidimensional inverted index, wherein the format includes an order of the two or more facets in the single multidimensional inverted index;

normalize the query to conform to the format of the single multidimensional inverted index by reordering the two or more facets in the query, the reordered two or more facets having the same order as the two or more facets in the single multidimensional inverted index;

search the single multidimensional inverted index for an entry having the combination of two or more facets included in the query;

identify, based on the searching the single multidimensional inverted index, a set of documents having the combination of the first and second facets included in the query;

search the set of documents for the one or more non-index terms;

generate a search result, wherein the search result includes only documents of the set of documents that include the one or more non-index terms; and

return the search result.

8. The computer program product of claim 7, wherein the determining of documents associated with respective facets of the combination of two or more facets of each entry includes determining that a first document is associated with each facet of the two or more facets.

9. The computer program product of claim 7, wherein the determining of documents associated with respective facets of the combination of two or more facets of each entry includes determining that a first document is associated with at least one facet of the two or more facets.

10. The computer program product of claim 7, wherein the determining of documents associated with respective facets of the combination of two or more facets of each entry includes determining that a first document is associated with only one facet of the two or more facets.

11. The computer program product of claim 7, further comprising selecting the single multidimensional inverted index for the collection of documents from first and second multidimensional inverted indices for the collection of documents based on the two or more facets included in the query.

12. The computer program product of claim 7, wherein at least one of the one of more entries of the single multidimensional inverted index is generated prior to receiving the query.