Research map / Label-efficient and robust learning / Recognition and long-tail
Cheb-GR: Rethinking K-nearest Neighbor Search in Re-ranking for Person Re-identification
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Cheb-GR, a parameter-free GCN-based re-ranking method for person ReID that replaces k-nearest neighbor search with a Chebyshev-inequality-guided adaptive threshold for edge pruning, achieving much lower re-ranking time.
Problem
Re-ranking methods for person re-identification rely on k-nearest neighbor search, which is sequential and computationally expensive (Θ(N² log N)), limiting practical use on large galleries.
Approach
Build a gallery graph where edges are pruned by a per-image adaptive threshold (mean minus λ standard deviations of distances, justified via Chebyshev's inequality) instead of k-NN selection, convert remaining distances to similarities with an exponential kernel, and propagate features with a parameter-free graph convolution.
Key results
- On Market-1501 with AGW features, Cheb-GR reaches 93.0 mAP in 0.9 s versus 94.9 mAP in 43.3 s for GCR, roughly 50x faster than k-reciprocal re-ranking.
- On CUHK03 with TransReID features, Cheb-GR improves mAP from 75.4 to 85.4 (+10.0) at 0.5 s.
- In the cross-domain Market2Duke setting, Cheb-GR gets 33.0 mAP versus 31.9 for GCR, with 0.9 s runtime.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace k-nearest-neighbor search with Chebyshev-guided adaptive neighbor search | Cheb-GR for person re-identification · Market-1501, DukeMTMC, and CUHK03 | time (s) | Helped |
| replace k-nearest-neighbor search with Chebyshev-guided adaptive neighbor search | Cheb-GR with TransReID · Market-1501 | mAP: 93.2% vs 94.0% | Mixed |
| replace k-nearest-neighbor search with Chebyshev-guided adaptive neighbor search | Cheb-GR with AGW · Market2Duke | mAP: 33.0 vs 31.9 | Helped |
| increase λ from small values toward an appropriate value, then increase it beyond the optimum (ablation) | Cheb-GR · CUHK03 | mAP | Mixed |
| vary the number of feature-propagation iterations T (ablation) | Cheb-GR · CUHK03 | mAP | Mixed |
| use smaller γ when λ is small, and larger γ when λ is large (ablation) | Cheb-GR · CUHK03 | mAP | Mixed |
Surprising findings
- Cheb-GR outperforms GCR in cross-domain settings even though GCR is stronger in-domain, suggesting adaptive neighbor search may generalize better than k-NN.
- The transformer-based TransReID features are considerably more sensitive to the threshold hyperparameter λ than CNN-based AGW features.
Limitations
- Sensitive to the trade-off hyperparameter λ, which must be tuned per model and dataset.
- Quadratic memory scaling of the adjacency matrix limits scalability.
- Performance depends on features from triplet-loss-trained models.
Experimental setup
Datasets: Market-1501 DukeMTMC-reID CUHK03
Benchmarks: Market-1501 DukeMTMC-reID CUHK03 Market2Duke Market2CUHK03
Metrics: mAP Rank-1 mINP execution time (s)
Baselines: k-reciprocal re-ranking (KR) GCR ECN QE LBR
Builds on: GCR k-reciprocal re-ranking AGW TransReID Chebyshev's inequality
Closest papers by meaning
- Re-Ranking Person Re-Identification With k-Reciprocal Encoding (CVPR 2017 · similarity 0.91)
- A Pose-Sensitive Embedding for Person Re-Identification With Expanded Cross Neighborhood Re-Ranking (CVPR 2018 · similarity 0.90)
- Relation-Aware Global Attention for Person Re-Identification (CVPR 2020 · similarity 0.89)
- Diverse Knowledge Distillation for End-to-End Person Search (AAAI 2021 · similarity 0.88)
- CA-Jaccard: Camera-aware Jaccard Distance for Person Re-identification (CVPR 2024 · similarity 0.88)
- Learning Continual Compatible Representation for Re-indexing Free Lifelong Person Re-identification (CVPR 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.