Method and system for document indexing and data querying

• US 9,946,753 B2
• Filed: 12/17/2015
• Issued: 04/17/2018
• Est. Priority Date: 07/23/2009
• Status: Active Grant

• Current Assignee: Alibaba Group Holding Ltd.
• Original Assignee: Alibaba Group Holding Ltd.
• Inventors: Wei, Lei, Shen, Jiaxiang
• Primary Examiner(s): Thomas, Ashish K
• Assistant Examiner(s): Ohba, Mellissa M
• Application Number:
  US14/973,395
• Publication Number:
  US 20160171052A1
• Time in Patent Office: 852 Days
• Field of Search: None
• 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; determining whether each monadic partition obtained from the document is a filter character and if so, forming a polynary partition with the monadic partition and at least one adjacent monadic partition and indexing the polynary partition, otherwise, indexing the monadic partition. Querying data comprising: receiving a data query, determining whether each monadic partition obtained from the data query is a filter character and if so, forming a polynary partition with the monadic partition and at least one adjacent monadic partition and using the polynary partition to obtain search results, otherwise, using the monadic partition to obtain search results; and combining search results to form a final query search result.

Claims

1. A system, comprising:

a processor; and

a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions which when executed cause the processor to;

generate a preset filter characters list based at least in part on a sample set of documents and appearance frequencies of monadic partitions that are present in the sample set of documents, wherein the monadic partitions comprise character text;

obtain a document to be indexed;

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

determine whether a first monadic partition of the plurality of monadic partitions associated with the document should be indexed directly or indexed with at least one other monadic partition from the plurality of monadic partitions as at least one polynary partition, wherein the determination comprises to;

determine that the first monadic partition matches a filter character monadic partition included in the preset filter characters list;

in response to the determination that the first monadic partition matches the filter character monadic partition, index the first monadic partition as the at least one polynary partition, including to;

determine whether the first monadic partition precedes a second monadic partition in the plurality of monadic partitions associated with the document, wherein the second monadic partition is adjacent to the first monadic partition in the document;

in response to a first determination that the first monadic partition precedes the second monadic partition, form a first binary partition by combining the first monadic partition with the second monadic partition;

determine whether the first monadic partition succeeds a third monadic partition in the plurality of monadic partitions associated with the document, wherein the third monadic partition is adjacent to the first monadic partition in the document;

in response to a second determination that the first monadic partition succeeds the third monadic partition, form a second binary partition by combining the first monadic partition with the third monadic partition; and

add a first entry in a document index corresponding to the first binary partition and a second entry in the document index corresponding to the second binary partition, without directly indexing the first monadic partition in the document index.

2. The system of claim 1, wherein to generate the preset filter characters list based at least in part on the sample set of documents and the appearance frequencies of monadic partitions that are present in the sample set of documents comprises to:

determine monadic partitions from the sample set of documents;

determine an appearance frequency for each of at least a subset of the monadic partitions among the sample set of documents; and

include a subset of the monadic partitions into the preset filter character list based at least in part on appearance frequencies corresponding to respective ones of the monadic partitions.

3. The system of claim 1, wherein the filter character monadic partition comprises a first filter character monadic partition, and wherein the processor is further configured to:

for a fourth monadic partition in the plurality of monadic partitions associated with the document;

determine that the fourth monadic partition does not match a second filter character monadic partition of the preset filter characters list; and

in response to the determination that the fourth monadic partition does not match the second filter character monadic partition, add another entry in the document index corresponding to the fourth monadic partition.

4. The system of claim 1, wherein the processor is further configured to:

determine that the first binary partition matches a filter character binary partition of the preset filter characters list;

in response to a third determination that the first binary partition matches the filter character binary partition;

form a ternary partition by combining the first binary partition with at least a fourth monadic partition in the plurality of monadic partitions associated with the document; and

add a third entry in the document index corresponding to the ternary partition without directly indexing the first binary partition.

5. A method, comprising:

generating a preset filter characters list based at least in part on a sample set of documents and appearance frequencies of monadic partitions that are present in the sample set of documents, wherein the monadic partitions comprise character text;

obtaining a document to be indexed;

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

determining whether a first monadic partition of the plurality of monadic partitions associated with the document should be indexed directly or indexed with at least one other monadic partition from the plurality of monadic partitions as at least one polynary partition, wherein the determination comprises;

determining that the first monadic partition matches a filter character monadic partition included in the preset filter characters list;

in response to the determination that the first monadic partition matches the filter character monadic partition, indexing the first monadic partition as the at least one polynary partition, including;

determining whether the first monadic partition precedes a second monadic partition in the plurality of monadic partitions associated with the document, wherein the second monadic partition is adjacent to the first monadic partition in the document;

