CINXE.COM
Sufficient Conditions for Efficient Indexing Under Different Matchings
<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8" /> <meta http-equiv="X-UA-Compatible" content="IE=edge" /> <meta name="google" content="notranslate"> <meta http-equiv="Content-Language" content="en"> <meta name="viewport" content="width=device-width, initial-scale=1" /> <meta name="csrf-token" content="JjnSeXmRrK4AzboltPR4sWLFM7afK5PSnq2yEwL5" /> <meta name="DC.Publisher" content="Schloss Dagstuhl – Leibniz-Zentrum für Informatik" /> <meta name="DC.Title" xml:lang="en" content="Sufficient Conditions for Efficient Indexing Under Different Matchings" /> <meta name="DC.Creator.PersonalName" content="Amir, Amihood" /> <meta name="DC.Creator.PersonalName" content="Kondratovsky, Eitan" /> <meta name="DC.Subject" content="off-the-shelf indexing algorithms" /> <meta name="DC.Subject" content="general matching relations" /> <meta name="DC.Subject" content="weaker sufficient conditions for indexing" /> <meta name="DC.Date.created" scheme="ISO8601" content="2019-06-06" /> <meta name="DC.Date.issued" scheme="ISO8601" content="2019-06-06" /> <meta name="DC.Date.modified" scheme="ISO8601" content="2019-06-06" /> <meta name="DC.Type" content="InProceedings" /> <meta name="DC.Format" scheme="IMT" content="application/pdf" /> <meta name="DC.Identifier" scheme="urn:nbn:de" content="urn:nbn:de:0030-drops-104773" /> <meta name="DC.Identifier" scheme="DOI" content="10.4230/LIPIcs.CPM.2019.6" /> <meta name="DC.Identifier" scheme="URL" content="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.6" /> <meta name="DC.Source" content="30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)" /> <meta name="DC.Source.URI" content="https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-128" /> <meta name="DC.Language" scheme="ISO639-1" content="en" /> <meta name="DC.Description" xml:lang="en" content="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." /> <meta name="DC.Rights" scheme="DCTERMS.URI" content="https://creativecommons.org/licenses/by/3.0/legalcode" /> <meta name="citation_conference_title" content="30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)" /> <meta name="citation_doi" content="10.4230/LIPIcs.CPM.2019.6" /> <meta name="citation_firstpage" content="6:1" /> <meta name="citation_lastpage" content="6:12" /> <meta name="citation_title" content="Sufficient Conditions for Efficient Indexing Under Different Matchings" /> <meta name="citation_language" content="en" /> <meta name="citation_keyword" content="off-the-shelf indexing algorithms" /> <meta name="citation_keyword" content="general matching relations" /> <meta name="citation_keyword" content="weaker sufficient conditions for indexing" /> <meta name="citation_author" content="Amir, Amihood" /> <meta name="citation_author_institution" content="Department of Computer Science, Bar-Ilan University, Israel" /> <meta name="citation_author" content="Kondratovsky, Eitan" /> <meta name="citation_author_institution" content="Department of Computer Science, Bar-Ilan University, Israel" /> <meta name="citation_date" content="2019" /> <meta name="citation_keyword" xml:lang="en" content="off-the-shelf indexing algorithms" /> <meta name="citation_keyword" xml:lang="en" content="general matching relations" /> <meta name="citation_keyword" xml:lang="en" content="weaker sufficient conditions for indexing" /> <meta name="citation_pdf_url" content="https://drops.dagstuhl.de/storage/00lipics/lipics-vol128-cpm2019/LIPIcs.CPM.2019.6/LIPIcs.CPM.2019.6.pdf" /> <meta name="citation_reference" content="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." /> <meta name="citation_reference" content="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." /> <meta name="citation_reference" content="A. Amir, M. Farach, and S. Muthukrishnan. Alphabet Dependence in Parameterized Matching. Information Processing Letters, 49:111-115, 1994." /> <meta name="citation_reference" content="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." /> <meta name="citation_reference" content="B. S. Baker. Parameterized Pattern Matching: Algorithms and Applications. Journal of Computer and System Sciences, 52(1):28-42, 1996." /> <meta name="citation_reference" content="B. S. Baker. Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance. SIAM J. Comput., 26(5):1343-1362, 1997." /> <meta name="citation_reference" content="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." /> <meta name="citation_reference" content="R. Cole and R. Hariharan. Dynamic LCA Queries in Trees. In Proc. 10th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 235-244, 1999." /> <meta name="citation_reference" content="R. Cole and R. Hariharan. Faster Suffix Tree Construction with Missing Suffix Links. SIAM J. Comput., 33(1):26-42, 2003." /> <meta name="citation_reference" content="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." /> <meta name="citation_reference" content="M. Farach. Optimal Suffix Tree Construction with Large Alphabets. Proc. 38th IEEE Symposium on Foundations of Computer Science, pages 137-143, 1997." /> <meta name="citation_reference" content="P. Ferragina and G. Manzini. Indexing Compressed Texts. J. of the ACM, 52(4):552-581, 2005." /> <meta name="citation_reference" content="R. Giancarlo. A Generalization of the Suffix Tree to Square Matrices, with Applications. SIAM J. Comput., 24(3):520-562, 1995." /> <meta name="citation_reference" content="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." /> <meta name="citation_reference" content="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." /> <meta name="citation_reference" content="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." /> <meta name="citation_reference" content="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." /> <meta name="citation_reference" content="T. Kopelowitz. On-line Indexing for General Alphabets. In Proc. 53rd IEEE Symposium on the Foundation of Computer Science (FOCS), 2012." /> <meta name="citation_reference" content="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." /> <meta name="citation_reference" content="G.M. Landau and U. Vishkin. Efficient string matching with k mismatches. Theoretical Computer Science, 43:239-249, 1986." /> <meta name="citation_reference" content="T. Lee, J.C. Na, and K. Park. On-Line Construction of Parameterized Suffix Trees. Information Processing Letters, 111(5):201-207, 2011." /> <meta name="citation_reference" content="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." /> <meta name="citation_reference" content="E. M. McCreight. A space-economical suffix tree construction algorithm. J. of the ACM, 23:262-272, 1976." /> <meta name="citation_reference" content="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." /> <meta name="citation_reference" content="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." /> <meta name="citation_reference" content="E. Ukkonen. On-line Construction of Suffix Trees. Algorithmica, 14:249-260, 1995." /> <meta name="citation_reference" content="P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and Implementation of an Efficient Priority Queue. Mathematical Systems Theory, 10:99-127, 1977." /> <meta name="citation_reference" content="P. Weiner. Linear Pattern Matching Algorithm. Proc. 14 IEEE Symposium on Switching and Automata Theory, pages 1-11, 1973." /> <link rel="canonical" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.6" /> <script type="application/json+ld"> {"@context":"https:\/\/schema.org\/","@type":"WebPage","mainEntity":{"@type":"ScholarlyArticle","@id":"#article12121","name":"Sufficient Conditions for Efficient Indexing Under Different Matchings","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\u201342, 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.","keywords":["off-the-shelf indexing algorithms","general matching relations","weaker sufficient conditions for indexing"],"author":[{"@type":"Person","name":"Amir, Amihood","givenName":"Amihood","familyName":"Amir","email":"mailto:amir@esc.biu.ac.il","affiliation":"Department of Computer Science, Bar-Ilan University, Israel","funding":"Partly supported by ISF grant 1475\/18 and BSF grant 2014028."},{"@type":"Person","name":"Kondratovsky, Eitan","givenName":"Eitan","familyName":"Kondratovsky","email":"mailto:kondrae@cs.biu.ac.il","affiliation":"Department of Computer Science, Bar-Ilan University, Israel","funding":"Partly supported by ISF grant 1475\/18."}],"position":6,"pageStart":"6:1","pageEnd":"6:12","dateCreated":"2019-06-06","datePublished":"2019-06-06","isAccessibleForFree":true,"license":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/legalcode","copyrightHolder":[{"@type":"Person","name":"Amir, Amihood","givenName":"Amihood","familyName":"Amir","email":"mailto:amir@esc.biu.ac.il","affiliation":"Department of Computer Science, Bar-Ilan University, Israel","funding":"Partly supported by ISF grant 1475\/18 and BSF grant 2014028."},{"@type":"Person","name":"Kondratovsky, Eitan","givenName":"Eitan","familyName":"Kondratovsky","email":"mailto:kondrae@cs.biu.ac.il","affiliation":"Department of Computer Science, Bar-Ilan University, Israel","funding":"Partly supported by ISF grant 1475\/18."}],"copyrightYear":"2019","accessMode":"textual","accessModeSufficient":"textual","creativeWorkStatus":"Published","inLanguage":"en-US","sameAs":"https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2019.6","publisher":"Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik","citation":"http:\/\/doi.org\/10.1098\/rsta.2013.0132","isPartOf":{"@type":"PublicationVolume","@id":"#volume6331","volumeNumber":128,"name":"30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)","dateCreated":"2019-06-06","datePublished":"2019-06-06","editor":[{"@type":"Person","name":"Pisanti, Nadia","givenName":"Nadia","familyName":"Pisanti","email":"mailto:pisanti@di.unipi.it","sameAs":"https:\/\/orcid.org\/0000-0003-3915-7665","affiliation":"University of Pisa, Italy"},{"@type":"Person","name":"P. Pissis, Solon","givenName":"Solon","familyName":"P. Pissis","email":"mailto:solon.pissis@cwi.nl","sameAs":"https:\/\/orcid.org\/0000-0002-1445-1932","affiliation":"CWI Amsterdam, the Netherlands"}],"isAccessibleForFree":true,"publisher":"Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik","hasPart":"#article12121","isPartOf":{"@type":"Periodical","@id":"#series116","name":"Leibniz International Proceedings in Informatics","issn":"1868-8969","isAccessibleForFree":true,"publisher":"Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik","hasPart":"#volume6331"}}}} </script> <title>Sufficient Conditions for Efficient Indexing Under Different Matchings</title> <link rel="icon" href="https://drops.dagstuhl.de/favicon.ico" /> <link rel="stylesheet" href="https://drops.dagstuhl.de/css/app.css?drops-core-2024-10-22" /> </head> <body> <nav class="navbar main fixed-top navbar-expand-lg navbar-light bg-light"> <div class="container-fluid"> <a class="navbar-brand" href="https://www.dagstuhl.de"> <img class="lzi-logo" src="https://drops.dagstuhl.de/images/LZI-Logo.jpg" width="84" height=62" alt="Schloss Dagstuhl - LZI - Logo" /> </a> <button class="navbar-toggler" type="button" data-bs-toggle="collapse" data-bs-target="#navbarSupportedContent" aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation"> <span class="navbar-toggler-icon"></span> </button> <div class="collapse navbar-collapse" id="navbarSupportedContent"> <ul class="navbar-nav me-auto mb-2 mb-lg-0"> <li class="nav-item" style="white-space: nowrap"> <a class="nav-link" href="https://drops.dagstuhl.de"> <i class="bi bi-house large-icon"></i> DROPS </a> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownSeries" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-journals large-icon"></i> Series </a> <ul class="dropdown-menu" aria-labelledby="navbarDropdown"> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/LIPIcs"> LIPIcs – Leibniz International Proceedings in Informatics </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/OASIcs"> OASIcs – Open Access Series in Informatics </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/DFU"> Dagstuhl Follow-Ups </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/DagAnnRep"> Schloss Dagstuhl Jahresbericht </a> </li> <li class="dropdown-divider"></li> <li> <a class="dropdown-item" href="/#discontinued-series">Discontinued Series</a> </li> </ul> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownJournals" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-journal large-icon"></i> Journals </a> <ul class="dropdown-menu" aria-labelledby="navbarDropdown"> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DARTS"> DARTS – Dagstuhl Artifacts Series </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DagRep"> Dagstuhl Reports </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DagMan"> Dagstuhl Manifestos </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/LITES"> LITES – Leibniz Transactions on Embedded Systems </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/TGDK"> TGDK – Transactions on Graph Data and Knowledge </a> </li> </ul> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownConferences" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-people large-icon"></i> Conferences </a> <ul class="dropdown-menu conference-dropdown" aria-labelledby="navbarDropdown"> <div class="row"> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AFT"> AFT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AIB"> AIB </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AofA"> AofA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/APPROX"> APPROX </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ATMOS"> ATMOS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CALCO"> CALCO </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CCC"> CCC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CONCUR"> CONCUR </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/COSIT"> COSIT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CP"> CP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CPM"> CPM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CSL"> CSL </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DISC"> DISC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DITAM"> DITAM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DNA"> DNA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ECOOP"> ECOOP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ECRTS"> ECRTS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ESA"> ESA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FAB"> FAB </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FMBC"> FMBC </a> </li> </div> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FORC"> FORC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FSCD"> FSCD </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FSTTCS"> FSTTCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FUN"> FUN </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/GD"> GD </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/GIScience"> GIScience </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICALP"> ICALP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICDT"> ICDT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICPEC"> ICPEC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/IPEC"> IPEC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/iPMVM"> iPMVM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ISAAC"> ISAAC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITC"> ITC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITCS"> ITCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITP"> ITP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/LDK"> LDK </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/MFCS"> MFCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/Microservices"> Microservices </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/NG-RES"> NG-RES </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/OPODIS"> OPODIS </a> </li> </div> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/PARMA"> PARMA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/RANDOM"> RANDOM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SAND"> SAND </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SAT"> SAT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SEA"> SEA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SLATE"> SLATE </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SNAPL"> SNAPL </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SoCG"> SoCG </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/STACS"> STACS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SWAT"> SWAT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TIME"> TIME </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/Tokenomics"> Tokenomics </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TQC"> TQC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TYPES"> TYPES </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/WABI"> WABI </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/WCET"> WCET </a> </li> </div> </div> </ul> </li> <li class="nav-item"> <a class="nav-link" href="https://drops.dagstuhl.de/docs/about" id="navbarAbout"> <i class="bi bi-info-circle large-icon"></i><span class="nav-text-about-drops"> About DROPS</span> </a> </li> </ul> <form class="navbar-search d-flex" action="https://drops.dagstuhl.de/search" method="post"> <input type="hidden" name="_token" value="JjnSeXmRrK4AzboltPR4sWLFM7afK5PSnq2yEwL5" autocomplete="off"> <div class="input-group"> <input class="form-control" type="search" placeholder="Search" aria-label="Search" name="term" autocomplete="off" maxlength="600"> <button class="btn btn-outline-success" type="submit"> <i class="bi bi-search" style="color: #000"></i> </button> </div> </form> <ul class="navbar-nav nav-metadata"> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" id="navbarDropdownMetadata" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-database-down large-icon"></i><span class="nav-text-metadata">Metadata Export</span> </a> <ul class="dropdown-menu dropdown-metadata" aria-labelledby="navbarDropdownMetadata"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/metadata">Metadata Export</a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/oai?verb=Identify" target="_blank">OAI Interface</a> </li> </ul> </li> </ul> </div> </div> </nav> <div id="app" data-release="drops-core-2024-10-22" class="container "> <div id="_top-of-page"></div> <div class="fixed-search-button"><i class="bi bi-search"></i></div> <div class="document-details"> <section class="mt-3 mb-5 title"> <div class="entity-type document"> <div class="row"> <div class="col-lg-3 entity-type-name"> <i class="bi bi-file-earmark"></i> Document <img src="https://drops.dagstuhl.de/images/open-access-logo.png" width="80px" alt="Open Access Logo" style="transform: translate(1em, -0.2em);"/> </div> <div class="col-lg-9"> <input id="doi" type="text" style="position: fixed; top: -50vh" value="https://doi.org/10.4230/LIPIcs.CPM.2019.6"/> <div class="sharing-section"> <span class="permalink"> <span> <code><span class="hide-mobile">https://doi.org/</span>10.4230/LIPIcs.CPM.2019.6</code> <span class="btn btn-clipboard copy-to-clipboard" title="Copy to clipboard" data-selector="doi"> <i class="bi bi-clipboard" aria-hidden="true"></i> <i class="bi bi-check -hidden" aria-hidden="true"></i> </span> </span> </span> <span class="sharing-buttons"> <a class="btn sharing-btn facebook" href="https://facebook.com/sharer/sharer.php?u=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.CPM.2019.6" target="_blank" rel="noopener" aria-hidden="true"> <i class="bi bi-facebook"></i> </a> <a class="btn sharing-btn reddit" href="https://www.reddit.com/submit?url=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.CPM.2019.6&title=Sufficient+Conditions+for+Efficient+Indexing+Under+Different+Matchings" target="_blank" rel="noopener" aria-hidden="true"> <i class="bi bi-reddit"></i> </a> <a class="btn sharing-btn twitter" href="https://twitter.com/intent/tweet/?text=Sufficient+Conditions+for+Efficient+Indexing+Under+Different+Matchings&url=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.CPM.2019.6" target="_blank" rel="noopener" aria-hidden="true"> <svg xmlns="http://www.w3.org/2000/svg" width="16" height="16" fill="currentColor" class="bi bi-twitter-x" viewBox="0 0 16 16"> <path d="M12.6.75h2.454l-5.36 6.142L16 15.25h-4.937l-3.867-5.07-4.425 5.07H.316l5.733-6.57L0 .75h5.063l3.495 4.633L12.601.75Zm-.86 13.028h1.36L4.323 2.145H2.865l8.875 11.633Z"/> </svg> </a> <a class="btn sharing-btn email" href="mailto:?subject=Sufficient+Conditions+for+Efficient+Indexing+Under+Different+Matchings&body=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.CPM.2019.6" target="_self" rel="noopener" aria-hidden="true"> <svg xmlns="http://www.w3.org/2000/svg" width="16" height="16" viewBox="0 0 24 24" fill="currentColor"> <path d="M22 4H2C.9 4 0 4.9 0 6v12c0 1.1.9 2 2 2h20c1.1 0 2-.9 2-2V6c0-1.1-.9-2-2-2zM7.25 14.43l-3.5 2c-.08.05-.17.07-.25.07-.17 0-.34-.1-.43-.25-.14-.24-.06-.55.18-.68l3.5-2c.24-.14.55-.06.68.18.14.24.06.55-.18.68zm4.75.07c-.1 0-.2-.03-.27-.08l-8.5-5.5c-.23-.15-.3-.46-.15-.7.15-.22.46-.3.7-.14L12 13.4l8.23-5.32c.23-.15.54-.08.7.15.14.23.07.54-.16.7l-8.5 5.5c-.08.04-.17.07-.27.07zm8.93 1.75c-.1.16-.26.25-.43.25-.08 0-.17-.02-.25-.07l-3.5-2c-.24-.13-.32-.44-.18-.68s.44-.32.68-.18l3.5 2c.24.13.32.44.18.68z"/> </svg> </a> </span> <span class="sharing-buttons"> <span class="dropdown"> <a class="btn sharing-btn metadata dropdown-toggle" href="#" role="button" data-bs-toggle="dropdown" aria-expanded="false"><i class="bi bi-download"></i></a> <ul class="dropdown-menu dropdown-menu-end"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.6/metadata/xml"> Export XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.6/metadata/acm-xml"> Export ACM-XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.6/metadata/doaj-xml"> Export DOAJ-XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.6/metadata/schema-org"> Export Schema.org </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.6/metadata/bibtex"> Export BibTeX </a> </li> </ul> </span> </span> </div> </div> </div> </div> <hr/> <h1>Sufficient Conditions for Efficient Indexing Under Different Matchings</h1> <h3 class="mt-2 authors"> Authors <a href="#author-details" style="font-size: 0.8em; padding-right: 1em"><i class="bi bi-info-circle"></i></a> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Amir, Amihood" class="name">Amihood Amir</a><!---->, </span> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Kondratovsky, Eitan" class="name">Eitan Kondratovsky</a><!----> </span> </h3> <hr/> <ul class="mt-4"> <li> <span style="margin-right: 10px; ">Part of:</span> <span style="white-space: nowrap"> <i class="bi bi-book-half"></i> Volume: </span> <a href="https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-128">30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019) </a> <br> <span style="margin-right: 10px; visibility: hidden;">Part of:</span> <span style="white-space: nowrap"> <i class="bi bi-journals"></i> Series: </span> <a href="https://drops.dagstuhl.de/entities/series/LIPIcs">Leibniz International Proceedings in Informatics (LIPIcs)</a> <br> <span style="margin-right: 10px; visibility: hidden;">Part of:</span> <span style="white-space: nowrap"> <i class="bi bi-people"></i> Conference: </span> <a href="https://drops.dagstuhl.de/entities/conference/CPM">Annual Symposium on Combinatorial Pattern Matching (CPM)</a> </li> <li class="mt-2">License: <a href="https://creativecommons.org/licenses/by/3.0/legalcode"> <img class="license-logo" src="https://drops.dagstuhl.de/images/cc-by.png" alt="CC-BY Logo"> Creative Commons Attribution 3.0 Unported license </a> </li> <li>Publication Date: 2019-06-06 </li> </ul> <hr/> </section> <a class="fixed-pdf-button" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol128-cpm2019/LIPIcs.CPM.2019.6/LIPIcs.CPM.2019.6.pdf"><i class="bi bi-file-earmark-pdf-fill" style="color:red"></i> PDF </a> <div class="row mt-2"> <div class="col-lg-4 mt-2"> <section class="thumbnail"> <a href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol128-cpm2019/LIPIcs.CPM.2019.6/LIPIcs.CPM.2019.6.pdf"><img src="https://drops.dagstuhl.de/storage/00lipics/lipics-vol128-cpm2019/thumbnails/LIPIcs.CPM.2019.6/LIPIcs.CPM.2019.6.png" alt="Thumbnail PDF" /></a> </section> <section class="files mt-5"> <h2>File</h2> <div class="content"> <div> <a href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol128-cpm2019/LIPIcs.CPM.2019.6/LIPIcs.CPM.2019.6.pdf"><i class="bi bi-file-earmark-pdf-fill" style="color:red"></i> LIPIcs.CPM.2019.6.pdf</a> <ul> <li>Filesize: 462 kB</li> <li>12 pages</li> </ul> </div> </div> </section> <section class="identifiers mt-3"> <h2>Document Identifiers</h2> <div class="content"> <ul> <li><b>DOI:</b> <a href="https://doi.org/10.4230/LIPIcs.CPM.2019.6">10.4230/LIPIcs.CPM.2019.6</a></li> <li><b>URN:</b> <a href="https://nbn-resolving.org/process-urn-form?identifier=urn:nbn:de:0030-drops-104773&verb=FULL">urn:nbn:de:0030-drops-104773</a></li> </ul> </div> </section> <section class="authors mt-3" id="author-details"> <h2>Author Details</h2> <div class="author person-details"> <div> <span class="name"><b>Amihood Amir</b></span> <a href="https://u.cs.biu.ac.il/~amir"><i class="bi bi-house"></i></a> <a href="mailto:amir@esc.biu.ac.il"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Amir, Amihood"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Department of Computer Science, Bar-Ilan University, Israel</li> </ul> </div> <div class="author person-details"> <div> <span class="name"><b>Eitan Kondratovsky</b></span> <a href="mailto:kondrae@cs.biu.ac.il"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Kondratovsky, Eitan"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Department of Computer Science, Bar-Ilan University, Israel</li> </ul> </div> </section> <section class="related-version mt-3"> <h2>Funding</h2> <div class="content"> <ul> <li><b>Amir, Amihood</b>: Partly supported by ISF grant 1475/18 and BSF grant 2014028.</li> <li><b>Kondratovsky, Eitan</b>: Partly supported by ISF grant 1475/18.</li> </ul> </div> </section> </div> <div class="col-lg-8 mt-2"> <section class="cite-as mt-3"> <h2>Cite As<span class="btn btn-primary btn-xs" style="float: right" data-bs-toggle="modal" data-bs-target="#bibtex-modal">Get BibTex</span></h2> <div class="content"> 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)<br> <a href="https://doi.org/10.4230/LIPIcs.CPM.2019.6" style="word-break: break-all">https://doi.org/10.4230/LIPIcs.CPM.2019.6</a> </div> <div class="modal fade" id="bibtex-modal" tabindex="-1" aria-labelledby="bibtexModalLabel" aria-hidden="true"> <div class="modal-dialog modal-dialog-centered"> <div class="modal-content"> <div class="modal-header"> <h5 class="modal-title" id="bibtexModalLabel">BibTex</h5> <button type="button" class="btn-close" data-bs-dismiss="modal" aria-label="Close"></button> </div> <div class="modal-body"> <pre class="bibtex">@InProceedings{amir_et_al:LIPIcs.CPM.2019.6, author = {Amir, Amihood and Kondratovsky, Eitan}, title = {{Sufficient Conditions for Efficient Indexing Under Different Matchings}}, booktitle = {30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)}, pages = {6:1--6:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-103-0}, ISSN = {1868-8969}, year = {2019}, volume = {128}, editor = {Pisanti, Nadia and P. Pissis, Solon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.6}, URN = {urn:nbn:de:0030-drops-104773}, doi = {10.4230/LIPIcs.CPM.2019.6}, annote = {Keywords: off-the-shelf indexing algorithms, general matching relations, weaker sufficient conditions for indexing} }</pre> <div style="overflow: hidden"> <textarea style="position: absolute; top: -400vh" id="bibtex-input">@InProceedings{amir_et_al:LIPIcs.CPM.2019.6, author = {Amir, Amihood and Kondratovsky, Eitan}, title = {{Sufficient Conditions for Efficient Indexing Under Different Matchings}}, booktitle = {30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)}, pages = {6:1--6:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-103-0}, ISSN = {1868-8969}, year = {2019}, volume = {128}, editor = {Pisanti, Nadia and P. Pissis, Solon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.6}, URN = {urn:nbn:de:0030-drops-104773}, doi = {10.4230/LIPIcs.CPM.2019.6}, annote = {Keywords: off-the-shelf indexing algorithms, general matching relations, weaker sufficient conditions for indexing} }</textarea> </div> </div> <div class="modal-footer"> <button type="button" class="btn btn-secondary" data-bs-dismiss="modal">Close</button> <button type="button" class="btn btn-primary copy-to-clipboard" data-selector="bibtex-input"><i class="bi bi-clipboard"></i> Copy BibTex To Clipboard<span class="bi bi-check -hidden" style="padding-left: 1em; font-weight: bold"></span></button> </div> </div> </div> </div> </section> <section class="abstract"> <h2>Abstract</h2> <div class="content"> 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. </div> </section> <section class="subject-classifications mt-3"> <h2>Subject Classification</h2> <div class="acm-subject-classifications"> <h5>ACM Subject Classification</h5> <div class="content"> <ul> <li>Theory of computation → Pattern matching</li> </ul> </div> </div> <div class="keywords"> <h5>Keywords</h5> <div class="content"> <ul class="list-style-comma"> <li>off-the-shelf indexing algorithms</li> <li>general matching relations</li> <li>weaker sufficient conditions for indexing</li> </ul> </div> </div> </section> <section class="metrics mt-3"> <h2>Metrics</h2> <div class="content"> <ul> <li> <a href="#" class="btn-statistics" data-entity="document/10.4230/LIPIcs.CPM.2019.6" data-title="Sufficient Conditions for Efficient Indexing Under Different Matchings"> <i class="bi bi-graph-up"></i> Access Statistics </a> </li> <li> Total Accesses (updated on a weekly basis) <div class="stats-total"> <div class="stats total-downloads"> <div class="circle"> <div class="number" data-number="0">0</div> </div> <div class="label">PDF Downloads</div> </div> <div class="stats total-metadata-views"> <div class="circle"> <div class="number" data-number="0">0</div> </div> <div class="label">Metadata Views</div> </div> </div> <!-- must be externally available for the series/journal case --> </li> </ul> </div> </section> <div class="offcanvas offcanvas-bottom" tabindex="-1" id="statistics-offcanvas" aria-labelledby="statistics-offcanvas"> <div class="offcanvas-header"> <h5 class="offcanvas-title"></h5> <button type="button" class="btn-close text-reset" data-bs-dismiss="offcanvas" aria-label="Close"></button> </div> <div class="offcanvas-body small" data-context=""> <div style="margin-top: 20vh" class="centered-loader"><div class="loader"></div></div> <iframe class="-hidden"></iframe> </div> </div> <section class="references mt-3"> <h2>References</h2> <div class="content"> <ol> <li> <span> 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: <a href="http://doi.org/10.1098/rsta.2013.0132">http://doi.org/10.1098/rsta.2013.0132</a>. </span> </li> <li> <span> 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. <a href="https://scholar.google.com/scholar?hl=en&q=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." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> A. Amir, M. Farach, and S. Muthukrishnan. Alphabet Dependence in Parameterized Matching. Information Processing Letters, 49:111-115, 1994. <a href="https://scholar.google.com/scholar?hl=en&q=A. Amir, M. Farach, and S. Muthukrishnan. Alphabet Dependence in Parameterized Matching. Information Processing Letters, 49:111-115, 1994." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> 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. <a href="https://scholar.google.com/scholar?hl=en&q=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." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> B. S. Baker. Parameterized Pattern Matching: Algorithms and Applications. Journal of Computer and System Sciences, 52(1):28-42, 1996. <a href="https://scholar.google.com/scholar?hl=en&q=B. S. Baker. Parameterized Pattern Matching: Algorithms and Applications. Journal of Computer and System Sciences, 52(1):28-42, 1996." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> B. S. Baker. Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance. SIAM J. Comput., 26(5):1343-1362, 1997. <a href="https://scholar.google.com/scholar?hl=en&q=B. S. Baker. Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance. SIAM J. Comput., 26(5):1343-1362, 1997." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> 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. <a href="https://scholar.google.com/scholar?hl=en&q=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." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> R. Cole and R. Hariharan. Dynamic LCA Queries in Trees. In Proc. 10th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 235-244, 1999. <a href="https://scholar.google.com/scholar?hl=en&q=R. Cole and R. Hariharan. Dynamic LCA Queries in Trees. In Proc. 10th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 235-244, 1999." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> R. Cole and R. Hariharan. Faster Suffix Tree Construction with Missing Suffix Links. SIAM J. Comput., 33(1):26-42, 2003. <a href="https://scholar.google.com/scholar?hl=en&q=R. Cole and R. Hariharan. Faster Suffix Tree Construction with Missing Suffix Links. SIAM J. Comput., 33(1):26-42, 2003." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> 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. <a href="https://scholar.google.com/scholar?hl=en&q=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." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> M. Farach. Optimal Suffix Tree Construction with Large Alphabets. Proc. 38th IEEE Symposium on Foundations of Computer Science, pages 137-143, 1997. <a href="https://scholar.google.com/scholar?hl=en&q=M. Farach. Optimal Suffix Tree Construction with Large Alphabets. Proc. 38th IEEE Symposium on Foundations of Computer Science, pages 137-143, 1997." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> P. Ferragina and G. Manzini. Indexing Compressed Texts. J. of the ACM, 52(4):552-581, 2005. <a href="https://scholar.google.com/scholar?hl=en&q=P. Ferragina and G. Manzini. Indexing Compressed Texts. J. of the ACM, 52(4):552-581, 2005." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> R. Giancarlo. A Generalization of the Suffix Tree to Square Matrices, with Applications. SIAM J. Comput., 24(3):520-562, 1995. <a href="https://scholar.google.com/scholar?hl=en&q=R. Giancarlo. A Generalization of the Suffix Tree to Square Matrices, with Applications. SIAM J. Comput., 24(3):520-562, 1995." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> 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. <a href="https://scholar.google.com/scholar?hl=en&q=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." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> 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. <a href="https://scholar.google.com/scholar?hl=en&q=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." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> 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. <a href="https://scholar.google.com/scholar?hl=en&q=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." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> 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. <a href="https://scholar.google.com/scholar?hl=en&q=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." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> T. Kopelowitz. On-line Indexing for General Alphabets. In Proc. 53rd IEEE Symposium on the Foundation of Computer Science (FOCS), 2012. <a href="https://scholar.google.com/scholar?hl=en&q=T. Kopelowitz. On-line Indexing for General Alphabets. In Proc. 53rd IEEE Symposium on the Foundation of Computer Science (FOCS), 2012." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> 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. <a href="https://scholar.google.com/scholar?hl=en&q=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." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> G.M. Landau and U. Vishkin. Efficient string matching with k mismatches. Theoretical Computer Science, 43:239-249, 1986. <a href="https://scholar.google.com/scholar?hl=en&q=G.M. Landau and U. Vishkin. Efficient string matching with k mismatches. Theoretical Computer Science, 43:239-249, 1986." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> T. Lee, J.C. Na, and K. Park. On-Line Construction of Parameterized Suffix Trees. Information Processing Letters, 111(5):201-207, 2011. <a href="https://scholar.google.com/scholar?hl=en&q=T. Lee, J.C. Na, and K. Park. On-Line Construction of Parameterized Suffix Trees. Information Processing Letters, 111(5):201-207, 2011." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> 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. <a href="https://scholar.google.com/scholar?hl=en&q=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." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> E. M. McCreight. A space-economical suffix tree construction algorithm. J. of the ACM, 23:262-272, 1976. <a href="https://scholar.google.com/scholar?hl=en&q=E. M. McCreight. A space-economical suffix tree construction algorithm. J. of the ACM, 23:262-272, 1976." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> 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. <a href="https://scholar.google.com/scholar?hl=en&q=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." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> 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. <a href="https://scholar.google.com/scholar?hl=en&q=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." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> E. Ukkonen. On-line Construction of Suffix Trees. Algorithmica, 14:249-260, 1995. <a href="https://scholar.google.com/scholar?hl=en&q=E. Ukkonen. On-line Construction of Suffix Trees. Algorithmica, 14:249-260, 1995." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and Implementation of an Efficient Priority Queue. Mathematical Systems Theory, 10:99-127, 1977. <a href="https://scholar.google.com/scholar?hl=en&q=P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and Implementation of an Efficient Priority Queue. Mathematical Systems Theory, 10:99-127, 1977." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> <li> <span> P. Weiner. Linear Pattern Matching Algorithm. Proc. 14 IEEE Symposium on Switching and Automata Theory, pages 1-11, 1973. <a href="https://scholar.google.com/scholar?hl=en&q=P. Weiner. Linear Pattern Matching Algorithm. Proc. 14 IEEE Symposium on Switching and Automata Theory, pages 1-11, 1973." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"/></a> </span> </li> </ol> </div> </section> </div> </div> </div> </div> <span class="_feedback-button"> <i class="bi bi-question-circle"></i> <span class="text">Questions / Remarks / Feedback</span> </span> <div class="_feedback-form -hidden"> <span class="_feedback-close">X</span> <p>Feedback for Dagstuhl Publishing</p> <div> <textarea class="form-control" name="_feedback"></textarea> <input class="form-control" type="text" name="name" autocomplete="off" placeholder="Name (optional)" maxlength="60" /> <input class="form-control" type="email" name="email" autocomplete="off" placeholder="Email (optional)" maxlength="60" /> <br/> <button class="btn btn-sm btn-default">Send</button> </div> </div> <div class="alert alert-success _feedback-success -hidden"> <span class="glyphicon glyphicon-ok"></span> <h3>Thanks for your feedback!</h3> <div>Feedback submitted</div> <button class="btn btn-white _feedback-done">OK</button> </div> <div class="alert alert-danger _feedback-error -hidden"> <span class="glyphicon glyphicon-remove"></span> <h3>Could not send message</h3> <div>Please try again later or send an <a href="mailto:publishing@dagstuhl.de">E-mail</a></div> <button class="btn btn-white _feedback-done">OK</button> </div> <a class="scroll-up-button -hidden" href="#_top-of-page"> <i class="bi bi-arrow-up-circle"></i> </a> <footer class="page-footer dark"> <div class="container"> <h5>About DROPS</h5> <p>Schloss Dagstuhl - Leibniz Center for Informatics has been operating the Dagstuhl Research Online Publication Server (short: DROPS) since 2004. DROPS enables publication of the latest research findings in a fast, uncomplicated manner, in addition to providing unimpeded, open access to them. All the requisite metadata on each publication is administered in accordance with general guidelines pertaining to online publications (cf. Dublin Core). This enables the online publications to be authorized for citation and made accessible to a wide readership on a permanent basis. Access is free of charge for readers following the open access idea which fosters unimpeded access to scientific publications. </p> </div> <div class="container"> <div class="row"> <div class="col-lg-6"> <h5>Instructions for Authors</h5> <div class="row"> <div class="col-sm-6"> <b>Dagstuhl Series</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/lipics#author">LIPIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/oasics#author">OASIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dfu#author">Dagstuhl Follow-Ups</a></li> </ul> </div> <div class="col-sm-6"> <b>Dagstuhl Journals</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/darts#author">DARTS – Dagstuhl Artifacts Series</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagrep#author">Dagstuhl Reports</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagman#author">Dagstuhl Manifestos</a></li> <li><a href="https://submission.dagstuhl.de/series/details/lites#author">LITES</a></li> <li><a href="https://submission.dagstuhl.de/series/details/tgdk#author">TGDK – Transactions on Graph Data and Knowledge</a></li> </ul> </div> </div> </div> <div class="col-lg-6"> <h5>Instructions for Editors</h5> <div class="row"> <div class="col-sm-6"> <b>Dagstuhl Series</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/lipics#editor">LIPIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/oasics#editor">OASIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dfu#editor">Dagstuhl Follow-Ups</a></li> </ul> </div> <div class="col-sm-6"> <b>Dagstuhl Journals</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/darts#editor">DARTS – Dagstuhl Artifacts Series</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagrep#editor">Dagstuhl Reports</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagman#editor">Dagstuhl Manifestos</a></li> <li><a href="https://submission.dagstuhl.de/series/details/lites#editor">LITES</a></li> <li><a href="https://submission.dagstuhl.de/series/details/tgdk#editor">TGDK – Transactions on Graph Data and Knowledge</a></li> </ul> </div> </div> </div> </div> </div> </footer> <div class="copyright"> © 2023-2024 <a href="https://www.dagstuhl.de">Schloss Dagstuhl – LZI GmbH</a> <a href="https://drops.dagstuhl.de/docs/imprint">Imprint</a> <a href="https://drops.dagstuhl.de/docs/privacy">Privacy</a> <a href="https://www.dagstuhl.de/en/publishing/team">Contact</a> </div> <script type="text/javascript" src="https://drops.dagstuhl.de/js/jquery-3.6.0.min.js"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/app.js?drops-core-2024-10-22"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/popper.min.js"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/circle-progress.js"></script> <script type="text/javascript"> $(document).ready(function() { const view = { statsServer: 'https://drops-stats.dagstuhl.de', animationStarted: false, isScrolledIntoView: function (elem) { const rect = elem.getBoundingClientRect(); const elemTop = rect.top; //const elemBottom = rect.bottom; // const elemHeight = rect.height; return (elemTop >= 0) && (elemTop <= window.innerHeight); }, progressCircle: function ($el) { $el.find('.circle').circleProgress({ value: 1, size: 80, fill: { color: '#555' }, animation: { duration: 1200 } }); }, countUp: function($el) { $el.find('.number').each(function() { const $this = $(this); const number = parseInt($this.attr('data-number')); let suffix = ''; if (number > 90000) { $this.text(Math.ceil(number/1000)+' k'); suffix = ' k'; } else if (number > 90000000) { $this.text(Math.ceil(number/1000000)+' m'); suffix = ' m'; } else { $this.text(Math.ceil(number)) } $({ Counter: 0 }).animate({ Counter: $this.text().replace(suffix, '').replace(',', '') }, { duration: 1000, easing: 'swing', step: function() { $this.text(Math.ceil(this.Counter).toString().replace(/\B(?=(\d{3})+(?!\d))/g, ",") + suffix); } }); }); }, checkVisibility: function() { const $container = $('.stats-total'); if (view.isScrolledIntoView($container[0])) { if (!view.animationStarted) { view.animationStarted = true; view.progressCircle($container); setTimeout(function() { view.countUp($container) }, 200); } } }, initialize: function() { $.ajax({ type: 'get', url: view.statsServer + '/api/external/drops2/document/10.4230/LIPIcs.CPM.2019.6/-/stats', success: function (result) { $('.total-downloads .number').attr('data-number', result.total.downloads); $('.total-metadata-views .number').attr('data-number', result.total.clicks); window.addEventListener('scroll', view.checkVisibility); view.checkVisibility(); }, error: function () { $('.total-downloads .number').text(0); $('.total-metadata-views .number').text(0); window.addEventListener('scroll', view.checkVisibility); view.checkVisibility(); } }); } }; view.initialize(); }); </script> <script type="text/javascript"> $(document).ready(function() { const statistics = { statsServer: 'https://drops-stats.dagstuhl.de', showStatistics: function(e) { e.preventDefault(); const $offCanvas = $('#statistics-offcanvas'); const $iframe = $offCanvas.find('iframe'); const $loader = $offCanvas.find('.centered-loader'); $iframe.addClass('-hidden'); $loader.removeClass('-hidden'); $iframe[0].onload = function () { $iframe.removeClass('-hidden'); $loader.addClass('-hidden'); }.bind(this); const modeParameter = ''; const $target = $(e.currentTarget); const entityId = $target.attr('data-entity'); const title = $target.attr('data-title'); const embedUrl = statistics.statsServer + '/embed/external/drops2/' + entityId + modeParameter; let context = $offCanvas.find('.offcanvas-body').attr('data-context'); if (context === title) { context = ''; } if (context !== '') { context += '<br>'; } $offCanvas.find('.offcanvas-title').html(context + '<h2 style="font-weight: bold">' + title + '</h2>'); $offCanvas.offcanvas('show'); $offCanvas.find('iframe').attr('src', embedUrl); return false; }, initialize: function() { $('.btn-statistics').on('click', this.showStatistics); } }; statistics.initialize(); }); </script> <script type="text/javascript"> function _enableFeedback() { var $feedbackButton = $('._feedback-button, .fixed-beta-button'); var $feedbackClose = $('._feedback-close'); var $feedbackForm = $('._feedback-form'); var $feedbackSubmit = $('._feedback-form button'); var $textarea = $feedbackForm.find('textarea'); var $feedbackSuccess = $('._feedback-success'); var $feedbackError = $('._feedback-error'); var $feedbackDoneButton = $('._feedback-done'); $feedbackButton.addClass('_show'); $feedbackButton.on('click', function () { $feedbackButton.addClass('-hidden'); $feedbackForm.removeClass('-hidden'); $textarea.focus(); }); $feedbackClose.on('click', function () { $feedbackSuccess.addClass('-hidden'); $feedbackForm.addClass('-hidden'); $feedbackButton.removeClass('-hidden'); }); $feedbackDoneButton.on('click', function () { $feedbackError.addClass('-hidden'); $feedbackSuccess.addClass('-hidden'); $feedbackForm.addClass('-hidden'); $feedbackButton.removeClass('-hidden'); }); $feedbackSubmit.on('click', function () { var message = $textarea.val(); if (message === undefined) { message = ''; } if (message.trim() !== '') { $.ajax({ url: '/api/v1/feedback', type: 'post', data: { content: message, context: window.location.href, name: $('input[name="name"]').val(), email: $('input[name="email"]').val(), }, success: function (result) { if (result === 'success') { $textarea.val(''); $feedbackSuccess.removeClass('-hidden'); } else { $feedbackError.removeClass('-hidden'); } }, error: function () { $feedbackError.removeClass('-hidden'); } }); } }); } var _defer_counter = 0; function _defer(method) { if (window.jQuery) { method(); } else { if (_defer_counter < 20) { setTimeout(function () { _defer(method); console.log(_defer_counter); _defer_counter++; }, 500); } } } setTimeout(function() { _defer(_enableFeedback); }, 1000); </script> <script type="text/javascript"> $(document).ready(function() { const app = { maxScrollPos: window.innerWidth < 500 ? 100 // mobile : 400, // desktop $el : { navbarSearch: $('nav .navbar-search'), fixedSearchButton: $('.fixed-search-button'), copyToClipboard: $('.copy-to-clipboard') }, methods: { hideMenuOnScroll: function(scrollPos) { const $menu = $('nav.navbar.main'); const $stickySearch = $('.search.sticky'); const $banner = $('#_banner'); const $fixedSearchButton = $('.fixed-search-button'); if (scrollPos > app.maxScrollPos) { $menu.addClass('-hide'); $banner.addClass('-hide'); $stickySearch.addClass('-top'); $fixedSearchButton.addClass('-show'); } else { app.methods.showMenu(null, false); } }, showMenu: function(e, focus) { const $menu = $('nav.navbar.main'); const $stickySearch = $('.search.sticky'); const $banner = $('#_banner'); const $fixedSearchButton = $('.fixed-search-button'); $menu.removeClass('-hide'); $banner.removeClass('-hide'); $stickySearch.removeClass('-top'); $fixedSearchButton.removeClass('-show'); if (focus !== false) { $('.navbar-search').find('input[name="term"]').focus(); } }, showUpLinkOnScroll: function(scrollPos) { const $upLink = $('.scroll-up-button'); if (scrollPos > app.maxScrollPos) { $upLink.removeClass('-hidden'); } else { $upLink.addClass('-hidden'); } }, scrollHandler: function() { const scrollPos = $(document).scrollTop(); app.methods.hideMenuOnScroll(scrollPos); app.methods.showUpLinkOnScroll(scrollPos); }, copyToClipboard: function(e) { e.preventDefault(); const $current = $(e.currentTarget); // console.log($current.attr('data-selector')); const element = $('#'+$current.attr('data-selector'))[0]; console.log(element); element.select(); document.execCommand("copy"); const $success = $current.find('.bi-check'); $success.removeClass('-hidden'); setTimeout(function() { $success.addClass('-hidden'); }, 1000); }, initTooltips: function() { const tooltipTriggerList = [].slice.call(document.querySelectorAll('[data-bs-toggle="tooltip"]')) const tooltipList = tooltipTriggerList.map(function (tooltipTriggerEl) { return new bootstrap.Tooltip(tooltipTriggerEl) }); }, expandSearch: function() { app.$el.navbarSearch.addClass('expanded'); }, collapseSearch: function(e) { if (!$(e.currentTarget).is('button.btn-outline-success')) { app.$el.navbarSearch.removeClass('expanded'); } }, initDeepLinksTabs: function() { const innerAnchors = [ 'resource-articles', 'cfp-si-resources', 'cfp-si-autonomous-systems-and-knowledge-graphs' ]; let anchors = []; $('a[role="tab"]').each(function() { anchors.push($(this).attr('aria-controls')); }); innerAnchors.forEach(function(anchor) { if ($('#'+anchor).length > 0) { anchors.push(anchor); } }); if (anchors.length === 0) { return; } let selectedAnchor = window.location.hash.substring(1); if (anchors.indexOf(selectedAnchor) === -1) { $('#publications-tab').tab('show'); window.scrollTo(0,0); return; } if (selectedAnchor !== 'publications') { const innerAnchorIndex = innerAnchors.indexOf(selectedAnchor); // anchor sits inside tab -> open the tab first, then scroll to anchor if (innerAnchorIndex > -1) { const $tab = $('#'+selectedAnchor).closest('.tab-pane'); console.log($tab); try { $('#'+$tab.attr('id')+'-tab').tab('show'); } catch (e) { } setTimeout(function () { $('#' + selectedAnchor)[0].scrollIntoView(); }, 800); } else { try { $('#' + selectedAnchor + '-tab').tab('show'); } catch (e) { } window.scrollTo(0, 0); } } $('[data-tab-link]').on('click', function(e) { const $target = $(e.currentTarget); let href = $target.attr('href'); let scrollLink = null; if (href === '#cfp-si-list') { scrollLink = href; href = '#cfp'; } try { console.log(href); $(href+'-tab').tab('show'); } catch(e) { } console.log(scrollLink); if (scrollLink !== null) { setTimeout(function() { $(scrollLink)[0].scrollIntoView(); }, 200); } else { setTimeout(function() { window.scrollTo(0,0); }, 200); } }); } }, initialize: function() { $(window).on('scroll', app.methods.scrollHandler); $(window).on('scroll-to-top', function() { window.scrollTo(0,0) }); $(document).trigger('scroll'); // set correct status for scroll-related parts (navbar/back-to-top) on page reload app.$el.copyToClipboard.on('click', app.methods.copyToClipboard); app.$el.fixedSearchButton.on('click', app.methods.showMenu); app.$el.navbarSearch.find('input').on('click', app.methods.expandSearch) app.$el.navbarSearch.find('input').on('blur', app.methods.collapseSearch); app.methods.initTooltips(); app.methods.initDeepLinksTabs(); } }; app.initialize(); }); </script> </body> </html>