Computer-implemented method of and system for searching an inverted index having a plurality of posting lists

• US 10,430,448 B2
• Filed: 07/08/2014
• Issued: 10/01/2019
• Est. Priority Date: 07/08/2013
• Status: Active Grant

• Current Assignee: YE Hub Armenia LLC
• Original Assignee: Yandex Europe AG (Yandex N.V.)
• Inventors: Gorodilov, Alexey Anatolievich
• Primary Examiner(s): Thomas, Ashish
• Assistant Examiner(s): Ohba, Mellissa M.
• Application Number:
  US14/903,697
• Publication Number:
  US 20160162574A1
• Time in Patent Office: 1,911 Days
• Field of Search: None
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

Method of searching an inverted index having a plurality of posting lists, comprising: receiving a search query to be searched including search terms; effecting a search of posting lists to yield search results, the posting lists associated with the search terms and including a plurality of a first type of postings being a reference to a data item actually containing the search term with which that posting list is associated, the search results including result items missing one of the search terms; sending the first search results; receiving an indication of a user-selected result item, the user-selected result item being the result item missing one of the search terms; effecting insertion, into the posting list associated with the missing one of the search terms in the user-selected result item, of a second-type of posting being a reference to the user-selected result item missing that search term.

Claims

1. A computer-implemented method of searching an inverted index having a plurality of posting lists, the method comprising:

receiving, from a first client device by at least one server, a first search query to be searched, the first search query including a first plurality of search terms, the first plurality of search terms comprising a first term;

effecting, by the at least one server, a first search of a first plurality of posting lists to yield first search results, each of the first plurality of posting lists associated with a one of the first plurality of search terms, the first plurality of posting lists comprising a first posting list associated with the first term,

each of the first plurality of posting lists including a plurality of a first type of postings, the first type of postings being a reference to a data item actually containing the search term with which that posting list is associated,

the first search results including a first plurality of result items, the first search results including

a result item missing the first term;

sending, by the at least one server to the first client device, at least a portion of the first search results including

the result item missing the first term;

receiving, from the first client device by the at least one server, an indication of a first user-selected result item,

the first user-selected result item being the result item missing the first term, and

the first user-selected result item having been selected by the user from the first search results;

effecting, by the at least one server, insertion of a reference to the first user-selected result item into the first posting list that is associated with the first term even though the first user-selected result item misses the first term, the reference to the first user-selected result item being a second-type of posting; and

storing, by at least one server, the first posting list with the inserted second-type of posting.

2. The computer-implemented method of claim 1, further comprising:

receiving, from a second client device by the at least one server, a second search query to be searched, the second search query containing a second plurality of search terms, one of the second plurality of search terms being the first term;

effecting, by the at least one server, a second search of a second plurality of posting lists to yield second search results, each of the second plurality of posting lists associated with a one of the second plurality of search terms, one of the second plurality of posting lists being the posting list associated with the first term and including the second-type of posting, and the second search including a consideration of the second-type of posting.

3. The computer-implemented method of claim 2, wherein, as a result of the consideration of the second-type of posting, the second search results include the first user-selected result item of the first search results.

4. The computer-implemented method of claim 2, wherein effecting the second search includes assigning an item weight to each data item being considered during the second search;

and each data item is included in the second search results only if its item weight is not less than a threshold item weight.

5. The computer-implemented method of claim 4, wherein each one of the second plurality of search terms is assigned a search term weight;

and wherein calculation of the item weight of each data item being considered includes a sum of the search term weights of those ones of the second plurality of search terms having one of the first-type of posting and the second-type of posting in respect of that data item in the one of the second plurality of posting lists associated with that one of the second plurality of search terms.