in response to a first determination that the first monadic partition precedes the second monadic partition, forming a first binary partition by combining the first monadic partition with the second monadic partition;

determining whether the first monadic partition succeeds a third monadic partition in the plurality of monadic partitions associated with the document, wherein the third monadic partition is adjacent to the first monadic partition in the document;

in response to a second determination that the first monadic partition succeeds the third monadic partition, forming a second binary partition by combining the first monadic partition with the third monadic partition; and

adding a first entry in a document index corresponding to the first binary partition and a second entry in the document index corresponding to the second binary partition, without directly indexing the first monadic partition.

6. The method of claim 5, wherein generating the preset filter characters list based at least in part on the sample set of documents and the appearance frequencies of monadic partitions that are present in the sample set of documents comprises:

determining monadic partitions from the sample set of documents;

determining an appearance frequency for each of at least a subset of the monadic partitions among the sample set of documents; and

including a subset of the monadic partitions into the preset filter character list based at least in part on appearance frequencies corresponding to respective ones of the monadic partitions.

7. The method of claim 5, wherein the filter character monadic partition comprises a first filter character monadic partition, and further comprising:

for a fourth monadic partition in the plurality of monadic partitions associated with the document;

determining that the fourth monadic partition does not match a second filter character monadic partition of the preset filter characters list; and

in response to the determination that the fourth monadic partition does not match the second filter character monadic partition, adding another entry in the document index corresponding to the fourth monadic partition.

8. The method of claim 5, further comprising:

determining that the first binary partition matches a filter character binary partition of the preset filter characters list;

in response to a third determination that the first binary partition matches the filter character binary partition;

forming a ternary partition by combining the first binary partition with at least a fourth monadic partition in the plurality of monadic partitions associated with the document; and

adding a third entry in the document index corresponding to the ternary partition without directly indexing the first binary partition.

9. A system, comprising:

a processor; and

a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions which when executed cause the processor to;

generate a preset filter characters list based at least in part on a sample set of documents and appearance frequencies of monadic partitions that are present in the sample set of documents, wherein the monadic partitions comprise character text;

receive a data query;

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

determine whether a first monadic partition of the plurality of monadic partitions associated with the data query should be searched directly or searched with at least one other monadic partition from the plurality of monadic partitions as at least one polynary partition, wherein the determination comprises to;

determine that the first monadic partition matches a filter character monadic partition included in the preset filter characters list;

in response to the determination that the first monadic partition matches the filter character monadic partition, searching the first monadic partition as the at least one polynary partition, including to;

determine whether the first monadic partition precedes a second monadic partition in the plurality of monadic partitions associated with the data query, wherein the second monadic partition is adjacent to the first monadic partition in the data query;

in response to a first determination that the first monadic partition precedes the second monadic partition, form a first binary partition by combining the first monadic partition with the second monadic partition;

determine whether the first monadic partition succeeds a third monadic partition in the plurality of monadic partitions associated with the data query, wherein the third monadic partition is adjacent to the first monadic partition in the data query;

in response to a second determination that the first monadic partition succeeds the third monadic partition, form a second binary partition by combining the first monadic partition with the third monadic partition; and

search a preset index using the first binary partition and the second binary partition, without searching the preset index directly using the first monadic partition.

10. The system of claim 9, wherein to generate the preset filter characters list based at least in part on the sample set of documents and the appearance frequencies of monadic partitions that are present in the sample set of documents comprises to:

determine monadic partitions from the sample set of documents;

determine an appearance frequency for each of at least a subset of the monadic partitions among the sample set of documents; and

include a subset of the monadic partitions into the preset filter character list based at least in part on appearance frequencies corresponding to respective ones of the monadic partitions.

11. The system of claim 9, wherein the filter character monadic partition comprises a first filter character monadic partition, and wherein the processor is further configured to:

for a fourth monadic partition in the plurality of monadic partitions associated with the data query;

determine that the fourth monadic partition does not match a second filter character monadic partition of the preset filter characters list; and

in response to a third determination that the fourth monadic partition does not match the second filter character monadic partition, search the preset index directly using the fourth monadic partition to obtain a search result.

12. The system of claim 9, wherein the processor is further configured to:

determine that the first binary partition matches a filter character binary partition of the preset filter characters list;

in response to a third determination that the first binary partition matches the filter character binary partition;

form a ternary partition by combining the first binary partition with at least a fourth monadic partition in the plurality of monadic partitions associated with the data query; and

search the preset index using the ternary partition to obtain a search result corresponding to the ternary partition without searching the preset index directly using the first binary partition.