Searching multi-dimensional data using a parallelization framework comprising data partitioning and short-cutting via early out

1. A method for searching multi-dimensional data, wherein the method comprises:

providing a parallelization framework for a search algorithm, wherein said providing is carried out by a module executing on a hardware processor, and wherein the search algorithm exposes architecture-sensitive tunable optimization parameters comprising:

query batching to determine which queries are evaluated simultaneously;

query partitioning to determine how queries are assigned across multiple processors;

data partitioning to determine how data items are distributed across multiple processors;

short-cutting via early-out to enable sharing of local search information across processors in order to reduce individual search times; and

data striping to determine a data memory layout to improve cache locality; and

using the architecture-sensitive tunable optimization parameters to tune the search algorithm to search multi-dimensional data in any underlying architecture, wherein said using is carried out by a module executing on a hardware processor.

2. The method of claim 1 , further comprising providing an auto-tuning layer on top of the parallelization framework, wherein the auto-tuning layer determines optimal tuning parameters for a given hardware platform.

3. The method of claim 2 , wherein for a given query workload and data, the auto-tuning layer initializes the architecture-sensitive tunable optimization parameters and iteratively traverses the space of parameter settings while measuring query performance at each step until a steady state is reached.

4. The method of claim 1 , further comprising auto-tuning a nearest neighbor (NN) algorithm on a multi-core architecture.

5. The method of claim 4 , further comprising using an offline auto-tuner for setting the architecture-sensitive tunable optimization parameters by iteratively measuring actual query execution times for a given workload and dataset.

6. The method of claim 1 , further comprising multi-threading, wherein multi-threading comprises concurrently performing data exploration for a single query and allowing multiple pending queries to run concurrently.

7. The method of claim 1 , further comprising block-cyclic load balancing.

8. The method of claim 1 , further comprising sharing short-cutting information between threads.

9. The method of claim 1 , further comprising multi-query cache sharing, wherein multi-query cache sharing comprises performing one data scan for multiple pending queries.

10. The method of claim 1 , further comprising providing a system, wherein the system comprises one or more distinct software modules, each of the one or more distinct software modules being embodied on a tangible computer-readable recordable storage medium, and wherein the one or more distinct software modules comprise an index and scan-based search module, an optimization parameters module and an auto-tuning layer module executing on a hardware processor.

11. A computer program product comprising a tangible computer readable recordable storage medium including computer useable program code for searching multi-dimensional data, the computer program product including:

computer useable program code for providing a parallelization framework for a search algorithm, wherein said providing is carried out by a module executing on a hardware processor, and wherein the search algorithm exposes architecture-sensitive tunable optimization parameters comprising:

query batching to determine which queries are evaluated simultaneously;

query partitioning to determine how queries are assigned across multiple processors;

data partitioning to determine how data items are distributed across multiple processors;

short-cutting via early-out to enable sharing of local search information across processors in order to reduce individual search times; and

data striping to determine a data memory layout to improve cache locality; and

computer useable program code for using the architecture-sensitive tunable optimization parameters to tune the search algorithm to search multi-dimensional data in any underlying architecture.

12. The computer program product of claim 11 , further comprising computer useable program code for providing an auto-tuning layer on top of the parallelization framework, wherein the auto-tuning layer determines optimal tuning parameters for a given hardware platform.

13. The computer program product of claim 11 , further comprising computer useable program code for auto-tuning a nearest neighbor (NN) algorithm on a multi-core architecture.

14. The computer program product of claim 11 , further comprising computer useable program code for multi-threading, wherein the computer useable program code for multi-threading comprises computer useable program code for concurrently performing data exploration for a single query and allowing multiple pending queries to run concurrently.

15. The computer program product of claim 11 , further comprising computer useable program code for multi-query cache sharing, wherein the computer useable program code for multi-query cache sharing comprises computer useable program code for performing one data scan for multiple pending queries.

16. The computer program product of claim 11 , wherein the computer useable program code comprises one or more distinct software modules, and wherein the one or more distinct software modules comprise an index and scan-based search module, an optimization parameters module and an auto-tuning layer module executing on a hardware processor.

17. A system for searching multi-dimensional data, comprising:

a memory; and

at least one processor coupled to the memory and operative to:

provide a parallelization framework for a search algorithm, wherein said providing is carried out by a module executing on a hardware processor, and wherein the search algorithm exposes architecture-sensitive tunable optimization parameters comprising:

query batching to determine which queries are evaluated simultaneously;

query partitioning to determine how queries are assigned across multiple processors;

data partitioning to determine how data items are distributed across multiple processors;

short-cutting via early-out to enable sharing of local search information across processors in order to reduce individual search times; and

data striping to determine a data memory layout to improve cache locality; and

use the architecture-sensitive tunable optimization parameters to tune the search algorithm to search multi-dimensional data in any underlying architecture.

18. The system of claim 17 , wherein the at least one processor coupled to the memory is further operative to provide an auto-tuning layer on top of the parallelization framework, wherein the auto-tuning layer determines optimal tuning parameters for a given hardware platform.

19. The system of claim 17 , wherein the at least one processor coupled to the memory is further operative to auto-tune a nearest neighbor (NN) algorithm on a multi-core architecture.

20. The system of claim 17 , wherein the at least one processor coupled to the memory is further operative to multi-thread, wherein multi-threading comprises concurrently performing data exploration for a single query and allowing multiple pending queries to run concurrently.

21. The system of claim 17 , further comprising a tangible computer-readable recordable storage medium having one or more distinct software modules embodied thereon, wherein the one or more distinct software modules comprise an index and scan-based search module, an optimization parameters module and an auto-tuning layer module executing on a hardware processor.

22. An apparatus for searching multi-dimensional data, the apparatus comprising:

means for providing a parallelization framework for a search algorithm via a module executing on a hardware processor, wherein the search algorithm exposes architecture-sensitive tunable optimization parameters comprising:

query batching to determine which queries are evaluated simultaneously;

query partitioning to determine how queries are assigned across multiple processors;

data partitioning to determine how data items are distributed across multiple processors;

short-cutting via early-out to enable sharing of local search information across processors in order to reduce individual search times; and

data striping to determine a data memory layout to improve cache locality; and

means for using the architecture-sensitive tunable optimization parameters to tune the search algorithm to search multi-dimensional data in any underlying architecture via a module executing on a hardware processor.