1 Ocak 2021 Dergi makalesi Açık Erişim

Hooshmand, Sahar; Abedin, Paniz; Kulekci, M. Oguzhan; Thankachan, Sharma V.

JSON

{
  "conceptrecid": "237247", 
  "created": "2022-10-07T09:51:37.934501+00:00", 
  "doi": "10.1016/j.tcs.2020.12.006", 
  "files": [
    {
      "bucket": "53990a75-3652-4cb5-afc6-7b81efc5ae82", 
      "checksum": "md5:92655b18e624bffd652c5c3c9a1eb3ad", 
      "key": "bib-17de205a-494b-4846-891f-bfac34f3113b.txt", 
      "links": {
        "self": "https://aperta.ulakbim.gov.tr/api/files/53990a75-3652-4cb5-afc6-7b81efc5ae82/bib-17de205a-494b-4846-891f-bfac34f3113b.txt"
      }, 
      "size": 169, 
      "type": "txt"
    }
  ], 
  "id": 237248, 
  "links": {
    "badge": "https://aperta.ulakbim.gov.tr/badge/doi/10.1016/j.tcs.2020.12.006.svg", 
    "bucket": "https://aperta.ulakbim.gov.tr/api/files/53990a75-3652-4cb5-afc6-7b81efc5ae82", 
    "doi": "https://doi.org/10.1016/j.tcs.2020.12.006", 
    "html": "https://aperta.ulakbim.gov.tr/record/237248", 
    "latest": "https://aperta.ulakbim.gov.tr/api/records/237248", 
    "latest_html": "https://aperta.ulakbim.gov.tr/record/237248"
  }, 
  "metadata": {
    "access_right": "open", 
    "access_right_category": "success", 
    "communities": [
      {
        "id": "tubitak-destekli-proje-yayinlari"
      }
    ], 
    "creators": [
      {
        "affiliation": "Univ Cent Florida, Dept Comp Sci, Orlando, FL 32816 USA", 
        "name": "Hooshmand, Sahar"
      }, 
      {
        "affiliation": "Univ Cent Florida, Dept Comp Sci, Orlando, FL 32816 USA", 
        "name": "Abedin, Paniz"
      }, 
      {
        "affiliation": "Istanbul Tech Univ, Informat Inst, Istanbul, Turkey", 
        "name": "Kulekci, M. Oguzhan"
      }, 
      {
        "affiliation": "Univ Cent Florida, Dept Comp Sci, Orlando, FL 32816 USA", 
        "name": "Thankachan, Sharma V."
      }
    ], 
    "description": "The non-overlapping indexing problem is defined as follows: pre-process a given text T[1, n] of length n into a data structure such that whenever a pattern P [1, m] comes as an input, we can efficiently report the largest set of non-overlapping occurrences of P in T. The best-known solution is by Cohen and Porat [ISAAC 2009]. The size of their structure is O (n) words and the query time is optimal O (m + nocc), where nocc is the output size. Later, Ganguly et al. [CPM 2015 and Algorithmica 2020] proposed a compressed space solution. We study this problem in the cache-oblivious model and present a new data structure of size O (n log n) words. It can answer queries in optimal O (m/B + log(B) n + nocc/B) I/O operations, where B is the block size. The space can be improved to O (n log(M/B) n) in the cache-aware model, where M is the size of main memory. Additionally, we study a generalization of this problem with an additional range [s, e] constraint. Here the task is to report the largest set of non-overlapping occurrences of P in T, that are within the range [s, e]. We present an O (n log(2) n) space data structure in the cache-aware model that can answer queries in optimal O (m/B + log(B) n + nocc([s,e]) B ) I/O operations, where nocc([s,e]) is the output size.", 
    "doi": "10.1016/j.tcs.2020.12.006", 
    "has_grant": false, 
    "journal": {
      "pages": "1-7", 
      "title": "THEORETICAL COMPUTER SCIENCE", 
      "volume": "857"
    }, 
    "license": {
      "id": "cc-by"
    }, 
    "publication_date": "2021-01-01", 
    "relations": {
      "version": [
        {
          "count": 1, 
          "index": 0, 
          "is_last": true, 
          "last_child": {
            "pid_type": "recid", 
            "pid_value": "237248"
          }, 
          "parent": {
            "pid_type": "recid", 
            "pid_value": "237247"
          }
        }
      ]
    }, 
    "resource_type": {
      "subtype": "article", 
      "title": "Dergi makalesi", 
      "type": "publication"
    }, 
    "science_branches": [
      "Di\u011fer"
    ], 
    "title": "I/O-efficient data structures for non-overlapping indexing"
  }, 
  "owners": [
    1
  ], 
  "revision": 1, 
  "stats": {
    "downloads": 3.0, 
    "unique_downloads": 3.0, 
    "unique_views": 14.0, 
    "version_downloads": 3.0, 
    "version_unique_downloads": 3.0, 
    "version_unique_views": 14.0, 
    "version_views": 14.0, 
    "version_volume": 507.0, 
    "views": 14.0, 
    "volume": 507.0
  }, 
  "updated": "2022-10-07T09:51:37.984941+00:00"
}