An apparatus that employs a directional antenna system updates a beam pattern table that includes entries corresponding to each of the other apparatuses with which the apparatus communicates. For example, for each of the other apparatuses, the beam pattern table may specify the antenna weights to be used to provide a quasi-omni-directional beam pattern, a sector level beam pattern, and a refined beam pattern when communicating with that other apparatus. In some aspects, the beam pattern table includes one or more characteristics associated with each of the beam patterns. These characteristics may be used in conjunction with a beam search criterion to trigger updating of the beam pattern table.