6. The computer-implemented method of claim 4, wherein calculation of the item weight for each data item being considered includes a sum of a plurality of addends, the addends in respect of the first-type of postings being the search term weights of those ones of the second plurality of search terms having one of the first type of posting in respect of that data item in the one of the second plurality of posting lists associated with that one of the second plurality of search terms multiplied by a first-type of reduction factor in respect of that addend, the addends in respect of the second-type of posting being the search term weights of those ones of the second plurality of search terms having one of the second type of posting in respect of that data item in the one of the second plurality of posting lists associated with that one of the second plurality of search terms.

7. The computer-implemented method of claim 4, wherein calculation of the item weight for each data item being considered includes a sum of a plurality of addends, the addends in respect of the first-type of postings being the search term weights of those ones of the second plurality of search terms having one of the first type of posting in respect of that data item in the one of the second plurality of posting lists associated with that one of the second plurality of search terms, the addends in respect of the second-type of posting being the search term weights of those ones of the second plurality of search terms having one of the second type of posting in respect of that data item in the one of the second plurality of posting lists associated with that one of the second plurality of search terms multiplied by a second-type of reduction factor in respect of that addend.

8. The computer-implemented method of claim 4, wherein calculation of the item weight for each data item being considered includes a sum of a plurality of addends, the addends in respect of the first-type of postings being the search term weights of those ones of the second plurality of search terms having one of the first type of posting in respect of that data item in the one of the second plurality of posting lists associated with that one of the second plurality of search terms multiplied by a first-type of reduction factor in respect of that addend, the addends in respect of the second-type of posting being the search term weights of those ones of the second plurality of search terms having one of the second type of posting in respect of that data item in the one of the second plurality of posting lists associated with that one of the second plurality of search terms multiplied by a second-type of reduction factor in respect of that addend.

9. The computer-implemented method of claim 7, wherein the second-type of reduction factor in respect of that addend is a function of a number of times that data item had been clicked-through in search results of previous search queries including the search term with which that one of the second plurality of posting lists is associated.

10. The computer-implemented method of claim 6, wherein the first-type of reduction factor in respect of that addend is a function of a number of times that data item contains the search term with which that one of the second plurality of posting lists is associated.

11. The computer-implemented method of claim 2, wherein a data item is included in the second search results only if a ratio of its second-type postings to its first-type postings is not greater than a threshold ratio.

12. The computer-implemented method of claim 2, further comprising:

sending, by the at least one server to the second client device, at least a portion of the second search results including the first user-selected result item;

receiving, from the second client device by the at least one server, an indication of a second user-selected result item, the second user-selected result item being the first user-selected result item;

effecting, by the at least one server, modification in the posting list associated with the missing one of the second plurality of search terms of the second-type of posting to the first user-selected result item, to take into account that the first user-selected result item is also the second user-selected result item.

13. A system comprising at least one server, the at least one server having at least one computer processor, and a non-transient computer information storage medium storing program instructions that when executed by the at least one computer processor effect:

receiving, from a first client device by at least one server, a first search query to be searched, the first search query including a first plurality of search terms, the first plurality of search terms comprising a first term;

effecting, by the at least one server, a first search of a first plurality of posting lists to yield first search results, each of the first plurality of posting lists associated with a one of the first plurality of search terms, the first plurality of posting lists comprising a first posting list associated with the first term,

each of the first plurality of posting lists including a plurality of a first type of postings, the first type of postings being a reference to a data item actually containing the search term with which that posting list is associated,

the first search results including a first plurality of result items, the first search results including

a result item missing the first term;

sending, by the at least one server to the first client device, at least a portion of the first search results including

the result item missing the first term;

receiving, from the first client device by the at least one server, an indication of a first user-selected result item,

the first user-selected result item being the result item missing the first term, and

the first user-selected result item having been selected by the user from the first search results;

effecting, by the at least one server, insertion of a reference to the first user-selected result item into the first posting list that is associated with the first term even though the first user-selected result item misses the first term, the reference to the first user-selected result item being a second-type of posting; and

storing, by at least one server, the first posting list with the inserted second-type of posting.

14. The system of claim 13, wherein the non-transient computer information storage medium further stores program instructions that when executed by the at least one computer processor effect:

