Model driven optimization of annotator execution in question answering system

• US 10,127,075 B2
• Filed: 04/14/2014
• Issued: 11/13/2018
• Est. Priority Date: 04/14/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Allen, Corville O., Carter, Bernadette A., Ghosh, Rahul
• Primary Examiner(s): Paula, Cesar B
• Assistant Examiner(s): Huang, Jian
• Application Number:
  US14/252,452
• Publication Number:
  US 20150293784A1
• Time in Patent Office: 1,674 Days
• Field of Search: 706 52, 715230, 7071141, 382118
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536
• CPC Class Codes: G06F 40/169 Annotation, e.g. comment data or footnotes
• CPC Class Codes: G06F 9/48 Program initiating; Program switching, e.g. by interrupt
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06N 5/041 Abduction

Abstract

Mechanisms are provided for scheduling execution of pre-execution operations of an annotator of a question and answer (QA) system pipeline. A model is used to represent a system of annotators of the QA system pipeline, where the model represents each annotator as a node having one or more performance parameters indicating a performance of an execution of an annotator corresponding to the node. For each annotator in a set of annotators of the system of annotators, an effective response time for the annotator is calculated based on the performance parameters. A pre-execution start interval for a first annotator based on an effective response time of a second annotator is calculated where execution of the first annotator is sequentially after execution of the second annotator. Execution of pre-execution operations associated with the first annotator is scheduled based on the calculated pre-execution start interval for the first annotator.

Claims

1. A computer program product comprising a non-transitory computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a computing device, causes the computing device to:

use a model to represent a system of annotators of a Question and Answer (QA) system pipeline, wherein the model represents each annotator in the system of annotators as a node having one or more performance parameters for indicating a performance of an execution of an annotator corresponding to the node, wherein each annotator in the system of annotators is a program that takes a portion of unstructured input text, extracts structured information from the portion of the unstructured input text, and generates annotations or metadata that are attached by the annotator to a source of the unstructured input text, wherein, for each node in the model, the one or more performance parameters corresponding to the node comprise an arrival rate parameter and a service rate parameter of the annotator associated with the node, wherein the arrival rate parameter indicates a number of jobs arriving in the node per second, and wherein the service rate parameter indicates a number of jobs being serviced by the node per second;

determine, for each annotator in a set of annotators of the system of annotators, an effective response time for the annotator based on the one or more performance parameters;

calculate a pre-execution start interval for a first annotator based on an effective response time of a second annotator, wherein execution of the first annotator is sequentially after execution of the second annotator; and

schedule execution of pre-execution operations associated with the first annotator based on the calculated pre-execution start interval for the first annotator.

2. The computer program product of claim 1, wherein at least one node in the model represents a plurality of annotators comprising an aggregate annotator.

3. The computer program product of claim 1, wherein the system is modeled as a tandem open queuing network in which each node in the model is modeled as a queue in the tandem open queuing network.

4. The computer program product of claim 1, wherein each annotator of the QA system pipeline is defined, in a data structure, as a sub-system of the QA system pipeline and is designated as either having or not having one or more non-dependent pre-execution operations that may be executed with the results of the one or more non-dependent pre-execution operations being stored/cached for use by the annotator, and wherein the computer readable program causes the computing device to schedule execution of pre-execution operations associated with the first annotator in response to the data structure indicating that the pre-execution operations associated with the first annotator are non-dependent pre-execution operations.

5. The computer program product of claim 1, wherein the computer readable program causes the computing device to calculate the pre-execution start interval for the first annotator based on an effective response time of the second annotator at least by calculating the pre-execution start interval based on a difference of a current execution time and an effective response time of the second annotator.

6. The computer program product of claim 1, wherein the scheduling generates a scheduling data structure, and wherein the computer readable program further causes the computing device to:

receive a job for processing by the QA system pipeline;

select a set of annotators in the system of annotators to execute the job, the set of annotators comprising the first annotator and the second annotator;

schedule the set of annotators, including the pre-execution operation of the first annotator, based on the scheduling data structure; and

process the job based on the scheduling of the set of annotators.

7. An apparatus comprising:

a processor; and

a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to;

use a model to represent a system of annotators of a Question and Answer (QA) system pipeline, wherein the model represents each annotator in the system of annotators as a node having one or more performance parameters for indicating a performance of an execution of an annotator corresponding to the node, wherein each annotator in the system of annotators is a program that takes a portion of unstructured input text, extracts structured information from the portion of the unstructured input text, and generates annotations or metadata that are attached by the annotator to a source of the unstructured input text, wherein, for each node in the model, the one or more performance parameters corresponding to the node comprises an arrival rate parameter and a service rate parameter of the annotator associated with the node, wherein the arrival rate parameter indicates a number of jobs arriving in the node per second and wherein the service rate parameter indicates a number of lobs being serviced by the node per second;

determine, for each annotator in a set of annotators of the system of annotators, an effective response time for the annotator based on the one or more performance parameters;

calculate a pre-execution start interval for a first annotator based on an effective response time of a second annotator, wherein execution of the first annotator is sequentially after execution of the second annotator; and

schedule execution of pre-execution operations associated with the first annotator based on the calculated pre-execution start interval for the first annotator.

8. The apparatus of claim 7, wherein the system is modeled as a tandem open queuing network in which each node in the model is modeled as a queue in the tandem open queuing network.

9. The apparatus of claim 7, wherein each annotator of the QA system pipeline is defined, in a data structure, as a sub-system of the QA system pipeline and is designated as either having or not having one or more non-dependent pre-execution operations that may be executed with the results of the one or more non-dependent pre-execution operations being stored/cached for use by the annotator, and wherein instructions cause the processor to schedule execution of pre-execution operations associated with the first annotator in response to the data structure indicating that the pre-execution operations associated with the first annotator are non-dependent pre-execution operations.

10. The apparatus of claim 7, wherein the instructions cause the processor to calculate the pre-execution start interval for the first annotator based on an effective response time of the second annotator at least by calculating the pre-execution start interval based on a difference of a current execution time and an effective response time of the second annotator.

11. The apparatus of claim 7, wherein the scheduling generates a scheduling data structure, and wherein the instructions further cause the processor to:

receive a job for processing by the QA system pipeline;

select a set of annotators in the system of annotators to execute the job, the set of annotators comprising the first annotator and the second annotator;

schedule the set of annotators, including the pre-execution operation of the first annotator, based on the scheduling data structure; and

process the job based on the scheduling of the set of annotators.