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


Ontology type: schema:Chapter     


Chapter Info

DATE

2013

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) expected 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 [2]). More... »

PAGES

650-660

References to SciGraph publications

Book

TITLE

Automata, Languages, and Programming

ISBN

978-3-642-39205-4
978-3-642-39206-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-39206-1_55

DOI

http://dx.doi.org/10.1007/978-3-642-39206-1_55

DIMENSIONS

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


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/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "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, Paris, 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 Kansas", 
          "id": "https://www.grid.ac/institutes/grid.266515.3", 
          "name": [
            "Department of Electrical Engineering & Computer Science, University of Kansas, USA"
          ], 
          "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/978-3-540-27836-8_52", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014166115", 
          "https://doi.org/10.1007/978-3-540-27836-8_52"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-27836-8_52", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014166115", 
          "https://doi.org/10.1007/978-3-540-27836-8_52"
        ], 
        "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": "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": "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.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": "2013", 
    "datePublishedReg": "2013-01-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) expected worst-case time. At any moment, we can report all occurrences of a pattern P in the current text in O(|P|\u2009+\u2009k) 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 [2]).", 
    "editor": [
      {
        "familyName": "Fomin", 
        "givenName": "Fedor V.", 
        "type": "Person"
      }, 
      {
        "familyName": "Freivalds", 
        "givenName": "R\u016bsi\u0146\u0161", 
        "type": "Person"
      }, 
      {
        "familyName": "Kwiatkowska", 
        "givenName": "Marta", 
        "type": "Person"
      }, 
      {
        "familyName": "Peleg", 
        "givenName": "David", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-39206-1_55", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-39205-4", 
        "978-3-642-39206-1"
      ], 
      "name": "Automata, Languages, and Programming", 
      "type": "Book"
    }, 
    "name": "Full-Fledged Real-Time Indexing for Constant Size Alphabets", 
    "pagination": "650-660", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-39206-1_55"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "05d8641685a90bf5590e7c61fce2b2eea6319376393a76366ad272d237046dd3"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1001227120"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-39206-1_55", 
      "https://app.dimensions.ai/details/publication/pub.1001227120"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T12:29", 
    "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/0000000001_0000000264/records_8663_00000243.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-642-39206-1_55"
  }
]
 

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/978-3-642-39206-1_55'

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/978-3-642-39206-1_55'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-39206-1_55'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-39206-1_55'


 

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

