×

zbMATH — the first resource for mathematics

Space-efficient indexes for forbidden extension queries. (English) Zbl 06993619

MSC:
68W Algorithms in computer science
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Biswas, S.; Ganguly, A.; Shah, R.; Thankachan, S. V., Forbidden extension queries, (35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2015, December 16-18, 2015, Bangalore, India, (2015)), 320-335 · Zbl 1366.68029
[2] Biswas, S.; Ganguly, A.; Shah, R.; Thankachan, S. V., Ranked document retrieval with forbidden pattern, (Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29-July 1, 2015, Proceedings, (2015)), 77-88 · Zbl 1432.68120
[3] Brodal, G. S.; Fagerberg, R.; Greve, M.; López-Ortiz, A., Online sorted range reporting, (Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings, (2009)), 173-182 · Zbl 1272.68113
[4] Chazelle, B.; Guibas, L. J., Fractional cascading: I. A data structuring technique, Algorithmica, 1, 1-4, 133-162, (1986) · Zbl 0639.68056
[5] Cohen, H.; Porat, E., Fast set intersection and two-patterns matching, Theor. Comput. Sci., 411, 40-42, 3795-3800, (2010) · Zbl 1207.68270
[6] Fischer, J.; Heun, V., Space-efficient preprocessing schemes for range minimum queries on static arrays, SIAM J. Comput., 40, 2, 465-492, (2011) · Zbl 1222.05024
[7] Fischer, J.; Gagie, T.; Kopelowitz, T.; Lewenstein, M.; Mäkinen, V.; Salmela, L.; Välimäki, N., Forbidden patterns, (Proceedings of the 10th Latin American International Conference on Theoretical Informatics, LATIN’12, (2012), Springer-Verlag Berlin, Heidelberg), 327-337 · Zbl 1353.68066
[8] Frederickson, G. N.; Johnson, D. B., The complexity of selection and ranking in \(X + Y\) and matrices with sorted columns, J. Comput. Syst. Sci., 24, 2, 197-208, (1982) · Zbl 0478.68062
[9] Fredman, M. L.; Willard, D. E., Trans-dichotomous algorithms for minimum spanning trees and shortest paths, J. Comput. Syst. Sci., 48, 3, 533-551, (1994) · Zbl 0806.68057
[10] Golynski, A.; Munro, J. I.; Rao, S. S., Rank/select operations on large alphabets: a tool for text indexing, (Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, (2006)), 368-373 · Zbl 1192.68800
[11] Grossi, R.; Gupta, A.; Vitter, J. S., High-order entropy-compressed text indexes, (Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA, (2003)), 841-850 · Zbl 1092.68584
[12] Gusfield, D., Algorithms on strings, trees, and sequences - computer science and computational biology, (1997), Cambridge University Press · Zbl 0934.68103
[13] Harel, D.; Tarjan, R. E., Fast algorithms for finding nearest common ancestors, SIAM J. Comput., 13, 2, 338-355, (1984) · Zbl 0535.68022
[14] Hon, W.-K.; Shah, R.; Thankachan, S.; Vitter, J., String retrieval for multi-pattern queries, (Chavez, E.; Lonardi, S., String Processing and Information Retrieval, Lecture Notes in Computer Science, vol. 6393, (2010), Springer Berlin Heidelberg), 55-66
[15] Hon, W.-K.; Shah, R.; Thankachan, S. V.; Vitter, J. S., Document listing for queries with excluded pattern, (Kärkkäinen, J.; Stoye, J., Combinatorial Pattern Matching, Lecture Notes in Computer Science, vol. 7354, (2012), Springer Berlin Heidelberg), 185-195 · Zbl 1358.68093
[16] Hon, W.; Thankachan, S. V.; Shah, R.; Vitter, J. S., Faster compressed top-k document retrieval, (2013 Data Compression Conference, DCC 2013, Snowbird, UT, USA, March 20-22, 2013, (2013)), 341-350
[17] Hon, W.; Shah, R.; Thankachan, S. V.; Vitter, J. S., Space-efficient frameworks for top-k string retrieval, J. ACM, 61, 2, 9, (2014) · Zbl 1295.68230
[18] Larsen, K.; Munro, J.; Nielsen, J.; Thankachan, S., On hardness of several string indexing problems, (Kulikov, A.; Kuznetsov, S.; Pevzner, P., Combinatorial Pattern Matching, Lecture Notes in Computer Science, vol. 8486, (2014), Springer International Publishing), 242-251 · Zbl 1407.68229
[19] Matias, Y.; Muthukrishnan, S.; Sahinalp, S.; Ziv, J., Augmenting suffix trees, with applications, (Bilardi, G.; Italiano, G.; Pietracaprina, A.; Pucci, G., Algorithms — ESA’ 98, Lecture Notes in Computer Science, vol. 1461, (1998), Springer Berlin Heidelberg), 67-78
[20] Munro, J. I., (Tables Foundations of Software Technology and Theoretical Computer Science, 16th Conference, Hyderabad, India, December 18-20, 1996, Proceedings, (1996)), 37-42
[21] Munro, J. I.; Navarro, G.; Nielsen, J. S.; Shah, R.; Thankachan, S. V., Top-k term-proximity in succinct space, (Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, (2014)), 169-180 · Zbl 1366.68039
[22] Muthukrishnan, S., Efficient algorithms for document retrieval problems, (Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA, (2002)), 657-666 · Zbl 1093.68588
[23] Navarro, G., Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences, ACM Comput. Surv., 46, 4, 52:1-52:47, (2013) · Zbl 1305.68078
[24] Navarro, G.; Nekrich, Y., Top-k document retrieval in optimal time and linear space, (Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, (2012), SIAM), 1066-1077
[25] Navarro, G.; Thankachan, S. V., Faster top-k document retrieval in optimal space, (String Processing and Information Retrieval - 20th International Symposium, SPIRE 2013, Jerusalem, Israel, October 7-9, 2013, Proceedings, (2013)), 255-262
[26] Patil, M.; Thankachan, S. V.; Shah, R.; Nekrich, Y.; Vitter, J. S., Categorical range maxima queries, (Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, (2014), ACM), 266-277
[27] Sadakane, K.; Navarro, G., Fully-functional succinct trees, (Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, (2010)), 134-149 · Zbl 1288.05046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.