METHOD AND AN APPARATUS FOR FAST MERGING INVERTED CHAINS

• US 20170083610A1
• Filed: 09/20/2016
• Published: 03/23/2017
• 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
• Granted Patent: US 10,452,692 B2
• Time in Patent Office: Days
• 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, 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

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.

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 inversed chains in accordance with multidimensional features to rank high-quality documents near the head positions of the inversed 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 inversed 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:

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

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

a sorting component configured for sorting the subset of the plurality of inverted chains by an ascending order of the lengths of the subset of multiple inverted chains; and

a merging component configured for 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.

12. The apparatus of claim 11, wherein the inverted index setup component is further configured for generating 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, further comprising:

a priority sorting component configured for sorting a plurality of documents recorded by the inversed chains in accordance with multidimensional features to rank high-quality documents near the head positions of the inversed 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 searching component is further configured for generating 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 sorting component is further configured for sorting 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 merging component is further configured for:

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

20. The apparatus of claim 15, wherein the inverted index setup component is further configured for setting the inverted index by using one of dichotomy method, trie method, and hash method.