{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T01:39:57Z","timestamp":1785548397454,"version":"3.56.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,6,29]],"date-time":"2017-06-29T00:00:00Z","timestamp":1498694400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"International Research Centres in Singapore Funding Initiative"},{"DOI":"10.13039\/501100001381","name":"National Research Foundation, Prime Ministers Office, Singapore","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001381","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61371192"],"award-info":[{"award-number":["61371192"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Key Laboratory Foundation of the Chinese Academy of Sciences","award":["CXJJ-17S044"],"award-info":[{"award-number":["CXJJ-17S044"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2017,11,30]]},"abstract":"<jats:p>Feature selection (FS) is an important technique in machine learning and data mining, especially for large-scale high-dimensional data. Most existing studies have been restricted to batch learning, which is often inefficient and poorly scalable when handling big data in real world. As real data may arrive sequentially and continuously, batch learning has to retrain the model for the new coming data, which is very computationally intensive. Online feature selection (OFS) is a promising new paradigm that is more efficient and scalable than batch learning algorithms. However, existing online algorithms usually fall short in their inferior efficacy. In this article, we present a novel second-order OFS algorithm that is simple yet effective, very fast and extremely scalable to deal with large-scale ultra-high dimensional sparse data streams. The basic idea is to exploit the second-order information to choose the subset of important features with high confidence weights. Unlike existing OFS methods that often suffer from extra high computational cost, we devise a novel algorithm with a MaxHeap-based approach, which is not only more effective than the existing first-order algorithms, but also significantly more efficient and scalable. Our extensive experiments validated that the proposed technique achieves highly competitive accuracy as compared with state-of-the-art batch FS methods, meanwhile it consumes significantly less computational cost that is orders of magnitude lower. Impressively, on a billion-scale synthetic dataset (1-billion dimensions, 1-billion non-zero features, and 1-million samples), the proposed algorithm takes less than 3 minutes to run on a single PC.<\/jats:p>","DOI":"10.1145\/3070646","type":"journal-article","created":{"date-parts":[[2017,6,30]],"date-time":"2017-06-30T12:36:19Z","timestamp":1498826179000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":31,"title":["Large-Scale Online Feature Selection for Ultra-High Dimensional Sparse Data"],"prefix":"10.1145","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4392-1307","authenticated-orcid":false,"given":"Yue","family":"Wu","sequence":"first","affiliation":[{"name":"University of Science and Technology of China, Singapore Management University, Hefei, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Steven C. H.","family":"Hoi","sequence":"additional","affiliation":[{"name":"Singapore Management University, Stamford Road, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tao","family":"Mei","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, Microsoft Research Asia, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nenghai","family":"Yu","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, Hefei, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,6,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2015.05.014"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-012-0487-8"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1248547.1248566"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1699571.1699577"},{"key":"e_1_2_1_5_1","volume-title":"Advances in Neural Information Processing Systems (NIPS\u201909). Curran Associates","author":"Crammer Koby"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-013-5327-x"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence (AAAI\u201915)","author":"Ding Yi","year":"2015"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390190"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2021068"},{"key":"e_1_2_1_10_1","unstructured":"M. Everingham L. Van Gool C. K. I. Williams J. Winn and A. Zisserman. 2007. The PASCAL Visual Object Classes Challenge 2007 (VOC2007) Results. (2007). Retrieved from http:\/\/www.pascal-network.org\/challenges\/VOC\/voc2007\/workshop\/index.html.  M. Everingham L. Van Gool C. K. I. Williams J. Winn and A. Zisserman. 2007. The PASCAL Visual Object Classes Challenge 2007 (VOC2007) Results. (2007). Retrieved from http:\/\/www.pascal-network.org\/challenges\/VOC\/voc2007\/workshop\/index.html."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1390681.1442794"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the T28th AAAI Conference on Artificial Intelligence (AAAI\u201914)","author":"Gao Xingyu","year":"2014"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1102351.1102383"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2351316.2351329"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2627450"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2008.08.001"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806521"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2015.01.023"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2015.07.005"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00043-X"},{"key":"e_1_2_1_21_1","volume-title":"Hinton","author":"Krizhevsky Alex","year":"2012"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neunet.2014.06.011"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2015.10.002"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13735-016-0117-4"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.66"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the JMLR Workshop and Conference Proceedings (ACML\u201913)","volume":"29","author":"Lu Jing","year":"2013"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the Artificial Intelligence and Statistics. 493--500","author":"Ma Justin","year":"2010"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2014.07.015"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2015.08.022"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2005.159"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 20th Annual International Conference on Machine Learning (ICML\u201903)","author":"Perkins Simon","year":"2003"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/int.21833"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1037\/h0042519"},{"key":"e_1_2_1_34_1","unstructured":"K. Simonyan and A. Zisserman. 2014. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556.  K. Simonyan and A. Zisserman. 2014. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2638579"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783374"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 13th AAAI Conference on Artificial Intelligence (AAAI\u201916)","author":"Wang Chenguang","year":"2016"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2014.46"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 29th International Conference on Machine Learning (ICML\u201912)","author":"Wang Jialei"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2932193"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.32"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2008.05.010"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/3104322.3104469"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1553374.1553520"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499907.2499909"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neunet.2015.08.004"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 20th International Conference on Machine Learning (ICML\u201903)","volume":"3","author":"Yu Lei","year":"2003"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCI.2014.2326099"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.222"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the International Conference on Machine Learning (ICML\u201903)","author":"Zinkevich Martin","year":"2003"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3070646","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3070646","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:27Z","timestamp":1750217427000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3070646"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,29]]},"references-count":50,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11,30]]}},"alternative-id":["10.1145\/3070646"],"URL":"https:\/\/doi.org\/10.1145\/3070646","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,29]]},"assertion":[{"value":"2016-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}