Compressing Dictionary Matching Index via Sparsification Technique View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2015-06

AUTHORS

Wing-Kai Hon, Tsung-Han Ku, Tak-Wah Lam, Rahul Shah, Siu-Lung Tam, Sharma V. Thankachan, Jeffrey Scott Vitter

ABSTRACT

Given a set of patterns of total length n, the dictionary matching problem is to index such that for any query text T, we can locate the occurrences of any pattern within T efficiently. This problem can be solved in optimal O(|T|+occ) time by the classical AC automaton (Aho and Corasick in Commun. ACM 18(6):333–340, 1975), where occ denotes the number of occurrences. The space requirement is O(n) words which is still far from optimal. In this paper, we show that in many cases, sparsification technique can be applied to improve the space requirements of the indexes for the dictionary matching and its related problems. First, we give a compressed index for dictionary matching, and show that such an index can be generalized to handle dynamic updates of . Also, we give a compressed index for approximate dictionary matching with one error. In each case, the query time is only slowed down by a polylogarithmic factor when compared with that achieved by the best O(n)-word counterparts. More... »

PAGES

515-538

References to SciGraph publications

  • 2002. Two Simplified Algorithms for Maintaining Order in a List in ALGORITHMS — ESA 2002
  • 2010. Succinct Dictionary Matching with No Slowdown in COMBINATORIAL PATTERN MATCHING
  • 1996. Sparse suffix trees in COMPUTING AND COMBINATORICS
  • 2009. On Entropy-Compressed Text Indexing in External Memory in STRING PROCESSING AND INFORMATION RETRIEVAL
  • 2010. Faster Compressed Dictionary Matching in STRING PROCESSING AND INFORMATION RETRIEVAL
  • 2007-12. Compressed Suffix Trees with Full Functionality in THEORY OF COMPUTING SYSTEMS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00453-013-9863-3

    DOI

    http://dx.doi.org/10.1007/s00453-013-9863-3

    DIMENSIONS

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


    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": "National Tsing Hua University", 
              "id": "https://www.grid.ac/institutes/grid.38348.34", 
              "name": [
                "National Tsing Hua University, Hsinchu City, Hsinchu, Taiwan, Republic of China"
              ], 
              "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": "National Tsing Hua University", 
              "id": "https://www.grid.ac/institutes/grid.38348.34", 
              "name": [
                "National Tsing Hua University, Hsinchu City, Hsinchu, Taiwan, Republic of China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ku", 
            "givenName": "Tsung-Han", 
            "id": "sg:person.013703760711.16", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013703760711.16"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Hong Kong", 
              "id": "https://www.grid.ac/institutes/grid.194645.b", 
              "name": [
                "The University of Hong Kong, Hong Kong, Hong Kong SAR"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lam", 
            "givenName": "Tak-Wah", 
            "id": "sg:person.01342007103.04", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01342007103.04"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Louisiana State University", 
              "id": "https://www.grid.ac/institutes/grid.64337.35", 
              "name": [
                "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": "University of Hong Kong", 
              "id": "https://www.grid.ac/institutes/grid.194645.b", 
              "name": [
                "The University of Hong Kong, Hong Kong, Hong Kong SAR"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Tam", 
            "givenName": "Siu-Lung", 
            "id": "sg:person.07673643625.68", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07673643625.68"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Louisiana State University", 
              "id": "https://www.grid.ac/institutes/grid.64337.35", 
              "name": [
                "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": [
                "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": "https://doi.org/10.1145/1007352.1007374", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007128103"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-16321-0_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009096663", 
              "https://doi.org/10.1007/978-3-642-16321-0_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-16321-0_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009096663", 
              "https://doi.org/10.1007/978-3-642-16321-0_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jalgor.2005.08.001", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013813324"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/301970.301973", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014848232"
            ], 
            "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": "https://doi.org/10.1145/1240233.1240244", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021021393"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/28395.28434", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022759585"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/360825.360855", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027390472"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1186810.1186812", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027932808"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jagm.2000.1104", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031406166"
            ], 
            "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": "sg:pub.10.1007/978-3-642-13509-5_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039950548", 
              "https://doi.org/10.1007/978-3-642-13509-5_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-13509-5_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039950548", 
              "https://doi.org/10.1007/978-3-642-13509-5_9"
            ], 
            "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.1006/jagm.2001.1171", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042877507"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0022-0000(05)80047-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045720509"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/inco.1995.1090", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050614400"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0196-6774(88)90041-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051627387"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/301250.301378", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052452880"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45749-6_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052730126", 
              "https://doi.org/10.1007/3-540-45749-6_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0214021", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841810"
            ], 
            "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/090779759", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062856985"
            ], 
            "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.1137/s009753970240481x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062879369"
            ], 
            "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.1109/sfcs.1991.185445", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086357260"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1998.743504", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094292447"
            ], 
            "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.2008.67", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095757483"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2015-06", 
        "datePublishedReg": "2015-06-01", 
        "description": "Given a set of patterns of total length n, the dictionary matching problem is to index such that for any query text T, we can locate the occurrences of any pattern within T efficiently. This problem can be solved in optimal O(|T|+occ) time by the classical AC automaton (Aho and Corasick in Commun. ACM 18(6):333\u2013340, 1975), where occ denotes the number of occurrences. The space requirement is O(n) words which is still far from optimal. In this paper, we show that in many cases, sparsification technique can be applied to improve the space requirements of the indexes for the dictionary matching and its related problems. First, we give a compressed index for dictionary matching, and show that such an index can be generalized to handle dynamic updates of . Also, we give a compressed index for approximate dictionary matching with one error. In each case, the query time is only slowed down by a polylogarithmic factor when compared with that achieved by the best O(n)-word counterparts.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00453-013-9863-3", 
        "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": "72"
          }
        ], 
        "name": "Compressing Dictionary Matching Index via Sparsification Technique", 
        "pagination": "515-538", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "9f8aa7fd80ec49e3907a373c43e61ce41185bd9d77b9f46dea28264f6ef1de11"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00453-013-9863-3"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1033490707"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00453-013-9863-3", 
          "https://app.dimensions.ai/details/publication/pub.1033490707"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T17:32", 
        "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_8672_00000514.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2Fs00453-013-9863-3"
      }
    ]
     

    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-9863-3'

    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-9863-3'

    Turtle is a human-readable linked data format.

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

    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-9863-3'


     

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

    217 TRIPLES      21 PREDICATES      60 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00453-013-9863-3 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N2333b717074a4657bcfe372337702d21
    4 schema:citation sg:pub.10.1007/3-540-45749-6_17
    5 sg:pub.10.1007/3-540-61332-3_155
    6 sg:pub.10.1007/978-3-642-03784-9_8
    7 sg:pub.10.1007/978-3-642-13509-5_9
    8 sg:pub.10.1007/978-3-642-16321-0_19
    9 sg:pub.10.1007/s00224-006-1198-x
    10 https://doi.org/10.1006/inco.1995.1090
    11 https://doi.org/10.1006/jagm.2000.1104
    12 https://doi.org/10.1006/jagm.2001.1171
    13 https://doi.org/10.1016/0020-0190(83)90075-3
    14 https://doi.org/10.1016/0196-6774(88)90041-7
    15 https://doi.org/10.1016/j.jalgor.2005.08.001
    16 https://doi.org/10.1016/j.tcs.2006.12.012
    17 https://doi.org/10.1016/s0022-0000(05)80047-9
    18 https://doi.org/10.1109/dcc.2008.62
    19 https://doi.org/10.1109/dcc.2008.67
    20 https://doi.org/10.1109/sfcs.1991.185445
    21 https://doi.org/10.1109/sfcs.1998.743504
    22 https://doi.org/10.1109/swat.1973.13
    23 https://doi.org/10.1137/0214021
    24 https://doi.org/10.1137/0222058
    25 https://doi.org/10.1137/090779759
    26 https://doi.org/10.1137/s0097539702402354
    27 https://doi.org/10.1137/s009753970240481x
    28 https://doi.org/10.1145/1007352.1007374
    29 https://doi.org/10.1145/1082036.1082039
    30 https://doi.org/10.1145/1186810.1186812
    31 https://doi.org/10.1145/1240233.1240244
    32 https://doi.org/10.1145/28395.28434
    33 https://doi.org/10.1145/301250.301378
    34 https://doi.org/10.1145/301970.301973
    35 https://doi.org/10.1145/321941.321946
    36 https://doi.org/10.1145/360825.360855
    37 schema:datePublished 2015-06
    38 schema:datePublishedReg 2015-06-01
    39 schema:description Given a set of patterns of total length n, the dictionary matching problem is to index such that for any query text T, we can locate the occurrences of any pattern within T efficiently. This problem can be solved in optimal O(|T|+occ) time by the classical AC automaton (Aho and Corasick in Commun. ACM 18(6):333–340, 1975), where occ denotes the number of occurrences. The space requirement is O(n) words which is still far from optimal. In this paper, we show that in many cases, sparsification technique can be applied to improve the space requirements of the indexes for the dictionary matching and its related problems. First, we give a compressed index for dictionary matching, and show that such an index can be generalized to handle dynamic updates of . Also, we give a compressed index for approximate dictionary matching with one error. In each case, the query time is only slowed down by a polylogarithmic factor when compared with that achieved by the best O(n)-word counterparts.
    40 schema:genre research_article
    41 schema:inLanguage en
    42 schema:isAccessibleForFree false
    43 schema:isPartOf N6cf57d52e56f49e4ab961ebf3ecce4e8
    44 N85f49cbe06774ea885e381874a056fba
    45 sg:journal.1047644
    46 schema:name Compressing Dictionary Matching Index via Sparsification Technique
    47 schema:pagination 515-538
    48 schema:productId N9adc10ff4519443e9a1e3a960f1dce16
    49 Nbe200006321447c290f93d280d9e8a95
    50 Nd3c5cbeef054479f851c430e15cf2c94
    51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033490707
    52 https://doi.org/10.1007/s00453-013-9863-3
    53 schema:sdDatePublished 2019-04-10T17:32
    54 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    55 schema:sdPublisher N5e40e90d37054a55bd4b31dc617c819b
    56 schema:url http://link.springer.com/10.1007%2Fs00453-013-9863-3
    57 sgo:license sg:explorer/license/
    58 sgo:sdDataset articles
    59 rdf:type schema:ScholarlyArticle
    60 N2333b717074a4657bcfe372337702d21 rdf:first sg:person.07456324600.70
    61 rdf:rest N9671f9860a814cbd808757aa16e1715e
    62 N26ce9f91d7ef4eefb65fc0d3a94deff3 rdf:first sg:person.07673643625.68
    63 rdf:rest Nad5f349529b84e8cafc0c33f97a2b9e8
    64 N5e40e90d37054a55bd4b31dc617c819b schema:name Springer Nature - SN SciGraph project
    65 rdf:type schema:Organization
    66 N6cf57d52e56f49e4ab961ebf3ecce4e8 schema:issueNumber 2
    67 rdf:type schema:PublicationIssue
    68 N79e57dd2d0ec4afbbe8c676d4a0ab583 rdf:first sg:person.0613677314.28
    69 rdf:rest rdf:nil
    70 N85f49cbe06774ea885e381874a056fba schema:volumeNumber 72
    71 rdf:type schema:PublicationVolume
    72 N9671f9860a814cbd808757aa16e1715e rdf:first sg:person.013703760711.16
    73 rdf:rest Nd8d1f0dc52d34949b50c5c0e70934631
    74 N9adc10ff4519443e9a1e3a960f1dce16 schema:name readcube_id
    75 schema:value 9f8aa7fd80ec49e3907a373c43e61ce41185bd9d77b9f46dea28264f6ef1de11
    76 rdf:type schema:PropertyValue
    77 Nad5f349529b84e8cafc0c33f97a2b9e8 rdf:first sg:person.014270733416.17
    78 rdf:rest N79e57dd2d0ec4afbbe8c676d4a0ab583
    79 Nbe200006321447c290f93d280d9e8a95 schema:name doi
    80 schema:value 10.1007/s00453-013-9863-3
    81 rdf:type schema:PropertyValue
    82 Nd3c5cbeef054479f851c430e15cf2c94 schema:name dimensions_id
    83 schema:value pub.1033490707
    84 rdf:type schema:PropertyValue
    85 Nd86393ba79ef48af9fbe317c6c5d7518 rdf:first sg:person.016536034313.19
    86 rdf:rest N26ce9f91d7ef4eefb65fc0d3a94deff3
    87 Nd8d1f0dc52d34949b50c5c0e70934631 rdf:first sg:person.01342007103.04
    88 rdf:rest Nd86393ba79ef48af9fbe317c6c5d7518
    89 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    90 schema:name Information and Computing Sciences
    91 rdf:type schema:DefinedTerm
    92 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    93 schema:name Artificial Intelligence and Image Processing
    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.01342007103.04 schema:affiliation https://www.grid.ac/institutes/grid.194645.b
    100 schema:familyName Lam
    101 schema:givenName Tak-Wah
    102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01342007103.04
    103 rdf:type schema:Person
    104 sg:person.013703760711.16 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
    105 schema:familyName Ku
    106 schema:givenName Tsung-Han
    107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013703760711.16
    108 rdf:type schema:Person
    109 sg:person.014270733416.17 schema:affiliation https://www.grid.ac/institutes/grid.64337.35
    110 schema:familyName Thankachan
    111 schema:givenName Sharma V.
    112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014270733416.17
    113 rdf:type schema:Person
    114 sg:person.016536034313.19 schema:affiliation https://www.grid.ac/institutes/grid.64337.35
    115 schema:familyName Shah
    116 schema:givenName Rahul
    117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016536034313.19
    118 rdf:type schema:Person
    119 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.266515.3
    120 schema:familyName Vitter
    121 schema:givenName Jeffrey Scott
    122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
    123 rdf:type schema:Person
    124 sg:person.07456324600.70 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
    125 schema:familyName Hon
    126 schema:givenName Wing-Kai
    127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07456324600.70
    128 rdf:type schema:Person
    129 sg:person.07673643625.68 schema:affiliation https://www.grid.ac/institutes/grid.194645.b
    130 schema:familyName Tam
    131 schema:givenName Siu-Lung
    132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07673643625.68
    133 rdf:type schema:Person
    134 sg:pub.10.1007/3-540-45749-6_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052730126
    135 https://doi.org/10.1007/3-540-45749-6_17
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/3-540-61332-3_155 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032340447
    138 https://doi.org/10.1007/3-540-61332-3_155
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/978-3-642-03784-9_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037542376
    141 https://doi.org/10.1007/978-3-642-03784-9_8
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1007/978-3-642-13509-5_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039950548
    144 https://doi.org/10.1007/978-3-642-13509-5_9
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1007/978-3-642-16321-0_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009096663
    147 https://doi.org/10.1007/978-3-642-16321-0_19
    148 rdf:type schema:CreativeWork
    149 sg:pub.10.1007/s00224-006-1198-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1039635416
    150 https://doi.org/10.1007/s00224-006-1198-x
    151 rdf:type schema:CreativeWork
    152 https://doi.org/10.1006/inco.1995.1090 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050614400
    153 rdf:type schema:CreativeWork
    154 https://doi.org/10.1006/jagm.2000.1104 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031406166
    155 rdf:type schema:CreativeWork
    156 https://doi.org/10.1006/jagm.2001.1171 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042877507
    157 rdf:type schema:CreativeWork
    158 https://doi.org/10.1016/0020-0190(83)90075-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016724958
    159 rdf:type schema:CreativeWork
    160 https://doi.org/10.1016/0196-6774(88)90041-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051627387
    161 rdf:type schema:CreativeWork
    162 https://doi.org/10.1016/j.jalgor.2005.08.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013813324
    163 rdf:type schema:CreativeWork
    164 https://doi.org/10.1016/j.tcs.2006.12.012 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032352574
    165 rdf:type schema:CreativeWork
    166 https://doi.org/10.1016/s0022-0000(05)80047-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045720509
    167 rdf:type schema:CreativeWork
    168 https://doi.org/10.1109/dcc.2008.62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095627320
    169 rdf:type schema:CreativeWork
    170 https://doi.org/10.1109/dcc.2008.67 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095757483
    171 rdf:type schema:CreativeWork
    172 https://doi.org/10.1109/sfcs.1991.185445 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086357260
    173 rdf:type schema:CreativeWork
    174 https://doi.org/10.1109/sfcs.1998.743504 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094292447
    175 rdf:type schema:CreativeWork
    176 https://doi.org/10.1109/swat.1973.13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086215622
    177 rdf:type schema:CreativeWork
    178 https://doi.org/10.1137/0214021 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841810
    179 rdf:type schema:CreativeWork
    180 https://doi.org/10.1137/0222058 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842461
    181 rdf:type schema:CreativeWork
    182 https://doi.org/10.1137/090779759 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062856985
    183 rdf:type schema:CreativeWork
    184 https://doi.org/10.1137/s0097539702402354 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879354
    185 rdf:type schema:CreativeWork
    186 https://doi.org/10.1137/s009753970240481x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879369
    187 rdf:type schema:CreativeWork
    188 https://doi.org/10.1145/1007352.1007374 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007128103
    189 rdf:type schema:CreativeWork
    190 https://doi.org/10.1145/1082036.1082039 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034511505
    191 rdf:type schema:CreativeWork
    192 https://doi.org/10.1145/1186810.1186812 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027932808
    193 rdf:type schema:CreativeWork
    194 https://doi.org/10.1145/1240233.1240244 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021021393
    195 rdf:type schema:CreativeWork
    196 https://doi.org/10.1145/28395.28434 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022759585
    197 rdf:type schema:CreativeWork
    198 https://doi.org/10.1145/301250.301378 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052452880
    199 rdf:type schema:CreativeWork
    200 https://doi.org/10.1145/301970.301973 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014848232
    201 rdf:type schema:CreativeWork
    202 https://doi.org/10.1145/321941.321946 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040652581
    203 rdf:type schema:CreativeWork
    204 https://doi.org/10.1145/360825.360855 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027390472
    205 rdf:type schema:CreativeWork
    206 https://www.grid.ac/institutes/grid.194645.b schema:alternateName University of Hong Kong
    207 schema:name The University of Hong Kong, Hong Kong, Hong Kong SAR
    208 rdf:type schema:Organization
    209 https://www.grid.ac/institutes/grid.266515.3 schema:alternateName University of Kansas
    210 schema:name The University of Kansas, Lawrence, KS, USA
    211 rdf:type schema:Organization
    212 https://www.grid.ac/institutes/grid.38348.34 schema:alternateName National Tsing Hua University
    213 schema:name National Tsing Hua University, Hsinchu City, Hsinchu, Taiwan, Republic of China
    214 rdf:type schema:Organization
    215 https://www.grid.ac/institutes/grid.64337.35 schema:alternateName Louisiana State University
    216 schema:name Louisiana State University, Baton Rouge, LA, USA
    217 rdf:type schema:Organization
     




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


    ...