{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T05:09:52Z","timestamp":1769749792099,"version":"3.49.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,1,20]],"date-time":"2016-01-20T00:00:00Z","timestamp":1453248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Basic Research Program of China","doi-asserted-by":"crossref","award":["2012CB316201"],"award-info":[{"award-number":["2012CB316201"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF of China for Key Program Award","award":["61572122"],"award-info":[{"award-number":["61572122"]}]},{"name":"NSF of China for Outstanding Young Scholars Award","award":["61322208"],"award-info":[{"award-number":["61322208"]}]},{"name":"Joint Research Fund for Overseas Natural Science of China","award":["61129002"],"award-info":[{"award-number":["61129002"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61272178"],"award-info":[{"award-number":["61272178"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2016,2,3]]},"abstract":"<jats:p>\n            The problem of finding matches of a regular expression (RE) on a string exists in many applications, such as text editing, biosequence search, and shell commands. Existing techniques first identify candidates using substrings in the RE, then verify each of them using an automaton. These techniques become inefficient when there are many candidate occurrences that need to be verified. In this article, we propose a novel technique that prunes false negatives by utilizing\n            <jats:italic>negative factors<\/jats:italic>\n            , which are substrings that\n            <jats:italic>cannot<\/jats:italic>\n            appear in an answer. A main advantage of the technique is that it can be integrated with many existing algorithms to improve their efficiency significantly. We present a detailed description of this technique. We develop an efficient algorithm that utilizes negative factors to prune candidates, then improve it by using bit operations to process negative factors in parallel. We show that negative factors, when used with necessary factors (substrings that must appear in each answer), can achieve much better pruning power. We analyze the large number of negative factors, and develop an algorithm for finding a small number of high-quality negative factors. We conducted a thorough experimental study of this technique on real datasets, including DNA sequences, proteins, and text documents, and show significant performance improvement of the state-of-the-art tools by an order of magnitude.\n          <\/jats:p>","DOI":"10.1145\/2847525","type":"journal-article","created":{"date-parts":[[2016,1,26]],"date-time":"2016-01-26T13:25:01Z","timestamp":1453814701000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Negative Factor"],"prefix":"10.1145","volume":"40","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6184-4771","authenticated-orcid":false,"given":"Xiaochun","family":"Yang","sequence":"first","affiliation":[{"name":"Northeastern University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tao","family":"Qiu","sequence":"additional","affiliation":[{"name":"Northeastern University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bin","family":"Wang","sequence":"additional","affiliation":[{"name":"Northeastern University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baihua","family":"Zheng","sequence":"additional","affiliation":[{"name":"Singapore Management University, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yaoshu","family":"Wang","sequence":"additional","affiliation":[{"name":"Northeastern University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chen","family":"Li","sequence":"additional","affiliation":[{"name":"University of California, Irvine"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,1,20]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Ullman","author":"Aho Alfred V.","year":"1985","unstructured":"Alfred V. Aho , Ravi Sethi , and Jeffrey D . Ullman . 1985 . Compilers : Principles, Techniques, and Tools. Addison-Wesley , Reading, MA. Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. 1985. Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading, MA."},{"key":"e_1_2_1_2_1","unstructured":"Sean E. Anderson. 2005. Bit twiddling hacks. http:\/\/graphics.stanford.edu\/&sim;seander\/bithacks.html.  Sean E. Anderson. 2005. Bit twiddling hacks. http:\/\/graphics.stanford.edu\/&sim;seander\/bithacks.html."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/135239.135243"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/235809.235810"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/39528.39537"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28873"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90287-4"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00140-5"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 6th Colloquium on Automata, Languages and Programming, Hermann A","author":"Commentz-Walter Beate","unstructured":"Beate Commentz-Walter . 1979. A string matching algorithm fast on the average . In Proceedings of the 6th Colloquium on Automata, Languages and Programming, Hermann A . Maurer (Ed.), Lecture Notes in Computer Science, Vol. 71 . Springer-Verlag , Graz, Austria, 118--132. Beate Commentz-Walter. 1979. A string matching algorithm fast on the average. In Proceedings of the 6th Colloquium on Automata, Languages and Programming, Hermann A. Maurer (Ed.), Lecture Notes in Computer Science, Vol. 71. Springer-Verlag, Graz, Austria, 118--132."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01185427"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2431211.2431212"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1070\/RM1961v016n05ABEH004112"},{"key":"e_1_2_1_13_1","unstructured":"David Harel. 1999. Factor Oracle of a Set of Words. Technical report. Universit\u00e9 de Marne-la-Vall\u00e9e.  David Harel. 1999. Factor Oracle of a Set of Words. Technical report. Universit\u00e9 de Marne-la-Vall\u00e9e."},{"key":"e_1_2_1_14_1","volume-title":"Ullman","author":"Hopcroft John E.","year":"2000","unstructured":"John E. Hopcroft and Jeffrey D . Ullman . 2000 . Introduction to Automata Theory, Languages and Computation, Second Edition (2 nd ed.). Addison-Wesley , Reading, MA. John E. Hopcroft and Jeffrey D. Ullman. 2000. Introduction to Automata Theory, Languages and Computation, Second Edition (2nd ed.). Addison-Wesley, Reading, MA.","edition":"2"},{"key":"e_1_2_1_15_1","first-page":"919","article-title":"Prosearch: Fast searching of protein sequences with regular expression patterns related to protein structure and function","volume":"13","author":"Kolakowski L. F.","year":"1992","unstructured":"L. F. Kolakowski , J. Leunissen , and J. E. Smith . 1992 . Prosearch: Fast searching of protein sequences with regular expression patterns related to protein structure and function . BioTechniques 13 , 6, 919 -- 921 . L. F. Kolakowski, J. Leunissen, and J. E. Smith. 1992. Prosearch: Fast searching of protein sequences with regular expression patterns related to protein structure and function. BioTechniques 13, 6, 919--921.","journal-title":"BioTechniques"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn032"},{"key":"e_1_2_1_17_1","first-page":"217","article-title":"String matching with automata","volume":"4","author":"Mohri Mehryar","year":"1997","unstructured":"Mehryar Mohri . 1997 . String matching with automata . Nordic Journal of Computing 4 , 2, 217 -- 231 . Mehryar Mohri. 1997. String matching with automata. Nordic Journal of Computing 4, 2, 217--231.","journal-title":"Nordic Journal of Computing"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/128749.128755"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.411"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/647256.720634"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384246"},{"key":"e_1_2_1_22_1","volume-title":"5th International Workshop, WAE 2001, Proceedings (Lecture Notes in Computer Science), Gerth St\u00f8lting Brodal, Daniele Frigioni, and Alberto Marchetti-Spaccamela (Eds.)","volume":"2141","author":"Navarro Gonzalo","year":"2001","unstructured":"Gonzalo Navarro and Mathieu Raffinot . 2001 . Compact DFA representation for fast regular expression search. In Algorithm Engineering , 5th International Workshop, WAE 2001, Proceedings (Lecture Notes in Computer Science), Gerth St\u00f8lting Brodal, Daniele Frigioni, and Alberto Marchetti-Spaccamela (Eds.) , Vol. 2141 . Springer-Verlag, Aarhus, Denmark, 1--12. Gonzalo Navarro and Mathieu Raffinot. 2001. Compact DFA representation for fast regular expression search. In Algorithm Engineering, 5th International Workshop, WAE 2001, Proceedings (Lecture Notes in Computer Science), Gerth St\u00f8lting Brodal, Daniele Frigioni, and Alberto Marchetti-Spaccamela (Eds.), Vol. 2141. Springer-Verlag, Aarhus, Denmark, 1--12."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1120-3"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the Prague Stringology Club Workshop, Jan Holub and Milan Sim\u00e1nek (Eds.). Department of Computer Science and Engineering, Faculty of Electrical Engineering","author":"Sim\u00e1nek Milan","year":"1998","unstructured":"Milan Sim\u00e1nek . 1998 . The factor automaton . In Proceedings of the Prague Stringology Club Workshop, Jan Holub and Milan Sim\u00e1nek (Eds.). Department of Computer Science and Engineering, Faculty of Electrical Engineering , Czech Technical University, Prague, Czech Republic, 102--106. Milan Sim\u00e1nek. 1998. The factor automaton. In Proceedings of the Prague Stringology Club Workshop, Jan Holub and Milan Sim\u00e1nek (Eds.). Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University, Prague, Czech Republic, 102--106."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.3109\/10425179109020792"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4573(93)90106-N"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00532-7"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/135239.135244"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465289"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2847525","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2847525","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:43:27Z","timestamp":1750225407000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2847525"}},"subtitle":["Improving Regular-Expression Matching in Strings"],"short-title":[],"issued":{"date-parts":[[2016,1,20]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,2,3]]}},"alternative-id":["10.1145\/2847525"],"URL":"https:\/\/doi.org\/10.1145\/2847525","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,20]]},"assertion":[{"value":"2015-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-01-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}