{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T09:57:47Z","timestamp":1790243867450,"version":"4.1.0"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,7,25]],"date-time":"2019-07-25T00:00:00Z","timestamp":1564012800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,7,25]]},"DOI":"10.1145\/3292500.3330923","type":"proceedings-article","created":{"date-parts":[[2019,7,26]],"date-time":"2019-07-26T13:17:26Z","timestamp":1564147046000},"page":"520-528","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Global String Kernel with Random Features"],"prefix":"10.1145","author":[{"given":"Lingfei","family":"Wu","sequence":"first","affiliation":[{"name":"IBM Research, Elmsford, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ian En-Hsu","family":"Yen","sequence":"additional","affiliation":[{"name":"CMU, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Siyu","family":"Huo","sequence":"additional","affiliation":[{"name":"IBM Research, Yorktown Heights, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Liang","family":"Zhao","sequence":"additional","affiliation":[{"name":"George Mason University, Fairfax, VA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kun","family":"Xu","sequence":"additional","affiliation":[{"name":"IBM Research, Yorktown Heights, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Liang","family":"Ma","sequence":"additional","affiliation":[{"name":"IBM Research, Yorktown Heights, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shouling","family":"Ji","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, UNK, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Charu","family":"Aggarwal","sequence":"additional","affiliation":[{"name":"IBM Research, Yorktown Heights, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,7,25]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1961189.1961199"},{"key":"e_1_3_2_1_2_1","volume-title":"Efficient one-vs-one kernel ridge regression for speech recognition","author":"Chen Jie","unstructured":"Jie Chen , Lingfei Wu , Kartik Audhkhasi , Brian Kingsbury , and Bhuvana Ramab- hadrari. 2016. Efficient one-vs-one kernel ridge regression for speech recognition . In ICASSP. IEEE , 2454--2458. Jie Chen, Lingfei Wu, Kartik Audhkhasi, Brian Kingsbury, and Bhuvana Ramab- hadrari. 2016. Efficient one-vs-one kernel ridge regression for speech recognition. In ICASSP. IEEE, 2454--2458."},{"key":"e_1_3_2_1_3_1","volume-title":"Journal of Machine Learning Research","author":"Chen Yihua","year":"2009","unstructured":"Yihua Chen , Eric K Garcia , Maya R Gupta , Ali Rahimi , and Luca Cazzanti . 2009 . Similarity-based classification: Concepts and algorithms . Journal of Machine Learning Research 10, Mar (2009), 747--776. Yihua Chen, Eric K Garcia, Maya R Gupta, Ali Rahimi, and Luca Cazzanti. 2009. Similarity-based classification: Concepts and algorithms. Journal of Machine Learning Research 10, Mar (2009), 747--776."},{"key":"e_1_3_2_1_4_1","volume-title":"Dzmitry Bahdanau, and Yoshua Ben- gio.","author":"Cho Kyunghyun","year":"2014","unstructured":"Kyunghyun Cho , Bart Van Merrie?nboer , Dzmitry Bahdanau, and Yoshua Ben- gio. 2014 . On the properties of neural machine translation: Encoder-decoder approaches. arXiv:1409.1259 (2014). Kyunghyun Cho, Bart Van Merrie?nboer, Dzmitry Bahdanau, and Yoshua Ben- gio. 2014. On the properties of neural machine translation: Encoder-decoder approaches. arXiv:1409.1259 (2014)."},{"key":"e_1_3_2_1_5_1","volume-title":"Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv:1412.3555","author":"Chung Junyoung","year":"2014","unstructured":"Junyoung Chung , Caglar Gulcehre , KyungHyun Cho , and Yoshua Bengio . 2014. Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv:1412.3555 ( 2014 ). Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. 2014. Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv:1412.3555 (2014)."},{"key":"e_1_3_2_1_6_1","first-page":"1035","article-title":"Rational kernels: Theory and algorithms","author":"Cortes Corinna","year":"2004","unstructured":"Corinna Cortes , Patrick Haffner , and Mehryar Mohri . 2004 . Rational kernels: Theory and algorithms . Journal of Machine Learning Research 5 , Aug (2004), 1035 -- 1062 . Corinna Cortes, Patrick Haffner, and Mehryar Mohri. 2004. Rational kernels: Theory and algorithms. Journal of Machine Learning Research 5, Aug (2004), 1035--1062.","journal-title":"Journal of Machine Learning Research 5"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Nello Cristianini John Shawe-Taylor etal 2000. An introduction to support vector machines and other kernel-based learning methods. Cambridge university press.   Nello Cristianini John Shawe-Taylor et al. 2000. An introduction to support vector machines and other kernel-based learning methods. Cambridge university press.","DOI":"10.1017\/CBO9780511801389"},{"key":"e_1_3_2_1_8_1","first-page":"1871","article-title":"LIBLINEAR: A library for large linear classification","author":"Fan Rong-En","year":"2008","unstructured":"Rong-En Fan , Kai-Wei Chang , Cho-Jui Hsieh , Xiang-Rui Wang , and Chih-Jen Lin . 2008 . LIBLINEAR: A library for large linear classification . Journal of machine learning research 9 , Aug (2008), 1871 -- 1874 . Rong-En Fan, Kai-Wei Chang, Cho-Jui Hsieh, Xiang-Rui Wang, and Chih-Jen Lin. 2008. LIBLINEAR: A library for large linear classification. Journal of machine learning research 9, Aug (2008), 1871--1874.","journal-title":"Journal of machine learning research 9"},{"key":"e_1_3_2_1_9_1","unstructured":"Muhammad Farhan Juvaria Tariq Arif Zaman Mudassir Shabbir and Imdad Ul- lah Khan. 2017. Efficient Approximation Algorithms for Strings Kernel Based Sequence Classification. In NIPS. 6938--6948.   Muhammad Farhan Juvaria Tariq Arif Zaman Mudassir Shabbir and Imdad Ul- lah Khan. 2017. Efficient Approximation Algorithms for Strings Kernel Based Sequence Classification. In NIPS. 6938--6948."},{"key":"e_1_3_2_1_10_1","volume-title":"UCI Machine Learning Repository {http:\/\/archive. ics. uci. edu\/ml}","author":"Frank Andrew","year":"2010","unstructured":"Andrew Frank and Arthur Asuncion . 2010. UCI Machine Learning Repository {http:\/\/archive. ics. uci. edu\/ml} . Irvine, CA : University of California . School of information and computer science 213 ( 2010 ). Andrew Frank and Arthur Asuncion. 2010. UCI Machine Learning Repository {http:\/\/archive. ics. uci. edu\/ml}. Irvine, CA: University of California. School of information and computer science 213 (2010)."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btg265"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143892"},{"key":"e_1_3_2_1_13_1","volume-title":"LSTM: A search space odyssey","author":"Greff Klaus","year":"2017","unstructured":"Klaus Greff , Rupesh K Srivastava , Jan Koutnik , Bas R Steunebrink , and Jurgen Schmidhuber . 2017 . LSTM: A search space odyssey . IEEE transactions on neural networks and learning systems 28, 10 (2017), 2222--2232. Klaus Greff, Rupesh K Srivastava, Jan Koutnik, Bas R Steunebrink, and Jurgen Schmidhuber. 2017. LSTM: A search space odyssey. IEEE transactions on neural networks and learning systems 28, 10 (2017), 2222--2232."},{"key":"e_1_3_2_1_14_1","volume-title":"Joint Pattern Recognition Symposium. Springer, 220--227","author":"Haasdonk Bernard","year":"2004","unstructured":"Bernard Haasdonk and Claus Bahlmann . 2004 . Learning with distance substitu- tion kernels . In Joint Pattern Recognition Symposium. Springer, 220--227 . Bernard Haasdonk and Claus Bahlmann. 2004. Learning with distance substitu- tion kernels. In Joint Pattern Recognition Symposium. Springer, 220--227."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Po-Sen Huang Haim Avron Tara N Sainath Vikas Sindhwani and Bhuvana Ramabhadran. 2014. Kernel methods match Deep Neural Networks on TIMIT.. In ICASSP. 205--209.  Po-Sen Huang Haim Avron Tara N Sainath Vikas Sindhwani and Bhuvana Ramabhadran. 2014. Kernel methods match Deep Neural Networks on TIMIT.. In ICASSP. 205--209.","DOI":"10.1109\/ICASSP.2014.6853587"},{"key":"e_1_3_2_1_17_1","unstructured":"Catalin Ionescu Alin Popa and Cristian Sminchisescu. 2017. Large-scale data- dependent kernel approximation. In AIStats. 19--27.  Catalin Ionescu Alin Popa and Cristian Sminchisescu. 2017. Large-scale data- dependent kernel approximation. In AIStats. 19--27."},{"key":"e_1_3_2_1_18_1","volume-title":"Kingma and Jimmy Ba","author":"Diederik","year":"2014","unstructured":"Diederik P. Kingma and Jimmy Ba . 2014 . Adam : A Method for Stochastic Opti- mization. CoRR abs\/1412.6980 (2014). Diederik P. Kingma and Jimmy Ba. 2014. Adam: A Method for Stochastic Opti- mization. CoRR abs\/1412.6980 (2014)."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1142\/S021972000500120X"},{"key":"e_1_3_2_1_20_1","unstructured":"Pavel P Kuksa Pai-Hsi Huang and Vladimir Pavlovic. 2009. Scalable algorithms for string kernels with inexact matching. In NIPS. 881--888.   Pavel P Kuksa Pai-Hsi Huang and Vladimir Pavlovic. 2009. Scalable algorithms for string kernels with inexact matching. In NIPS. 881--888."},{"key":"e_1_3_2_1_21_1","volume-title":"Biocomputing","author":"Leslie Christina","year":"2002","unstructured":"Christina Leslie , Eleazar Eskin , and William Stafford Noble . 2001. The spectrum kernel: A string kernel for SVM protein classification . In Biocomputing 2002 . World Scientific , 564--575. Christina Leslie, Eleazar Eskin, and William Stafford Noble. 2001. The spectrum kernel: A string kernel for SVM protein classification. In Biocomputing 2002. World Scientific, 564--575."},{"key":"e_1_3_2_1_22_1","unstructured":"ChristinaLeslie EleazarEskin JasonWeston andWilliamStaffordNoble.2003. Mismatch string kernels for SVM protein classification. In NIPS. Neural informa- tion processing systems foundation.   ChristinaLeslie EleazarEskin JasonWeston andWilliamStaffordNoble.2003. Mismatch string kernels for SVM protein classification. In NIPS. Neural informa- tion processing systems foundation."},{"key":"e_1_3_2_1_23_1","first-page":"1435","article-title":"Fast string kernels using inexact matching for protein sequences","author":"Leslie Christina","year":"2004","unstructured":"Christina Leslie and Rui Kuang . 2004 . Fast string kernels using inexact matching for protein sequences . Journal of Machine Learning Research 5 , Nov (2004), 1435 -- 1455 . Christina Leslie and Rui Kuang. 2004. Fast string kernels using inexact matching for protein sequences. Journal of Machine Learning Research 5, Nov (2004), 1435--1455.","journal-title":"Journal of Machine Learning Research 5"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btg431"},{"key":"e_1_3_2_1_25_1","volume-title":"Soviet physics doklady","author":"Levenshtein Vladimir I","unstructured":"Vladimir I Levenshtein . 1966. Binary codes capable of correcting deletions, insertions, and reversals . In Soviet physics doklady , Vol. 10 . 707--710. Vladimir I Levenshtein. 1966. Binary codes capable of correcting deletions, insertions, and reversals. In Soviet physics doklady, Vol. 10. 707--710."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1162\/153244302760200687"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2015.2477830"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2006.04.012"},{"key":"e_1_3_2_1_30_1","unstructured":"Ali Rahimi and Benjamin Recht. 2008. Random features for large-scale kernel machines. In NIPS. 1177--1184.   Ali Rahimi and Benjamin Recht. 2008. Random features for large-scale kernel machines. In NIPS. 1177--1184."},{"key":"e_1_3_2_1_31_1","unstructured":"Alessandro Rudi and Lorenzo Rosasco. 2017. Generalization properties of learning with random features. In NIPS. 3218--3228.   Alessandro Rudi and Lorenzo Rosasco. 2017. Generalization properties of learning with random features. In NIPS. 3218--3228."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth141"},{"key":"e_1_3_2_1_33_1","volume-title":"Pavel A Pevzner, Michael S Waterman, et al.","author":"Scholkopf Bernhard","year":"2004","unstructured":"Bernhard Scholkopf , Koji Tsuda , Jean-Philippe Vert , Director Sorin Istrail , Pavel A Pevzner, Michael S Waterman, et al. 2004 . Kernel methods in computational biology. MIT press . Bernhard Scholkopf, Koji Tsuda, Jean-Philippe Vert, Director Sorin Istrail, Pavel A Pevzner, Michael S Waterman, et al. 2004. Kernel methods in computational biology. MIT press."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/3122009.3122029"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(81)90046-4"},{"key":"e_1_3_2_1_36_1","unstructured":"Alex J Smola and SVN Vishwanathan. 2003. Fast kernels for string and tree matching. In NIPS. 585--592.   Alex J Smola and SVN Vishwanathan. 2003. Fast kernels for string and tree matching. In NIPS. 585--592."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2670313"},{"key":"e_1_3_2_1_38_1","volume-title":"Computer alignment of sequences. Phylogenetic analysis of DNA sequences","author":"Waterman MICHAEL S","year":"1991","unstructured":"MICHAEL S Waterman , JANA Joyce , and Mark Eggert . 1991. Computer alignment of sequences. Phylogenetic analysis of DNA sequences ( 1991 ), 59--72. MICHAEL S Waterman, JANA Joyce, and Mark Eggert. 1991. Computer alignment of sequences. Phylogenetic analysis of DNA sequences (1991), 59--72."},{"key":"e_1_3_2_1_39_1","volume-title":"Dynamic alignment kernels. NIPS","author":"Watkins Chris","year":"1999","unstructured":"Chris Watkins . 1999. Dynamic alignment kernels. NIPS ( 1999 ), 39--50. Chris Watkins. 1999. Dynamic alignment kernels. NIPS (1999), 39--50."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02530507"},{"key":"e_1_3_2_1_41_1","unstructured":"Christopher KI Williams and Matthias Seeger. 2001. Using the Nystrom method to speed up kernel machines. In NIPS. 682--688.  Christopher KI Williams and Matthias Seeger. 2001. Using the Nystrom method to speed up kernel machines. In NIPS. 682--688."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220090"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939794"},{"key":"e_1_3_2_1_44_1","volume-title":"Fangli Xu, Pradeep Ravikuma, and Michael Witbrock.","author":"Wu Lingfei","year":"2018","unstructured":"Lingfei Wu , Ian En-Hsu Yen , Fangli Xu, Pradeep Ravikuma, and Michael Witbrock. 2018 . D2KE: From Distance to Kernel and Embedding. arXiv:1802.04956 (2018). {46} Lingfei Wu, Ian En-Hsu Yen, Jinfeng Yi, Fangli Xu, Qi Lei, and Michael Witbrock. 2018. Random Warping Series: A Random Features Method for Time-Series Embedding. In AIStats . 793--802. Lingfei Wu, Ian En-Hsu Yen, Fangli Xu, Pradeep Ravikuma, and Michael Witbrock. 2018. D2KE: From Distance to Kernel and Embedding. arXiv:1802.04956 (2018). {46} Lingfei Wu, Ian En-Hsu Yen, Jinfeng Yi, Fangli Xu, Qi Lei, and Michael Witbrock. 2018. Random Warping Series: A Random Features Method for Time-Series Embedding. In AIStats. 793--802."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1882471.1882478"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1078"}],"event":{"name":"KDD '19: The 25th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","location":"Anchorage AK USA","acronym":"KDD '19","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data"]},"container-title":["Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3292500.3330923","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3292500.3330923","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:26:03Z","timestamp":1750206363000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3292500.3330923"}},"subtitle":["Beyond Counting Substructures"],"short-title":[],"issued":{"date-parts":[[2019,7,25]]},"references-count":45,"alternative-id":["10.1145\/3292500.3330923","10.1145\/3292500"],"URL":"https:\/\/doi.org\/10.1145\/3292500.3330923","relation":{},"subject":[],"published":{"date-parts":[[2019,7,25]]},"assertion":[{"value":"2019-07-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}