In this paper we present a simple technique that uses background information to improve mining the frequent patterns of structured data. This technique uses a heuristic function that remaps the search space in a way the greatly reduces the number of costly subgraph isomorphism tests, without using space-expensive data structures. We illustrate our approach on a popular structured data mining problem, called the frequent subgraph mining problem, and show, through experiments on synthetic and real-life data, that this simple approach has advantages over other frequent pattern mining algorithms.