Accelerated searching of substrings

• US 8,688,685 B2
• Filed: 06/15/2012
• Issued: 04/01/2014
• Est. Priority Date: 06/15/2012
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Qin, Bin, Davis, Michael, Lyons, David
• Primary Examiner(s): Nguyen, Loan T
• Application Number:
  US13/525,160
• Publication Number:
  US 20130339339A1
• Time in Patent Office: 655 Days
• Field of Search: None
• US Class Current: 707/713
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24535 of sub-queries or views

Abstract

Accelerated sub-string searches on large data sets can be performed using filtering processes that can improve or optimize run time performance. A first filtering process can include partitioning a binary tree into sections to enable an exact search to replace a substring search for part of the binary tree and for part of the binary tree to be potentially excluded from substring searching. A second filtering process can include comparing count representations of entries in the binary tree and of a received input string to potentially further exclude entries from substring searching.

Claims

1. A computer program product comprising a non-transitory machine-readable medium storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:

determining a length of a received input string;

generating a count representation of the received input string;

applying a first filtering process to a data set to be searched, the first filtering process comprising partitioning a binary tree for a field of the data set into a section S1, a section S2, and a section S3, the section S1 comprising entries in the binary tree that have keys longer than the length of the received input string, the section S2 comprising entries in the binary tree that have keys equal to the length of the received input string and contents that are greater than or equal to the received input string, and the section S3 comprising other entries in the binary tree, the other entries comprising those entries in the binary tree that are not in section S1 or in section S2, the first filtering process further comprising excluding the section S3 and performing an exact search for input string on the section S2;

applying a second filtering process to the section S1 of the data set, the second filtering process comprising excluding entries in the section S1, the excluded entries in the section S1 having an entry count representation that is not consistent with the count representation of the input string;

executing a substring search algorithm on a remaining subset of the data set, the remaining subset comprising non-excluded data records of the section S1; and

returning a search result set based on results of executing the substring search algorithm on the remaining subset of the section S1 and the exact search on the section S2.

2. The computer program product as in claim 1, wherein the operations are performed in an in-memory database environment.

3. The computer program product as in claim 1, wherein the operations further comprise building the binary tree and sorting the binary tree.

4. The computer program product as in claim 3, wherein the sorting of the binary tree comprises sorting using a first sorting criterion comprising a reverse order of lengths of values in the field, and using a second sorting criterion comprising a reverse order of contents of the keys of the entries in the binary tree.

5. The computer program product as in claim 1, wherein the generating of the count representation of the input string comprises an indication of a number of instances of a given character or group of characters are present in the input string.

6. The computer program product as in claim 1, wherein the operations further comprise generating the entry count representation for the entries in the binary tree.

7. A system comprising:

a computer hardware comprising at least one programmable processor; and

a machine-readable medium storing instructions that, when executed by the at least one programmable processor, cause the at least one programmable processor to perform operations comprising;

determining a length of a received input string;

generating a count representation of the received input string;

applying a first filtering process to a data set to be searched, the first filtering process comprising partitioning a binary tree for a field of the data set into a section S1, a section S2, and a section S3, the section S1 comprising entries in the binary tree that have keys longer than the length of the received input string, the section S2 comprising entries in the binary tree that have keys equal to the length of the received input string and contents that are greater than or equal to the received input string, and the section S3 comprising other entries in the binary tree, the other entries comprising those entries in the binary tree that are not in section S1 or in section S2, the first filtering process further comprising excluding the section S3 and performing an exact search for input string on the section S2;

applying a second filtering process to the section S1 of the data set, the second filtering process comprising excluding entries in the section S1, the excluded entries in the section S1 having an entry count representation that is not consistent with the count representation of the input string;

executing a substring search algorithm on a remaining subset of the data set, the remaining subset comprising non-excluded data records of the section S1; and

returning a search result set based on results of executing the substring search algorithm on the remaining subset of the section S1 and the exact search on the section S2.

8. The system as in claim 7, wherein the operations are performed in an in-memory database environment.

9. The system as in claim 7, wherein the operations further comprise building the binary tree and sorting the binary tree.

10. The system as in claim 9, wherein the sorting of the binary tree comprises sorting using a first sorting criterion comprising a reverse order of lengths of values in the field, and using a second sorting criterion comprising a reverse order of contents of the keys of the entries in the binary tree.

11. The system as in claim 7, wherein the generating of the count representation of the input string comprises an indication of a number of instances of a given character or group of characters are present in the input string.

12. The system as in claim 7, wherein the operations further comprise generating the entry count representation for the entries in the binary tree.

13. The computer-implemented method comprising:

determining a length of a received input string;

generating a count representation of the received input string;

applying a first filtering process to a data set to be searched, the first filtering process comprising partitioning a binary tree for a field of the data set into a section S1, a section S2, and a section S3, the section S1 comprising entries in the binary tree that have keys longer than the length of the received input string, the section S2 comprising entries in the binary tree that have keys equal to the length of the received input string and contents that are greater than or equal to the received input string, and the section S3 comprising other entries in the binary tree, the other entries comprising those entries in the binary tree that are not in section S1 or in section S2, the first filtering process further comprising excluding the section S3 and performing an exact search for input string on the section S2;

applying a second filtering process to the section S1 of the data set, the second filtering process comprising excluding entries in the section S1, the excluded entries in the section S1 having an entry count representation that is not consistent with the count representation of the input string;

executing a substring search algorithm on a remaining subset of the data set, the remaining subset comprising non-excluded data records of the section S1; and

returning a search result set based on results of executing the substring search algorithm on the remaining subset of the section S1 and the exact search on the section S2.

14. The computer-implemented method as in claim 13, wherein the operations are performed in an in-memory database environment.

15. The computer-implemented method as in claim 13, wherein the operations further comprise building the binary tree and sorting the binary tree.

16. The computer-implemented method as in claim 15, wherein the sorting of the binary tree comprises sorting using a first sorting criterion comprising a reverse order of lengths of values in the field, and using a second sorting criterion comprising a reverse order of contents of the keys of the entries in the binary tree.

17. The computer-implemented method as in claim 13, wherein the generating of the count representation of the input string comprises an indication of a number of instances of a given character or group of characters are present in the input string.

18. The computer-implemented method as in claim 13, wherein the operations further comprise generating the entry count representation for the entries in the binary tree.

19. The computer-implemented method as in claim 13, wherein at least one of the determining, the generating, the applying of the first filtering, the applying of the second filtering, the executing, and the returning is performed by at least one programmable processor.