ACCELERATED DETECTION OF MATCHING PATTERNS

• US 20170024439A1
• Filed: 07/21/2015
• Published: 01/26/2017
• Est. Priority Date: 07/21/2015
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: PALAKODETY, RAVI, LUI, DENNIS, CHAVAN, SHASANK
• Granted Patent: US 10,241,979 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 40/126 Character encoding

Abstract

Techniques related to accelerated detection of matching patterns are disclosed. In an embodiment, a method may involve, for a single field of a body of records, contiguously storing field values, thereby storing the field values as a concatenation. The method may also involve identifying a match in the concatenation that matches a value pattern specified by a value pattern expression. The value pattern may include a first partial pattern and a second partial pattern. Further, the method may involve determining that the match is contained in a single field value of the body of records. Still further, the method may involve establishing the match as a matching value. The match may be determined to be contained in the single field value based on searching a data structure comprising length information or offset information for a subset of the field values stored as the concatenation.

Claims

1. A method comprising:

for a single field of a body of records, contiguously storing field values, thereby storing said field values as a concatenation;

identifying a match in said concatenation that matches a value pattern specified by a value pattern expression;

determining that said match is contained in a single field value of said body of records;

establishing said single field value as a matching value,

wherein said method is performed by one or more computing devices.

2. The method of claim 1, wherein determining that said match is contained in said single field value of said body of records comprises finding a particular field value that corresponds to a portion of said match based on searching a data structure comprising length information or offset information for a subset of said field values stored as said concatenation.

3. The method of claim 1, wherein establishing said single field value as said matching value comprises:

obtaining, from a record of said body of records that contains said single field value, a code that represents said single field value in a different body of records;

identifying one or more records of said different body of records that contain said code;

establishing that said one or more records contain said matching value.

4. The method of claim 1, wherein storing said field values as said concatenation comprises sorting said field values prior to contiguously storing said field values.

5. The method of claim 4, wherein identifying said match in said concatenation that matches said value pattern specified by said value pattern expression comprises skipping any portion of said concatenation that is determined, based on said sorting, to be unable to match said value pattern.

6. The method of claim 1, wherein identifying said match in said concatenation that matches said value pattern specified by said value pattern expression comprises skipping any portion of said concatenation that is determined, based on a sequential order indicated by said value pattern, to be unable to match said value pattern.

7. The method of claim 1, wherein identifying said match in said concatenation that matches said value pattern specified by said value pattern expression comprises searching for, in turn, each partial pattern of said value pattern.

8. A method comprising:

for a single field of a body of records, contiguously storing field values, thereby storing the field values as a concatenation;

identifying a field value in said concatenation that matches a value pattern specified by a value pattern expression, wherein identifying said field value comprises;

based on said value pattern, generating a sequence of partial patterns, each of said partial patterns specifying a portion of said value pattern, said sequence of partial patterns having a sequential order;

in said sequential order, iteratively finding a respective match for each of said partial patterns until each respective match is found in a same record of said body of records;

when said each respective match is found in said same record, storing data specifying that said same record contains said field value that matches said value pattern,

wherein said method is performed by one or more computing devices.

9. The method of claim 8, wherein a record corresponding to said each respective match is found based on searching a data structure comprising length information or offset information for a subset of said field values stored as said concatenation.

10. The method of claim 8, wherein identifying said field value comprises:

obtaining, from said same record of said body of records, a code that represents said field value in a different body of records;

identifying one or more records of said different body of records that contain said code;

establishing that said one or more records of said different body of records contain said field value.

11. The method of claim 8, wherein said field values are sorted prior to being stored as said concatenation.

12. The method of claim 11, wherein said field value is identified by skipping any portion of said concatenation that is determined, based on said sorting, to be unable to match each of said partial patterns.

13. The method of claim 8, wherein said match is identified by skipping any portion of said concatenation that is determined, based on said sequential order, to be unable to match each of said partial patterns.

14. One or more non-transitory storage media storing instructions which, when processed by one or more computing devices, cause:

for a single field of a body of records, contiguously storing field values, thereby storing the field values as a concatenation;

identifying a match in said concatenation that matches a value pattern specified by a value pattern expression;

determining that said match is contained in a single field value of said body of records;

establishing said single field value as a matching value.

15. The one or more non-transitory storage media of claim 14, wherein determining that said match is contained in said single field value of said body of records comprises finding a particular field value that corresponds to a portion of said match based on searching a data structure comprising length information or offset information for a subset of said field values stored as said concatenation.

17. The one or more non-transitory storage media of claim 14, wherein establishing said single field value as said matching value comprises:

obtaining, from a record of said body of records that contains said single field value, a code that represents said single field value in a different body of records;

identifying one or more records of said different body of records that contain said code;

establishing that said one or more records contain said matching value.

18. The one or more non-transitory storage media of claim 14, wherein storing said field values as said concatenation comprises sorting said field values prior to contiguously storing said field values.

19. The one or more non-transitory storage media of claim 14, wherein identifying said match in said concatenation that matches said value pattern specified by said value pattern expression comprises skipping any portion of said concatenation that is determined, based on a sequential order indicated by said value pattern, to be unable to match said value pattern.

20. The one or more non-transitory storage media of claim 14, wherein identifying said match in said concatenation that matches said value pattern specified by said value pattern expression comprises searching for, in turn, each partial pattern of said value pattern.