В моей последней работе у нас была похожая проблема: нам приходилось обнаруживать изменения, вставки и удаления определенных элементов между двумя файлами XML. Файлы не были произвольными XML; они должны были придерживаться нашего XSD.
Наше решение заключалось в реализации своего рода сортировки слиянием: анализ файлов (с использованием SAX-анализатора, а не DOM-анализатора, чтобы разрешить произвольно большие файлы) и сохранение проанализированных данных в отдельных HashMaps. Затем мы сравнили содержимое двух карт, используя алгоритм с сортировкой слиянием.
Естественно, чем больше файлы, тем больше мы испытываем нехватки памяти, поэтому я в конечном итоге написал класс FileHashMap, который помещал пространство значений HashMap в файлы с произвольным доступом. Хотя это теоретически медленнее, это решение позволило нашим сравнениям работать с очень большими файлами, не затрагивая условия OutOfMemoryError. (Версия этого класса FileHashMap доступна в этой библиотеке: http://www.clapper.org/software/java/util/)
Я понятия не имею, является ли то, что я только что описал, даже отдаленно близко к тому, что вам нужно, но я решил поделиться этим, на всякий случай.
Удачи.