Temporal data contain time-stamping information that affects the results of data mining. Traditional techniques for finding frequent itemsets assume that datasets are static and the induced rules are relevant across the entire dataset. However, this is not the case when data is temporal. In this paper, we are trying to improve the efficiency of mining frequent itemsets on temporal data. Since patterns can hold in either all or some of the intervals, we propose a new algorithm to restrict time intervals, which is called frequent itemset mining with time cubes. Our focus is developing an efficient algorithm for this mining problem by extending the well-known a priori algorithm. The notion of time cubes is proposed to handle time hierarchies. This is the way by which the patterns that happen periodically, during a time interval or both, are recognized. A new density threshold is also proposed to solve the overestimating problem of time periods and also make sure that discovered patterns are valid. We evaluate our algorithms via experiments