Method and an apparatus for fast merging inverted chains

• US 10,452,692 B2
• Filed: 09/20/2016
• Issued: 10/22/2019
• Est. Priority Date: 09/22/2015
• Status: Active Grant

• Current Assignee: Alibaba Group Holding Ltd.
• Original Assignee: Guangzhou SHENMA Information Technology Co. Ltd.
• Inventors: Wang, Gang, Wan, Mingcheng, Zeng, Honglei
• Primary Examiner(s): Alam, Shahid A
• Application Number:
  US15/270,725
• Publication Number:
  US 20170083610A1
• Time in Patent Office: 1,127 Days
• Field of Search: 707742
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/325 Hash tables
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence

Abstract

In accordance with various embodiments of the disclosed subject matter, a method for fast merging inverted chains, and a related apparatus are provided. In some embodiments, the method comprises: pre-setting an inverted index including a plurality of inverted chains and recording a length of each inverted chain; searching the inverted index and obtaining a subset of the plurality of inverted chains that correspond to at least one keyword; sorting the subset of the plurality of inverted chains in an ascending order of the lengths of the subset of multiple inverted chains; and merging the subset of the plurality of inverted chains sequentially as the ascending order starting from one of the subset of the plurality of inverted chains that has the shortest length.

Claims

1. A method for fast merging inverted chains performed by a hardware processor, comprising:

pre-setting an inverted index including a plurality of inverted chains and recording a length of each inverted chain;

searching the inverted index and obtaining a subset of the plurality of inverted chains that correspond to at least one keyword;

sorting the subset of the plurality of inverted chains in an ascending order of the lengths of the subset of multiple inverted chains; and

sequentially merging the subset of the plurality of inverted chains as the ascending order, wherein the merging includes;

merging one of the subset of the plurality of inverted chains that has a shortest length with one of the subset of the plurality of inverted chains that has a second shortest length to generate an inverted chain including the one of the subset of the plurality of inverted chains that has the shortest length and the one of the subset of the plurality of inverted chains that has the second shortest length, and

merging the inverted chain with one of the subset of the plurality of inverted chains that has a third shortest length.

2. The method of claim 1, wherein pre-setting the inverted index further comprises:

generating a plurality of inverted chains that contain retrieval units and semantic units.

3. The method of claim 2, wherein each retrieval unit comprises at least one search keyword obtained by a small granularity text segmentation scheme.

4. The method of claim 2, wherein each semantic unit comprises at least one search keyword obtained by a large granularity text segmentation scheme.

5. The method of claim 1, wherein pre-setting the inverted index further comprises:

sorting a plurality of documents recorded by the inverted chains in accordance with multidimensional features to rank high-quality documents near the head positions of the inverted chains.

6. The method of claim 5, wherein the multidimensional features of a document comprises author information of the document, view number of the document, quality information of the document.

7. The method of claim 1, wherein the at least one keyword is generated by using multi-granularity text segmentation scheme to a text associated with a user search query.

8. The method of claim 1, wherein the subset of the plurality of inverted chains are sorted by using one of the following methods:

insertion sorting method, bubble sorting method, and selection sorting method.

9. The method of claim 5, further comprising:

suspending the merging process of the subset of multiple inverted chains when a preset number of documents ranked near the head positions of the inverted chains are recalled.

10. The method of claim 5, wherein the inverted index is set by using one of dichotomy method, trie method, and hash method.

11. An apparatus for fast merging inverted chains, comprising:

a hardware processor, wherein the hardware processor is configured to;

pre-set an inverted index including a plurality of inverted chains and record a length of each inverted chain;

search the inverted index and obtaining a subset of the plurality of inverted chains that correspond to at least one keyword;

sort the subset of the plurality of inverted chains by an ascending order of the lengths of the subset of multiple inverted chains; and

sequentially merge the subset of the plurality of inverted chains as the ascending order, wherein the hardware processor is further configured to;

merge one of the subset of the plurality of inverted chains that has a shortest length with one of the subset of the plurality of inverted chains that has a second shortest length to generate an inverted chain including the one of the subset of the plurality of inverted chains that has the shortest length and the one of the subset of the plurality of inverted chains that has the second shortest length, and

merge the generated inverted chain with one of the subset of the plurality of inverted chains that has a third shortest length.

12. The apparatus of claim 11, wherein the processor is further configured to generate a plurality of inverted chains that contain retrieval units and semantic units.

13. The apparatus of claim 12, wherein each retrieval unit comprises at least one search keyword obtained by a small granularity text segmentation scheme.

14. The apparatus of claim 12, wherein each semantic unit comprises at least one search keyword obtained by a large granularity text segmentation scheme.

15. The apparatus of claim 11, wherein the hardware processor is further configured to:

sort a plurality of documents recorded by the inverted chains in accordance with multidimensional features to rank high-quality documents near the head positions of the inverted chains.

16. The apparatus of claim 15, wherein the multidimensional features of a document comprises author information of the document, view number of the document, quality information of the document.

17. The apparatus of claim 11, wherein the hardware processor is further configured to generate the at least one keyword by using multi-granularity text segmentation scheme to a text associated with a user search query.

18. The apparatus of claim 11, wherein the hardware processor is further configured to sort the subset of the plurality of inverted chains by using one of the following methods:

insertion sorting method, bubble sorting method, and selection sorting method.

19. The apparatus of claim 15, wherein the hardware processor is further configured to suspend the merging process of the subset of multiple inverted chains when a preset number of documents ranked near the head positions of the inverted chains are recalled.

20. The apparatus of claim 15, wherein the hardware processor is further configured to set the inverted index by using one of dichotomy method, trie method, and hash method.