Working notes: ideas for parallelizing on one node - psastras/vocabtree GitHub Wiki

Training

• Parallel cv::kmeans. I expect this is very expensive for the initial large number of images, for, at minimum, the root node (the initial branch) we should parallelize this k-means. Not much other work can be done on other threads before the initial split
• Parallel branching. Each child for a node should be able to be computed completely in parallel. Maybe just split the first level (depending on the split)
• for loops in VocabTree::buildTreeRecursive could be parallel (including the branching mentioned above)
• Inserting images and getting data vectors for them could be parallelized- just a for loop over all images. Could vector instructions work for this too?
• Final iteration over the map. I don't know if this can be done in parallel, not familiar enough with iterators and their restrictions

Searching

• VocabTree::generateVector iterates over all descriptors. This could be parallel. Training uses this function as well. If we use the above idea of parallelizing over images then we wouldn't want to further parallelize over the descriptors for training, so we may need to condition on whether the function is being used for training or searching. PROBLEM: each work on descriptors use a shared vector and set, these shared data structures may make it harder/slower to parallelize.
• Can run computations once you have all the possible images in parallel, but not completely trivial, including the sorting