Additional spatial dimensions, essential for formulating quantum gravity in the context of string theory, have been proposed as a solution to the standard model hierarchy problem. In the model of Arkani-Hamed, Dimopoulos, and Dvali (ADD) compactified extra dimensions are postulated. Gravity is assumed to propagate in the entire higher-dimensional space, while particles of the standard model are confined to a 3-dimensional slice of the multidimensional space. The resulting fundamental Planck energy scale in the ADD model can be reduced to significantly lower values than suggested by the apparent Planck mass M(Planck) ≈ 1.2 · 10^19 GeV deduced for 3 spatial dimensions. At the LHC, virtual graviton exchange can lead to changes in the production rate of muon and electron pairs at very high invariant masses. We are searching for such deviations in the data taken by CMS.