Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Speeding Up Cover Time of Sparse Graphs Using Local Knowledge Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Fast Multiple Order-Preserving Matching Algorithms

verfasst von : Myoungji Han, Munseong Kang, Sukhyeun Cho, Geonmo Gu, Jeong Seop Sim, Kunsoo Park

Erschienen in: Combinatorial Algorithms

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Given a text T and a pattern P, the order-preserving matching problem is to find all substrings in T which have the same relative orders as P. Order-preserving matching has been an active research area since it was introduced by Kubica et al. [13] and Kim et al. [11]. In this paper we present two algorithms for the multiple order-preserving matching problem, one of which runs in sublinear time on average and the other in linear time on average. Both algorithms run much faster than the previous algorithms.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs
Nächstes Kapitel Minimum Degree Conditions and Optimal Graphs for Completely Independent Spanning Trees
Fußnoten
1
For the implementation of the van-Emde-Boas tree used in [2], we used the source code publicly available at https://​code.​google.​com/​p/​libveb/​.
 
Literatur
1.
Abramowitz, M., Stegun, I.A.: Handbook of Mathematical Functions. Dover, New York (1972)MATH
2.
Belazzougui, D., Pierrot, A., Raffinot, M., Vialette, S.: Single and multiple consecutive permutation motif search. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) Algorithms and Computation. LNCS, vol. 8283, pp. 66–77. Springer, Heidelberg (2013)CrossRef
3.
Chhabra, T., Tarhio, J.: Order-preserving matching with filtration. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 307–314. Springer, Heidelberg (2014)
4.
Cho, S., Na, J.C., Park, K., Sim, J.S.: A fast algorithm for order-preserving pattern matching. Inf. Process. Lett. 115(2), 397–402 (2015)CrossRefMathSciNetMATH
5.
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)MATH
6.
Crochemore, M., et al.: Order-preserving incomplete suffix trees and order-preserving indexes. In: Kurland, O., Lewenstein, M., Porat, E. (eds.) SPIRE 2013. LNCS, vol. 8214, pp. 84–95. Springer, Heidelberg (2013)CrossRef
7.
Faro, S., Külekci, O.: Efficient Algorithms for the Order Preserving Pattern Matching Problem. arXiv preprint arxiv:​1501.​04001 (2015)
8.
Gawrychowski, P., Uznański, P.: Order-preserving pattern matching with k mismatches. In: Kulikov, A.S., Kuznetsov, S.O., Pevzner, P. (eds.) CPM 2014. LNCS, vol. 8486, pp. 130–139. Springer, Heidelberg (2014)
9.
10.
Kim, J., Amir, A., Na, J.C., Park, K., Sim, J.S.: On representations of ternary order relations in numeric strings. In: ICABD, pp. 46–52. Springer (2014)
11.
Kim, J., Eades, P., Fleischer, R., Hong, S., Iliopoulos, C.S., Park, K., Puglisi, S.J., Tokuyama, T.: Order-preserving matching. Theoret. Comput. Sci. 525, 68–79 (2014)CrossRefMathSciNetMATH
12.
Knuth, D.E.: The Art of Computer Programming, vol. 2. Seminumerical Algorithms. Addison Wesley, Reading (1998)
13.
Kubica, M., Kulczyński, T., Radoszewski, J., Rytter, W., Waleń, T.: A linear time algorithm for consecutive permutation pattern matching. Inf. Process. Lett. 113(12), 430–433 (2013)CrossRefMATH
14.
Wu, S., Manber, U.: A fast algorithm for multi-pattern searching. Technical report. TR-94-17, Department of Computer Science, University of Arizona (1994)
Metadaten
Titel
Fast Multiple Order-Preserving Matching Algorithms
verfasst von
Myoungji Han
Munseong Kang
Sukhyeun Cho
Geonmo Gu
Jeong Seop Sim
Kunsoo Park
Copyright-Jahr
2016
Buch
Combinatorial Algorithms

Print ISBN: 978-3-319-29515-2

Electronic ISBN: 978-3-319-29516-9

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-29516-9_21

Premium Partner

    Bildnachweise