Abstract
We describe a set of basic succinct data structures which have been implemented as part of the Succinct library, and applications on top of the library: an index to speed-up the access to collections of semi-structured data, a compressed string dictionary, and a compressed dictionary for scored strings which supports top-k prefix matching.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Apache Hadoop, http://hadoop.apache.org/
Arroyuelo, D., Cánovas, R., Navarro, G., Sadakane, K.: Succinct trees in practice. In: ALENEX, pp. 84–97 (2010)
Barbay, J., He, M., Munro, J.I., Satti, S.R.: Succinct indexes for strings, binary relations and multilabeled trees. ACM Transactions on Algorithms 7(4), 52 (2011)
Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88–94. Springer, Heidelberg (2000)
Benoit, D., Demaine, E.D., Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Representing trees of higher degree. Algorithmica 43(4), 275–292 (2005)
Buhrman, H., Miltersen, P.B., Radhakrishnan, J., Venkatesh, S.: Are bitvectors optimal? SIAM Journal on Computing 31(6), 1723–1744 (2002)
Davoodi, P., Raman, R., Satti, S.R.: Succinct representations of binary trees for range minimum queries. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol. 7434, pp. 396–407. Springer, Heidelberg (2012)
Dean, J., Ghemawat, S.: MapReduce: Simplified data processing on large clusters. In: OSDI, pp. 137–150 (2004)
Elias, P.: Efficient storage and retrieval by content and address of static files. Journal of the ACM (JACM) 21(2), 246–260 (1974)
Elias, P., Flower, R.A.: The complexity of some simple retrieval problems. Journal of the ACM 22(3), 367–379 (1975)
Fano, R.: On the number of bits required to implement an associative memory. Memorandum 61. Computer Structures Group, Project MAC. MIT (1971)
Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM 52(4), 552–581
Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. 40(2), 465–492 (2011)
Grossi, R., Ottaviano, G.: Fast compressed tries through path decompositions. In: ALENEX, pp. 65–74 (2012)
Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput. 35(2), 378–407 (2005)
Hsu, B.J.P., Ottaviano, G.: Space-efficient data structures for top-k completion. In: Proceedings of the 22st World Wide Web Conference (WWW) (2013)
Jacobson, G.: Space-efficient static trees and graphs. In: FOCS, pp. 549–554 (1989)
JSON specification, http://json.org/
Kao, M.Y. (ed.): Encyclopedia of Algorithms. Springer (2008)
Knuth, D.E.: The Art of Computer Programming. Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams, vol. 4. Addison-Wesley (2009)
libcds - Compact Data Structures Library, http://libcds.recoded.cl/
Miltersen, P.B.: The bit probe complexity measure revisited. In: Enjalbert, P., Wagner, K.W., Finkel, A. (eds.) STACS 1993. LNCS, vol. 665, pp. 662–671. Springer, Heidelberg (1993)
Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM Journal on Computing 31(3), 762–776 (2001)
Okanohara, D., Sadakane, K.: Practical entropy-compressed rank/select dictionary. In: ALENEX (2007)
Ottaviano, G., Grossi, R.: Semi-indexing semi-structured data in tiny space. In: CIKM, pp. 1485–1494 (2011)
Pǎtraşcu, M.: Succincter. In: FOCS 2008, pp. 305–313 (2008)
Pǎtraşcu, M., Thorup, M.: Time-space trade-offs for predecessor search. In: STOC, pp. 232–240 (2006)
Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Alg. 3(4) (2007)
rsdic - Compressed Rank Select Dictionary, http://code.google.com/p/rsdic/
Sadakane, K., Navarro, G.: Fully-functional succinct trees. In: SODA 2010, pp. 134–149 (2010)
SDSL - Succinct Data Structure Library, http://www.uni-ulm.de/in/theo/research/sdsl.html
Succinct library, http://github.com/ot/succinct
Sux - Implementing Succinct Data Structures, http://sux.dsi.unimi.it/
Vigna, S.: Broadword implementation of rank/select queries. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 154–168. Springer, Heidelberg (2008)
Viola, E.: Bit-probe lower bounds for succinct data structures. SIAM J. Comput. 41(6), 1593–1604 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Grossi, R., Ottaviano, G. (2013). Design of Practical Succinct Data Structures for Large Data Collections. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds) Experimental Algorithms. SEA 2013. Lecture Notes in Computer Science, vol 7933. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38527-8_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-38527-8_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38526-1
Online ISBN: 978-3-642-38527-8
eBook Packages: Computer ScienceComputer Science (R0)