High utility co-location pattern (HUCP) mining refers to discovering a set of spatial features from a spatial dataset whose instances are not only closed in space but also have a high sum of utility participation ratios. The traditional HUCP does not consider the pattern length, resulting in short patterns and long patterns being treated unfairly, and long patterns are more likely to be high utility. Therefore, the high average utility co-location pattern (HAUCP), that takes the length of the pattern into account when computing its utility, is proposed. However, the pattern interestingness measurement, average utility ratio (AUR), does not satisfy the downward-closure property, thus current mining HAUCP algorithms are still inefficient since many candidates are examined. This paper proposes an upper bound to prune unnecessary candidates and designs an efficient algorithm for mining HAUCPs. First, neighboring instances are enumerated by using maximal cliques, and then they are further arranged into a specified two-level hash table structure. The keys in the first level are the initial possible candidates and the values are another hash table structure with keys that are spatial feature types and values are the instances in these maximal cliques. The upper bound of a candidate is quickly computed from this hash structure. If the upper bound value is lower than the minimum utility threshold set by users, it can be directly determined as a non-HAUCP without executing the participating instance search process. The results of extensive experiments that are conducted on both synthetic and real-world datasets show that the designed algorithm outperforms the existing algorithms.