2012 LinearSpaceDirectPatternSamplin: Difference between revisions
(Importing text file) |
m (Text replacement - " ↵↵" to " ") |
||
(13 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
* ([[2012_LinearSpaceDirectPatternSamplin|Boley | * ([[2012_LinearSpaceDirectPatternSamplin|Boley et al., 2012]]) ⇒ [[author::Mario Boley]], [[author::Sandy Moens]], and [[author::Thomas Gärtner]]. ([[year::2012]]). “Linear Space Direct Pattern Sampling Using Coupling from the Past.” In: [[proceedings::Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining]] ([[conference::KDD-2012]]). ISBN:978-1-4503-1462-6 [http://dx.doi.org/10.1145/2339530.2339545 doi:10.1145/2339530.2339545] | ||
<B>Subject Headings:</B> | <B>Subject Headings:</B> | ||
==Notes== | == Notes == | ||
==Cited By== | ==Cited By== | ||
Line 9: | Line 9: | ||
* http://dl.acm.org/citation.cfm?id=2339530.2339545&preflayout=flat#citedby | * http://dl.acm.org/citation.cfm?id=2339530.2339545&preflayout=flat#citedby | ||
==Quotes== | == Quotes == | ||
===Author Keywords=== | |||
=== Author Keywords === | |||
* [[Cftp]]; [[data mining]]; [[frequent set]]s; [[local pattern]]s; [[sampling]] | * [[Cftp]]; [[data mining]]; [[frequent set]]s; [[local pattern]]s; [[sampling]] | ||
===Abstract=== | === Abstract === | ||
[[This paper]] shows how [[coupling | [[This paper]] shows how [[coupling from the past (CFTP)]] can be used to [[avoid time]] and [[memory bottleneck]]s in [[direct local pattern sampling procedure]]s. </s> | ||
Such | Such [[procedure]]s draw [[controlled amount]]s of suitably [[biased samples]] directly from the [[pattern space]] of a given [[dataset]] in [[polynomial time]]. </s> | ||
Previous direct pattern | Previous [[direct pattern sampling method]]s can produce [[pattern]]s in [[rapid succession]] after some initial [[preprocessing phase]]. </s> | ||
This [[preprocessing phase]], however, turns out to be prohibitive in terms of time and memory for many [[dataset]]s. </s> | This [[preprocessing phase]], however, turns out to be prohibitive in terms of [[time]] and [[memory]] for many [[dataset]]s. </s> | ||
[[We]] show how [[CFTP]] can be used to avoid any [[super-linear preprocessing]] and [[memory requirement]]s. </s> | [[We]] show how [[CFTP]] can be used to avoid any [[super-linear preprocessing]] and [[super-linear memory|memory requirement]]s. </s> | ||
This allows to simulate more [[complex distribution]]s, which previously were intractable. </s> | This allows to [[simulate]] more [[complex distribution]]s, which previously were [[intractable]]. </s> | ||
[[We]] show for a [[large number of public real-world dataset]]s that these [[ | [[We]] show for a [[large number]] of [[public real-world dataset]]s that these new [[algorithm]]s are fast to [[execute]] and their [[pattern collection]]s outperform previous [[approach]]es both in [[unsupervised]] as well as [[supervised context]]s. </s> | ||
==References== | == References == | ||
{{#ifanon:| | {{#ifanon:| | ||
* 1. Mohammad Al Hasan, Mohammed J. Zaki, Output Space Sampling for Graph Patterns, Proceedings of the VLDB Endowment, v.2 n.1, August 2009 | * 1. Mohammad Al Hasan, Mohammed J. Zaki, Output Space Sampling for Graph Patterns, Proceedings of the VLDB Endowment, v.2 n.1, August 2009 |
Latest revision as of 19:33, 20 December 2023
- (Boley et al., 2012) ⇒ Mario Boley, Sandy Moens, and Thomas Gärtner. (2012). “Linear Space Direct Pattern Sampling Using Coupling from the Past.” In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2012). ISBN:978-1-4503-1462-6 doi:10.1145/2339530.2339545
Subject Headings:
Notes
Cited By
- http://scholar.google.com/scholar?q=%222012%22+Linear+Space+Direct+Pattern+Sampling+Using+Coupling+from+the+Past
- http://dl.acm.org/citation.cfm?id=2339530.2339545&preflayout=flat#citedby
Quotes
Author Keywords
Abstract
This paper shows how coupling from the past (CFTP) can be used to avoid time and memory bottlenecks in direct local pattern sampling procedures. Such procedures draw controlled amounts of suitably biased samples directly from the pattern space of a given dataset in polynomial time. Previous direct pattern sampling methods can produce patterns in rapid succession after some initial preprocessing phase. This preprocessing phase, however, turns out to be prohibitive in terms of time and memory for many datasets. We show how CFTP can be used to avoid any super-linear preprocessing and memory requirements. This allows to simulate more complex distributions, which previously were intractable. We show for a large number of public real-world datasets that these new algorithms are fast to execute and their pattern collections outperform previous approaches both in unsupervised as well as supervised contexts.
References
;
Author | volume | Date Value | title | type | journal | titleUrl | doi | note | year | |
---|---|---|---|---|---|---|---|---|---|---|
2012 LinearSpaceDirectPatternSamplin | Thomas Gärtner Sandy Moens Mario Boley | Linear Space Direct Pattern Sampling Using Coupling from the Past | 10.1145/2339530.2339545 | 2012 |