Ontology type: schema:ScholarlyArticle
2017-04
AUTHORSAmina Kemmar, Yahia Lebbah, Samir Loudni, Patrice Boizumault, Thierry Charnois
ABSTRACTSequential pattern mining (SPM) is an important data mining problem with broad applications. SPM is a hard problem due to the huge number of intermediate subsequences to be considered. State of the art approaches for SPM (e.g., PrefixSpan Pei et al. 2001) are largely based on the pattern-growth approach, where for each frequent prefix subsequence, only its related suffix subsequences need to be considered, and the database is recursively projected into smaller ones. Many authors have promoted the use of constraints to focus on the most promising patterns according to the interests of the end user. The top-k SPM problem is also used to cope with the difficulty of thresholding and to control the number of solutions. State of the art methods developed for SPM and top-k SPM, though efficient, are locked into a rather rigid search strategy, and suffer from the lack of declarativity and flexibility. Indeed, adding new constraints usually amounts to changing the data-structures used in the core of the algorithm, and combining these new constraints often require new developments. Recent works (e.g. Kemmar et al. 2014; Négrevergne and Guns 2015) have investigated the use of Constraint Programming (CP) for SPM. However, despite their nice declarative aspects, all these modelings have scaling problems, due to the huge size of their constraint networks. To address this issue, we propose the Prefix-Projection global constraint, which encapsulates both the subsequence relation as well as the frequency constraint. Its filtering algorithm relies on the principle of projected databases which allows to keep in the variables domain, only values leading to a frequent pattern in the database. Prefix-Projection filtering algorithm enforces domain consistency on the variable succeeding the current frequent prefix in polynomial time. This global constraint also allows for a straightforward implementation of additional constraints such as size, item membership, regular expressions and any combination of them. Experimental results show that our approach clearly outperforms existing CP approaches and competes well with the state-of-the-art methods on large datasets for mining frequent sequential patterns, sequential patterns under various constraints, and top-k sequential patterns. Unlike existing CP methods, our approach achieves a better scalability. More... »
PAGES265-306
http://scigraph.springernature.com/pub.10.1007/s10601-016-9252-z
DOIhttp://dx.doi.org/10.1007/s10601-016-9252-z
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1026007441
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/0806",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information Systems",
"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": "University of Oran",
"id": "https://www.grid.ac/institutes/grid.440479.a",
"name": [
"LITIO, University of Oran 1 Ahmed Ben Bella, Oran, Algeria"
],
"type": "Organization"
},
"familyName": "Kemmar",
"givenName": "Amina",
"id": "sg:person.012316104121.11",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012316104121.11"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "University of Oran",
"id": "https://www.grid.ac/institutes/grid.440479.a",
"name": [
"LITIO, University of Oran 1 Ahmed Ben Bella, Oran, Algeria"
],
"type": "Organization"
},
"familyName": "Lebbah",
"givenName": "Yahia",
"id": "sg:person.012476030467.45",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012476030467.45"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Universit\u00e9 de Caen Basse-Normandie",
"id": "https://www.grid.ac/institutes/grid.412043.0",
"name": [
"GREYC (CNRS UMR 6072), University of Caen, Caen, France"
],
"type": "Organization"
},
"familyName": "Loudni",
"givenName": "Samir",
"id": "sg:person.014232477671.68",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014232477671.68"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Universit\u00e9 de Caen Basse-Normandie",
"id": "https://www.grid.ac/institutes/grid.412043.0",
"name": [
"GREYC (CNRS UMR 6072), University of Caen, Caen, France"
],
"type": "Organization"
},
"familyName": "Boizumault",
"givenName": "Patrice",
"id": "sg:person.012370060421.99",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012370060421.99"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Paris 13 University",
"id": "https://www.grid.ac/institutes/grid.11318.3a",
"name": [
"LIPN (CNRS UMR 7030), University PARIS 13, Paris, France"
],
"type": "Organization"
},
"familyName": "Charnois",
"givenName": "Thierry",
"id": "sg:person.013564766405.01",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013564766405.01"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/3-540-45571-x_47",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1007543846",
"https://doi.org/10.1007/3-540-45571-x_47"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.artint.2011.05.002",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1013588077"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/354756.354849",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1016486740"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-33954-2_15",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1024097538",
"https://doi.org/10.1007/978-3-319-33954-2_15"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/775047.775109",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1025571209"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0895-7177(94)90127-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1028829495"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-23219-5_17",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1028894666",
"https://doi.org/10.1007/978-3-319-23219-5_17"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/584792.584799",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1029522805"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1023/a:1007652502315",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1035368646",
"https://doi.org/10.1023/a:1007652502315"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-53914-5_10",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1035592085",
"https://doi.org/10.1007/978-3-642-53914-5_10"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10489-013-0506-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1040903817",
"https://doi.org/10.1007/s10489-013-0506-9"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-07046-9_6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043437903",
"https://doi.org/10.1007/978-3-319-07046-9_6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-30201-8_36",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1044615390",
"https://doi.org/10.1007/978-3-540-30201-8_36"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-30201-8_36",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1044615390",
"https://doi.org/10.1007/978-3-540-30201-8_36"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-18008-3_20",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1046309836",
"https://doi.org/10.1007/978-3-319-18008-3_20"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/2133360.2133362",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1047471934"
],
"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.1109/tkde.2002.1000341",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061661051"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/tkde.2004.44",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061661318"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/tkde.2005.81",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061661479"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/1.9781611972733.15",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1088799903"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/1.9781611972771.22",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1088800178"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/icdm.2011.100",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1093506242"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/icde.2004.1319986",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1093587884"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/icdm.2008.111",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1093764879"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/cbms.2012.6266367",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1093868142"
],
"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/ictai.2014.89",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1094950014"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/icdm.2002.1183905",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1095067961"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/icdm.2013.92",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1095401829"
],
"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.1109/icde.2001.914830",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1095566607"
],
"type": "CreativeWork"
}
],
"datePublished": "2017-04",
"datePublishedReg": "2017-04-01",
"description": "Sequential pattern mining (SPM) is an important data mining problem with broad applications. SPM is a hard problem due to the huge number of intermediate subsequences to be considered. State of the art approaches for SPM (e.g., PrefixSpan Pei et al. 2001) are largely based on the pattern-growth approach, where for each frequent prefix subsequence, only its related suffix subsequences need to be considered, and the database is recursively projected into smaller ones. Many authors have promoted the use of constraints to focus on the most promising patterns according to the interests of the end user. The top-k SPM problem is also used to cope with the difficulty of thresholding and to control the number of solutions. State of the art methods developed for SPM and top-k SPM, though efficient, are locked into a rather rigid search strategy, and suffer from the lack of declarativity and flexibility. Indeed, adding new constraints usually amounts to changing the data-structures used in the core of the algorithm, and combining these new constraints often require new developments. Recent works (e.g. Kemmar et al. 2014; N\u00e9grevergne and Guns 2015) have investigated the use of Constraint Programming (CP) for SPM. However, despite their nice declarative aspects, all these modelings have scaling problems, due to the huge size of their constraint networks. To address this issue, we propose the Prefix-Projection global constraint, which encapsulates both the subsequence relation as well as the frequency constraint. Its filtering algorithm relies on the principle of projected databases which allows to keep in the variables domain, only values leading to a frequent pattern in the database. Prefix-Projection filtering algorithm enforces domain consistency on the variable succeeding the current frequent prefix in polynomial time. This global constraint also allows for a straightforward implementation of additional constraints such as size, item membership, regular expressions and any combination of them. Experimental results show that our approach clearly outperforms existing CP approaches and competes well with the state-of-the-art methods on large datasets for mining frequent sequential patterns, sequential patterns under various constraints, and top-k sequential patterns. Unlike existing CP methods, our approach achieves a better scalability.",
"genre": "research_article",
"id": "sg:pub.10.1007/s10601-016-9252-z",
"inLanguage": [
"en"
],
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1043977",
"issn": [
"1383-7133",
"1572-9354"
],
"name": "Constraints",
"type": "Periodical"
},
{
"issueNumber": "2",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "22"
}
],
"name": "Prefix-projection global constraint and top-k approach for sequential pattern mining",
"pagination": "265-306",
"productId": [
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"7be613f48a7ea37bab9357725ee72a5021e110a12dd3bf6babd57eec7f1f1767"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s10601-016-9252-z"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1026007441"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s10601-016-9252-z",
"https://app.dimensions.ai/details/publication/pub.1026007441"
],
"sdDataset": "articles",
"sdDatePublished": "2019-04-11T12:21",
"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/0000000362_0000000362/records_87079_00000000.jsonl",
"type": "ScholarlyArticle",
"url": "https://link.springer.com/10.1007%2Fs10601-016-9252-z"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
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/s10601-016-9252-z'
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/s10601-016-9252-z'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10601-016-9252-z'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10601-016-9252-z'
This table displays all metadata directly associated to this object as RDF triples.
198 TRIPLES
21 PREDICATES
58 URIs
19 LITERALS
7 BLANK NODES