  Autonomous Driving (AD) systems extensively manipulate 3D point clouds for
object detection and vehicle localization. Thereby, efficient processing of 3D
point clouds is crucial in these systems. In this work we propose K-D Bonsai, a
technique to cut down memory usage during radius search, a critical building
block of point cloud processing. K-D Bonsai exploits value similarity in the
data structure that holds the point cloud (a k-d tree) to compress the data in
memory. K-D Bonsai further compresses the data using a reduced floating-point
representation, exploiting the physically limited range of point cloud values.
For easy integration into nowadays systems, we implement K-D Bonsai through
Bonsai-extensions, a small set of new CPU instructions to compress, decompress,
and operate on points. To maintain baseline safety levels, we carefully craft
the Bonsai-extensions to detect precision loss due to compression, allowing
re-computation in full precision to take place if necessary. Therefore, K-D
Bonsai reduces data movement, improving performance and energy efficiency,
while guaranteeing baseline accuracy and programmability. We evaluate K-D
Bonsai over the euclidean cluster task of Autoware.ai, a state-of-the-art
software stack for AD. We achieve an average of 9.26% improvement in end-to-end
latency, 12.19% in tail latency, and a reduction of 10.84% in energy
consumption. Differently from expensive accelerators proposed in related work,
K-D Bonsai improves radius search with minimal area increase (0.36%).
