Optimizing efficiency and cost of crowd-sourced polling

• US 10,115,116 B2
• Filed: 03/02/2015
• Issued: 10/30/2018
• Est. Priority Date: 03/02/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Livshits, Benjamin, Mytkowicz, Todd, Kastrinis, Georgios
• Primary Examiner(s): Brooks, David T.
• Application Number:
  US14/635,110
• Publication Number:
  US 20160259824A1
• Time in Patent Office: 1,338 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: G06F 16/24549 Run-time optimisation
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0203 Market surveys; Market polls

Abstract

A “Poll Optimizer” provides automated techniques for performing various combinations of both static and runtime optimizations for crowd-sourced queries including, but not limited to, crowd-sourced opinion-based polls. These optimizations have been observed to improve poll performance by reducing factors such as completion times, monetary costs, and error rates of polls. In various implementations, the Poll Optimizer receives an input query representing a crowd-sourced poll that is formatted as a multi-layer structure (e.g., LINQ-based queries natively supported by .NET languages, JQL-based queries supported by JAVA, etc.). The Poll optimizer then iteratively reduces the multi-layer structure of the input query to construct a reformulated query. This reformulated query is then matched to an optimized execution process selected from a plurality of predefined execution processes. Finally, the reformulated query and matching optimized execution process are provided as an optimized version of the crowd-sourced poll for execution via a computer-based crowd-sourcing backend.

Claims

1. A system for optimizing computer-based crowd-sourced polling, comprising:

a processor; and

a memory comprising instructions that, when executed by the processor, cause the processor to perform a method comprising;

receiving an input query representing a crowd-sourced poll comprising two or more branches, each branch associated with a corresponding set of worker qualifications, the query being formatted as a multi-layer structure;

iteratively reducing the multi-layer structure of the input query to construct a reformulated query, the reformulated query having a reduced complexity relative to the input query;

reducing one or more of expected completion time and expected cost associated with the reformulated query by matching the reformulated query to an optimized execution process selected from a plurality of predefined execution processes;

presenting the reformulated query and matching optimized execution process as an optimized version of the crowd-sourced poll for execution via a computer-based crowd-sourcing backend;

during execution of the optimized version of the crowd-sourced poll, improving poll efficiency by automatically changing the matching optimized execution process to another of the predefined execution processes and dynamically changing the reformulated query to correspond to the automatically changed execution process in response to collected runtime statistics relating to execution of the optimized version of the crowd-sourced poll; and

further during execution, presenting the changed reformulated query and changed matching optimized execution process for continued execution via the computer-based crowd-sourcing backend.

2. The system of claim 1 wherein iteratively reducing the multi-layer structure of the input query further comprises removing intermediate structures in the input query by recursively flattening expressions of each of a plurality of clauses in each layer and then logically combining like clauses between different layers of the input query, thereby constructing the reformulated query.

3. The system of claim 1 wherein iteratively reducing the multi-layer structure of the input query further comprises:

creating a first set of questions comprising general and demographic comparisons that are gathered from the input query;

flattening the input query and creating a second set of questions comprising one or more filter questions extracted from the flattened query; and

constructing the reformulated query from the first set of questions in combination with a subset of questions from the second set of questions that are not already addressed by the first set of questions.

4. The system of claim 1 wherein iteratively reducing the multi-layer structure of the input query further comprises:

identifying common subexpressions in the input query; and

merging common subexpressions so that expressions in the input query reference merged subexpressions in place of the common subexpressions.

5. The system of claim 1 wherein matching the reformulated query to an optimized execution process selected from a plurality of predefined execution processes further comprises post-filtering available crowd-sourced workers to include crowd-sourced workers matching qualifying questions extracted from the input query.

6. The system of claim 1 wherein matching the reformulated query to an optimized execution process selected from a plurality of predefined execution processes further comprises performing an automated process comprising:

querying crowd-sourced workers to determine which crowd-sourced workers match qualifying questions extracted from the input query; and

inviting crowd-sourced workers that match the qualifying questions to respond to the reformulated query.

7. The system of claim 1 wherein matching the reformulated query to an optimized execution process selected from a plurality of predefined execution processes further comprises performing an automated process comprising:

presenting crowd-sourced workers with one or more multiple choice questions to determine which crowd-sourced workers match qualifying questions extracted from the input query; and

inviting crowd-sourced workers that match the qualifying questions to respond to the reformulated query.

8. The system of claim 1 further comprising automatically determining relative numbers of workers for each of two or more branches of the crowd-sourced poll during execution of the poll via the crowd-sourcing backend.

9. The system of claim 8 further comprising automatically adapting payment offers to workers meeting qualifications of under-represented branches to increase numbers of qualified workers in those under-represented branches, each under-represented branch having fewer workers than a predetermined percentage of workers for that branch.

10. The system of claim 8 further comprising automatically adapting payment offers to workers meeting qualifications of over-represented branches to decrease numbers of qualified workers in over-represented branches, each over-represented branch having more workers than a predetermined percentage of workers for that branch.

