High Average Utility Itemset (HAUI) mining is an improvement on High-Utility Itemset (HUI) mining widely used in various pattern mining applications. The utility measure is proportional to the length of the itemset, which is a key flaw in HUI mining. HAUI finds the itemsets by relating the usefulness of itemsets totheir length using an unbiased measure termed average utility. Pruning methods such as average-utility upper bound, revised tighter upper bound, and looser upper bound used to eliminate weak candidates, overestimates the average usefulness of itemsets, causing the mining process to slow down. In the proposed methodology, Upper Bound using Remaining Items Utility(UBRIU), Maximum Itemset Utility(MIU) and Sum of Maximum Utility in a Transaction(SMUT) are used to avoid processing unpromising candidate itemsets and efficiently minimise the search space and therefore the processing time. UBRIU value is used to check if the itemset can be extended or not. The key-value mapping structure used for storing the utility values reduces the lookup time compared to existing IL, IDUL structure. The performance of the proposed work is evaluated in terms of memory usage and the time taken for processing. The proposed algorithm is significantly faster than existing state-of-the-art HAUI mining algorithms and utilizes significantly less memory, according to experimental results. The proposed work increases the overall efficiency of the system by employing effective pruning algorithms for pruning poor candidate itemsets and an efficient data structure for storing utility values.