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 N461784280abc4433812938ae40b9cc25
    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 N7c7c96b3be3445ba8a196ea7412dc222
    22 schema:genre chapter
    23 schema:inLanguage en
    24 schema:isAccessibleForFree true
    25 schema:isPartOf Na542185007c9468ea3859620d84e0762
    26 schema:name Using Convolution to Mine Obscure Periodic Patterns in One Pass
    27 schema:pagination 605-620
    28 schema:productId N38c5ea6ef8e04619aea363147c2b645f
    29 N626a276080ec465b9d03c0f39ca18b66
    30 N89260d049b144cdeb4ab71e5299358a9
    31 schema:publisher N62d670506288418ebed5219e5c0776f1
    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 Ne8768414884343c9b8d4fda7ea271f45
    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 N076f8ea0da4844879bb75cabb3c4b48d schema:familyName Böhm
    42 schema:givenName Klemens
    43 rdf:type schema:Person
    44 N0cd75a7f4032430b9cae698a64560832 rdf:first N076f8ea0da4844879bb75cabb3c4b48d
    45 rdf:rest N7a65cd8eb7594b94ae0d3282e4a095b8
    46 N38c5ea6ef8e04619aea363147c2b645f schema:name dimensions_id
    47 schema:value pub.1030694382
    48 rdf:type schema:PropertyValue
    49 N3c7e4482d88247ae84cc6fd681b18d50 rdf:first Nb495ed7b2aba4720919fedaa782fbe57
    50 rdf:rest N939e235b8ac3400186a8540b92088941
    51 N461784280abc4433812938ae40b9cc25 rdf:first sg:person.013215427230.76
    52 rdf:rest N4f35488ffc164fd4b1619f40d2e72c1a
    53 N4f35488ffc164fd4b1619f40d2e72c1a rdf:first sg:person.01326230264.61
    54 rdf:rest Nb6eb21ac4733488483ec17ebcd78d914
    55 N517967ff271c4a558400f1380cfc9c79 schema:familyName Koubarakis
    56 schema:givenName Manolis
    57 rdf:type schema:Person
    58 N626a276080ec465b9d03c0f39ca18b66 schema:name readcube_id
    59 schema:value 923965c3010c08bf7ba7995e6dab601b23e9bad8479ad6aa9cfddb018cb434e9
    60 rdf:type schema:PropertyValue
    61 N62d670506288418ebed5219e5c0776f1 schema:location Berlin, Heidelberg
    62 schema:name Springer Berlin Heidelberg
    63 rdf:type schema:Organisation
    64 N633312d48ee64e25a19ab99a2375d698 rdf:first N8235008da18c45b19a3cbb7ba5b097e0
    65 rdf:rest N81f054e8156840da875702f78fe7c1ac
    66 N77065b2ea9db4d8d8033a2f11d32daa5 schema:familyName Bertino
    67 schema:givenName Elisa
    68 rdf:type schema:Person
    69 N7a65cd8eb7594b94ae0d3282e4a095b8 rdf:first Nc9c48c1e54eb47a4a2b448b577370630
    70 rdf:rest rdf:nil
    71 N7c7c96b3be3445ba8a196ea7412dc222 rdf:first N77065b2ea9db4d8d8033a2f11d32daa5
    72 rdf:rest N3c7e4482d88247ae84cc6fd681b18d50
    73 N81f054e8156840da875702f78fe7c1ac rdf:first N517967ff271c4a558400f1380cfc9c79
    74 rdf:rest N0cd75a7f4032430b9cae698a64560832
    75 N8235008da18c45b19a3cbb7ba5b097e0 schema:familyName Christophides
    76 schema:givenName Vassilis
    77 rdf:type schema:Person
    78 N89260d049b144cdeb4ab71e5299358a9 schema:name doi
    79 schema:value 10.1007/978-3-540-24741-8_35
    80 rdf:type schema:PropertyValue
    81 N939e235b8ac3400186a8540b92088941 rdf:first Nc738719bcff74b2b991b889d740cf722
    82 rdf:rest N633312d48ee64e25a19ab99a2375d698
    83 Na542185007c9468ea3859620d84e0762 schema:isbn 978-3-540-21200-3
    84 978-3-540-24741-8
    85 schema:name Advances in Database Technology - EDBT 2004
    86 rdf:type schema:Book
    87 Nb495ed7b2aba4720919fedaa782fbe57 schema:familyName Christodoulakis
    88 schema:givenName Stavros
    89 rdf:type schema:Person
    90 Nb6eb21ac4733488483ec17ebcd78d914 rdf:first sg:person.0717524353.09
    91 rdf:rest rdf:nil
    92 Nc738719bcff74b2b991b889d740cf722 schema:familyName Plexousakis
    93 schema:givenName Dimitris
    94 rdf:type schema:Person
    95 Nc9c48c1e54eb47a4a2b448b577370630 schema:familyName Ferrari
    96 schema:givenName Elena
    97 rdf:type schema:Person
    98 Ne8768414884343c9b8d4fda7ea271f45 schema:name Springer Nature - SN SciGraph project
    99 rdf:type schema:Organization
    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)


    ...