Geometric BWT: Compressed Text Indexing via Sparse Suffixes and Range Searching View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2015-02

AUTHORS

Yu-Feng Chien, Wing-Kai Hon, Rahul Shah, Sharma V. Thankachan, Jeffrey Scott Vitter

ABSTRACT

We introduce a new variant of the popular Burrows-Wheeler transform (BWT), called Geometric Burrows-Wheeler Transform (GBWT), which converts a text into a set of points in 2-dimensional geometry. We also introduce a reverse transform, called Points2Text, which converts a set of points into text. Using these two transforms, we show strong equivalence between data structural problems in geometric range searching and text pattern matching. This allows us to apply the lower bounds known in the field of orthogonal range searching to the problems in compressed text indexing. In addition, we give the first succinct (compact) index for I/O-efficient pattern matching in external memory, and show how this index can be further improved to achieve higher-order entropy compressed space. More... »

PAGES

258-278

References to SciGraph publications

  • 2004. Advantages of Backward Searching — Efficient Secondary Memory and Distributed Implementation of Compressed Suffix Arrays in ALGORITHMS AND COMPUTATION
  • 1996. Tables in FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE
  • 2007. A Lempel-Ziv Text Index on Secondary Storage in COMBINATORIAL PATTERN MATCHING
  • 2009. Efficient Data Structures for the Orthogonal Range Successor Problem in COMPUTING AND COMBINATORICS
  • 1996. Sparse suffix trees in COMPUTING AND COMBINATORICS
  • 2001-12. SP-GiST: An Extensible Database Index for Supporting Space Partitioning Trees in JOURNAL OF INTELLIGENT INFORMATION SYSTEMS
  • 2009. On Entropy-Compressed Text Indexing in External Memory in STRING PROCESSING AND INFORMATION RETRIEVAL
  • 2012. Forbidden Patterns in LATIN 2012: THEORETICAL INFORMATICS
  • 2006. Position-Restricted Substring Searching in LATIN 2006: THEORETICAL INFORMATICS
  • 2009. Succinct Index for Dynamic Dictionary Matching in ALGORITHMS AND COMPUTATION
  • 2007-12. Compressed Suffix Trees with Full Functionality in THEORY OF COMPUTING SYSTEMS
  • 2011. Compressed Indexes for Aligned Pattern Matching in STRING PROCESSING AND INFORMATION RETRIEVAL
  • 1999-01-15. Optimal Dynamic Range Searching inNon-replicating Index Structures in DATABASE THEORY — ICDT’99
  • 2010. Compression, Indexing, and Retrieval for Massive String Data in COMBINATORIAL PATTERN MATCHING
  • 2011. Compressed Text Indexing with Wildcards in STRING PROCESSING AND INFORMATION RETRIEVAL
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00453-013-9792-1

    DOI

    http://dx.doi.org/10.1007/s00453-013-9792-1

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "National Tsing Hua University", 
              "id": "https://www.grid.ac/institutes/grid.38348.34", 
              "name": [
                "Department of CS, National Tsing Hua University, Hsinchu, Taiwan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chien", 
            "givenName": "Yu-Feng", 
            "id": "sg:person.012224612455.05", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012224612455.05"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "National Tsing Hua University", 
              "id": "https://www.grid.ac/institutes/grid.38348.34", 
              "name": [
                "Department of CS, National Tsing Hua University, Hsinchu, Taiwan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Hon", 
            "givenName": "Wing-Kai", 
            "id": "sg:person.07456324600.70", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07456324600.70"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Louisiana State University", 
              "id": "https://www.grid.ac/institutes/grid.64337.35", 
              "name": [
                "Department of CS, Louisiana State University, Baton Rouge, LA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Shah", 
            "givenName": "Rahul", 
            "id": "sg:person.016536034313.19", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016536034313.19"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Louisiana State University", 
              "id": "https://www.grid.ac/institutes/grid.64337.35", 
              "name": [
                "Department of CS, Louisiana State University, Baton Rouge, LA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Thankachan", 
            "givenName": "Sharma V.", 
            "id": "sg:person.014270733416.17", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014270733416.17"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Kansas", 
              "id": "https://www.grid.ac/institutes/grid.266515.3", 
              "name": [
                "Department of EECS, The University of Kansas, Lawrence, KS, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Vitter", 
            "givenName": "Jeffrey Scott", 
            "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-24583-1_40", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006594118", 
              "https://doi.org/10.1007/978-3-642-24583-1_40"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/77600.77614", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007189276"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1064092.1064119", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010201614"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/48529.48535", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014013712"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/301970.301973", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014848232"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-10631-6_104", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016520822", 
              "https://doi.org/10.1007/978-3-642-10631-6_104"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-10631-6_104", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016520822", 
              "https://doi.org/10.1007/978-3-642-10631-6_104"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(83)90075-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016724958"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-24583-1_26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017753429", 
              "https://doi.org/10.1007/978-3-642-24583-1_26"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11682462_64", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019176861", 
              "https://doi.org/10.1007/11682462_64"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11682462_64", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019176861", 
              "https://doi.org/10.1007/11682462_64"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-02882-3_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026954855", 
              "https://doi.org/10.1007/978-3-642-02882-3_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-02882-3_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026954855", 
              "https://doi.org/10.1007/978-3-642-02882-3_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0306-4379(96)00025-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028259179"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-73437-6_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028612463", 
              "https://doi.org/10.1007/978-3-540-73437-6_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-73437-6_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028612463", 
              "https://doi.org/10.1007/978-3-540-73437-6_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-13509-5_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029367197", 
              "https://doi.org/10.1007/978-3-642-13509-5_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-13509-5_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029367197", 
              "https://doi.org/10.1007/978-3-642-13509-5_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2000807.2000821", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030205361"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-61332-3_155", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032340447", 
              "https://doi.org/10.1007/3-540-61332-3_155"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2006.12.012", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032352574"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1082036.1082039", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034511505"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-03784-9_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037542376", 
              "https://doi.org/10.1007/978-3-642-03784-9_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-006-1198-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039635416", 
              "https://doi.org/10.1007/s00224-006-1198-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/321941.321946", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040652581"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/602259.602266", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042817816"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-29344-3_28", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043593048", 
              "https://doi.org/10.1007/978-3-642-29344-3_28"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-49257-7_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045979130", 
              "https://doi.org/10.1007/3-540-49257-7_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-49257-7_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045979130", 
              "https://doi.org/10.1007/3-540-49257-7_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1012809914301", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046699652", 
              "https://doi.org/10.1023/a:1012809914301"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-62034-6_35", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051372882", 
              "https://doi.org/10.1007/3-540-62034-6_35"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30551-4_59", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051899747", 
              "https://doi.org/10.1007/978-3-540-30551-4_59"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30551-4_59", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051899747", 
              "https://doi.org/10.1007/978-3-540-30551-4_59"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/356924.356930", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052104755"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0222058", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062842461"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539702402354", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062879354"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1989.63533", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086192305"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/swat.1973.13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086215622"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/conm/223/03131", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1089203810"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/dcc.2010.45", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093453141"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/ccp.2011.45", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095379958"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/dcc.2008.62", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095627320"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/dcc.2011.18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095705603"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/dcc.2008.67", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095757483"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2015-02", 
        "datePublishedReg": "2015-02-01", 
        "description": "We introduce a new variant of the popular Burrows-Wheeler transform (BWT), called Geometric Burrows-Wheeler Transform (GBWT), which converts a text into a set of points in 2-dimensional geometry. We also introduce a reverse transform, called Points2Text, which converts a set of points into text. Using these two transforms, we show strong equivalence between data structural problems in geometric range searching and text pattern matching. This allows us to apply the lower bounds known in the field of orthogonal range searching to the problems in compressed text indexing. In addition, we give the first succinct (compact) index for I/O-efficient pattern matching in external memory, and show how this index can be further improved to achieve higher-order entropy compressed space.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00453-013-9792-1", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "71"
          }
        ], 
        "name": "Geometric BWT: Compressed Text Indexing via Sparse Suffixes and Range Searching", 
        "pagination": "258-278", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "8c1238663889598320b3870b0d92b87320c58ea267d9fe23694dd1988bc80693"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00453-013-9792-1"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1029402972"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00453-013-9792-1", 
          "https://app.dimensions.ai/details/publication/pub.1029402972"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T15:01", 
        "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_00000513.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2Fs00453-013-9792-1"
      }
    ]
     

    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-013-9792-1'

    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-013-9792-1'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-013-9792-1'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-013-9792-1'


     

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

    221 TRIPLES      21 PREDICATES      64 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00453-013-9792-1 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author Nd0d5c0ff87fd425d944aca0cb077f488
    4 schema:citation sg:pub.10.1007/11682462_64
    5 sg:pub.10.1007/3-540-49257-7_17
    6 sg:pub.10.1007/3-540-61332-3_155
    7 sg:pub.10.1007/3-540-62034-6_35
    8 sg:pub.10.1007/978-3-540-30551-4_59
    9 sg:pub.10.1007/978-3-540-73437-6_11
    10 sg:pub.10.1007/978-3-642-02882-3_11
    11 sg:pub.10.1007/978-3-642-03784-9_8
    12 sg:pub.10.1007/978-3-642-10631-6_104
    13 sg:pub.10.1007/978-3-642-13509-5_24
    14 sg:pub.10.1007/978-3-642-24583-1_26
    15 sg:pub.10.1007/978-3-642-24583-1_40
    16 sg:pub.10.1007/978-3-642-29344-3_28
    17 sg:pub.10.1007/s00224-006-1198-x
    18 sg:pub.10.1023/a:1012809914301
    19 https://doi.org/10.1016/0020-0190(83)90075-3
    20 https://doi.org/10.1016/0306-4379(96)00025-7
    21 https://doi.org/10.1016/j.tcs.2006.12.012
    22 https://doi.org/10.1090/conm/223/03131
    23 https://doi.org/10.1109/ccp.2011.45
    24 https://doi.org/10.1109/dcc.2008.62
    25 https://doi.org/10.1109/dcc.2008.67
    26 https://doi.org/10.1109/dcc.2010.45
    27 https://doi.org/10.1109/dcc.2011.18
    28 https://doi.org/10.1109/sfcs.1989.63533
    29 https://doi.org/10.1109/swat.1973.13
    30 https://doi.org/10.1137/0222058
    31 https://doi.org/10.1137/s0097539702402354
    32 https://doi.org/10.1145/1064092.1064119
    33 https://doi.org/10.1145/1082036.1082039
    34 https://doi.org/10.1145/2000807.2000821
    35 https://doi.org/10.1145/301970.301973
    36 https://doi.org/10.1145/321941.321946
    37 https://doi.org/10.1145/356924.356930
    38 https://doi.org/10.1145/48529.48535
    39 https://doi.org/10.1145/602259.602266
    40 https://doi.org/10.1145/77600.77614
    41 schema:datePublished 2015-02
    42 schema:datePublishedReg 2015-02-01
    43 schema:description We introduce a new variant of the popular Burrows-Wheeler transform (BWT), called Geometric Burrows-Wheeler Transform (GBWT), which converts a text into a set of points in 2-dimensional geometry. We also introduce a reverse transform, called Points2Text, which converts a set of points into text. Using these two transforms, we show strong equivalence between data structural problems in geometric range searching and text pattern matching. This allows us to apply the lower bounds known in the field of orthogonal range searching to the problems in compressed text indexing. In addition, we give the first succinct (compact) index for I/O-efficient pattern matching in external memory, and show how this index can be further improved to achieve higher-order entropy compressed space.
    44 schema:genre research_article
    45 schema:inLanguage en
    46 schema:isAccessibleForFree false
    47 schema:isPartOf N35712ff598564607a20d2afd6b5db629
    48 Ndbe30e340389465a81dcdb78d2dca682
    49 sg:journal.1047644
    50 schema:name Geometric BWT: Compressed Text Indexing via Sparse Suffixes and Range Searching
    51 schema:pagination 258-278
    52 schema:productId N0bbb1d8c33cb43629ec9b659bdfcd68c
    53 N1a4d34377c3147c6a17d05d684e24e36
    54 N36ccfe051ed8485eb6d9aba225f647a1
    55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029402972
    56 https://doi.org/10.1007/s00453-013-9792-1
    57 schema:sdDatePublished 2019-04-10T15:01
    58 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    59 schema:sdPublisher N31dc531b1dbd4bd8bdea1c8692d9110d
    60 schema:url http://link.springer.com/10.1007%2Fs00453-013-9792-1
    61 sgo:license sg:explorer/license/
    62 sgo:sdDataset articles
    63 rdf:type schema:ScholarlyArticle
    64 N0bbb1d8c33cb43629ec9b659bdfcd68c schema:name readcube_id
    65 schema:value 8c1238663889598320b3870b0d92b87320c58ea267d9fe23694dd1988bc80693
    66 rdf:type schema:PropertyValue
    67 N1a4d34377c3147c6a17d05d684e24e36 schema:name doi
    68 schema:value 10.1007/s00453-013-9792-1
    69 rdf:type schema:PropertyValue
    70 N2c7876bc308c4e28b3e8b2dabc28f6af rdf:first sg:person.07456324600.70
    71 rdf:rest Nbf2bf85dee564774b4311a2cfbb8c404
    72 N31dc531b1dbd4bd8bdea1c8692d9110d schema:name Springer Nature - SN SciGraph project
    73 rdf:type schema:Organization
    74 N35712ff598564607a20d2afd6b5db629 schema:issueNumber 2
    75 rdf:type schema:PublicationIssue
    76 N36ccfe051ed8485eb6d9aba225f647a1 schema:name dimensions_id
    77 schema:value pub.1029402972
    78 rdf:type schema:PropertyValue
    79 N9149adf5c5ab4fb6831106da814f2912 rdf:first sg:person.014270733416.17
    80 rdf:rest Na210d9c4fdd5493cb3c176c49fd6dadd
    81 Na210d9c4fdd5493cb3c176c49fd6dadd rdf:first sg:person.0613677314.28
    82 rdf:rest rdf:nil
    83 Nbf2bf85dee564774b4311a2cfbb8c404 rdf:first sg:person.016536034313.19
    84 rdf:rest N9149adf5c5ab4fb6831106da814f2912
    85 Nd0d5c0ff87fd425d944aca0cb077f488 rdf:first sg:person.012224612455.05
    86 rdf:rest N2c7876bc308c4e28b3e8b2dabc28f6af
    87 Ndbe30e340389465a81dcdb78d2dca682 schema:volumeNumber 71
    88 rdf:type schema:PublicationVolume
    89 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    90 schema:name Mathematical Sciences
    91 rdf:type schema:DefinedTerm
    92 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    93 schema:name Pure Mathematics
    94 rdf:type schema:DefinedTerm
    95 sg:journal.1047644 schema:issn 0178-4617
    96 1432-0541
    97 schema:name Algorithmica
    98 rdf:type schema:Periodical
    99 sg:person.012224612455.05 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
    100 schema:familyName Chien
    101 schema:givenName Yu-Feng
    102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012224612455.05
    103 rdf:type schema:Person
    104 sg:person.014270733416.17 schema:affiliation https://www.grid.ac/institutes/grid.64337.35
    105 schema:familyName Thankachan
    106 schema:givenName Sharma V.
    107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014270733416.17
    108 rdf:type schema:Person
    109 sg:person.016536034313.19 schema:affiliation https://www.grid.ac/institutes/grid.64337.35
    110 schema:familyName Shah
    111 schema:givenName Rahul
    112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016536034313.19
    113 rdf:type schema:Person
    114 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.266515.3
    115 schema:familyName Vitter
    116 schema:givenName Jeffrey Scott
    117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
    118 rdf:type schema:Person
    119 sg:person.07456324600.70 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
    120 schema:familyName Hon
    121 schema:givenName Wing-Kai
    122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07456324600.70
    123 rdf:type schema:Person
    124 sg:pub.10.1007/11682462_64 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019176861
    125 https://doi.org/10.1007/11682462_64
    126 rdf:type schema:CreativeWork
    127 sg:pub.10.1007/3-540-49257-7_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045979130
    128 https://doi.org/10.1007/3-540-49257-7_17
    129 rdf:type schema:CreativeWork
    130 sg:pub.10.1007/3-540-61332-3_155 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032340447
    131 https://doi.org/10.1007/3-540-61332-3_155
    132 rdf:type schema:CreativeWork
    133 sg:pub.10.1007/3-540-62034-6_35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051372882
    134 https://doi.org/10.1007/3-540-62034-6_35
    135 rdf:type schema:CreativeWork
    136 sg:pub.10.1007/978-3-540-30551-4_59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051899747
    137 https://doi.org/10.1007/978-3-540-30551-4_59
    138 rdf:type schema:CreativeWork
    139 sg:pub.10.1007/978-3-540-73437-6_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028612463
    140 https://doi.org/10.1007/978-3-540-73437-6_11
    141 rdf:type schema:CreativeWork
    142 sg:pub.10.1007/978-3-642-02882-3_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026954855
    143 https://doi.org/10.1007/978-3-642-02882-3_11
    144 rdf:type schema:CreativeWork
    145 sg:pub.10.1007/978-3-642-03784-9_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037542376
    146 https://doi.org/10.1007/978-3-642-03784-9_8
    147 rdf:type schema:CreativeWork
    148 sg:pub.10.1007/978-3-642-10631-6_104 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016520822
    149 https://doi.org/10.1007/978-3-642-10631-6_104
    150 rdf:type schema:CreativeWork
    151 sg:pub.10.1007/978-3-642-13509-5_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029367197
    152 https://doi.org/10.1007/978-3-642-13509-5_24
    153 rdf:type schema:CreativeWork
    154 sg:pub.10.1007/978-3-642-24583-1_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017753429
    155 https://doi.org/10.1007/978-3-642-24583-1_26
    156 rdf:type schema:CreativeWork
    157 sg:pub.10.1007/978-3-642-24583-1_40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006594118
    158 https://doi.org/10.1007/978-3-642-24583-1_40
    159 rdf:type schema:CreativeWork
    160 sg:pub.10.1007/978-3-642-29344-3_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043593048
    161 https://doi.org/10.1007/978-3-642-29344-3_28
    162 rdf:type schema:CreativeWork
    163 sg:pub.10.1007/s00224-006-1198-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1039635416
    164 https://doi.org/10.1007/s00224-006-1198-x
    165 rdf:type schema:CreativeWork
    166 sg:pub.10.1023/a:1012809914301 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046699652
    167 https://doi.org/10.1023/a:1012809914301
    168 rdf:type schema:CreativeWork
    169 https://doi.org/10.1016/0020-0190(83)90075-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016724958
    170 rdf:type schema:CreativeWork
    171 https://doi.org/10.1016/0306-4379(96)00025-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028259179
    172 rdf:type schema:CreativeWork
    173 https://doi.org/10.1016/j.tcs.2006.12.012 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032352574
    174 rdf:type schema:CreativeWork
    175 https://doi.org/10.1090/conm/223/03131 schema:sameAs https://app.dimensions.ai/details/publication/pub.1089203810
    176 rdf:type schema:CreativeWork
    177 https://doi.org/10.1109/ccp.2011.45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095379958
    178 rdf:type schema:CreativeWork
    179 https://doi.org/10.1109/dcc.2008.62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095627320
    180 rdf:type schema:CreativeWork
    181 https://doi.org/10.1109/dcc.2008.67 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095757483
    182 rdf:type schema:CreativeWork
    183 https://doi.org/10.1109/dcc.2010.45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093453141
    184 rdf:type schema:CreativeWork
    185 https://doi.org/10.1109/dcc.2011.18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095705603
    186 rdf:type schema:CreativeWork
    187 https://doi.org/10.1109/sfcs.1989.63533 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086192305
    188 rdf:type schema:CreativeWork
    189 https://doi.org/10.1109/swat.1973.13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086215622
    190 rdf:type schema:CreativeWork
    191 https://doi.org/10.1137/0222058 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842461
    192 rdf:type schema:CreativeWork
    193 https://doi.org/10.1137/s0097539702402354 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879354
    194 rdf:type schema:CreativeWork
    195 https://doi.org/10.1145/1064092.1064119 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010201614
    196 rdf:type schema:CreativeWork
    197 https://doi.org/10.1145/1082036.1082039 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034511505
    198 rdf:type schema:CreativeWork
    199 https://doi.org/10.1145/2000807.2000821 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030205361
    200 rdf:type schema:CreativeWork
    201 https://doi.org/10.1145/301970.301973 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014848232
    202 rdf:type schema:CreativeWork
    203 https://doi.org/10.1145/321941.321946 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040652581
    204 rdf:type schema:CreativeWork
    205 https://doi.org/10.1145/356924.356930 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052104755
    206 rdf:type schema:CreativeWork
    207 https://doi.org/10.1145/48529.48535 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014013712
    208 rdf:type schema:CreativeWork
    209 https://doi.org/10.1145/602259.602266 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042817816
    210 rdf:type schema:CreativeWork
    211 https://doi.org/10.1145/77600.77614 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007189276
    212 rdf:type schema:CreativeWork
    213 https://www.grid.ac/institutes/grid.266515.3 schema:alternateName University of Kansas
    214 schema:name Department of EECS, The University of Kansas, Lawrence, KS, USA
    215 rdf:type schema:Organization
    216 https://www.grid.ac/institutes/grid.38348.34 schema:alternateName National Tsing Hua University
    217 schema:name Department of CS, National Tsing Hua University, Hsinchu, Taiwan
    218 rdf:type schema:Organization
    219 https://www.grid.ac/institutes/grid.64337.35 schema:alternateName Louisiana State University
    220 schema:name Department of CS, Louisiana State University, Baton Rouge, LA, USA
    221 rdf:type schema:Organization
     




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


    ...