Document Open Access Logo

Sufficient Conditions for Efficient Indexing Under Different Matchings

Authors Amihood Amir, Eitan Kondratovsky

PDF
Thumbnail PDF

File

LIPIcs.CPM.2019.6.pdf
  • Filesize: 462 kB
  • 12 pages

Document Identifiers

Author Details

Amihood Amir
  • Department of Computer Science, Bar-Ilan University, Israel
Eitan Kondratovsky
  • Department of Computer Science, Bar-Ilan University, Israel

Funding

  • Amir, Amihood: Partly supported by ISF grant 1475/18 and BSF grant 2014028.
  • Kondratovsky, Eitan: Partly supported by ISF grant 1475/18.

Cite As Get BibTex

Amihood Amir and Eitan Kondratovsky. Sufficient Conditions for Efficient Indexing Under Different Matchings. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.CPM.2019.6

Abstract

The most important task derived from the massive digital data accumulation in the world, is efficient access to this data, hence the importance of indexing. In the last decade, many different types of matching relations were defined, each requiring an efficient indexing scheme. Cole and Hariharan in a ground breaking paper [Cole and Hariharan, SIAM J. Comput., 33(1):26–42, 2003], formulate sufficient conditions for building an efficient indexing for quasi-suffix collections, collections that behave as suffixes. It was shown that known matchings, including parameterized, 2-D array and order preserving matchings, fit their indexing settings. In this paper, we formulate more basic sufficient conditions based on the order relation derived from the matching relation itself, our conditions are more general than the previously known conditions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pattern matching
Keywords
  • off-the-shelf indexing algorithms
  • general matching relations
  • weaker sufficient conditions for indexing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Amir, A. Butman, and E. Porat. On the Relationship between Histogram Indexing and Block-Mass Indexing. Philosophical Transactions of the Royal Society A: Mathematical Physical and Engineering Sciences, 372(2016), 2014. URL: http://doi.org/10.1098/rsta.2013.0132.
  2. A. Amir, T.M. Chan, M. Lewenstein, and N. Lewenstein. On the Hardness of Jumbled Indexing. In Proc. 41st International Colloquium on Automata, Languages and Programming (ICALP), pages 114-125, 2014. Google Scholar
  3. A. Amir, M. Farach, and S. Muthukrishnan. Alphabet Dependence in Parameterized Matching. Information Processing Letters, 49:111-115, 1994. Google Scholar
  4. A. Amir and I. Nor. Real-Time Indexing over Fixed Finite Alphabets. In Proc. 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1086-1095, 2008. Google Scholar
  5. B. S. Baker. Parameterized Pattern Matching: Algorithms and Applications. Journal of Computer and System Sciences, 52(1):28-42, 1996. Google Scholar
  6. B. S. Baker. Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance. SIAM J. Comput., 26(5):1343-1362, 1997. Google Scholar
  7. S. Cho, J. C. Na, K. Park, and J. S. Sim. A fast algorithm for order-preserving pattern matching. Information Processing Letters, 115(2):397-402, 2015. Google Scholar
  8. R. Cole and R. Hariharan. Dynamic LCA Queries in Trees. In Proc. 10th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 235-244, 1999. Google Scholar
  9. R. Cole and R. Hariharan. Faster Suffix Tree Construction with Missing Suffix Links. SIAM J. Comput., 33(1):26-42, 2003. Google Scholar
  10. M. Crochemore, C. S. Iliopoulos, T. Kociumaka, M. Kubica, A. Langiu, S. P. Pissis, J. Radoszewski, W. Rytter, and T. Walen. Order-preserving Indexing. Theoretical Computer Science, 613:122-135, 2016. Google Scholar
  11. M. Farach. Optimal Suffix Tree Construction with Large Alphabets. Proc. 38th IEEE Symposium on Foundations of Computer Science, pages 137-143, 1997. Google Scholar
  12. P. Ferragina and G. Manzini. Indexing Compressed Texts. J. of the ACM, 52(4):552-581, 2005. Google Scholar
  13. R. Giancarlo. A Generalization of the Suffix Tree to Square Matrices, with Applications. SIAM J. Comput., 24(3):520-562, 1995. Google Scholar
  14. J. Kärkkäinen and P. Sanders. Simple linear work suffix array construction. In Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP 03), pages 943-955, 2003. LNCS 2719. Google Scholar
  15. T. Kasai, G. Lee, S. Arikawa, and K. Park. Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications. In Amihood Amir, editor, Combinatorial Pattern Matching, pages 181-192. Springer, 2001. Google Scholar
  16. J. Kim, A. Amir, J. C. Na, K. Park, and J. S. Sim. On Representations of Ternary Order Relations in Numeric Strings. Mathematics in Computer Science, 11(2):127-136, 2017. Google Scholar
  17. J. Kim, P. Eades, R. Fleischer, S.-H. Hong, C. S. Iliopoulos, K. Park, S. J. Puglisi, and T. Tokuyama. Order Preserving Matching. Theoretical Computer Science, 525:68-79, 2014. Google Scholar
  18. T. Kopelowitz. On-line Indexing for General Alphabets. In Proc. 53rd IEEE Symposium on the Foundation of Computer Science (FOCS), 2012. Google Scholar
  19. M. Kubica, T. Kulczynski, J. Radoszewski, W. Rytter, and T. Walen. A linear time algorithm for consecutive permutation pattern matching. Information Processing Letters, 113(12):430-433, 2013. Google Scholar
  20. G.M. Landau and U. Vishkin. Efficient string matching with k mismatches. Theoretical Computer Science, 43:239-249, 1986. Google Scholar
  21. T. Lee, J.C. Na, and K. Park. On-Line Construction of Parameterized Suffix Trees. Information Processing Letters, 111(5):201-207, 2011. Google Scholar
  22. U. Manber and G. Myers. Suffix Arrays: A New Method for On-Line String Searches. In Proc. 1st ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 319-327, 1990. Google Scholar
  23. E. M. McCreight. A space-economical suffix tree construction algorithm. J. of the ACM, 23:262-272, 1976. Google Scholar
  24. J. Ng, A. Amir, and P. A. Pevzner. Blocked Pattern Matching Problem and its Applications in Proteomics. In Proc. 15th Annual International Conference on Research in Computational Molecular Biology (RECOMB), pages 298-319, 2011. Google Scholar
  25. S. G. Park, A. Amir, G. M. Landau, and K. Park. Cartesian Tree Matching and Indexing. In Proc. 30th Annual Symposium on Combinatorial Pattern Matching (CPM), 2019. To appear. Google Scholar
  26. E. Ukkonen. On-line Construction of Suffix Trees. Algorithmica, 14:249-260, 1995. Google Scholar
  27. P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and Implementation of an Efficient Priority Queue. Mathematical Systems Theory, 10:99-127, 1977. Google Scholar
  28. P. Weiner. Linear Pattern Matching Algorithm. Proc. 14 IEEE Symposium on Switching and Automata Theory, pages 1-11, 1973. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact