{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,20]],"date-time":"2025-08-20T12:30:29Z","timestamp":1755693029008},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:p>\n            Thanks to the popularity of GPU and the growth of its computational power, more and more deep learning tasks, such as face recognition, image retrieval and word embedding, can take advantage of extreme classification to improve accuracy. However, it remains a big challenge to train a deep model with millions of classes efficiently due to the huge memory and computation consumption in the last layer. By sampling a small set of classes to avoid the total classes calculation, sampling-based approaches have been proved to be an effective solution. But most of them suffer from the following two issues: i) the important classes are ignored or only partly sampled, such as the methods using random sampling scheme or retrieval techniques of low recall (e.g., locality-sensitive hashing), resulting in the degradation of accuracy; ii) inefficient implementation owing to incompatibility with GPU, like selective softmax. It uses hashing forest to help select classes, but the search process is implemented in CPU. To address the above issues, we propose a new sampling-based softmax called\n            <jats:italic>ANN Softmax<\/jats:italic>\n            in this paper. Specifically, we employ binary quantization with inverted file system to improve the recall of important classes. With the help of dedicated kernel design, it can be totally parallelized in mainstream training framework. Then, we find the size of important classes that are recalled by each training sample has a great impact on the final accuracy, so we introduce sample grouping optimization to well approximate the full classes training. Experimental evaluations on two tasks (Embedding Learning and Classification) and ten datasets (e.g., MegaFace, ImageNet, SKU datasets) demonstrate our proposed method maintains the same precision as Full Softmax for different loss objectives, including cross entropy loss, ArcFace, CosFace and D-Softmax loss, with only 1\/10 sampled classes, which outperforms the state-of-the-art techniques. Moreover, we implement\n            <jats:italic>ANN Soft-max<\/jats:italic>\n            in a complete GPU pipeline that can accelerate the training more than 4.3X. Equipped our method with a 256 GPUs cluster, the time of training a classifier of 300 million classes on our SKU-300M dataset can be reduced to ten days.\n          <\/jats:p>","DOI":"10.14778\/3485450.3485451","type":"journal-article","created":{"date-parts":[[2022,1,14]],"date-time":"2022-01-14T23:26:50Z","timestamp":1642202810000},"page":"1-10","source":"Crossref","is-referenced-by-count":6,"title":["ANN softmax"],"prefix":"10.14778","volume":"15","author":[{"given":"Kang","family":"Zhao","sequence":"first","affiliation":[{"name":"Alibaba Group, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liuyihan","family":"Song","sequence":"additional","affiliation":[{"name":"Alibaba Group, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yingya","family":"Zhang","sequence":"additional","affiliation":[{"name":"Alibaba Group, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pan","family":"Pan","sequence":"additional","affiliation":[{"name":"Alibaba Group, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yinghui","family":"Xu","sequence":"additional","affiliation":[{"name":"Alibaba Group, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rong","family":"Jin","sequence":"additional","affiliation":[{"name":"Alibaba Group, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,1,14]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Tensorflow: A system for large-scale machine learning. In 12th {USENIX} symposium on operating systems design and implementation (OSDI). 265--283.","author":"Abadi Mart\u00edn","year":"2016","unstructured":"Mart\u00edn Abadi , Paul Barham , Jianmin Chen , Zhifeng Chen , Andy Davis , Jeffrey Dean , Matthieu Devin , Sanjay Ghemawat , Geoffrey Irving , Michael Isard , 2016 . Tensorflow: A system for large-scale machine learning. In 12th {USENIX} symposium on operating systems design and implementation (OSDI). 265--283. Mart\u00edn Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. 2016. Tensorflow: A system for large-scale machine learning. In 12th {USENIX} symposium on operating systems design and implementation (OSDI). 265--283."},{"key":"e_1_2_1_2_1","volume-title":"Partial FC: Training 10 Million Identities on a Single Machine. arXiv preprint arXiv:2010.05222","author":"An Xiang","year":"2020","unstructured":"Xiang An , Xuhan Zhu , Yang Xiao , Lan Wu , Ming Zhang , Yuan Gao , Bin Qin , Debing Zhang , and Ying Fu . 2020 . Partial FC: Training 10 Million Identities on a Single Machine. arXiv preprint arXiv:2010.05222 (2020). Xiang An, Xuhan Zhu, Yang Xiao, Lan Wu, Ming Zhang, Yuan Gao, Bin Qin, Debing Zhang, and Ying Fu. 2020. Partial FC: Training 10 Million Identities on a Single Machine. arXiv preprint arXiv:2010.05222 (2020)."},{"key":"e_1_2_1_3_1","volume-title":"International Conference on Very Large Data Bases (VLDB). 288--299","author":"Andr\u00e9 Fabien","year":"2016","unstructured":"Fabien Andr\u00e9 , Anne-Marie Kermarrec , and Nicolas Le Scouarnec . 2016 . Cache locality is not enough: High-performance nearest neighbor search with product quantization fast scan . In International Conference on Very Large Data Bases (VLDB). 288--299 . Fabien Andr\u00e9, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. 2016. Cache locality is not enough: High-performance nearest neighbor search with product quantization fast scan. In International Conference on Very Large Data Bases (VLDB). 288--299."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3204028.3204034"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICIP.2018.8451704"},{"key":"e_1_2_1_6_1","volume-title":"Strategies for training large vocabulary neural language models. arXiv preprint arXiv:1512.04906","author":"Chen Welin","year":"2015","unstructured":"Welin Chen , David Grangier , and Michael Auli . 2015. Strategies for training large vocabulary neural language models. arXiv preprint arXiv:1512.04906 ( 2015 ). Welin Chen, David Grangier, and Michael Auli. 2015. Strategies for training large vocabulary neural language models. arXiv preprint arXiv:1512.04906 (2015)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2009.5206848"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2019.00482"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3430915.3430921"},{"key":"e_1_2_1_10_1","volume-title":"Conference of the North American Chapter of the Association for Computational Linguistics (NAACL). 4171--4186","author":"Devlin Jacob","year":"2019","unstructured":"Jacob Devlin , Ming-Wei Chang , Kenton Lee , and Kristina Toutanova . 2019 . Bert: Pre-training of deep bidirectional transformers for language understanding . In Conference of the North American Chapter of the Association for Computational Linguistics (NAACL). 4171--4186 . Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. Bert: Pre-training of deep bidirectional transformers for language understanding. In Conference of the North American Chapter of the Association for Computational Linguistics (NAACL). 4171--4186."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46475-6_48"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2018.00384"},{"key":"e_1_2_1_13_1","volume-title":"Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph. In International Conference on Very Large Data Bases (VLDB). 461--474","author":"Fu Cong","year":"2019","unstructured":"Cong Fu , Chao Xiang , Changxu Wang , and Deng Cai . 2019 . Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph. In International Conference on Very Large Data Bases (VLDB). 461--474 . Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph. In International Conference on Very Large Data Bases (VLDB). 461--474."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588565"},{"key":"e_1_2_1_15_1","volume-title":"International Conference on Very Large Data Bases (VLDB). 518--529","author":"Gionis Aristides","year":"1999","unstructured":"Aristides Gionis , Piotr Indyk , Rajeev Motwani , 1999 . Similarity search in high dimensions via hashing . In International Conference on Very Large Data Bases (VLDB). 518--529 . Aristides Gionis, Piotr Indyk, Rajeev Motwani, et al. 1999. Similarity search in high dimensions via hashing. In International Conference on Very Large Data Bases (VLDB). 518--529."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2001.940893"},{"key":"e_1_2_1_17_1","volume-title":"large minibatch sgd: Training imagenet in 1 hour. arXiv preprint arXiv:1706.02677","author":"Goyal Priya","year":"2017","unstructured":"Priya Goyal , Piotr Doll\u00e1r , Ross Girshick , Pieter Noordhuis , Lukasz Wesolowski , Aapo Kyrola , Andrew Tulloch , Yangqing Jia , and Kaiming He. 2017. Accurate , large minibatch sgd: Training imagenet in 1 hour. arXiv preprint arXiv:1706.02677 ( 2017 ). Priya Goyal, Piotr Doll\u00e1r, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. 2017. Accurate, large minibatch sgd: Training imagenet in 1 hour. arXiv preprint arXiv:1706.02677 (2017)."},{"key":"e_1_2_1_18_1","volume-title":"International Conference on Artificial Intelligence and Statistics (AISTATS). 297--304","author":"Gutmann Michael","year":"2010","unstructured":"Michael Gutmann and Aapo Hyv\u00e4rinen . 2010 . Noise-contrastive estimation: A new estimation principle for unnormalized statistical models . In International Conference on Artificial Intelligence and Statistics (AISTATS). 297--304 . Michael Gutmann and Aapo Hyv\u00e4rinen. 2010. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In International Conference on Artificial Intelligence and Statistics (AISTATS). 297--304."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.90"},{"key":"e_1_2_1_20_1","volume-title":"Softmax Dissection: Towards Understanding Intra-and Inter-class Objective for Embedding Learning. In The AAAI Conference on Artificial Intelligence (AAAI)","volume":"34","author":"He Lanqing","year":"2020","unstructured":"Lanqing He , Zhongdao Wang , Yali Li , and Shengjin Wang . 2020 . Softmax Dissection: Towards Understanding Intra-and Inter-class Objective for Embedding Learning. In The AAAI Conference on Artificial Intelligence (AAAI) , Vol. 34 . 10957--10964. Lanqing He, Zhongdao Wang, Yali Li, and Shengjin Wang. 2020. Softmax Dissection: Towards Understanding Intra-and Inter-class Objective for Embedding Learning. In The AAAI Conference on Artificial Intelligence (AAAI), Vol. 34. 10957--10964."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.527"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342276"},{"key":"e_1_2_1_25_1","first-page":"1097","article-title":"Imagenet classification with deep convolutional neural networks","volume":"25","author":"Krizhevsky Alex","year":"2012","unstructured":"Alex Krizhevsky , Ilya Sutskever , and Geoffrey E Hinton . 2012 . Imagenet classification with deep convolutional neural networks . Advances in Neural Information Processing Systems (NeurIPS) 25 , 1097 -- 1105 . Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. 2012. Imagenet classification with deep convolutional neural networks. Advances in Neural Information Processing Systems (NeurIPS) 25, 1097--1105.","journal-title":"Advances in Neural Information Processing Systems (NeurIPS)"},{"key":"e_1_2_1_26_1","volume-title":"LSH Softmax: Sub-Linear Learning and Inference of the Softmax Layer in Deep Architectures. In Workshop of Advances in Neural Information Processing Systems (NeurIPSW).","author":"Levy Daniel","year":"2017","unstructured":"Daniel Levy , Danlu Chen , and Stefano Ermon . 2017 . LSH Softmax: Sub-Linear Learning and Inference of the Softmax Layer in Deep Architectures. In Workshop of Advances in Neural Information Processing Systems (NeurIPSW). Daniel Levy, Danlu Chen, and Stefano Ermon. 2017. LSH Softmax: Sub-Linear Learning and Inference of the Softmax Layer in Deep Architectures. In Workshop of Advances in Neural Information Processing Systems (NeurIPSW)."},{"key":"e_1_2_1_27_1","volume-title":"International Conference on Very Large Data Bases (VLDB). 2549--2562","author":"Li Jinfeng","year":"2020","unstructured":"Jinfeng Li , Yuliang Li , Xiaolan Wang , and Wang-Chiew Tan . 2020 . Deep or simple models for semantic tagging? it depends on your data . In International Conference on Very Large Data Bases (VLDB). 2549--2562 . Jinfeng Li, Yuliang Li, Xiaolan Wang, and Wang-Chiew Tan. 2020. Deep or simple models for semantic tagging? it depends on your data. In International Conference on Very Large Data Bases (VLDB). 2549--2562."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415530"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352136"},{"key":"e_1_2_1_30_1","volume-title":"International Conference on Very Large Data Bases (VLDB). 950--961","author":"Lv Qin","year":"2007","unstructured":"Qin Lv , William Josephson , Zhe Wang , Moses Charikar , and Kai Li . 2007 . Multi-probe LSH: efficient indexing for high-dimensional similarity search . In International Conference on Very Large Data Bases (VLDB). 950--961 . Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. 2007. Multi-probe LSH: efficient indexing for high-dimensional similarity search. In International Conference on Very Large Data Bases (VLDB). 950--961."},{"key":"e_1_2_1_31_1","unstructured":"Tharun Medini Qixuan Huang Yiqiu Wang Vijai Mohan and Anshumali Shrivastava. 2019. Extreme classification in log memory using count-min sketch: A case study of amazon search with 50m products. In Advances in Neural Information Processing Systems (NeurIPS). 13244--13254.  Tharun Medini Qixuan Huang Yiqiu Wang Vijai Mohan and Anshumali Shrivastava. 2019. Extreme classification in log memory using count-min sketch: A case study of amazon search with 50m products. In Advances in Neural Information Processing Systems (NeurIPS). 13244--13254."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPRW.2017.250"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/WACV.2016.7477558"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2940014"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403342"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733024"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR42600.2020.00643"},{"key":"e_1_2_1_38_1","volume-title":"ODIN: Automated Drift Detection and Recovery in Video Analytics. In International Conference on Very Large Data Bases (VLDB). 2453--2465","author":"Suprem Abhijit","year":"2020","unstructured":"Abhijit Suprem , Joy Arulraj , Calton Pu , and Joao Ferreira . 2020 . ODIN: Automated Drift Detection and Recovery in Video Analytics. In International Conference on Very Large Data Bases (VLDB). 2453--2465 . Abhijit Suprem, Joy Arulraj, Calton Pu, and Joao Ferreira. 2020. ODIN: Automated Drift Detection and Recovery in Video Analytics. In International Conference on Very Large Data Bases (VLDB). 2453--2465."},{"key":"e_1_2_1_39_1","unstructured":"Ilya Sutskever Oriol Vinyals and Quoc V Le. 2014. Sequence to sequence learning with neural networks. In Advances in Neural Information Processing Systems (NeurIPS). 3104--3112.  Ilya Sutskever Oriol Vinyals and Quoc V Le. 2014. Sequence to sequence learning with neural networks. In Advances in Neural Information Processing Systems (NeurIPS). 3104--3112."},{"key":"e_1_2_1_40_1","volume-title":"Workshop of International Conference on Learning Representations (ICLRW).","author":"Vijayanarasimhan Sudheendra","year":"2015","unstructured":"Sudheendra Vijayanarasimhan , Jonathon Shlens , Rajat Monga , and Jay Yagnik . 2015 . Deep networks with large output spaces . In Workshop of International Conference on Learning Representations (ICLRW). Sudheendra Vijayanarasimhan, Jonathon Shlens, Rajat Monga, and Jay Yagnik. 2015. Deep networks with large output spaces. In Workshop of International Conference on Learning Representations (ICLRW)."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of Machine Learning and Systems (MLSys) 3","author":"Wang Guanhua","year":"2021","unstructured":"Guanhua Wang , Zhuang Liu , Brandon Hsieh , Siyuan Zhuang , Joseph Gonzalez , Trevor Darrell , and Ion Stoica . 2021 . sensAI: ConvNets Decomposition via Class Parallelism for Fast Inference on Live Data . Proceedings of Machine Learning and Systems (MLSys) 3 (2021). Guanhua Wang, Zhuang Liu, Brandon Hsieh, Siyuan Zhuang, Joseph Gonzalez, Trevor Darrell, and Ion Stoica. 2021. sensAI: ConvNets Decomposition via Class Parallelism for Fast Inference on Live Data. Proceedings of Machine Learning and Systems (MLSys) 3 (2021)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2018.00552"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.30"},{"key":"e_1_2_1_44_1","volume-title":"Accelerating Deep Learning with Millions of Classes. In European Conference on Computer Vision (ECCV). 711--726","author":"Yuan Zhuoning","year":"2020","unstructured":"Zhuoning Yuan , Zhishuai Guo , Xiaotian Yu , Xiaoyu Wang , and Tianbao Yang . 2020 . Accelerating Deep Learning with Millions of Classes. In European Conference on Computer Vision (ECCV). 711--726 . Zhuoning Yuan, Zhishuai Guo, Xiaotian Yu, Xiaoyu Wang, and Tianbao Yang. 2020. Accelerating Deep Learning with Millions of Classes. In European Conference on Computer Vision (ECCV). 711--726."},{"key":"e_1_2_1_45_1","volume-title":"The AAAI Conference on Artificial Intelligence (AAAI)","volume":"32","author":"Zhang Xingcheng","year":"2018","unstructured":"Xingcheng Zhang , Lei Yang , Junjie Yan , and Dahua Lin . 2018 . Accelerated training for massive classification via dynamic class selection . In The AAAI Conference on Artificial Intelligence (AAAI) , Vol. 32 . Xingcheng Zhang, Lei Yang, Junjie Yan, and Dahua Lin. 2018. Accelerated training for massive classification via dynamic class selection. In The AAAI Conference on Artificial Intelligence (AAAI), Vol. 32."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3372716.3372721"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219820"},{"key":"e_1_2_1_48_1","volume-title":"The AAAI Conference on Artificial Intelligence (AAAI)","volume":"28","author":"Zhao Kang","year":"2014","unstructured":"Kang Zhao , Hongtao Lu , and Jincheng Mei . 2014 . Locality preserving hashing . In The AAAI Conference on Artificial Intelligence (AAAI) , Vol. 28 . Kang Zhao, Hongtao Lu, and Jincheng Mei. 2014. Locality preserving hashing. In The AAAI Conference on Artificial Intelligence (AAAI), Vol. 28."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3357834"},{"key":"e_1_2_1_51_1","volume-title":"Cross-age lfw: A database for studying cross-age face recognition in unconstrained environments. arXiv preprint arXiv:1708.08197","author":"Zheng Tianyue","year":"2017","unstructured":"Tianyue Zheng , Weihong Deng , and Jiani Hu. 2017. Cross-age lfw: A database for studying cross-age face recognition in unconstrained environments. arXiv preprint arXiv:1708.08197 ( 2017 ). Tianyue Zheng, Weihong Deng, and Jiani Hu. 2017. Cross-age lfw: A database for studying cross-age face recognition in unconstrained environments. arXiv preprint arXiv:1708.08197 (2017)."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3485450.3485451","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:40:11Z","timestamp":1672224011000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3485450.3485451"}},"subtitle":["acceleration of extreme classification training"],"short-title":[],"issued":{"date-parts":[[2021,9]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["10.14778\/3485450.3485451"],"URL":"https:\/\/doi.org\/10.14778\/3485450.3485451","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,9]]}}}