receiving, from a second client device by the at least one server, a second search query to be searched, the second search query containing a second plurality of search terms, one of the second plurality of search terms being the first term; and

effecting, by the at least one server, a second search of a second plurality of posting lists to yield second search results, each of the second plurality of posting lists associated with a one of the second plurality of search terms, one of the second plurality of posting lists being the posting list associated with the first term and including the second-type of posting, and the second search including a consideration of the second-type of posting.

15. The system of claim 14, wherein, as a result of the consideration of the second-type of posting, the second search results include the first user-selected result item of the first search results.

16. The system of claim 14, wherein effecting the second search includes assigning an item weight to each data item being considered during the second search;

and each data item is included in the second search results only if its item weight is not less than a threshold item weight.

17. The system of claim 16, wherein each one of the second plurality of search terms is assigned a search term weight;

and wherein calculation of the item weight of each data item being considered includes a sum of the search term weights of those ones of the second plurality of search terms having one of the first-type of posting and the second-type of posting in respect of that data item in the one of the second plurality of posting lists associated with that one of the second plurality of search terms.

18. The system of claim 16, wherein calculation of the item weight for each data item being considered includes a sum of a plurality of addends, the addends in respect of the first-type of postings being the search term weights of those ones of the second plurality of search terms having one of the first type of posting in respect of that data item in the one of the second plurality of posting lists associated with that one of the second plurality of search terms multiplied by a first-type of reduction factor in respect of that addend, the addends in respect of the second-type of posting being the search term weights of those ones of the second plurality of search terms having one of the second type of posting in respect of that data item in the one of the second plurality of posting lists associated with that one of the second plurality of search terms.

19. The system of claim 16, wherein calculation of the item weight for each data item being considered includes a sum of a plurality of addends, the addends in respect of the first-type of postings being the search term weights of those ones of the second plurality of search terms having one of the first type of posting in respect of that data item in the one of the second plurality of posting lists associated with that one of the second plurality of search terms, the addends in respect of the second-type of posting being the search term weights of those ones of the second plurality of search terms having one of the second type of posting in respect of that data item in the one of the second plurality of posting lists associated with that one of the second plurality of search terms multiplied by a second-type of reduction factor in respect of that addend.

20. The system of claim 16, wherein calculation of the item weight for each data item being considered includes a sum of a plurality of addends, the addends in respect of the first-type of postings being the search term weights of those ones of the second plurality of search terms having one of the first type of posting in respect of that data item in the one of the second plurality of posting lists associated with that one of the second plurality of search terms multiplied by a first-type of reduction factor in respect of that addend, the addends in respect of the second-type of posting being the search term weights of those ones of the second plurality of search terms having one of the second type of posting in respect of that data item in the one of the second plurality of posting lists associated with that one of the second plurality of search terms multiplied by a second-type of reduction factor in respect of that addend.

21. The system of claim 19, wherein the second-type of reduction factor in respect of that addend is a function of a number of times that data item had been clicked-through in search results of previous search queries including the search term with which that one of the second plurality of posting lists is associated.

22. The system of claim 18, wherein the first-type of reduction factor in respect of that addend is a function of a number of times that data item contains the search term with which that one of the second plurality of posting lists is associated.

23. The system of claim 14, wherein a data item is included in the second search results only if a ratio of its second-type postings to its first-type postings is not greater than a threshold ratio.

24. The system of claim 14, wherein the non-transient computer information storage medium further stores program instructions that when executed by the at least one computer processor effect:

sending, by the at least one server to the second client device, at least a portion of the second search results including the first user-selected result item;

receiving, from the second client device by the at least one server, an indication of a second user-selected result item, the second user-selected result item being the first user-selected result item;

effecting, by the at least one server, modification in the posting list associated with the missing one of the second plurality of search terms of the second-type of posting to the first user-selected result item, to take into account that the first user-selected result item is also the second user-selected result item.