Skip to main content
SpringerLink
Log in

Flexible Indexing of Repetitive Collections

  • Conference paper
  • First Online:
Book cover Unveiling Dynamics and Complexity (CiE 2017)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 10307))

Included in the following conference series:

Abstract

Highly repetitive strings are increasingly being amassed by genome sequencing experiments, and by versioned archives of source code and webpages. We describe practical data structures that support counting and locating all the exact occurrences of a pattern in a repetitive text, by combining the run-length encoded Burrows-Wheeler transform (RLBWT) with the boundaries of Lempel-Ziv 77 factors. One such variant uses an amount of space comparable to LZ77 indexes, but it answers count queries between two and four orders of magnitude faster than all LZ77 and hybrid index implementations, at the cost of slower locate queries. Combining the RLBWT with the compact directed acyclic word graph answers locate queries for short patterns between four and ten times faster than a version of the run-length compressed suffix array (RLCSA) that uses comparable memory, and with very short patterns our index achieves speedups even greater than ten with respect to RLCSA.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    Our source code is available at https://github.com/nicolaprezza/lz-rlbwt and https://github.com/nicolaprezza/slz-rlbwt and it is based on SDSL [11].

  2. 2.

    Our source code is available at https://github.com/mathieuraffinot/locate-cdawg.

  3. 3.

    http://pizzachili.dcc.uchile.cl/repcorpus.html.

  4. 4.

    We compile the sequential version of https://github.com/adamnovak/rlcsa with PSI_FLAGS and SA_FLAGS turned off (in other words, we use a gap-encoded bitvector rather than a succinct bitvector to mark sampled positions in the suffix array). The block size of psi vectors (RLCSA_BLOCK_SIZE) is 32 bytes.

  5. 5.

    We perform all experiments on a single core of a 6-core, 2.50 GHz, Intel Xeon E5-2640 processor, with access to 128 GiB of RAM and running CentOS 6.3. We measure resources with GNU Time 1.7, and we compile with GCC 5.3.0.

  6. 6.

    We use as patterns random substrings of each dataset, containing just DNA bases, generated with the genpatterns tool from the Pizza&Chili repetitive corpus.

