Using local memory nodes of a multicore machine to process a search query

Patent metadata

Field	Value
Publication number	US-10423616-B2
Application number	US-201415307043-A
Country	US
Kind code	B2
Filing date	Apr 30, 2014
Priority date	Apr 30, 2014
Publication date	Sep 24, 2019
Grant date	Sep 24, 2019

Abstract

An example technique includes assigning partitions of a dataset of multidimensional points to a plurality of local memory nodes of a multicore machine and using the local memory nodes for a search query to determine similarity matches in the dataset for a given multidimensional point. The using includes parallel searching with the local memory nodes in the assigned partitions to identify candidate similarity matches to the given multidimensional point using indexes derived from the multidimensional points, the parallel searching for each node progressing through a sequence of search distances and providing an ongoing search result for each search distance from the given multidimensional point and regulating an extent of the parallel searching based on the ongoing search results.

First claim

What is claimed is:

1. A computer-implemented method of performing an efficient search of a dataset of multidimensional points, the method comprising:
assigning partitions of the dataset of multidimensional points to a plurality of local memory nodes of a multicore machine having a processing unit for each local memory node;
receiving a search query corresponding to a given multidimensional point;
storing the partitions of the dataset into the local memory nodes to which they are assigned;
storing index building parameters, including a plurality of search distances, into the local memory nodes;
building, with the processing unit associated with each of the local memory nodes in parallel, a sequence of locality sensitive hash indexes of the partition of the dataset in that local memory node, each locality sensitive hash index associated with one of the plurality of search distances;
performing, using the processing unit associated with each of the local memory nodes, parallel searching in the assigned partitions to identify candidate similarity matches to the given multidimensional point, the parallel searching for each processing unit and local memory node progressing through the sequence of locality sensitive hash indexes associated with the plurality of search distances;
providing, to a coordinator with each processing unit, an ongoing search result for each search distance from the given multidimensional point; and
regulating, with the coordinator, an extent of the parallel searching based on the ongoing search results to determine similarity matches in the dataset for the given multidimensional point.

2. The method of claim 1 , wherein the regulating the extent of the parallel searching comprises selectively halting the parallel searching based on a determination that a number of the ongoing search results exceeds a predetermined number.

3. The method of claim 1 , wherein searching with at least one of the processing units and local memory nodes comprises:
using a plurality of threads to search the sequence of locality sensitive hash indexes in parallel.

4. The method of claim 3 , wherein searching with at least one of the processing units and local memory nodes further comprises:
merging results of the searching of the sequence of locality sensitive hash indexes into a candidate search result set; and
using the plurality of threads to perform a straightforward exhaustive search on the candidate search result set to identify the ongoing search result for one of the search distances.

5. The method of claim 1 , further comprising:
merging the ongoing search results to determine the similarity matches.

6. The method of claim 1 , wherein the parallel searching comprises performing locality sensitive hash (LSH) index-based searching.

7. The method of claim 1 , wherein assigning the partitions to the local memory nodes comprises assigning the partitions to groups of processing cores that share a local memory.

8. An apparatus comprising:
a multicore machine comprising a plurality of local memory nodes each storing index building parameters, including a plurality of search distances;
a plurality of processing units, each configured to search one of a plurality of partitions of a dataset, each partition stored in one of the local memory nodes; and
a coordinator to, in response to a query for matches in the dataset to a given multidimensional point:
initiate parallel searching by each of the processing units in the one of the partitions of the dataset stored in the local memory node for that processing unit to identify candidate similarity matches to the given multidimensional point, wherein each processing unit searches by:
building, in parallel, a sequence of locality sensitive hash indexes of the partition of the dataset in the local memory node for that processing unit, each locality sensitive hash index associated with one of the plurality of search distances; and
progressing through the sequence of locality sensitive hash indexes associated with the plurality of search distances;

receive an ongoing search result from each processing unit for each search distance; and
collect the ongoing search results and selectively halt the parallel searching in response to determining that the collected ongoing search results satisfy the query.

9. The apparatus of claim 8 , wherein the local memory nodes comprise non-uniform memory access architecture (NUMA) nodes.

10. The apparatus of claim 8 , further comprising:
a persistent memory store to store the dataset.

11. The apparatus of claim 10 , wherein the persistent memory further stores data representing the indexes.

12. The apparatus of claim 10 , further comprising a tracker to launch the processing units, assign the partitions to the processing units and relaunch a given processing unit in response to determining that the processing unit has failed.

13. An article comprising a non-transitory computer readable storage medium storing instructions for performing an efficient search of a dataset of multidimensional points that, when executed by a computer cause the computer to:
assign partitions of the dataset of multidimensional points to a plurality of local memory nodes of a multicore machine having a processing unit for each local memory node;
receive a search query corresponding to a given multidimensional point;
store the partitions of the dataset into the local memory nodes to which they are assigned;
store index building parameters, including a plurality of search distances, into the local memory nodes;
build, with the processing unit associated with each of the local memory nodes in parallel, a sequence of locality sensitive hash indexes of the partition of the dataset in that local memory node, each locality sensitive hash index associated with one of the plurality of search distances;
perform, by use of the processing unit associated with each of the local memory nodes, parallel searching in the assigned partitions to identify candidate similarity matches to the given multidimensional point, the parallel searching for each processing unit and local memory node progressing through the sequence of locality sensitive hash indexes associated with the plurality of search distances;
provide, to a coordinator with each processing unit, an ongoing search result for each search distance from the given multidimensional point; and
regulate, with the coordinator, an extent of the parallel searching based on the ongoing search results to determine similarity matches in the dataset for the given multidimensional point.

14. The article of claim 13 , the storage medium storing instructions that when executed by the computer cause the computer to perform locality sensitive hash (LSH) index-based searching.

15. The article of claim 13 , wherein the local memory nodes comprise non-uniform memory architecture (NUMA) nodes.

Assignees

• Hewlett Packard Entpr Dev Lp

Inventors

• Li Jun
• Viswanathan Krishnamurthy
• Kim Mijung

Classifications

• G06F16/90339 Primary

  by using parallel associative memories or content-addressable memories · CPC title

• G06F16/2255

  Hash tables · CPC title

• G06F16/24532 Primary

  of parallel queries · CPC title

• G06F16/2264

  Multidimensional index structures · CPC title