{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:50Z","timestamp":1759638290289},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642312649"},{"type":"electronic","value":"9783642312656"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31265-6_15","type":"book-chapter","created":{"date-parts":[[2012,6,12]],"date-time":"2012-06-12T03:28:23Z","timestamp":1339471703000},"page":"185-195","source":"Crossref","is-referenced-by-count":10,"title":["Document Listing for Queries with Excluded Pattern"],"prefix":"10.1007","author":[{"given":"Wing-Kai","family":"Hon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Shah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sharma V.","family":"Thankachan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"15_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1007\/978-3-642-24583-1_38","volume-title":"String Processing and Information Retrieval","author":"D. Belazzougui","year":"2011","unstructured":"Belazzougui, D., Navarro, G.: Improved Compressed Indexes for Full-Text Document Retrieval. In: Grossi, R., Sebastiani, F., Silvestri, F. (eds.) SPIRE 2011. LNCS, vol.\u00a07024, pp. 386\u2013397. Springer, Heidelberg (2011)"},{"key":"15_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"M.A. Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA Problem Revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol.\u00a01776, pp. 88\u201394. Springer, Heidelberg (2000)"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Chien, Y.-F., Hon, W.-K., Shah, R., Vitter, J.S.: Geometric Burrows-Wheeler transform: Linking range searching and text indexing. In: DCC, pp. 252\u2013261 (2008)","DOI":"10.1109\/DCC.2008.67"},{"issue":"40-42","key":"15_CR4","doi-asserted-by":"publisher","first-page":"3795","DOI":"10.1016\/j.tcs.2010.06.002","volume":"411","author":"H. Cohen","year":"2010","unstructured":"Cohen, H., Porat, E.: Fast Set Intersection and Two Patterns Matching. Theor. Comput. Sci.\u00a0411(40-42), 3795\u20133800 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-642-15781-3_17","volume-title":"Algorithms \u2013 ESA 2010","author":"J. Shane Culpepper","year":"2010","unstructured":"Shane Culpepper, J., Navarro, G., Puglisi, S.J., Turpin, A.: Top-k Ranked Document Search in General Text Databases. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part II. LNCS, vol.\u00a06347, pp. 194\u2013205. Springer, Heidelberg (2010)"},{"issue":"8","key":"15_CR6","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1016\/j.ic.2008.12.010","volume":"207","author":"P. Ferragina","year":"2009","unstructured":"Ferragina, P., Giancarlo, R., Manzini, G.: The Myriad Virtues of Wavelet Trees. Inf. and Comp.\u00a0207(8), 849\u2013866 (2009)","journal-title":"Inf. and Comp."},{"issue":"4","key":"15_CR7","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1016\/S0022-0000(03)00028-X","volume":"66","author":"P. Ferragina","year":"2003","unstructured":"Ferragina, P., Koudas, N., Muthukrishnan, S., Srivastava, D.: Two-dimensional substring indexing. J. Comput. Syst. Sci.\u00a066(4), 763\u2013774 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"15_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/978-3-642-29344-3_28","volume-title":"LATIN 2012: Theoretical Informatics","author":"J. Fischer","year":"2012","unstructured":"Fischer, J., Gagie, T., Kopelowitz, T., Lewenstein, M., M\u00e4kinen, V., Salmela, L., V\u00e4lim\u00e4ki, N.: Forbidden Patterns. In: Fern\u00e1ndez-Baca, D. (ed.) LATIN 2012. LNCS, vol.\u00a07256, pp. 327\u2013337. Springer, Heidelberg (2012)"},{"key":"15_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-642-16321-0_7","volume-title":"String Processing and Information Retrieval","author":"T. Gagie","year":"2010","unstructured":"Gagie, T., Navarro, G., Puglisi, S.J.: Colored Range Queries and Document Retrieval. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol.\u00a06393, pp. 67\u201381. Springer, Heidelberg (2010)"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Golynski, A., Munro, J.I., Rao, S.S.: Rank\/select operations on large alphabets: a tool for text indexing. In: SODA, pp. 368\u2013373 (2006)","DOI":"10.1145\/1109557.1109599"},{"key":"15_CR11","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-Order Entropy-Compressed Text Indexes. In: SODA, pp. 841\u2013850 (2003)"},{"issue":"4","key":"15_CR12","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1016\/j.jda.2010.08.003","volume":"8","author":"W.K. Hon","year":"2010","unstructured":"Hon, W.K., Patil, M., Shah, R., Wu, S.-B.: Efficient Index for Retrieving Top-k Most Frequent Documents. Journal of Discrete Algorithms\u00a08(4), 402\u2013417 (2010)","journal-title":"Journal of Discrete Algorithms"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Hon, W.K., Shah, R., Vitter, J.S.: Space-Efficient Framework for Top-k String Retrival Problems. In: FOCS, pp. 713\u2013722 (2009)","DOI":"10.1109\/FOCS.2009.19"},{"key":"15_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-642-13509-5_24","volume-title":"Combinatorial Pattern Matching","author":"W.-K. Hon","year":"2010","unstructured":"Hon, W.-K., Shah, R., Vitter, J.S.: Compression, Indexing, and Retrieval for Massive String Data. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol.\u00a06129, pp. 260\u2013274. Springer, Heidelberg (2010)"},{"key":"15_CR15","series-title":"LNCS","first-page":"173","volume-title":"CPM 2012","author":"W.-K. Hon","year":"2012","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V.: Towards an Optimal Space-and-Query-Time Index for Top-k Document Retrieval. In: K\u00e4rkk\u00e4inen, J., Stoye, J. (eds.) CPM 2012. LNCS, vol.\u00a07354, pp. 173\u2013184. Springer, Heidelberg (2012)"},{"key":"15_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-642-16321-0_6","volume-title":"String Processing and Information Retrieval","author":"W.-K. Hon","year":"2010","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V., Vitter, J.S.: String Retrieval for Multi-pattern Queries. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol.\u00a06393, pp. 55\u201366. Springer, Heidelberg (2010)"},{"key":"15_CR17","unstructured":"Jansson, J., Sadakane, K., Sung, W.K.: Ultra-succinct Representation of Ordered Trees. In: SODA, pp. 575\u2013584 (2007)"},{"key":"15_CR18","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Nekrich, Y.: Top-K Color Queries for Document Retrieval. In: SODA, pp. 401\u2013411 (2011)","DOI":"10.1137\/1.9781611973082.32"},{"issue":"5","key":"15_CR19","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U. Manber","year":"1993","unstructured":"Manber, U., Myers, G.: Suffix Arrays: A New Method for On-Line String Searches. SICOMP\u00a022(5), 935\u2013948 (1993)","journal-title":"SICOMP"},{"key":"15_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/3-540-68530-8_6","volume-title":"Algorithms - ESA \u201998","author":"Y. Matias","year":"1998","unstructured":"Matias, Y., Muthukrishnan, S.M., \u015eahinalp, S.C., Ziv, J.: Augmenting Suffix Trees, with Applications. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol.\u00a01461, pp. 67\u201378. Springer, Heidelberg (1998)"},{"key":"15_CR21","unstructured":"Muthukrishnan, S.: Efficient Algorithms for Document Retrieval Problems. In: SODA, pp. 657\u2013666 (2002)"},{"key":"15_CR22","doi-asserted-by":"crossref","unstructured":"Navarro, G., Nekrich, Y.: Top-k document retrieval in optimal time and linear space. In: SODA, pp. 1066\u20131077 (2012)","DOI":"10.1137\/1.9781611973099.84"},{"key":"15_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/978-3-642-16321-0_33","volume-title":"String Processing and Information Retrieval","author":"G. Navarro","year":"2010","unstructured":"Navarro, G., Puglisi, S.J.: Dual-Sorted Inverted Lists. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol.\u00a06393, pp. 309\u2013321. Springer, Heidelberg (2010)"},{"key":"15_CR24","doi-asserted-by":"crossref","unstructured":"Patil, M., Thankachan, S.V., Shah, R., Hon, W.K., Vitter, J.S., Chandrasekaran, S.: Inverted Indexes for Phrases and Strings. In: SIGIR, pp. 555\u2013564 (2011)","DOI":"10.1145\/2009916.2009992"},{"key":"15_CR25","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets. TALG\u00a03(4) (2007)","DOI":"10.1145\/1290672.1290680"},{"issue":"1","key":"15_CR26","first-page":"12","volume":"5","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Succinct Data Structures for Flexible Text Retrieval Systems. JDA\u00a05(1), 12\u201322 (2007)","journal-title":"JDA"},{"key":"15_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-540-73437-6_22","volume-title":"Combinatorial Pattern Matching","author":"N. V\u00e4lim\u00e4ki","year":"2007","unstructured":"V\u00e4lim\u00e4ki, N., M\u00e4kinen, V.: Space-Efficient Algorithms for Document Retrieval. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 205\u2013215. Springer, Heidelberg (2007)"},{"key":"15_CR28","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear Pattern Matching Algorithms. In: Proc. Switching and Automata Theory, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31265-6_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:54:09Z","timestamp":1620129249000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31265-6_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642312649","9783642312656"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31265-6_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}