# Accelerating Non-Maximum Suppression: A Graph Theory Perspective

arXiv: https://arxiv.org/abs/2409.20520 · HTML: https://mlsanity.com/paper/2409.20520/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 47 references that are in the map.
- First posted on arXiv 30 Sep 2024.

## Builds on (most cited first, 28 of 28)

- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks](https://mlsanity.com/paper/1506.01497/) (2015)
- [Mask R-CNN](https://mlsanity.com/paper/1703.06870/) (2017)
- [You Only Look Once: Unified, Real-Time Object Detection](https://mlsanity.com/paper/1506.02640/) (2015)
- [SSD: Single Shot MultiBox Detector](https://mlsanity.com/paper/1512.02325/) (2015)
- [Fast R-CNN](https://mlsanity.com/paper/1504.08083/) (2015)
- [YOLOv3: An Incremental Improvement](https://mlsanity.com/paper/1804.02767/) (2018)
- [Rich feature hierarchies for accurate object detection and semantic segmentation](https://mlsanity.com/paper/1311.2524/) (2013)
- [YOLOv4: Optimal Speed and Accuracy of Object Detection](https://mlsanity.com/paper/2004.10934/) (2020)
- [YOLO9000: Better, Faster, Stronger](https://mlsanity.com/paper/1612.08242/) (2016)
- [DETRs Beat YOLOs on Real-time Object Detection](https://mlsanity.com/paper/2304.08069/) (2023)
- [RepVGG: Making VGG-style ConvNets Great Again](https://mlsanity.com/paper/2101.03697/) (2021)
- [YOLACT: Real-time Instance Segmentation](https://mlsanity.com/paper/1904.02689/) (2019)
- [Deep Learning for Medical Image Analysis](https://mlsanity.com/paper/1708.08987/) (2017)
- [Soft-NMS -- Improving Object Detection With One Line of Code](https://mlsanity.com/paper/1704.04503/) (2017)
- [CSPNet: A New Backbone that can Enhance Learning Capability of CNN](https://mlsanity.com/paper/1911.11929/) (2019)
- [Multiple Object Tracking: A Literature Review](https://mlsanity.com/paper/1409.7618/) (2014)
- [Bounding Box Regression with Uncertainty for Accurate Object Detection](https://mlsanity.com/paper/1809.08545/) (2018)
- [Learning non-maximum suppression](https://mlsanity.com/paper/1705.02950/) (2017)
- [3D Object Detection for Autonomous Driving: A Survey](https://mlsanity.com/paper/2106.10823/) (2021)
- [Enhancing Geometric Factors in Model Learning and Inference for Object Detection and Instance Segmentation](https://mlsanity.com/paper/2005.03572/) (2020)
- [Adaptive NMS: Refining Pedestrian Detection in a Crowd](https://mlsanity.com/paper/1904.03629/) (2019)
- [TAMM: TriAdapter Multi-Modal Learning for 3D Shape Understanding](https://mlsanity.com/paper/2402.18490/) (2024)
- [NOH-NMS: Improving Pedestrian Detection by Nearby Objects Hallucination](https://mlsanity.com/paper/2007.13376/) (2020)
- [A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree](https://mlsanity.com/paper/2111.15478/) (2021)
- [ASAP-NMS: Accelerating Non-Maximum Suppression Using Spatially Aware Priors](https://mlsanity.com/paper/2007.09785/) (2020)
- [PSRR-MaxpoolNMS: Pyramid Shifted MaxpoolNMS with Relationship Recovery](https://mlsanity.com/paper/2105.12990/) (2021)

## Built on by (most cited first, 2 of 2)

- [A3: Towards Advertising Aesthetic Assessment](https://mlsanity.com/paper/2603.24037/) (2026)
- [Counterfactual Anatomy-guided Spatial-Temporal Decoding for Annotation-Free Hallucination Mitigation in Medical VLMs](https://mlsanity.com/paper/2608.17427/) (2026)

## Abstract (arXiv)

Non-maximum suppression (NMS) is an indispensable post-processing step in object detection. With the continuous optimization of network models, NMS has become the ``last mile'' to enhance the efficiency of object detection. This paper systematically analyzes NMS from a graph theory perspective for the first time, revealing its intrinsic structure. Consequently, we propose two optimization methods, namely QSI-NMS and BOE-NMS. The former is a fast recursive divide-and-conquer algorithm with negligible mAP loss, and its extended version (eQSI-NMS) achieves optimal complexity of O(nlog n). The latter, concentrating on the locality of NMS, achieves an optimization at a constant level without an mAP loss penalty. Moreover, to facilitate rapid evaluation of NMS methods for researchers, we introduce NMS-Bench, the first benchmark designed to comprehensively assess various NMS methods. Taking the YOLOv8-N model on MS COCO 2017 as the benchmark setup, our method QSI-NMS provides 6.2× speed of original NMS on the benchmark, with a 0.1% decrease in mAP. The optimal eQSI-NMS, with only a 0.3% mAP decrease, achieves 10.7× speed. Meanwhile, BOE-NMS exhibits 5.1× speed with no compromise in mAP.