References

  1. Arroyuelo, D., Navarro, G., Sadakane, K.: Stronger Lempel-Ziv based compressed text indexing. Algorithmica 62, 54–101 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  2. Belazzougui, D.: Linear time construction of compressed text indices in compact space. In: Proceedings of the STOC, pp. 148–193 (2014)

    Google Scholar 

  3. Belazzougui, D., Cunial, F., Gagie, T., Prezza, N., Raffinot, M.: Composite repetition-aware data structures. In: Cicalese, F., Porat, E., Vaccaro, U. (eds.) CPM 2015. LNCS, vol. 9133, pp. 26–39. Springer, Cham (2015). doi:10.1007/978-3-319-19929-0_3

    Chapter  Google Scholar 

  4. Blumer, A., et al.: Complete inverted files for efficient text retrieval and analysis. JACM 34, 578–595 (1987)

    Article  MathSciNet  Google Scholar 

  5. Chan, T.M., Larsen, K.G., Pătraşcu, M.: Orthogonal range searching on the RAM, revisited. In: Proceediings of the SoCG, pp. 1–10 (2011)

    Google Scholar 

  6. Crochemore, M., Hancart, C.: Automata for matching patterns. In: Rozenberg, G., et al. (eds.) Handbook of Formal Languages, pp. 399–462. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

  7. Crochemore, M., Vérin, R.: Direct construction of compact directed acyclic word graphs. In: Apostolico, A., Hein, J. (eds.) CPM 1997. LNCS, vol. 1264, pp. 116–129. Springer, Heidelberg (1997). doi:10.1007/3-540-63220-4_55

    Chapter  Google Scholar 

  8. Elias, P., Flower, R.A.: The complexity of some simple retrieval problems. JACM 22, 367–379 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  9. Ferragina, P., Manzini, G.: Indexing compressed texts. JACM 52(4), 552–581 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  10. Gagie, T., Gawrychowski, P., Kärkkäinen, J., Nekrich, Y., Puglisi, S.J.: LZ77-based self-indexing with faster pattern matching. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 731–742. Springer, Heidelberg (2014). doi:10.1007/978-3-642-54423-1_63

    Chapter  Google Scholar 

  11. Gog, S., Beller, T., Moffat, A., Petri, M.: From theory to practice: plug and play with succinct data structures. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 326–337. Springer, Cham (2014). doi:10.1007/978-3-319-07959-2_28

    Google Scholar 

  12. Gusfield, D.: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)

    Book  MATH  Google Scholar 

  13. Kärkkäinen, J., Ukkonen, E.: Lempel-Ziv parsing and sublinear-size index structures for string matching. In: Proceedings of the WSP, pp. 141–155 (1996)

    Google Scholar 

  14. Kreft, S.: Self-index based on LZ77. Master’s thesis, Department of Computer Science, University of Chile (2010)

    Google Scholar 

  15. Kreft, S., Navarro, G.: On compressing and indexing repetitive sequences. TCS 483, 115–133 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  16. Mäkinen, V., Navarro, G.: Succinct suffix arrays based on run-length encoding. In: Apostolico, A., Crochemore, M., Park, K. (eds.) CPM 2005. LNCS, vol. 3537, pp. 45–56. Springer, Heidelberg (2005). doi:10.1007/11496656_5

    Chapter  Google Scholar 

  17. Mäkinen, V., et al.: Storage and retrieval of highly repetitive sequence collections. JCB 17, 281–308 (2010)

    MathSciNet  Google Scholar 

  18. Morrison, D.R.: PATRICIA – practical algorithm to retrieve information coded in alphanumeric. JACM 15, 514–534 (1968)

    Article  Google Scholar 

  19. Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31, 762–776 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  20. Raffinot, M.: On maximal repeats in strings. IPL 80, 165–169 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  21. Sirén, J., Välimäki, N., Mäkinen, V., Navarro, G.: Run-length compressed indexes are superior for highly repetitive sequence collections. In: Amir, A., Turpin, A., Moffat, A. (eds.) SPIRE 2008. LNCS, vol. 5280, pp. 164–175. Springer, Heidelberg (2008). doi:10.1007/978-3-540-89097-3_17

    Chapter  Google Scholar 

  22. Valenzuela, D.: CHICO: a compressed hybrid index for repetitive collections. In: Goldberg, A.V., Kulikov, A.S. (eds.) SEA 2016. LNCS, vol. 9685, pp. 326–338. Springer, Cham (2016). doi:10.1007/978-3-319-38851-9_22

    Google Scholar 

  23. Willard, D.E.: Log-logarithmic worst-case range queries are possible in space \(\theta (n)\). IPL 17, 81–84 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  24. Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE TIT 23, 337–343 (1977)

    MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. DTISI-CERIST, Algiers, Algeria

    Djamal Belazzougui

  2. MPI-CBG, Dresden, Germany

    Fabio Cunial

  3. UDP and CeBiB, Santiago, Chile

    Travis Gagie

  4. DTU, Copenhagen, Denmark

    Nicola Prezza

  5. CNRS, Bordeaux, France

    Mathieu Raffinot

Authors
  1. Djamal Belazzougui
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Fabio Cunial
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Travis Gagie
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Nicola Prezza
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Mathieu Raffinot
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Fabio Cunial .

Editor information

Editors and Affiliations

  1. University of Turku, Turku, Finland

    Jarkko Kari

  2. Christian-Albrechts-University of Kiel, Kiel, Germany

    Florin Manea

  3. Åbo Akademi University, Turku, Finland

    Ion Petre

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Belazzougui, D., Cunial, F., Gagie, T., Prezza, N., Raffinot, M. (2017). Flexible Indexing of Repetitive Collections. In: Kari, J., Manea, F., Petre, I. (eds) Unveiling Dynamics and Complexity. CiE 2017. Lecture Notes in Computer Science(), vol 10307. Springer, Cham. https://doi.org/10.1007/978-3-319-58741-7_17

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-58741-7_17

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-58740-0

  • Online ISBN: 978-3-319-58741-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation