Method and system for document indexing and data querying

• US 20110022596A1
• Filed: 07/20/2010
• Published: 01/27/2011
• Est. Priority Date: 07/23/2009
• Status: Active Grant

• Current Assignee: Alibaba Group Holding Ltd.
• Original Assignee: Alibaba Group Holding Ltd.
• Inventors: Shen, Jiaxiang, Wei, Lei
• Granted Patent: US 9,275,128 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/316 Indexing structures
• CPC Class Codes: G06F 16/3337 Translation of the query language, e.g. Chinese to English
• CPC Class Codes: G06F 16/93 Document management systems

Abstract

Generating a document index comprises: obtaining a document to be indexed; performing a monadic partition operation on the document to obtain a plurality of monadic partitions; and for each monadic partition in the plurality of monadic partitions: determining whether said each monadic partition is a filter character; in the event said each monadic partition is a filter character, forming a polynary partition by combining the monadic partition with at least one other monadic partition adjacent to the monadic partition, and indexing the polynary partition; and in the event that the monadic partition is not a filter character, indexing the monadic partition. Querying data comprising: receiving a data query; performing a monadic partition operation on the data query to obtain a plurality of monadic partitions; and for each monadic partition in the plurality of monadic partitions: determining whether said each monadic partition is a filter character; in the event that the monadic partition is a filter character, forming a polynary partition by combining the monadic partition with at least one monadic partition adjacent to the monadic partition, and searching a preset index using the polynary partition to obtain a search result corresponding to the polynary partition; and in the event that the monadic partition is not a filter character, searching the preset index using the monadic partition to obtain a search result corresponding to the monadic partition; and combining the search results to form a final query search result.

Claims

1. A method for generating a document index, comprising:

obtaining a document to be indexed;

performing a monadic partition operation on the document to obtain a plurality of monadic partitions;

for each monadic partition in the plurality of monadic partitions;

determining whether said each monadic partition is a filter character;

in the event said each monadic partition is a filter character, forming a polynary partition by combining the monadic partition with at least one other monadic partition adjacent to the monadic partition, and indexing the polynary partition; and

in the event that the monadic partition is not a filter character, indexing the monadic partition.

2. The method of claim 1, further comprising presetting a filter characters list according to frequencies of appearance of characters in a plurality of documents.

3. The method of claim 2, wherein determining whether a monadic partition is a filter character includes comparing the monadic partition with the preset filter characters list.

4. The method of claim 1, wherein forming a polynary partition includes forming a binary partition by combining the monadic partition with at least one other monadic partition adjacent to the monadic partition.

5. The method of claim 4, wherein forming a binary partition further comprises:

forming a binary partition by combining the monadic partition with a subsequent monadic partition in the event that the monadic partition is the first monadic partition in the document;

forming a binary partition by combining the monadic partition with a previous monadic partition when the monadic partition is the last monadic partition in the document; and

forming a first binary partition by combining the monadic partition with the previous monadic partition a second binary partition by combining the monadic partition with the subsequent monadic partition in the event the monadic partition is neither the first monadic partition nor the last monadic partition in the document.

6. A method for querying data, comprising:

receiving a data query;

performing a monadic partition operation on the data query to obtain a plurality of monadic partitions;

for each monadic partition in the plurality of monadic partitions;

determining whether said each monadic partition is a filter character;

in the event that the monadic partition is a filter character, forming a polynary partition by combining the monadic partition with at least one monadic partition adjacent to the monadic partition, and searching a preset index using the polynary partition to obtain a search result corresponding to the polynary partition; and

in the event that the monadic partition is not a filter character, searching the preset index using the monadic partition to obtain a search result corresponding to the monadic partition; and

combining the search results to form a final query search result.

7. The method of claim 6, wherein the preset index is established by:

obtaining a document to be indexed;

performing an indexing monadic partition operation on the document to obtain a second plurality of monadic partitions; and

for each monadic partition in the second plurality of monadic partitions;

determining whether said each monadic partition is a filter character; and

in the event that said each monadic partition is a filter character, forming a second polynary partition by combining said each monadic partition with at least one other monadic partition adjacent to the monadic partition, and indexing the second polynary partition; and

in the event that said each monadic partition is not a filter character, indexing said each monadic partition.

8. The method of claim 6, wherein determining whether the monadic partition is a filter character includes comparing the monadic partition with a preset filter characters list.

9. The method of claim 6, wherein forming the polynary partition includes forming a binary partition by combining the monadic partition with a monadic partition adjacent to the monadic partition.

10. The method of claim 9, wherein forming a binary further comprises:

forming a binary partition by combining the monadic partition and a subsequent monadic partition in the event that the monadic partition is the first monadic partition in the document;

forming a binary partition by combining the monadic partition and a previous monadic partition in the event that the monadic partition is the last monadic partition in the document; and

forming a first binary partition by combining the monadic partition with the previous monadic partition a second binary partition by combining the monadic partition with the subsequent monadic partition in the event that the monadic partition is neither the first monadic partition nor the last monadic partition in the document.

11. A document indexing system, comprising:

one or more processors coupled to an interface, configured to;

obtain a document to be indexed;

perform a monadic partition operation on the document to obtain a plurality of monadic partitions; and

for each monadic partition in the plurality of monadic partitions;

determine whether said each monadic partition is a filter character;

in the event said each monadic partition is a filter character, form a polynary partition by combining the monadic partition with at least one other monadic partition adjacent to the monadic partition, and index the polynary partition; and

in the event that the monadic partition is not a filter character, index the monadic partition; and

one or more memories coupled to one or more processors, configured to provide the processors with instructions.

12. The system of claim 11, wherein the one or more processors are further configured to preset a filter characters list according to frequencies of appearance of characters in a plurality of documents.

13. The system of claim 12, wherein determining whether a monadic partition is a filter character includes comparing the monadic partition with the preset filter characters list.

14. The system of claim 11, wherein forming a polynary partition includes forming a binary partition by combining the monadic partition with at least one other monadic partition adjacent to the monadic partition.

15. The system of claim 14, wherein forming a binary partition further comprises:

forming a binary partition by combining the monadic partition with a subsequent monadic partition in the event that the monadic partition is the first monadic partition in the document;

forming a binary partition by combining the monadic partition with a previous monadic partition when the monadic partition is the last monadic partition in the document; and

forming a first binary partition by combining the monadic partition with the previous monadic partition a second binary partition by combining the monadic partition with the subsequent monadic partition in the event the monadic partition is neither the first monadic partition nor the last monadic partition in the document.

16. A data querying system, comprising:

one or more processors coupled to an interface, configured to;

perform a monadic partition operation on the data query to obtain a plurality of monadic partitions;

for each monadic partition in the plurality of monadic partitions;

determine whether said each monadic partition is a filter character;

in the event that the monadic partition is a filter character, form a polynary partition by combining the monadic partition with at least one monadic partition adjacent to the monadic partition, and search a preset index using the polynary partition to obtain a search result corresponding to the polynary partition; and

in the event that the monadic partition is not a filter character, search the preset index using the monadic partition to obtain a search result corresponding to the monadic partition; and

combine the search results to form a final query search result; and

one or more memories coupled to one or more processors, configured to provide the processors with instruction.

17. The system of claim 16, wherein the preset index is established by:

obtaining a document to be indexed;

performing an indexing monadic partition operation on the document to obtain a second plurality of monadic partitions;

for each monadic partition in the second plurality of monadic partitions;

determining whether said each monadic partition is a filter character; and

in the event that said each monadic partition is a filter character, forming a second polynary partition by combining said each monadic partition with at least one other monadic partition adjacent to the monadic partition, and indexing the second polynary partition; and

in the event that said each monadic partition is not a filter character, indexing said each monadic partition.

18. The system of claim 16, wherein determining whether the monadic partition is a filter character includes comparing the monadic partition with the preset filter characters list.

19. The method of claim 16, wherein forming the polynary partition includes forming a binary partition by combining the monadic partition with a monadic partition adjacent to the monadic partition.

20. The method of claim 19, wherein forming a binary further comprises:

forming a binary partition by combining the monadic partition and a subsequent monadic partition in the event that the monadic partition is the first monadic partition in the document;

forming a binary partition by combining the monadic partition and a previous monadic partition in the event that the monadic partition is the last monadic partition in the document; and

forming a first binary partition by combining the monadic partition with the previous monadic partition a second binary partition by combining the monadic partition with the subsequent monadic partition in the event that the monadic partition is neither the first monadic partition nor the last monadic partition in the document.