Using Convolution to Mine Obscure Periodic Patterns in One Pass View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

Mohamed G. Elfeky , Walid G. Aref , Ahmed K. Elmagarmid

ABSTRACT

The mining of periodic patterns in time series databases is an interesting data mining problem that can be envisioned as a tool for forecasting and predicting the future behavior of time series data. Existing periodic patterns mining algorithms either assume that the periodic rate (or simply the period) is user-specified, or try to detect potential values for the period in a separate phase. The former assumption is a considerable disadvantage, especially in time series databases where the period is not known a priori. The latter approach results in a multi-pass algorithm, which on the other hand is to be avoided in online environments (e.g., data streams). In this paper, we develop an algorithm that mines periodic patterns in time series databases with unknown or obscure periods such that discovering the period is part of the mining process. Based on convolution, our algorithm requires only one pass over a time series of length n, with O(n log n) time complexity. More... »

PAGES

605-620

References to SciGraph publications

  • 1996. Mining sequential patterns: Generalizations and performance improvements in ADVANCES IN DATABASE TECHNOLOGY — EDBT '96
  • Book

    TITLE

    Advances in Database Technology - EDBT 2004

    ISBN

    978-3-540-21200-3
    978-3-540-24741-8

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-24741-8_35

    DOI

    http://dx.doi.org/10.1007/978-3-540-24741-8_35

    DIMENSIONS

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


    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": "Purdue University", 
              "id": "https://www.grid.ac/institutes/grid.169077.e", 
              "name": [
                "Department of Computer Sciences, Purdue University"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Elfeky", 
            "givenName": "Mohamed G.", 
            "id": "sg:person.013215427230.76", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013215427230.76"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Purdue University", 
              "id": "https://www.grid.ac/institutes/grid.169077.e", 
              "name": [
                "Department of Computer Sciences, Purdue University"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Aref", 
            "givenName": "Walid G.", 
            "id": "sg:person.01326230264.61", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01326230264.61"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Purdue University", 
              "id": "https://www.grid.ac/institutes/grid.169077.e", 
              "name": [
                "Department of Computer Sciences, Purdue University"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Elmagarmid", 
            "givenName": "Ahmed K.", 
            "id": "sg:person.0717524353.09", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0717524353.09"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/775047.775109", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025571209"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/047134608x.w4308", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030129704"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/047134608x.w4308", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030129704"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/384192.384193", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040182656"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/775047.775128", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041873341"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/347090.347150", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048020249"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0014140", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050497818", 
              "https://doi.org/10.1007/bfb0014140"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1063/1.1531823", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1057717106"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/69.683754", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061213669"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tkde.2003.1262186", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061661232"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0216067", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062842013"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/icde.1998.655804", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093929625"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/icde.1995.380415", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094007712"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/icde.1999.754913", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094268582"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/icde.2001.914829", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094936225"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2004", 
        "datePublishedReg": "2004-01-01", 
        "description": "The mining of periodic patterns in time series databases is an interesting data mining problem that can be envisioned as a tool for forecasting and predicting the future behavior of time series data. Existing periodic patterns mining algorithms either assume that the periodic rate (or simply the period) is user-specified, or try to detect potential values for the period in a separate phase. The former assumption is a considerable disadvantage, especially in time series databases where the period is not known a priori. The latter approach results in a multi-pass algorithm, which on the other hand is to be avoided in online environments (e.g., data streams). In this paper, we develop an algorithm that mines periodic patterns in time series databases with unknown or obscure periods such that discovering the period is part of the mining process. Based on convolution, our algorithm requires only one pass over a time series of length n, with O(n log n) time complexity.", 
        "editor": [
          {
            "familyName": "Bertino", 
            "givenName": "Elisa", 
            "type": "Person"
          }, 
          {
            "familyName": "Christodoulakis", 
            "givenName": "Stavros", 
            "type": "Person"
          }, 
          {
            "familyName": "Plexousakis", 
            "givenName": "Dimitris", 
            "type": "Person"
          }, 
          {
            "familyName": "Christophides", 
            "givenName": "Vassilis", 
            "type": "Person"
          }, 
          {
            "familyName": "Koubarakis", 
            "givenName": "Manolis", 
            "type": "Person"
          }, 
          {
            "familyName": "B\u00f6hm", 
            "givenName": "Klemens", 
            "type": "Person"
          }, 
          {
            "familyName": "Ferrari", 
            "givenName": "Elena", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-24741-8_35", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-21200-3", 
            "978-3-540-24741-8"
          ], 
          "name": "Advances in Database Technology - EDBT 2004", 
          "type": "Book"
        }, 
        "name": "Using Convolution to Mine Obscure Periodic Patterns in One Pass", 
        "pagination": "605-620", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1030694382"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-24741-8_35"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "923965c3010c08bf7ba7995e6dab601b23e9bad8479ad6aa9cfddb018cb434e9"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-24741-8_35", 
          "https://app.dimensions.ai/details/publication/pub.1030694382"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:09", 
        "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/0000000360_0000000360/records_118332_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-540-24741-8_35"
      }
    ]
     

    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-540-24741-8_35'

    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-540-24741-8_35'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24741-8_35'

    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-540-24741-8_35'


     

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

    152 TRIPLES      23 PREDICATES      41 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-24741-8_35 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N5515171be249486e8ce6b43002d92f93
    4 schema:citation sg:pub.10.1007/bfb0014140
    5 https://doi.org/10.1002/047134608x.w4308
    6 https://doi.org/10.1063/1.1531823
    7 https://doi.org/10.1109/69.683754
    8 https://doi.org/10.1109/icde.1995.380415
    9 https://doi.org/10.1109/icde.1998.655804
    10 https://doi.org/10.1109/icde.1999.754913
    11 https://doi.org/10.1109/icde.2001.914829
    12 https://doi.org/10.1109/tkde.2003.1262186
    13 https://doi.org/10.1137/0216067
    14 https://doi.org/10.1145/347090.347150
    15 https://doi.org/10.1145/384192.384193
    16 https://doi.org/10.1145/775047.775109
    17 https://doi.org/10.1145/775047.775128
    18 schema:datePublished 2004
    19 schema:datePublishedReg 2004-01-01
    20 schema:description The mining of periodic patterns in time series databases is an interesting data mining problem that can be envisioned as a tool for forecasting and predicting the future behavior of time series data. Existing periodic patterns mining algorithms either assume that the periodic rate (or simply the period) is user-specified, or try to detect potential values for the period in a separate phase. The former assumption is a considerable disadvantage, especially in time series databases where the period is not known a priori. The latter approach results in a multi-pass algorithm, which on the other hand is to be avoided in online environments (e.g., data streams). In this paper, we develop an algorithm that mines periodic patterns in time series databases with unknown or obscure periods such that discovering the period is part of the mining process. Based on convolution, our algorithm requires only one pass over a time series of length n, with O(n log n) time complexity.
    21 schema:editor N07f576bb2f9041dfb437bc2de21e94f5
    22 schema:genre chapter
    23 schema:inLanguage en
    24 schema:isAccessibleForFree true
    25 schema:isPartOf N5348cd7c848246fba3588b577d252969
    26 schema:name Using Convolution to Mine Obscure Periodic Patterns in One Pass
    27 schema:pagination 605-620
    28 schema:productId N5fbf9c5ac1db4ffe800a47dbc077c60c
    29 N664da68ac841422181e23b1fa0a44032
    30 Ne1668c3a39de4a4a9fb30649e559684e
    31 schema:publisher N581e4217e3474edc98fbb0e63887fda6
    32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030694382
    33 https://doi.org/10.1007/978-3-540-24741-8_35
    34 schema:sdDatePublished 2019-04-16T08:09
    35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    36 schema:sdPublisher N606972d9994441bb9e56e4e6a5c61cf0
    37 schema:url https://link.springer.com/10.1007%2F978-3-540-24741-8_35
    38 sgo:license sg:explorer/license/
    39 sgo:sdDataset chapters
    40 rdf:type schema:Chapter
    41 N07f576bb2f9041dfb437bc2de21e94f5 rdf:first Nb7aaab5a2975482cad944e850d3f89c5
    42 rdf:rest Nc15ab76ee32349a1a6c8238169727d56
    43 N2f7893ad4e334c3c88510d2f184391f5 schema:familyName Plexousakis
    44 schema:givenName Dimitris
    45 rdf:type schema:Person
    46 N3a0269147ca94f51b0826ddba4487e21 schema:familyName Koubarakis
    47 schema:givenName Manolis
    48 rdf:type schema:Person
    49 N406767451766451ba56c1cdf44867d9f rdf:first sg:person.0717524353.09
    50 rdf:rest rdf:nil
    51 N467ee9ee5aa74d08b1ec7d860e9e8286 schema:familyName Böhm
    52 schema:givenName Klemens
    53 rdf:type schema:Person
    54 N523a62e6c88140629811953d49866efc schema:familyName Ferrari
    55 schema:givenName Elena
    56 rdf:type schema:Person
    57 N5348cd7c848246fba3588b577d252969 schema:isbn 978-3-540-21200-3
    58 978-3-540-24741-8
    59 schema:name Advances in Database Technology - EDBT 2004
    60 rdf:type schema:Book
    61 N5515171be249486e8ce6b43002d92f93 rdf:first sg:person.013215427230.76
    62 rdf:rest Ndbd01e34d66e4e5183a4a0321a1b45d9
    63 N581e4217e3474edc98fbb0e63887fda6 schema:location Berlin, Heidelberg
    64 schema:name Springer Berlin Heidelberg
    65 rdf:type schema:Organisation
    66 N5abf57e987c84d88ae9e4201a32f794e rdf:first N2f7893ad4e334c3c88510d2f184391f5
    67 rdf:rest N99051f2d15aa4c8c900b76d099e87583
    68 N5fbf9c5ac1db4ffe800a47dbc077c60c schema:name doi
    69 schema:value 10.1007/978-3-540-24741-8_35
    70 rdf:type schema:PropertyValue
    71 N6002daf6eec64fcd899e98e4ee8fc518 rdf:first N467ee9ee5aa74d08b1ec7d860e9e8286
    72 rdf:rest N6550dc7e5bce4b0f8f4643b7bfb10045
    73 N606972d9994441bb9e56e4e6a5c61cf0 schema:name Springer Nature - SN SciGraph project
    74 rdf:type schema:Organization
    75 N6550dc7e5bce4b0f8f4643b7bfb10045 rdf:first N523a62e6c88140629811953d49866efc
    76 rdf:rest rdf:nil
    77 N664da68ac841422181e23b1fa0a44032 schema:name readcube_id
    78 schema:value 923965c3010c08bf7ba7995e6dab601b23e9bad8479ad6aa9cfddb018cb434e9
    79 rdf:type schema:PropertyValue
    80 N99051f2d15aa4c8c900b76d099e87583 rdf:first Ne71baec911b44ce996cc7bfee5f475ed
    81 rdf:rest Nb3518050971f48f18e24cf6681cde984
    82 Na0dc23a077474a60b4e6025f1ef65d8d schema:familyName Christodoulakis
    83 schema:givenName Stavros
    84 rdf:type schema:Person
    85 Nb3518050971f48f18e24cf6681cde984 rdf:first N3a0269147ca94f51b0826ddba4487e21
    86 rdf:rest N6002daf6eec64fcd899e98e4ee8fc518
    87 Nb7aaab5a2975482cad944e850d3f89c5 schema:familyName Bertino
    88 schema:givenName Elisa
    89 rdf:type schema:Person
    90 Nc15ab76ee32349a1a6c8238169727d56 rdf:first Na0dc23a077474a60b4e6025f1ef65d8d
    91 rdf:rest N5abf57e987c84d88ae9e4201a32f794e
    92 Ndbd01e34d66e4e5183a4a0321a1b45d9 rdf:first sg:person.01326230264.61
    93 rdf:rest N406767451766451ba56c1cdf44867d9f
    94 Ne1668c3a39de4a4a9fb30649e559684e schema:name dimensions_id
    95 schema:value pub.1030694382
    96 rdf:type schema:PropertyValue
    97 Ne71baec911b44ce996cc7bfee5f475ed schema:familyName Christophides
    98 schema:givenName Vassilis
    99 rdf:type schema:Person
    100 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    101 schema:name Information and Computing Sciences
    102 rdf:type schema:DefinedTerm
    103 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    104 schema:name Artificial Intelligence and Image Processing
    105 rdf:type schema:DefinedTerm
    106 sg:person.013215427230.76 schema:affiliation https://www.grid.ac/institutes/grid.169077.e
    107 schema:familyName Elfeky
    108 schema:givenName Mohamed G.
    109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013215427230.76
    110 rdf:type schema:Person
    111 sg:person.01326230264.61 schema:affiliation https://www.grid.ac/institutes/grid.169077.e
    112 schema:familyName Aref
    113 schema:givenName Walid G.
    114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01326230264.61
    115 rdf:type schema:Person
    116 sg:person.0717524353.09 schema:affiliation https://www.grid.ac/institutes/grid.169077.e
    117 schema:familyName Elmagarmid
    118 schema:givenName Ahmed K.
    119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0717524353.09
    120 rdf:type schema:Person
    121 sg:pub.10.1007/bfb0014140 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050497818
    122 https://doi.org/10.1007/bfb0014140
    123 rdf:type schema:CreativeWork
    124 https://doi.org/10.1002/047134608x.w4308 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030129704
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.1063/1.1531823 schema:sameAs https://app.dimensions.ai/details/publication/pub.1057717106
    127 rdf:type schema:CreativeWork
    128 https://doi.org/10.1109/69.683754 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061213669
    129 rdf:type schema:CreativeWork
    130 https://doi.org/10.1109/icde.1995.380415 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094007712
    131 rdf:type schema:CreativeWork
    132 https://doi.org/10.1109/icde.1998.655804 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093929625
    133 rdf:type schema:CreativeWork
    134 https://doi.org/10.1109/icde.1999.754913 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094268582
    135 rdf:type schema:CreativeWork
    136 https://doi.org/10.1109/icde.2001.914829 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094936225
    137 rdf:type schema:CreativeWork
    138 https://doi.org/10.1109/tkde.2003.1262186 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061661232
    139 rdf:type schema:CreativeWork
    140 https://doi.org/10.1137/0216067 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842013
    141 rdf:type schema:CreativeWork
    142 https://doi.org/10.1145/347090.347150 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048020249
    143 rdf:type schema:CreativeWork
    144 https://doi.org/10.1145/384192.384193 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040182656
    145 rdf:type schema:CreativeWork
    146 https://doi.org/10.1145/775047.775109 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025571209
    147 rdf:type schema:CreativeWork
    148 https://doi.org/10.1145/775047.775128 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041873341
    149 rdf:type schema:CreativeWork
    150 https://www.grid.ac/institutes/grid.169077.e schema:alternateName Purdue University
    151 schema:name Department of Computer Sciences, Purdue University
    152 rdf:type schema:Organization
     




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


    ...