I found this cool paper that says that removing some of the tests in elkans algorithm can speed it up:
http://proceedings.mlr.press/v48/newling16.pdf

The paper also looks at a simplified ying-yang algorithm, which I still think is interesting (apparently mostly for low-dim spaces and when Elkans needs too much RAM).