129 TRIPLES      23 PREDICATES      38 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-39206-1_55 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N7f2904b9be024cb58305503fe1ab8865
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-540-27836-8_52
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 https://doi.org/10.1016/s0022-0000(05)80064-9
11 https://doi.org/10.1109/focs.2012.79
12 https://doi.org/10.1137/1.9781611973099.84
13 https://doi.org/10.1145/1541885.1541889
14 https://doi.org/10.1145/322234.322244
15 schema:datePublished 2013
16 schema:datePublishedReg 2013-01-01
17 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) expected 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 [2]).
18 schema:editor Nbf98f267a6aa4a8eaed9aafa3d5db856
19 schema:genre chapter
20 schema:inLanguage en
21 schema:isAccessibleForFree false
22 schema:isPartOf Nbf33c9e7fcd34132bbcb0910ce8f7b26
23 schema:name Full-Fledged Real-Time Indexing for Constant Size Alphabets
24 schema:pagination 650-660
25 schema:productId N11817c5277ec4202b796023a6c038a35
26 N8fcc53b914dc4c26b12099cabd506e3f
27 Na66e7bcb03f14bb7908b12d44d2272a1
28 schema:publisher Ndb40dc84d5de4079aaef999bdcd95268
29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001227120
30 https://doi.org/10.1007/978-3-642-39206-1_55
31 schema:sdDatePublished 2019-04-15T12:29
32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
33 schema:sdPublisher N4e5ceeac68994d6480bdd0dfb02434da
34 schema:url http://link.springer.com/10.1007/978-3-642-39206-1_55
35 sgo:license sg:explorer/license/
36 sgo:sdDataset chapters
37 rdf:type schema:Chapter
38 N1161ff4004724e99bbb8af71daec22f8 rdf:first sg:person.014556642366.63
39 rdf:rest rdf:nil
40 N11817c5277ec4202b796023a6c038a35 schema:name dimensions_id
41 schema:value pub.1001227120
42 rdf:type schema:PropertyValue
43 N27556f5a48134423a65c9301435d5411 rdf:first N6f0aec760bb2438f865e0b8f74206dfd
44 rdf:rest rdf:nil
45 N4e5ceeac68994d6480bdd0dfb02434da schema:name Springer Nature - SN SciGraph project
46 rdf:type schema:Organization
47 N53c338792ead42ceada98b70b4e2a194 rdf:first N768d47d179284a8b821861305fb72c09
48 rdf:rest N733ff966ad454fb38d7b9d033d5361f5
49 N6f0aec760bb2438f865e0b8f74206dfd schema:familyName Peleg
50 schema:givenName David
51 rdf:type schema:Person
52 N733ff966ad454fb38d7b9d033d5361f5 rdf:first N870dd6ba3a91433b872492e4d6dd2b38
53 rdf:rest N27556f5a48134423a65c9301435d5411
54 N768d47d179284a8b821861305fb72c09 schema:familyName Freivalds
55 schema:givenName Rūsiņš
56 rdf:type schema:Person
57 N7f2904b9be024cb58305503fe1ab8865 rdf:first sg:person.013163701366.40
58 rdf:rest N1161ff4004724e99bbb8af71daec22f8
59 N870dd6ba3a91433b872492e4d6dd2b38 schema:familyName Kwiatkowska
60 schema:givenName Marta
61 rdf:type schema:Person
62 N8fcc53b914dc4c26b12099cabd506e3f schema:name doi
63 schema:value 10.1007/978-3-642-39206-1_55
64 rdf:type schema:PropertyValue
65 Na66e7bcb03f14bb7908b12d44d2272a1 schema:name readcube_id
66 schema:value 05d8641685a90bf5590e7c61fce2b2eea6319376393a76366ad272d237046dd3
67 rdf:type schema:PropertyValue
68 Nbf33c9e7fcd34132bbcb0910ce8f7b26 schema:isbn 978-3-642-39205-4
69 978-3-642-39206-1
70 schema:name Automata, Languages, and Programming
71 rdf:type schema:Book
72 Nbf98f267a6aa4a8eaed9aafa3d5db856 rdf:first Nc7d2c709307d465b9f525232da50805f
73 rdf:rest N53c338792ead42ceada98b70b4e2a194
74 Nc7d2c709307d465b9f525232da50805f schema:familyName Fomin
75 schema:givenName Fedor V.
76 rdf:type schema:Person
77 Ndb40dc84d5de4079aaef999bdcd95268 schema:location Berlin, Heidelberg
78 schema:name Springer Berlin Heidelberg
79 rdf:type schema:Organisation
80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
81 schema:name Information and Computing Sciences
82 rdf:type schema:DefinedTerm
83 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
84 schema:name Information Systems
85 rdf:type schema:DefinedTerm
86 sg:person.013163701366.40 schema:affiliation https://www.grid.ac/institutes/grid.462940.d
87 schema:familyName Kucherov
88 schema:givenName Gregory
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013163701366.40
90 rdf:type schema:Person
91 sg:person.014556642366.63 schema:affiliation https://www.grid.ac/institutes/grid.266515.3
92 schema:familyName Nekrich
93 schema:givenName Yakov
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014556642366.63
95 rdf:type schema:Person
96 sg:pub.10.1007/11575832_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017195072
97 https://doi.org/10.1007/11575832_9
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/3-540-08921-7_97 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001138670
100 https://doi.org/10.1007/3-540-08921-7_97
101 rdf:type schema:CreativeWork
102 sg:pub.10.1007/978-3-540-27836-8_52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014166115
103 https://doi.org/10.1007/978-3-540-27836-8_52
104 rdf:type schema:CreativeWork
105 sg:pub.10.1007/978-3-642-21458-5_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011929559
106 https://doi.org/10.1007/978-3-642-21458-5_16
107 rdf:type schema:CreativeWork
108 sg:pub.10.1007/978-3-642-24583-1_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028745906
109 https://doi.org/10.1007/978-3-642-24583-1_16
110 rdf:type schema:CreativeWork
111 sg:pub.10.1007/978-3-642-31265-6_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012866216
112 https://doi.org/10.1007/978-3-642-31265-6_16
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1016/s0022-0000(05)80064-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017760034
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1109/focs.2012.79 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095553984
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1137/1.9781611973099.84 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801552
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1145/1541885.1541889 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017405123
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1145/322234.322244 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002627098
123 rdf:type schema:CreativeWork
124 https://www.grid.ac/institutes/grid.266515.3 schema:alternateName University of Kansas
125 schema:name Department of Electrical Engineering & Computer Science, University of Kansas, USA
126 rdf:type schema:Organization
127 https://www.grid.ac/institutes/grid.462940.d schema:alternateName Laboratoire d'Informatique Gaspard-Monge
128 schema:name Laboratoire d’Informatique Gaspard Monge, Université Paris-Est & CNRS, Marne-la-Vallée, Paris, France
129 rdf:type schema:Organization
 




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


...