  Hyperdimensional computing (HDC) is a method to perform classification that
uses binary vectors with high dimensions and the majority rule. This approach
has the potential to be energy-efficient and hence deemed suitable for
resource-limited platforms due to its simplicity and massive parallelism.
However, in order to achieve high accuracy, HDC sometimes uses hypervectors
with tens of thousands of dimensions. This potentially negates its efficiency
advantage. In this paper, we examine the necessity of such high dimensions and
conduct a detailed theoretical analysis of the relationship between hypervector
dimensions and accuracy. Our results demonstrate that as the dimension of the
hypervectors increases, the worst-case/average-case HDC prediction accuracy
with the majority rule decreases. Building on this insight, we develop HDC
models that use binary hypervectors with dimensions orders of magnitude lower
than those of state-of-the-art HDC models while maintaining equivalent or even
improved accuracy and efficiency. For instance, on the MNIST dataset, we
achieve 91.12% HDC accuracy in image classification with a dimension of only
64. Our methods perform operations that are only 0.35% of other HDC models with
dimensions of 10,000. Furthermore, we evaluate our methods on ISOLET, UCI-HAR,
and Fashion-MNIST datasets and investigate the limits of HDC computing.
