{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:04:46Z","timestamp":1768107886355,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":28,"publisher":"ACM","license":[{"start":{"date-parts":[[2004,11,13]],"date-time":"2004-11-13T00:00:00Z","timestamp":1100304000000},"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":[[2004,11,13]]},"DOI":"10.1145\/1031171.1031212","type":"proceedings-article","created":{"date-parts":[[2005,1,30]],"date-time":"2005-01-30T17:58:48Z","timestamp":1107107928000},"page":"198-207","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Indexing text data under space constraints"],"prefix":"10.1145","author":[{"given":"Bijit","family":"Hore","sequence":"first","affiliation":[{"name":"University of California - Irvine, CA"}]},{"given":"Hakan","family":"Hacigumus","sequence":"additional","affiliation":[{"name":"IBM Almaden Research Center"}]},{"given":"Bala","family":"Iyer","sequence":"additional","affiliation":[{"name":"Silicon Valley Lab"}]},{"given":"Sharad","family":"Mehrotra","sequence":"additional","affiliation":[{"name":"University of California - Irvine, CA"}]}],"member":"320","published-online":{"date-parts":[[2004,11,13]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Proc. of ICDE","author":"Cho S.","year":"2002","unstructured":"J. Cho and S. Rajagopalan . A Fast Regular Expression Indexing Engine . In Proc. of ICDE , 2002 . J. Cho and S. Rajagopalan. A Fast Regular Expression Indexing Engine. In Proc. of ICDE, 2002."},{"key":"e_1_3_2_1_2_1","unstructured":"Digital Bibliography & Library Project. http:\/\/dblp.uni-trier.de\/.  Digital Bibliography & Library Project. http:\/\/dblp.uni-trier.de\/."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00031-9"},{"key":"e_1_3_2_1_4_1","volume-title":"Algorithmica","author":"Ukkonen","year":"1993","unstructured":"E. Ukkonen . Online construction of Suffix-trees . Algorithmica , 1993 . E. Ukkonen. Online construction of Suffix-trees. Algorithmica, 1993."},{"issue":"4","key":"e_1_3_2_1_5_1","first-page":"28","article-title":"Using q grams in a dbms for approximate string processing","volume":"24","author":"Gravano P. G.","year":"2001","unstructured":"L. Gravano , P. G. Ipeirotis , H. V. Jagadish , N. Koudas , S. Muthukrishnan , L. Pietarinen , and D. Srivastava . Using q grams in a dbms for approximate string processing . IEEE Data Engineering Bulletin , 24 ( 4 ): 28 -- 34 , 2001 . L. Gravano, P. G. Ipeirotis, H. V. Jagadish, N. Koudas, S. Muthukrishnan, L. Pietarinen, and D. Srivastava. Using q grams in a dbms for approximate string processing. IEEE Data Engineering Bulletin, 24(4):28--34, 2001.","journal-title":"IEEE Data Engineering Bulletin"},{"key":"e_1_3_2_1_6_1","first-page":"491","volume-title":"VLDB","author":"Gravano P. G.","year":"2001","unstructured":"L. Gravano , P. G. Ipeirotis , H. V. Jagadish , N. Koudas , S. Muthukrishnan , and D. Srivastava . Approximate string joins in a database (almost) for free . In VLDB , pages 491 -- 500 , 2001 . L. Gravano, P. G. Ipeirotis, H. V. Jagadish, N. Koudas, S. Muthukrishnan, and D. Srivastava. Approximate string joins in a database (almost) for free. In VLDB, pages 491--500, 2001."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/299432.299460"},{"key":"e_1_3_2_1_8_1","unstructured":"Hore B. Hacigumus H. Iyer B. Mehrotra S. Indexing Text Data under Space Constraints TR-DB-04-02 www-db.ics.uci.edu\/pages\/publications\/index.shtml  Hore B. Hacigumus H. Iyer B. Mehrotra S. Indexing Text Data under Space Constraints TR-DB-04-02 www-db.ics.uci.edu\/pages\/publications\/index.shtml"},{"key":"e_1_3_2_1_9_1","volume-title":"Set cover, vertex cover, independent set, and related problems. Approximation algorithms for NP-hard problems","author":"Hochbaum","year":"1996","unstructured":"D. S. Hochbaum . Approximating covering and packing problems : Set cover, vertex cover, independent set, and related problems. Approximation algorithms for NP-hard problems , PWS Publishing Co. , Boston , 1996 . D. S. Hochbaum. Approximating covering and packing problems: Set cover, vertex cover, independent set, and related problems. Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, 1996."},{"key":"e_1_3_2_1_10_1","volume-title":"Analysis of the Greedy Approach in Problems of Maximum k-Coverage. Naval Research Quarterly, (45):615--627","author":"Hochbaum A.","year":"1998","unstructured":"D. S. Hochbaum and A. Pathria . Analysis of the Greedy Approach in Problems of Maximum k-Coverage. Naval Research Quarterly, (45):615--627 , 1998 . D. S. Hochbaum and A. Pathria. Analysis of the Greedy Approach in Problems of Maximum k-Coverage. Naval Research Quarterly, (45):615--627, 1998."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/375360.375365"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564747"},{"key":"e_1_3_2_1_13_1","volume-title":"Computers and Intractability: A Guide to Theory of NP-Completeness","author":"Garey M. R","year":"1979","unstructured":"Garey , M. R , Johnson , D. S. Computers and Intractability: A Guide to Theory of NP-Completeness . Freeman , San Francisco , 1979 . Garey, M. R, Johnson, D. S. Computers and Intractability: A Guide to Theory of NP-Completeness. Freeman, San Francisco, 1979."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/320521.320530"},{"key":"e_1_3_2_1_15_1","volume-title":"Organization and maintenance of large ordered indexes Acta Informatica","author":"Bayer R.","year":"1972","unstructured":"Bayer , R. , and McCreight , C. Organization and maintenance of large ordered indexes Acta Informatica , 1972 , pp173--189. Bayer, R., and McCreight, C. Organization and maintenance of large ordered indexes Acta Informatica, 1972, pp173--189."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225287"},{"key":"e_1_3_2_1_17_1","volume-title":"Introduction to automata theory, languages and computation","author":"Hopcroft J., E.","year":"1979","unstructured":"Hopcroft , J., E. , and Ullman , D . Introduction to automata theory, languages and computation . Addison-Wesley , 1979 . Hopcroft, J., E., and Ullman, D. Introduction to automata theory, languages and computation. Addison-Wesley, 1979."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/235809.235810"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/978-3-662-07675-0_9","volume-title":"Handbook of formal languages","author":"Crochemore M.","year":"1997","unstructured":"Crochemore , M. , Hancart , C. Automata for Matching Patterns , Handbook of formal languages . Rosenberg, C., and Salaama, A. eds 2, Springer-Verlag , 1997 , pp. 399 -- 462 Crochemore, M., Hancart, C. Automata for Matching Patterns, Handbook of formal languages. Rosenberg, C., and Salaama, A. eds 2, Springer-Verlag, 1997, pp. 399--462"},{"key":"e_1_3_2_1_20_1","first-page":"31","volume-title":"The smallest automaton recognizing the subwords of a text. Theoretical computer science, 40(1)","author":"Blumer A.","year":"1985","unstructured":"Blumer , A. , Blumer , J. , Haussler , D. , Ehrenfeucht , A. , Chen , M., T. , and Seiferas , J . The smallest automaton recognizing the subwords of a text. Theoretical computer science, 40(1) , 1985 , pp. 31 -- 55 . Blumer, A., Blumer, J., Haussler, D., Ehrenfeucht, A., Chen, M., T., and Seiferas, J. The smallest automaton recognizing the subwords of a text. Theoretical computer science, 40(1), 1985, pp. 31--55."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"e_1_3_2_1_24_1","volume-title":"The Art of Computer Programming","author":"Knuth D., E.","year":"1973","unstructured":"Knuth , D., E. The Art of Computer Programming . Addison-Wesley , 1973 Vol 3: Sorting and Searching. Knuth, D., E. The Art of Computer Programming. Addison-Wesley, 1973 Vol 3: Sorting and Searching."},{"key":"e_1_3_2_1_25_1","volume-title":"Automatic Text Processing","author":"Salton G.","year":"1989","unstructured":"Salton , G. Automatic Text Processing . Addison-Wesley , 1989 . Salton, G. Automatic Text Processing. Addison-Wesley, 1989."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276336"},{"key":"e_1_3_2_1_27_1","volume-title":"Transaction Processing: Concepts and Techniques. Morgan Kaufmann Pub","author":"Gray J.","year":"1993","unstructured":"Gray , J. , Reuters , A. Transaction Processing: Concepts and Techniques. Morgan Kaufmann Pub , 1993 . Gray, J., Reuters, A. Transaction Processing: Concepts and Techniques. Morgan Kaufmann Pub, 1993."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304185"}],"event":{"name":"CIKM04: Conference on Information and Knowledge Management","location":"Washington D.C. USA","acronym":"CIKM04","sponsor":["ACM Association for Computing Machinery","SIGIR ACM Special Interest Group on Information Retrieval"]},"container-title":["Proceedings of the thirteenth ACM international conference on Information and knowledge management"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1031171.1031212","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1031171.1031212","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:31:08Z","timestamp":1750264268000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1031171.1031212"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,11,13]]},"references-count":28,"alternative-id":["10.1145\/1031171.1031212","10.1145\/1031171"],"URL":"https:\/\/doi.org\/10.1145\/1031171.1031212","relation":{},"subject":[],"published":{"date-parts":[[2004,11,13]]},"assertion":[{"value":"2004-11-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}