search

markmfredrickson / optmatch

Functions for optimal matching in R
https://markmfredrickson.github.io/optmatch
Other
47 stars 14 forks source link

Faster fullmatch possible? #219

Closed jay-sf closed 2 years ago

jay-sf commented 2 years ago

Hi, I was wondering if you guys are working there on a faster version of fullmatch, and what the current status is. A faster version would be really great, since currently I use it heavily and I noticed that computation time increases drastically with sample size. Is there a faster version particularly of fullmatch available e.g. written in C, or is it possible to speed up fullmatch by parallel computing? Thanks!

markmfredrickson commented 2 years ago

Thanks for the interest. The actual matching portion of fullmatch is written in a lower level language (either fortran or C++ depending on which backend you use). These algorithms are some of the currently fastest implementations available. These algorithms tend to be close to O(n^3) for run time, so you are right that the time scaling can increase quite a bit as you go from moderate to large problems.

There are some parallelized "auction" algorithms. I don't get the impression the implementations are ready for prime time, but they are on our radar screen, and it is something we would like to get to at some point in the future.

As you noticed, we are looking for practical ways to speed up matching problems in some common cases. One area we've identified is trying to save information across similar matching problems so that if users want to tweak or update a match, we can start from the results of the previous match to save time. We've also identified some common designs that can be sped up, such as matching on a single scalar index (like a propensity score). I can't offer any particular timeline on this, but it is on our agenda.

Again, thanks for the interest. I wish I could offer more concrete timelines.

jay-sf commented 2 years ago

@markmfredrickson Thanks Mark, I'm glad to hear that, I'll stay tuned! Cheers!

josherrickson commented 2 years ago

@jay-sf If you haven't already seen this vignette, it details how if you can split your matching problem into several subproblems, you can later combine the matches and ultimately greatly speed up matching performance.

jay-sf commented 2 years ago

@josherrickson Very helpful, I definitely will have a look into this, thanks!