An Efficient Algorithm for Enumerating Closed Patterns in Transaction Databases View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

Takeaki Uno , Tatsuya Asai , Yuzo Uchida , Hiroki Arimura

ABSTRACT

The class of closed patterns is a well known condensed representations of frequent patterns, and have recently attracted considerable interest. In this paper, we propose an efficient algorithm LCM (Linear time Closed pattern Miner) for mining frequent closed patterns from large transaction databases. The main theoretical contribution is our proposed prefix-preserving closure extension of closed patterns, which enables us to search all frequent closed patterns in a depth-first manner, in linear time for the number of frequent closed patterns. Our algorithm do not need any storage space for the previously obtained patterns, while the existing algorithms needs it. Performance comparisons of LCM with straightforward algorithms demonstrate the advantages of our prefix-preserving closure extension. More... »

PAGES

16-31

References to SciGraph publications

Book

TITLE

Discovery Science

ISBN

978-3-540-23357-2
978-3-540-30214-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-30214-8_2

DOI

http://dx.doi.org/10.1007/978-3-540-30214-8_2

DIMENSIONS

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


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 Institute of Informatics", 
          "id": "https://www.grid.ac/institutes/grid.250343.3", 
          "name": [
            "National Institute of Informatics, 2-1-2, Hitotsubashi, Chiyoda-ku, Tokyo, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Uno", 
        "givenName": "Takeaki", 
        "id": "sg:person.016517167551.57", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016517167551.57"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Kyushu University", 
          "id": "https://www.grid.ac/institutes/grid.177174.3", 
          "name": [
            "Department of Informatics, Kyushu University, 6-10-1, Hakozaki, Fukuoka, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Asai", 
        "givenName": "Tatsuya", 
        "id": "sg:person.015367141327.55", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015367141327.55"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Kyushu University", 
          "id": "https://www.grid.ac/institutes/grid.177174.3", 
          "name": [
            "Department of Informatics, Kyushu University, 6-10-1, Hakozaki, Fukuoka, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Uchida", 
        "givenName": "Yuzo", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Kyushu University", 
          "id": "https://www.grid.ac/institutes/grid.177174.3", 
          "name": [
            "Department of Informatics, Kyushu University, 6-10-1, Hakozaki, Fukuoka, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Arimura", 
        "givenName": "Hiroki", 
        "id": "sg:person.013325377075.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013325377075.00"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/s0306-4379(99)00003-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000463430"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45841-7_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004444201", 
          "https://doi.org/10.1007/3-540-45841-7_10"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45841-7_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004444201", 
          "https://doi.org/10.1007/3-540-45841-7_10"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10115-004-0175-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016569315", 
          "https://doi.org/10.1007/s10115-004-0175-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/956750.956784", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020461301"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/342009.335372", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025244221"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-39644-4_6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025309521", 
          "https://doi.org/10.1007/978-3-540-39644-4_6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-39644-4_6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025309521", 
          "https://doi.org/10.1007/978-3-540-39644-4_6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/380995.381033", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030106472"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-49257-7_25", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048579740", 
          "https://doi.org/10.1007/3-540-49257-7_25"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-49257-7_25", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048579740", 
          "https://doi.org/10.1007/3-540-49257-7_25"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/380995.381017", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049909998"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/69.846291", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061213826"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9781611972726.10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1088799860"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9781611972726.27", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1088799881"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/icdm.2002.1183882", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094395359"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/icde.2001.914857", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095061845"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/icdm.2003.1250939", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095443679"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/276304.276313", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098992874"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "The class of closed patterns is a well known condensed representations of frequent patterns, and have recently attracted considerable interest. In this paper, we propose an efficient algorithm LCM (Linear time Closed pattern Miner) for mining frequent closed patterns from large transaction databases. The main theoretical contribution is our proposed prefix-preserving closure extension of closed patterns, which enables us to search all frequent closed patterns in a depth-first manner, in linear time for the number of frequent closed patterns. Our algorithm do not need any storage space for the previously obtained patterns, while the existing algorithms needs it. Performance comparisons of LCM with straightforward algorithms demonstrate the advantages of our prefix-preserving closure extension.", 
    "editor": [
      {
        "familyName": "Suzuki", 
        "givenName": "Einoshin", 
        "type": "Person"
      }, 
      {
        "familyName": "Arikawa", 
        "givenName": "Setsuo", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-30214-8_2", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-23357-2", 
        "978-3-540-30214-8"
      ], 
      "name": "Discovery Science", 
      "type": "Book"
    }, 
    "name": "An Efficient Algorithm for Enumerating Closed Patterns in Transaction Databases", 
    "pagination": "16-31", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1032189170"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-30214-8_2"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "995750a337b50124d56ad77f5a5856c5ba1e67f5950b362cd6f469ff05cfb435"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-30214-8_2", 
      "https://app.dimensions.ai/details/publication/pub.1032189170"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:24", 
    "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/0000000363_0000000363/records_70046_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-30214-8_2"
  }
]
 

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-30214-8_2'

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-30214-8_2'

Turtle is a human-readable linked data format.

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

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-30214-8_2'


 

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

145 TRIPLES      23 PREDICATES      43 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-30214-8_2 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Nabd8669140f0436fb7f48544953ec9a7
4 schema:citation sg:pub.10.1007/3-540-45841-7_10
5 sg:pub.10.1007/3-540-49257-7_25
6 sg:pub.10.1007/978-3-540-39644-4_6
7 sg:pub.10.1007/s10115-004-0175-4
8 https://doi.org/10.1016/s0306-4379(99)00003-4
9 https://doi.org/10.1109/69.846291
10 https://doi.org/10.1109/icde.2001.914857
11 https://doi.org/10.1109/icdm.2002.1183882
12 https://doi.org/10.1109/icdm.2003.1250939
13 https://doi.org/10.1137/1.9781611972726.10
14 https://doi.org/10.1137/1.9781611972726.27
15 https://doi.org/10.1145/276304.276313
16 https://doi.org/10.1145/342009.335372
17 https://doi.org/10.1145/380995.381017
18 https://doi.org/10.1145/380995.381033
19 https://doi.org/10.1145/956750.956784
20 schema:datePublished 2004
21 schema:datePublishedReg 2004-01-01
22 schema:description The class of closed patterns is a well known condensed representations of frequent patterns, and have recently attracted considerable interest. In this paper, we propose an efficient algorithm LCM (Linear time Closed pattern Miner) for mining frequent closed patterns from large transaction databases. The main theoretical contribution is our proposed prefix-preserving closure extension of closed patterns, which enables us to search all frequent closed patterns in a depth-first manner, in linear time for the number of frequent closed patterns. Our algorithm do not need any storage space for the previously obtained patterns, while the existing algorithms needs it. Performance comparisons of LCM with straightforward algorithms demonstrate the advantages of our prefix-preserving closure extension.
23 schema:editor N01999b88a98d47bebabc6292578ca211
24 schema:genre chapter
25 schema:inLanguage en
26 schema:isAccessibleForFree true
27 schema:isPartOf N00ad2235b4e04d398217afbe631d5947
28 schema:name An Efficient Algorithm for Enumerating Closed Patterns in Transaction Databases
29 schema:pagination 16-31
30 schema:productId N06cf18d8dcd746d09b0a35f7bb1b987f
31 Nb4c0e76ce7ca4808a94626b57f1c4e3d
32 Ne9942c87c57c4695aba191d44f1d5a95
33 schema:publisher Na07fee81be004d4398d37429b4916bf6
34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032189170
35 https://doi.org/10.1007/978-3-540-30214-8_2
36 schema:sdDatePublished 2019-04-16T08:24
37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
38 schema:sdPublisher N613c796d59c4480589dd1993f5cf058b
39 schema:url https://link.springer.com/10.1007%2F978-3-540-30214-8_2
40 sgo:license sg:explorer/license/
41 sgo:sdDataset chapters
42 rdf:type schema:Chapter
43 N00ad2235b4e04d398217afbe631d5947 schema:isbn 978-3-540-23357-2
44 978-3-540-30214-8
45 schema:name Discovery Science
46 rdf:type schema:Book
47 N01999b88a98d47bebabc6292578ca211 rdf:first N11e1174de4fe4f2fb5f4acb69dfeab6f
48 rdf:rest N27c8e12bab17421884da3ae8e7ca98b8
49 N06cf18d8dcd746d09b0a35f7bb1b987f schema:name dimensions_id
50 schema:value pub.1032189170
51 rdf:type schema:PropertyValue
52 N11e1174de4fe4f2fb5f4acb69dfeab6f schema:familyName Suzuki
53 schema:givenName Einoshin
54 rdf:type schema:Person
55 N1f2b70b8239b42feb3559c89d7c2e7dc rdf:first Ne4b0718a7f2b43e18d3663a207f69c3a
56 rdf:rest N8034b321fddf4be4892bcdfc7c96b091
57 N27c8e12bab17421884da3ae8e7ca98b8 rdf:first N36da2eb8d7074855b7709f1d85bb9c67
58 rdf:rest rdf:nil
59 N36da2eb8d7074855b7709f1d85bb9c67 schema:familyName Arikawa
60 schema:givenName Setsuo
61 rdf:type schema:Person
62 N613c796d59c4480589dd1993f5cf058b schema:name Springer Nature - SN SciGraph project
63 rdf:type schema:Organization
64 N8034b321fddf4be4892bcdfc7c96b091 rdf:first sg:person.013325377075.00
65 rdf:rest rdf:nil
66 Na07fee81be004d4398d37429b4916bf6 schema:location Berlin, Heidelberg
67 schema:name Springer Berlin Heidelberg
68 rdf:type schema:Organisation
69 Nabd8669140f0436fb7f48544953ec9a7 rdf:first sg:person.016517167551.57
70 rdf:rest Nb5e5de3df82b4298ab99858393f4073c
71 Nb4c0e76ce7ca4808a94626b57f1c4e3d schema:name readcube_id
72 schema:value 995750a337b50124d56ad77f5a5856c5ba1e67f5950b362cd6f469ff05cfb435
73 rdf:type schema:PropertyValue
74 Nb5e5de3df82b4298ab99858393f4073c rdf:first sg:person.015367141327.55
75 rdf:rest N1f2b70b8239b42feb3559c89d7c2e7dc
76 Ne4b0718a7f2b43e18d3663a207f69c3a schema:affiliation https://www.grid.ac/institutes/grid.177174.3
77 schema:familyName Uchida
78 schema:givenName Yuzo
79 rdf:type schema:Person
80 Ne9942c87c57c4695aba191d44f1d5a95 schema:name doi
81 schema:value 10.1007/978-3-540-30214-8_2
82 rdf:type schema:PropertyValue
83 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
84 schema:name Information and Computing Sciences
85 rdf:type schema:DefinedTerm
86 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
87 schema:name Artificial Intelligence and Image Processing
88 rdf:type schema:DefinedTerm
89 sg:person.013325377075.00 schema:affiliation https://www.grid.ac/institutes/grid.177174.3
90 schema:familyName Arimura
91 schema:givenName Hiroki
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013325377075.00
93 rdf:type schema:Person
94 sg:person.015367141327.55 schema:affiliation https://www.grid.ac/institutes/grid.177174.3
95 schema:familyName Asai
96 schema:givenName Tatsuya
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015367141327.55
98 rdf:type schema:Person
99 sg:person.016517167551.57 schema:affiliation https://www.grid.ac/institutes/grid.250343.3
100 schema:familyName Uno
101 schema:givenName Takeaki
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016517167551.57
103 rdf:type schema:Person
104 sg:pub.10.1007/3-540-45841-7_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004444201
105 https://doi.org/10.1007/3-540-45841-7_10
106 rdf:type schema:CreativeWork
107 sg:pub.10.1007/3-540-49257-7_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048579740
108 https://doi.org/10.1007/3-540-49257-7_25
109 rdf:type schema:CreativeWork
110 sg:pub.10.1007/978-3-540-39644-4_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025309521
111 https://doi.org/10.1007/978-3-540-39644-4_6
112 rdf:type schema:CreativeWork
113 sg:pub.10.1007/s10115-004-0175-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016569315
114 https://doi.org/10.1007/s10115-004-0175-4
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1016/s0306-4379(99)00003-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000463430
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1109/69.846291 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061213826
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1109/icde.2001.914857 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095061845
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1109/icdm.2002.1183882 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094395359
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1109/icdm.2003.1250939 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095443679
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1137/1.9781611972726.10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088799860
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1137/1.9781611972726.27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088799881
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1145/276304.276313 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098992874
131 rdf:type schema:CreativeWork
132 https://doi.org/10.1145/342009.335372 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025244221
133 rdf:type schema:CreativeWork
134 https://doi.org/10.1145/380995.381017 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049909998
135 rdf:type schema:CreativeWork
136 https://doi.org/10.1145/380995.381033 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030106472
137 rdf:type schema:CreativeWork
138 https://doi.org/10.1145/956750.956784 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020461301
139 rdf:type schema:CreativeWork
140 https://www.grid.ac/institutes/grid.177174.3 schema:alternateName Kyushu University
141 schema:name Department of Informatics, Kyushu University, 6-10-1, Hakozaki, Fukuoka, Japan
142 rdf:type schema:Organization
143 https://www.grid.ac/institutes/grid.250343.3 schema:alternateName National Institute of Informatics
144 schema:name National Institute of Informatics, 2-1-2, Hitotsubashi, Chiyoda-ku, Tokyo, Japan
145 rdf:type schema:Organization
 




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


...