Full-Fledged Real-Time Indexing for Constant Size Alphabets View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2017-10

AUTHORS

Gregory Kucherov, Yakov Nekrich

ABSTRACT

In this paper we describe a data structure that supports pattern matching queries on a dynamically arriving text over an alphabet of constant size. Each new symbol can be prepended to T in O(1) worst-case time. At any moment, we can report all occurrences of a pattern P in the current text in O(|P|+k) time, where |P| is the length of P and k is the number of occurrences. This resolves, under assumption of constant size alphabet, a long-standing open problem of existence of a real-time indexing method for string matching (see Amir and Nor in Real-time indexing over fixed finite alphabets, pp. 1086–1095, 2008). More... »

PAGES

387-400

References to SciGraph publications

  • 2011. Simple Real-Time Constant-Space String Matching in COMBINATORIAL PATTERN MATCHING
  • 1976-12. Design and implementation of an efficient priority queue in MATHEMATICAL SYSTEMS THEORY
  • 2005. Towards Real-Time Suffix Tree Construction in STRING PROCESSING AND INFORMATION RETRIEVAL
  • 2015. Alphabet-Dependent String Searching with Wexponential Search Trees in COMBINATORIAL PATTERN MATCHING
  • 2012. Cross-Document Pattern Matching in COMBINATORIAL PATTERN MATCHING
  • 1978. String-matching in real time: Some properties of the data structure in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 1978
  • 2011. Near Real-Time Suffix Tree Construction via the Fringe Marked Ancestor Problem in STRING PROCESSING AND INFORMATION RETRIEVAL
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00453-016-0199-7

    DOI

    http://dx.doi.org/10.1007/s00453-016-0199-7

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1048466616


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Laboratoire d'Informatique Gaspard-Monge", 
              "id": "https://www.grid.ac/institutes/grid.462940.d", 
              "name": [
                "Laboratoire d\u2019Informatique Gaspard Monge, Universit\u00e9 Paris-Est & CNRS, Marne-la-Vall\u00e9e, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kucherov", 
            "givenName": "Gregory", 
            "id": "sg:person.013163701366.40", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013163701366.40"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Waterloo", 
              "id": "https://www.grid.ac/institutes/grid.46078.3d", 
              "name": [
                "Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Nekrich", 
            "givenName": "Yakov", 
            "id": "sg:person.014556642366.63", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014556642366.63"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-08921-7_97", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001138670", 
              "https://doi.org/10.1007/3-540-08921-7_97"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/322234.322244", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002627098"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-21458-5_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011929559", 
              "https://doi.org/10.1007/978-3-642-21458-5_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-21458-5_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011929559", 
              "https://doi.org/10.1007/978-3-642-21458-5_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-31265-6_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012866216", 
              "https://doi.org/10.1007/978-3-642-31265-6_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11575832_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017195072", 
              "https://doi.org/10.1007/11575832_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11575832_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017195072", 
              "https://doi.org/10.1007/11575832_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1541885.1541889", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017405123"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0022-0000(05)80064-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017760034"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/28395.28434", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022759585"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-24583-1_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028745906", 
              "https://doi.org/10.1007/978-3-642-24583-1_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/195058.195170", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037964780"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0890-5401(92)90034-d", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045238564"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-19929-0_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050208184", 
              "https://doi.org/10.1007/978-3-319-19929-0_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01683268", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053048814", 
              "https://doi.org/10.1007/bf01683268"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01683268", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053048814", 
              "https://doi.org/10.1007/bf01683268"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539700370539", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062879236"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9781611973099.84", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1088801552"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/focs.2012.79", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095553984"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2017-10", 
        "datePublishedReg": "2017-10-01", 
        "description": "In this paper we describe a data structure that supports pattern matching queries on a dynamically arriving text over an alphabet of constant size. Each new symbol can be prepended to T in O(1) worst-case time. At any moment, we can report all occurrences of a pattern P in the current text in O(|P|+k) time, where |P| is the length of P and k is the number of occurrences. This resolves, under assumption of constant size alphabet, a long-standing open problem of existence of a real-time indexing method for string matching (see Amir and Nor in Real-time indexing over fixed finite alphabets, pp. 1086\u20131095, 2008).", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00453-016-0199-7", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "79"
          }
        ], 
        "name": "Full-Fledged Real-Time Indexing for Constant Size Alphabets", 
        "pagination": "387-400", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "e6e2e2a700d28b29771aa4a0e3716637dbe53e72030279219faac0cbe9db4ea0"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00453-016-0199-7"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1048466616"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00453-016-0199-7", 
          "https://app.dimensions.ai/details/publication/pub.1048466616"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T12:41", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000363_0000000363/records_70053_00000002.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs00453-016-0199-7"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00453-016-0199-7'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00453-016-0199-7'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-016-0199-7'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-016-0199-7'


     

    This table displays all metadata directly associated to this object as RDF triples.

    126 TRIPLES      21 PREDICATES      43 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00453-016-0199-7 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N92e43df91f604a3d9bc08b5ee2c9ad76
    4 schema:citation sg:pub.10.1007/11575832_9
    5 sg:pub.10.1007/3-540-08921-7_97
    6 sg:pub.10.1007/978-3-319-19929-0_14
    7 sg:pub.10.1007/978-3-642-21458-5_16
    8 sg:pub.10.1007/978-3-642-24583-1_16
    9 sg:pub.10.1007/978-3-642-31265-6_16
    10 sg:pub.10.1007/bf01683268
    11 https://doi.org/10.1016/0890-5401(92)90034-d
    12 https://doi.org/10.1016/s0022-0000(05)80064-9
    13 https://doi.org/10.1109/focs.2012.79
    14 https://doi.org/10.1137/1.9781611973099.84
    15 https://doi.org/10.1137/s0097539700370539
    16 https://doi.org/10.1145/1541885.1541889
    17 https://doi.org/10.1145/195058.195170
    18 https://doi.org/10.1145/28395.28434
    19 https://doi.org/10.1145/322234.322244
    20 schema:datePublished 2017-10
    21 schema:datePublishedReg 2017-10-01
    22 schema:description In this paper we describe a data structure that supports pattern matching queries on a dynamically arriving text over an alphabet of constant size. Each new symbol can be prepended to T in O(1) worst-case time. At any moment, we can report all occurrences of a pattern P in the current text in O(|P|+k) time, where |P| is the length of P and k is the number of occurrences. This resolves, under assumption of constant size alphabet, a long-standing open problem of existence of a real-time indexing method for string matching (see Amir and Nor in Real-time indexing over fixed finite alphabets, pp. 1086–1095, 2008).
    23 schema:genre research_article
    24 schema:inLanguage en
    25 schema:isAccessibleForFree true
    26 schema:isPartOf N6b4d7bf65e084b1fa15dd430c0c3dd59
    27 Nb93797a1a863419fbc56bc1aeae56e55
    28 sg:journal.1047644
    29 schema:name Full-Fledged Real-Time Indexing for Constant Size Alphabets
    30 schema:pagination 387-400
    31 schema:productId N3c09999530044f0380e8bab931c95334
    32 N59fca13a77e94313a161a64d538ad5f8
    33 Nafebb50db4fd43738b332822f58dbcde
    34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048466616
    35 https://doi.org/10.1007/s00453-016-0199-7
    36 schema:sdDatePublished 2019-04-11T12:41
    37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    38 schema:sdPublisher N5f2f5cc5bacd4892bf3903b5e8006839
    39 schema:url https://link.springer.com/10.1007%2Fs00453-016-0199-7
    40 sgo:license sg:explorer/license/
    41 sgo:sdDataset articles
    42 rdf:type schema:ScholarlyArticle
    43 N3c09999530044f0380e8bab931c95334 schema:name doi
    44 schema:value 10.1007/s00453-016-0199-7
    45 rdf:type schema:PropertyValue
    46 N59fca13a77e94313a161a64d538ad5f8 schema:name readcube_id
    47 schema:value e6e2e2a700d28b29771aa4a0e3716637dbe53e72030279219faac0cbe9db4ea0
    48 rdf:type schema:PropertyValue
    49 N5f2f5cc5bacd4892bf3903b5e8006839 schema:name Springer Nature - SN SciGraph project
    50 rdf:type schema:Organization
    51 N67dc81f0194a4296b4265fc2c524ff4f rdf:first sg:person.014556642366.63
    52 rdf:rest rdf:nil
    53 N6b4d7bf65e084b1fa15dd430c0c3dd59 schema:volumeNumber 79
    54 rdf:type schema:PublicationVolume
    55 N92e43df91f604a3d9bc08b5ee2c9ad76 rdf:first sg:person.013163701366.40
    56 rdf:rest N67dc81f0194a4296b4265fc2c524ff4f
    57 Nafebb50db4fd43738b332822f58dbcde schema:name dimensions_id
    58 schema:value pub.1048466616
    59 rdf:type schema:PropertyValue
    60 Nb93797a1a863419fbc56bc1aeae56e55 schema:issueNumber 2
    61 rdf:type schema:PublicationIssue
    62 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    63 schema:name Information and Computing Sciences
    64 rdf:type schema:DefinedTerm
    65 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    66 schema:name Artificial Intelligence and Image Processing
    67 rdf:type schema:DefinedTerm
    68 sg:journal.1047644 schema:issn 0178-4617
    69 1432-0541
    70 schema:name Algorithmica
    71 rdf:type schema:Periodical
    72 sg:person.013163701366.40 schema:affiliation https://www.grid.ac/institutes/grid.462940.d
    73 schema:familyName Kucherov
    74 schema:givenName Gregory
    75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013163701366.40
    76 rdf:type schema:Person
    77 sg:person.014556642366.63 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
    78 schema:familyName Nekrich
    79 schema:givenName Yakov
    80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014556642366.63
    81 rdf:type schema:Person
    82 sg:pub.10.1007/11575832_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017195072
    83 https://doi.org/10.1007/11575832_9
    84 rdf:type schema:CreativeWork
    85 sg:pub.10.1007/3-540-08921-7_97 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001138670
    86 https://doi.org/10.1007/3-540-08921-7_97
    87 rdf:type schema:CreativeWork
    88 sg:pub.10.1007/978-3-319-19929-0_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050208184
    89 https://doi.org/10.1007/978-3-319-19929-0_14
    90 rdf:type schema:CreativeWork
    91 sg:pub.10.1007/978-3-642-21458-5_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011929559
    92 https://doi.org/10.1007/978-3-642-21458-5_16
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/978-3-642-24583-1_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028745906
    95 https://doi.org/10.1007/978-3-642-24583-1_16
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/978-3-642-31265-6_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012866216
    98 https://doi.org/10.1007/978-3-642-31265-6_16
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/bf01683268 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053048814
    101 https://doi.org/10.1007/bf01683268
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1016/0890-5401(92)90034-d schema:sameAs https://app.dimensions.ai/details/publication/pub.1045238564
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1016/s0022-0000(05)80064-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017760034
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1109/focs.2012.79 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095553984
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1137/1.9781611973099.84 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801552
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1137/s0097539700370539 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879236
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1145/1541885.1541889 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017405123
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1145/195058.195170 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037964780
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1145/28395.28434 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022759585
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1145/322234.322244 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002627098
    120 rdf:type schema:CreativeWork
    121 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
    122 schema:name Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada
    123 rdf:type schema:Organization
    124 https://www.grid.ac/institutes/grid.462940.d schema:alternateName Laboratoire d'Informatique Gaspard-Monge
    125 schema:name Laboratoire d’Informatique Gaspard Monge, Université Paris-Est & CNRS, Marne-la-Vallée, France
    126 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...