Fast Construction of Wavelet Trees View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2014

AUTHORS

J. Ian Munro , Yakov Nekrich , Jeffrey S. Vitter

ABSTRACT

In this paper we describe a fast algorithm that creates a wavelet tree for a sequence of symbols. We show that a wavelet tree can be constructed in \(O(n\lceil{\frac{\log \sigma}{\sqrt{\log n}}}\rceil)\) time where n is the number of symbols and σ is the alphabet size.

PAGES

101-110

References to SciGraph publications

  • 2011. Space Efficient Wavelet Tree Construction in STRING PROCESSING AND INFORMATION RETRIEVAL
  • 2011. On Wavelet Tree Construction in COMBINATORIAL PATTERN MATCHING
  • Book

    TITLE

    String Processing and Information Retrieval

    ISBN

    978-3-319-11917-5
    978-3-319-11918-2

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-319-11918-2_10

    DOI

    http://dx.doi.org/10.1007/978-3-319-11918-2_10

    DIMENSIONS

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


    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", 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Waterloo", 
              "id": "https://www.grid.ac/institutes/grid.46078.3d", 
              "name": [
                "David R. Cheriton School of Computer Science, University of Waterloo, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Munro", 
            "givenName": "J. Ian", 
            "id": "sg:person.010362264441.20", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010362264441.20"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Waterloo", 
              "id": "https://www.grid.ac/institutes/grid.46078.3d", 
              "name": [
                "David R. Cheriton School of Computer Science, University of 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"
          }, 
          {
            "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": "Vitter", 
            "givenName": "Jeffrey S.", 
            "id": "sg:person.0613677314.28", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-642-21458-5_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000271084", 
              "https://doi.org/10.1007/978-3-642-21458-5_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-24583-1_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043979341", 
              "https://doi.org/10.1007/978-3-642-24583-1_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-24583-1_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043979341", 
              "https://doi.org/10.1007/978-3-642-24583-1_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jda.2013.07.004", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046344664"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0217026", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062842045"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1989.63533", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086192305"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2014", 
        "datePublishedReg": "2014-01-01", 
        "description": "In this paper we describe a fast algorithm that creates a wavelet tree for a sequence of symbols. We show that a wavelet tree can be constructed in \\(O(n\\lceil{\\frac{\\log \\sigma}{\\sqrt{\\log n}}}\\rceil)\\) time where n is the number of symbols and \u03c3 is the alphabet size.", 
        "editor": [
          {
            "familyName": "Moura", 
            "givenName": "Edleno", 
            "type": "Person"
          }, 
          {
            "familyName": "Crochemore", 
            "givenName": "Maxime", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-319-11918-2_10", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-319-11917-5", 
            "978-3-319-11918-2"
          ], 
          "name": "String Processing and Information Retrieval", 
          "type": "Book"
        }, 
        "name": "Fast Construction of Wavelet Trees", 
        "pagination": "101-110", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-319-11918-2_10"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "bc2d76e7017d7ad112876676404d0757cf5c41533392b369b2b02e57b02a0018"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1039503668"
            ]
          }
        ], 
        "publisher": {
          "location": "Cham", 
          "name": "Springer International Publishing", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-319-11918-2_10", 
          "https://app.dimensions.ai/details/publication/pub.1039503668"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T21:03", 
        "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_8690_00000267.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-319-11918-2_10"
      }
    ]
     

    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-319-11918-2_10'

    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-319-11918-2_10'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-11918-2_10'

    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-319-11918-2_10'


     

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

    96 TRIPLES      22 PREDICATES      30 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-319-11918-2_10 schema:author N4434a186a46b405791ec4f23e277dace
    2 schema:citation sg:pub.10.1007/978-3-642-21458-5_19
    3 sg:pub.10.1007/978-3-642-24583-1_19
    4 https://doi.org/10.1016/j.jda.2013.07.004
    5 https://doi.org/10.1109/sfcs.1989.63533
    6 https://doi.org/10.1137/0217026
    7 schema:datePublished 2014
    8 schema:datePublishedReg 2014-01-01
    9 schema:description In this paper we describe a fast algorithm that creates a wavelet tree for a sequence of symbols. We show that a wavelet tree can be constructed in \(O(n\lceil{\frac{\log \sigma}{\sqrt{\log n}}}\rceil)\) time where n is the number of symbols and σ is the alphabet size.
    10 schema:editor N100e46aa8f534e3897deb4970956ade2
    11 schema:genre chapter
    12 schema:inLanguage en
    13 schema:isAccessibleForFree false
    14 schema:isPartOf N4c62207f45714d2a93a91f86c5011de0
    15 schema:name Fast Construction of Wavelet Trees
    16 schema:pagination 101-110
    17 schema:productId N533ec14ac116479487ee20505dacaefe
    18 N7e457fd56e9a45b898983a1b059ec6c6
    19 Nc9f8f4d734844592bf13c3c59d7061d9
    20 schema:publisher N1c96bcbeca7e422bbb597ea747e29335
    21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039503668
    22 https://doi.org/10.1007/978-3-319-11918-2_10
    23 schema:sdDatePublished 2019-04-15T21:03
    24 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    25 schema:sdPublisher N7f01e2cf00274e41abc5a5142e7d99dd
    26 schema:url http://link.springer.com/10.1007/978-3-319-11918-2_10
    27 sgo:license sg:explorer/license/
    28 sgo:sdDataset chapters
    29 rdf:type schema:Chapter
    30 N100e46aa8f534e3897deb4970956ade2 rdf:first Nbd35f39eadbe467ba08fdd3ba03bb352
    31 rdf:rest N3d0f86535ca44a0b991f7997bc885ddf
    32 N157c7549237844c495edf842a5834471 schema:familyName Crochemore
    33 schema:givenName Maxime
    34 rdf:type schema:Person
    35 N1c96bcbeca7e422bbb597ea747e29335 schema:location Cham
    36 schema:name Springer International Publishing
    37 rdf:type schema:Organisation
    38 N290efb7fa3d242519370c578ee347174 rdf:first sg:person.0613677314.28
    39 rdf:rest rdf:nil
    40 N348b96badd7f4cd2a843e350a94821a5 rdf:first sg:person.014556642366.63
    41 rdf:rest N290efb7fa3d242519370c578ee347174
    42 N3d0f86535ca44a0b991f7997bc885ddf rdf:first N157c7549237844c495edf842a5834471
    43 rdf:rest rdf:nil
    44 N4434a186a46b405791ec4f23e277dace rdf:first sg:person.010362264441.20
    45 rdf:rest N348b96badd7f4cd2a843e350a94821a5
    46 N4c62207f45714d2a93a91f86c5011de0 schema:isbn 978-3-319-11917-5
    47 978-3-319-11918-2
    48 schema:name String Processing and Information Retrieval
    49 rdf:type schema:Book
    50 N533ec14ac116479487ee20505dacaefe schema:name dimensions_id
    51 schema:value pub.1039503668
    52 rdf:type schema:PropertyValue
    53 N7e457fd56e9a45b898983a1b059ec6c6 schema:name readcube_id
    54 schema:value bc2d76e7017d7ad112876676404d0757cf5c41533392b369b2b02e57b02a0018
    55 rdf:type schema:PropertyValue
    56 N7f01e2cf00274e41abc5a5142e7d99dd schema:name Springer Nature - SN SciGraph project
    57 rdf:type schema:Organization
    58 Nbd35f39eadbe467ba08fdd3ba03bb352 schema:familyName Moura
    59 schema:givenName Edleno
    60 rdf:type schema:Person
    61 Nc9f8f4d734844592bf13c3c59d7061d9 schema:name doi
    62 schema:value 10.1007/978-3-319-11918-2_10
    63 rdf:type schema:PropertyValue
    64 sg:person.010362264441.20 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
    65 schema:familyName Munro
    66 schema:givenName J. Ian
    67 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010362264441.20
    68 rdf:type schema:Person
    69 sg:person.014556642366.63 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
    70 schema:familyName Nekrich
    71 schema:givenName Yakov
    72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014556642366.63
    73 rdf:type schema:Person
    74 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.266515.3
    75 schema:familyName Vitter
    76 schema:givenName Jeffrey S.
    77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
    78 rdf:type schema:Person
    79 sg:pub.10.1007/978-3-642-21458-5_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000271084
    80 https://doi.org/10.1007/978-3-642-21458-5_19
    81 rdf:type schema:CreativeWork
    82 sg:pub.10.1007/978-3-642-24583-1_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043979341
    83 https://doi.org/10.1007/978-3-642-24583-1_19
    84 rdf:type schema:CreativeWork
    85 https://doi.org/10.1016/j.jda.2013.07.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046344664
    86 rdf:type schema:CreativeWork
    87 https://doi.org/10.1109/sfcs.1989.63533 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086192305
    88 rdf:type schema:CreativeWork
    89 https://doi.org/10.1137/0217026 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842045
    90 rdf:type schema:CreativeWork
    91 https://www.grid.ac/institutes/grid.266515.3 schema:alternateName University of Kansas
    92 schema:name Department of Electrical Engineering & Computer Science, University of Kansas, USA
    93 rdf:type schema:Organization
    94 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
    95 schema:name David R. Cheriton School of Computer Science, University of Waterloo, Canada
    96 rdf:type schema:Organization
     




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


    ...