Brute force searching
Your current approach would benefit from sorted inputs.

But an even simpler approach would be to ignore the irrelevant verbs and rephrase the problem like this:


  A noun phrase is a pair of nouns. We are given two input sets of noun phrases, and must compute set intersection, using a problem specific notion of "phrase equality".


This implies a linear O(n) input pre-processing pass, where you populate a HashSet with each input phrase, X+" "+Y.

With that in hand, your task is trivial. Scan the other collection of phrases, and for each phrase make two set membership queries: is X+" "+Y or Y+" "+X present in the set?

BTW, your identifier storeAsserions seems to be a typo for storeAssertions. And please include a space after keywords like if &amp; for.