6 - Sequences
Published online by Cambridge University Press: 05 September 2016
- Type
- Chapter
- Information
- Compact Data StructuresA Practical Approach, pp. 120 - 166Publisher: Cambridge University PressPrint publication year: 2016
References
, , and (2010). Compressed self-indices supporting conjunctive queries on document collections. In Proc. 17th International Symposium on String Processing and Information Retrieval (SPIRE), LNCS 6393, pages 43–54.Google Scholar
, , , , and (2012a). Distributed search based on self-indexed compressed text. Information Processing and Management, 48(5), 819–827.
, , , , and (2012b). To index or not to index: time-space trade-offs in search engines with positional ranking functions. In Proc. 35th International ACM Conference on Research and Development in Information Retrieval (SIGIR), pages 255–264.Google Scholar
and (2013). On compressing permutations and adaptive sorting. Theoretical Computer Science, 513, 109–123.Google Scholar
, , , and (2011). Succinct indexes for strings, binary relations and multilabeled trees. ACM Transactions on Algorithms, 7(4), article 52.Google Scholar
, , , , and (2014). Efficient fully-compressed sequence representations. Algorithmica, 69(1), 232–268.Google Scholar
, , and (2016). A space efficient direct access data structure. In Proc. 26th Data Compression Conference (DCC), pages 63–72.Google Scholar
and (2015). Optimal lower and upper bounds for representing sequences. ACM Transactions on Algorithms, 11(4), article 31.Google Scholar
(2010). Multiary Wavelet Trees in Practice. Honours thesis, RMIT University, Australia.
, , , and (2012). Implicit indexing of natural language text by reorganizing bytecodes. Information Retrieval, 15(6), 527–557.Google Scholar
and (2013). Adaptive and approximate orthogonal range counting. In Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 241–251.Google Scholar
, , and (2011). Space efficient wavelet tree construction. In Proc. 18th International Symposium on String Processing and Information Retrieval (SPIRE), LNCS 7024, pages 185–196.Google Scholar
, , and (2015). The wavelet matrix: An efficient wavelet tree for large alphabets. Information Systems, 47, 15–32.Google Scholar
, , , and (2010). Top-k ranked document search in general text databases. In Proc. 18th Annual European Symposium on Algorithms (ESA B), LNCS 6347, pages 194–205 (part II).Google Scholar
and (2007). A simple storage scheme for strings achieving entropy bounds. Theoretical Computer Science, 371(1), 115–121.Google Scholar
, , , and (2007). Compressed representations of sequences and full-text indexes. ACM Transactions on Algorithms, 3(2), article 20.Google Scholar
, , and (2009). The myriad virtues of wavelet trees. Information and Computation, 207(8), 849–866.Google Scholar
, , , and (2006). When indexing equals compression: Experiments with compressing suffix arrays and applications. ACM Transactions on Algorithms, 2(4), 611–639.Google Scholar
, , , and (2014). Efficientwavelet tree construction and querying for multicore architectures. In Proc. 13th International Symposium on Experimental Algorithms (SEA), LNCS 8504, pages 150–161.Google Scholar
, , and (2009). Range quantile queries:Another virtue ofwavelet trees. In Proc. 16th International Symposium on String Processing and Information Retrieval (SPIRE), LNCS 5721, pages 1–6.Google Scholar
, , and (2012). New algorithms on wavelet trees and applications to information retrieval. Theoretical Computer Science, 426-427, 25–41.Google Scholar
, , , and (2015). Efficient and compact representations of prefix codes. IEEE Transactions on Information Theory, 61(9), 4999–5011.Google Scholar
(2009). Cell probe lower bounds for succinct data structures. In Proc. 20th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pages 625–634.Google Scholar
, , and (2006). Rank/select operations on large alphabets: a tool for text indexing. In Proc. 17th ACM-SIAM Annual Symposium on Discrete Algorithms (SODA), pages 368–373.Google Scholar
, , and (2008). On the redundancy of succinct data structures. In Proc. 11th Scandinavian Workshop on Algorithm Theory (SWAT), LNCS 5124, pages 148–159.Google Scholar
and (2012). The wavelet trie: Maintaining an indexed sequence of strings in compressed space. In Proc. 31st ACM Symposium on Principles of Database Systems (PODS), pages 203–214.Google Scholar
, , and (2003). High-order entropy-compressed text indexes. In Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 841–850.Google Scholar
, , and (2010). Optimal trade-offs for succinct string indexes. In Proc. 37th International Colloquium on Algorithms, Languages and Programming (ICALP), pages 678–689.Google Scholar
, , and (2011).Wavelet trees: From theory to practice. In Proc. 1st International Conference on Data Compression, Communications and Processing (CCP), pages 210–221.Google Scholar
and (2012). Dual-sorted inverted lists in practice. In Proc. 19th International Symposium on String Processing and Information Retrieval (SPIRE), LNCS 7608, pages 295–306.Google Scholar
(2014). Enhanced variable-length codes: Improved compression with efficient random access. In Proc. 24th Data Compression Conference (DCC), pages 362–371.Google Scholar
, , and (2016). Parallel lightweight wavelet tree, suffix array and FM-index construction. In Proc. 26th Data Compression Conference (DCC), pages 33–42.Google Scholar
and (2005). Succinct suffix arrays based on run-length encoding. Nordic Journal of Computing, 12(1), 40–66.Google Scholar
and (2007). Rank and select revisited and extended. Theoretical Computer Science, 387(3), 332–347.Google Scholar
(2012). Wavelet trees: A survey. Computer Science and Information Systems, 9(2), 585–625.Google Scholar
and (1990). Bounded ordered dictionaries in O(log logN) time and O(n) space. Information Processing Letters, 35(4), 183–189.Google Scholar
, , and (2016). Fast construction of wavelet trees. Theoretical Computer Science, 638, 91–97.Google Scholar
(2015). Parallel wavelet tree construction. In Proc. 25th Data Compression Conference (DCC), pages 63–72.Google Scholar
(2011). On wavelet tree construction. In Proc. 22nd Annual Symposium on Combinatorial Pattern Matching (CPM), LNCS 6661, pages 208–218.Google Scholar
, , , and (2008). Canonical Huffman code based full-text index. Progress in Natural Science, 18(3), 325–330.Google Scholar