11. The system of claim 1 further comprising automatically inviting workers assigned to a pre-constructed worker panel via an automated iterative panel building process to respond the optimized version of the crowd-sourced poll via the crowd-sourcing backend.

12. A computer-implemented process, comprising:

using a computer to perform process actions for;

receiving a crowd-sourced query formatted as a multi-layer structure, the crowd-sourced query comprising two or more branches, each branch associated with a corresponding set of worker qualifications;

applying one or more optimizations to the crowd-sourced query to construct a reformulated query, said optimizations serving to reduce a complexity of the crowd-sourced query;

reducing one or more of expected completion time and expected cost associated with the reformulated query by matching the reformulated query to an optimized execution process;

presenting the reformulated query and matching optimized execution process as an optimized version of the crowd-sourced query for execution via a computer-based crowd-sourcing backend;

during execution of the optimized version of the crowd-sourced query, improving query efficiency by automatically changing the matching optimized execution process to a different optimized execution processes and dynamically changing the reformulated query to correspond to the automatically changed execution process in response to collected runtime statistics relating to execution of the optimized version of the crowd-sourced query; and

further during execution, presenting the changed reformulated query and changed matching optimized execution process for continued execution via the computer-based crowd-sourcing backend.

13. The computer-implemented process of claim 12 wherein a query flattening optimization comprises:

iteratively removing intermediate structures in the crowd-sourced query by recursively flattening expressions of each of a plurality of clauses in each layer of the crowd-sourced query; and

logically combining like clauses between different layers of the crowd-sourced query.

14. The computer-implemented process of claim 12 wherein a query splitting optimization comprises:

flattening the crowd-sourced query by gathering general and demographic questions that filter based on demographic characteristics into a single where clause; and

gathering the remaining questions of the crowd-sourced query into a single select clause.

15. The computer-implemented process of claim 12 wherein a common subexpression elimination optimization comprises:

identifying common subexpressions in the input query; and

merging the identified common subexpressions so that expressions in the input query reference merged subexpressions in place of the common subexpressions.

16. The computer-implemented process of claim 12 wherein matching the reformulated query to an optimized execution process further comprises selecting one or more execution processes from a plurality of predefined execution processes, the plurality of predefined execution processes comprising:

post-filtering available crowd-sourced workers to include crowd-sourced workers matching qualifying questions extracted from the crowd-sourced query;

inviting a first set of crowd-sourced workers that match qualifying questions extracted from the crowd-sourced query to respond to the reformulated query; and

inviting a second set of crowd-sourced workers that match predetermined qualifications determined via one or more multiple choice questions to respond to the reformulated query.

17. The computer-implemented process of claim 12 further comprising:

automatically adapting payment offers to workers meeting qualifications of under-represented branches of the crowd-sourced query to increase numbers of qualified workers in those under-represented branches, each under-represented branch having less than a predetermined number of workers for that branch; and

automatically adapting payment offers to workers meeting qualifications of over-represented branches of the crowd-sourced query to decrease numbers of qualified workers in over-represented branches, each over-represented branch having more than a predetermined number of workers for that branch.

18. A cloud-based crowd-sourced query system, comprising:

a general purpose computing device; and

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to;

receive a crowd-sourced query comprising two or more branches, each branch associated with a corresponding set of worker qualifications;

apply one or more automated optimizations to the crowd-sourced query to construct a reformulated query, the reformulated query having a reduced complexity relative to the crowd-sourced query;

reduce one or more of expected completion time and expected cost associated with the reformulated query by associating the reformulated query with a matching optimized execution process selected from a plurality of predefined execution processes;

provide the reformulated query and matching optimized execution process as an optimized version of the crowd-sourced query for execution via a cloud-based crowd-sourcing backend;

during execution of the optimized version of the crowd-sourced query, improve query efficiency by automatically changing the matching optimized execution process to a different one of the predefined execution processes and dynamically changing the reformulated query to correspond to the changed execution process in response to collected runtime statistics relating to execution of the optimized version of the crowd-sourced query; and

further during execution, presenting the changed reformulated query and changed matching optimized execution process for continued execution via the cloud-based crowd-sourcing backend.

19. The cloud-based crowd-sourced query system of claim 18 wherein the crowd-sourced query is formatted as a multi-layer structure, and wherein the automated optimizations include any combination of query flattening, query splitting, and common subexpression elimination.

20. The cloud-based crowd-sourced query system of claim 18 wherein matching the reformulated query to an optimized execution process further comprises selecting one or more execution processes from a plurality of predefined execution processes, the plurality of predefined execution processes comprising:

post-filtering available crowd-sourced workers to include crowd-sourced workers matching qualifying questions extracted from the crowd-sourced query;

inviting a first set of crowd-sourced workers that match qualifying questions extracted from the crowd-sourced query to respond to the reformulated query; and

inviting a second set of crowd-sourced workers that match predetermined qualifications determined via one or more multiple choice questions to respond to the reformulated query.