In order to leverage computational complexity and avoid information losses, “big data” analysis requires a new class of algorithms and methods to be designed and implemented. In this sense, information theory-based techniques can play a key role to effectively unveil change and anomaly patterns within big data sets. A framework that aims at detecting the anomaly patterns of a given dataset is introduced. The proposed method, namely PROMODE, relies on a representation of the given dataset performed by means of undirected bipartite graphs. Then the anomalies are searched and detected by progressively spanning the graph. The proposed architecture delivers a computational load that is less than that carried by typical frameworks in literature, so that PROMODE can be considered as a valid algorithm for efficient detection of change patterns in remotely sensed big data.