This is a big problem I have been facing. You will notice that all the images I use in my c++ demos are small for this reason. I'm trying to solve this scaling issue but I wasn't able to get a solution quickly so I decided to release this and continue to work on it and hopefully release an improved version at some point (or let other people work on it and hopefully find solutions).
I find it's the combination of a poor keypoint finder, noise and needing to be able to match partial images is the problem. If I could guarantee that 99% of the keypoints in the query image would be in the matching image and that the extracted hashes wouldn't be affected (hugely) by noise and that most of the query image was present in the matching image then I could simply discard a huge amount of the triangles and only query for a manageable number of them. Obviously that's a lot to ask but the better I can make each part the more options I will have for culling the hashes. For the moment I need to query as many fragments as possible to have a good chance of finding the matching image.