Between May 2009 and May 2010, the IceCube neutrino detector at the South
Pole recorded 32 billion muons generated in air showers produced by cosmic rays
with a median energy of 20 TeV. With a data set of this size, it is possible to
probe the southern sky for per-mille anisotropy on all angular scales in the
arrival direction distribution of cosmic rays. Applying a power spectrum
analysis to the relative intensity map of the cosmic ray flux in the southern
hemisphere, we show that the arrival direction distribution is not isotropic,
but shows significant structure on several angular scales. In addition to
previously reported large-scale structure in the form of a strong dipole and
quadrupole, the data show small-scale structure on scales between 15 degrees
and 30 degrees. The skymap exhibits several localized regions of significant
excess and deficit in cosmic ray intensity. The relative intensity of the
smaller-scale structures is about a factor of 5 weaker than that of the dipole
and quadrupole structure. The most significant structure, an excess localized
at right ascension 122.4 degrees and declination -47.4 degrees, extends over at
least 20 degrees in right ascension and has a post-trials significance of 5.3
sigma. The origin of this anisotropy is still unknown.