Skip to main content
Erschienen in: Knowledge and Information Systems 10/2020

24.06.2020 | Regular Paper

Mining evolutions of complex spatial objects using a single-attributed Directed Acyclic Graph

verfasst von: Frédéric Flouvat, Nazha Selmaoui-Folcher, Jérémy Sanhes, Chengcheng Mu, Claude Pasquier, Jean-François Boulicaut

Erschienen in: Knowledge and Information Systems | Ausgabe 10/2020

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Directed acyclic graphs (DAGs) are used in many domains ranging from computer science to bioinformatics, including industry and geoscience. They enable to model complex evolutions where spatial objects (e.g., soil erosion) may move, (dis)appear, merge or split. We study a new graph-based representation, called attributed DAG (a-DAG). It enables to capture interactions between objects as well as information on objects (e.g., characteristics or events). In this paper, we focus on pattern mining in such data. Our patterns, called weighted paths, offer a good trade-off between expressiveness and complexity. Frequency and compactness constraints are used to filter out uninteresting patterns. These constraints lead to an exact condensed representation (without loss of information) in the single-graph setting. A depth-first search strategy and an optimized data structure are proposed to achieve the efficiency of weighted path discovery. It does a progressive extension of patterns based on database projections. Relevance, scalability and genericity are illustrated by means of qualitative and quantitative results when mining various real and synthetic datasets. In particular, we show how such an approach can be used to monitor soil erosion using remote sensing and geographical information system (GIS) data.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Agrawal R, Srikant R (1994) Fast algorithms for mining association rules in large databases. In: Proceedings of the 20th international conference on very large data bases (VLDB). Morgan Kaufmann, pp 487–499 Agrawal R, Srikant R (1994) Fast algorithms for mining association rules in large databases. In: Proceedings of the 20th international conference on very large data bases (VLDB). Morgan Kaufmann, pp 487–499
2.
Zurück zum Zitat Agrawal R, Srikant R (1995) Mining sequential patterns. In: Proceedings of the eleventh international conference on data engineering (ICDE). IEEE Computer Society, pp 3–14 Agrawal R, Srikant R (1995) Mining sequential patterns. In: Proceedings of the eleventh international conference on data engineering (ICDE). IEEE Computer Society, pp 3–14
3.
Zurück zum Zitat Alatrista-Salas H, Bringay S, Flouvat F, Selmaoui-Folcher N, Teisseire M (2012) The pattern next door: towards spatio-sequential pattern discovery. In: Advances in knowledge discovery and data mining. Springer, pp 157–168 Alatrista-Salas H, Bringay S, Flouvat F, Selmaoui-Folcher N, Teisseire M (2012) The pattern next door: towards spatio-sequential pattern discovery. In: Advances in knowledge discovery and data mining. Springer, pp 157–168
4.
Zurück zum Zitat Arimura H, Uno T (2009) Polynomial-delay and polynomial-space algorithms for mining closed sequences, graphs, and pictures in accessible set systems. In: Proceedings of the SIAM international conference on data mining (SDM). SIAM, pp 1088–1099 Arimura H, Uno T (2009) Polynomial-delay and polynomial-space algorithms for mining closed sequences, graphs, and pictures in accessible set systems. In: Proceedings of the SIAM international conference on data mining (SDM). SIAM, pp 1088–1099
5.
Zurück zum Zitat Aydin B, Angryk RA (2016) A graph-based approach to spatiotemporal event sequence mining. In: Proceedings of the IEEE international conference on data mining workshops (ICDMW). IEEE Computer Society, pp 1090–1097 Aydin B, Angryk RA (2016) A graph-based approach to spatiotemporal event sequence mining. In: Proceedings of the IEEE international conference on data mining workshops (ICDMW). IEEE Computer Society, pp 1090–1097
6.
Zurück zum Zitat Bannari A, Morin D, Bonn F, Huete A (1995) A review of vegetation indices. Remote Sens Rev 13(1–2):95–120CrossRef Bannari A, Morin D, Bonn F, Huete A (1995) A review of vegetation indices. Remote Sens Rev 13(1–2):95–120CrossRef
7.
Zurück zum Zitat Berthold MR, Cebron N, Dill F, Gabriel TR, Kötter T, Meinl T, Ohl P, Sieb C, Thiel K, Wiswedel B (2007) KNIME: the Konstanz information miner. In: Studies in classification, data analysis, and knowledge organization (GfKL 2007). Springer Berthold MR, Cebron N, Dill F, Gabriel TR, Kötter T, Meinl T, Ohl P, Sieb C, Thiel K, Wiswedel B (2007) KNIME: the Konstanz information miner. In: Studies in classification, data analysis, and knowledge organization (GfKL 2007). Springer
8.
Zurück zum Zitat Beucher S, Meyer F (1993) The morphological approach to segmentation: the watershed transformation. Mathematical morphology in image processing. Opt Eng 34:433–481 Beucher S, Meyer F (1993) The morphological approach to segmentation: the watershed transformation. Mathematical morphology in image processing. Opt Eng 34:433–481
9.
Zurück zum Zitat Bonchi F, Lucchese C (2004) On closed constrained frequent pattern mining. In: Proceedings of the IEEE international conference on data mining (ICDM). IEEE Computer Society, pp 35–42 Bonchi F, Lucchese C (2004) On closed constrained frequent pattern mining. In: Proceedings of the IEEE international conference on data mining (ICDM). IEEE Computer Society, pp 35–42
10.
Zurück zum Zitat Borges J, Levene M (2000) A fine grained heuristic to capture web navigation patterns. ACM SIGKDD Explor 2(1):40–50CrossRef Borges J, Levene M (2000) A fine grained heuristic to capture web navigation patterns. ACM SIGKDD Explor 2(1):40–50CrossRef
11.
Zurück zum Zitat Boulicaut JF, Bykowski A, Rigotti C (2003) Free-sets: a condensed representation of boolean data for the approximation of frequency queries. Data Min Knowl Discov 7(1):5–22MathSciNetCrossRef Boulicaut JF, Bykowski A, Rigotti C (2003) Free-sets: a condensed representation of boolean data for the approximation of frequency queries. Data Min Knowl Discov 7(1):5–22MathSciNetCrossRef
12.
Zurück zum Zitat Bringmann B, Nijssen S (2008) What is frequent in a single graph? In: Proceedings of the Pacific-Asia conference on advances in knowledge discovery and data mining (PAKDD). Springer, pp 858–863 Bringmann B, Nijssen S (2008) What is frequent in a single graph? In: Proceedings of the Pacific-Asia conference on advances in knowledge discovery and data mining (PAKDD). Springer, pp 858–863
13.
Zurück zum Zitat Calders T, Rigotti C, Boulicaut JF (2004) A survey on condensed representations for frequent sets. In: Constraint-based mining and inductive databases. Springer, pp 64–80 Calders T, Rigotti C, Boulicaut JF (2004) A survey on condensed representations for frequent sets. In: Constraint-based mining and inductive databases. Springer, pp 64–80
14.
Zurück zum Zitat Casali A, Cicchetti R, Lakhal L (2005) Essential patterns: a perfect cover of frequent patterns. In: Proceedings of the international conference on data warehousing and knowledge discovery (DaWaK). Springer, pp 428–437 Casali A, Cicchetti R, Lakhal L (2005) Essential patterns: a perfect cover of frequent patterns. In: Proceedings of the international conference on data warehousing and knowledge discovery (DaWaK). Springer, pp 428–437
15.
Zurück zum Zitat Celik M, Shekhar S, Rogers JP, Shine JA (2008) Mixed-drove spatiotemporal co-occurrence pattern mining. IEEE Trans Knowl Data Eng 20(10):1322–1335CrossRef Celik M, Shekhar S, Rogers JP, Shine JA (2008) Mixed-drove spatiotemporal co-occurrence pattern mining. IEEE Trans Knowl Data Eng 20(10):1322–1335CrossRef
16.
Zurück zum Zitat Chen MS, Park JS, Yu PS (1998) Efficient data mining for path traversal patterns. IEEE Trans Knowl Data Eng 10(2):209–221CrossRef Chen MS, Park JS, Yu PS (1998) Efficient data mining for path traversal patterns. IEEE Trans Knowl Data Eng 10(2):209–221CrossRef
17.
Zurück zum Zitat Chen Yl, Kao Hp, Ko Mt (2004) Mining DAG patterns from DAG databases. In: Advances in web-age information management, pp 579–588 Chen Yl, Kao Hp, Ko Mt (2004) Mining DAG patterns from DAG databases. In: Advances in web-age information management, pp 579–588
18.
Zurück zum Zitat Collin M, Flouvat F, Selmaoui-Folcher N (2016) Patsi: pattern mining of time series of satellite images in knime. In: Proceedings of the IEEE international conference on data mining workshops (ICDMW). IEEE Computer Society, pp 1292–1295 Collin M, Flouvat F, Selmaoui-Folcher N (2016) Patsi: pattern mining of time series of satellite images in knime. In: Proceedings of the IEEE international conference on data mining workshops (ICDMW). IEEE Computer Society, pp 1292–1295
19.
20.
Zurück zum Zitat De Raedt L, Kramer S (2001) The levelwise version space algorithm and its application to molecular fragment finding. In: Proceedings of the international joint conference on artificial intelligence (IJCAI), vol 2. Morgan Kaufmann, pp 853–859 De Raedt L, Kramer S (2001) The levelwise version space algorithm and its application to molecular fragment finding. In: Proceedings of the international joint conference on artificial intelligence (IJCAI), vol 2. Morgan Kaufmann, pp 853–859
21.
Zurück zum Zitat De Raedt L, Jaeger M, Lee SD, Mannila H (2002) A theory of inductive query answering. In: Proceedings of the IEEE international conference on data mining (ICDM). IEEE Computer Society, pp 123–130 De Raedt L, Jaeger M, Lee SD, Mannila H (2002) A theory of inductive query answering. In: Proceedings of the IEEE international conference on data mining (ICDM). IEEE Computer Society, pp 123–130
22.
Zurück zum Zitat Douar B, Liquiere M, Latiri C, Slimani Y (2015) Lc-mine: a framework for frequent subgraph mining with local consistency techniques. Knowl Inf Syst 44(1):1–25CrossRef Douar B, Liquiere M, Latiri C, Slimani Y (2015) Lc-mine: a framework for frequent subgraph mining with local consistency techniques. Knowl Inf Syst 44(1):1–25CrossRef
23.
Zurück zum Zitat Dube MP, Egenhofer MJ (2014) Surrounds in partitions. In: Proceedings of the ACM international conference on advances in geographic information systems (SIGSPATIAL). ACM, pp 233–242 Dube MP, Egenhofer MJ (2014) Surrounds in partitions. In: Proceedings of the ACM international conference on advances in geographic information systems (SIGSPATIAL). ACM, pp 233–242
24.
Zurück zum Zitat Dube MP, Barrett JV, Egenhofer MJ (2015) From metric to topology: determining relations in discrete space. In: International workshop on spatial information theory. Springer, pp 151–171 Dube MP, Barrett JV, Egenhofer MJ (2015) From metric to topology: determining relations in discrete space. In: International workshop on spatial information theory. Springer, pp 151–171
25.
Zurück zum Zitat Fariha A, Ahmed CF, Leung CKS, Abdullah S, Cao L (2013) Mining frequent patterns from human interactions in meetings using directed acyclic graphs. In: Proceedings of the Pacific-Asia conference on advances in knowledge discovery and data mining (PAKDD). Springer, pp 38–49 Fariha A, Ahmed CF, Leung CKS, Abdullah S, Cao L (2013) Mining frequent patterns from human interactions in meetings using directed acyclic graphs. In: Proceedings of the Pacific-Asia conference on advances in knowledge discovery and data mining (PAKDD). Springer, pp 38–49
26.
Zurück zum Zitat Fiedler M, Borgelt C (2007) Support computation for mining frequent subgraphs in a single graph. In: Mining and learning with graphs Fiedler M, Borgelt C (2007) Support computation for mining frequent subgraphs in a single graph. In: Mining and learning with graphs
27.
Zurück zum Zitat Flouvat F, Sanhes J, Pasquier C, Selmaoui-Folcher N, Boulicaut JF (2014) Improving pattern discovery relevancy by deriving constraints from expert models. In: Proceedings of the European conference on artificial intelligence (ECAI). IOS Press, pp 327–332 Flouvat F, Sanhes J, Pasquier C, Selmaoui-Folcher N, Boulicaut JF (2014) Improving pattern discovery relevancy by deriving constraints from expert models. In: Proceedings of the European conference on artificial intelligence (ECAI). IOS Press, pp 327–332
28.
Zurück zum Zitat Fukuzaki M, Seki M, Kashima H, Sese J (2010) Finding itemset-sharing patterns in a large itemset-associated graph. In: Proceedings of the Pacific-Asia conference on advances in knowledge discovery and data mining (PAKDD). Springer, pp 147–159 Fukuzaki M, Seki M, Kashima H, Sese J (2010) Finding itemset-sharing patterns in a large itemset-associated graph. In: Proceedings of the Pacific-Asia conference on advances in knowledge discovery and data mining (PAKDD). Springer, pp 147–159
29.
Zurück zum Zitat Garriga GC, Khardon R, De Raedt L (2012) Mining closed patterns in relational, graph and network data. In: Annals of mathematics and artificial intelligence, pp 1–28 Garriga GC, Khardon R, De Raedt L (2012) Mining closed patterns in relational, graph and network data. In: Annals of mathematics and artificial intelligence, pp 1–28
30.
Zurück zum Zitat Geng R, Xu W, Dong X (2007) WTPMiner: efficient mining of weighted frequent patterns based on graph traversals. In: Proceedings of the international conference on knowledge science, engineering and management (KSEM). Springer, pp 412–424 Geng R, Xu W, Dong X (2007) WTPMiner: efficient mining of weighted frequent patterns based on graph traversals. In: Proceedings of the international conference on knowledge science, engineering and management (KSEM). Springer, pp 412–424
31.
Zurück zum Zitat Giannotti F, Pedreschi D (eds) (2008) Mobility, data mining and privacy—geographic knowledge discovery. Springer, Berlin Giannotti F, Pedreschi D (eds) (2008) Mobility, data mining and privacy—geographic knowledge discovery. Springer, Berlin
32.
Zurück zum Zitat Gudes E, Shimony SE, Vanetik N (2006) Discovering frequent graph patterns using disjoint paths. IEEE Trans Knowl Data Eng 18(11):1441–1456CrossRef Gudes E, Shimony SE, Vanetik N (2006) Discovering frequent graph patterns using disjoint paths. IEEE Trans Knowl Data Eng 18(11):1441–1456CrossRef
33.
Zurück zum Zitat Günnemann S, Seidl T (2010) Subgraph mining on directed and weighted graphs. In: Proceedings of the Pacific-Asia conference on advances in knowledge discovery and data mining (PAKDD). Springer, pp 133–146 Günnemann S, Seidl T (2010) Subgraph mining on directed and weighted graphs. In: Proceedings of the Pacific-Asia conference on advances in knowledge discovery and data mining (PAKDD). Springer, pp 133–146
34.
Zurück zum Zitat Gunopulos D, Mannila H, Saluja S (1997) Discovering all most specific sentences by randomized algorithms extended abstract. Springer, BerlinCrossRef Gunopulos D, Mannila H, Saluja S (1997) Discovering all most specific sentences by randomized algorithms extended abstract. Springer, BerlinCrossRef
35.
Zurück zum Zitat Haas BJ, Delcher AL, Wortman JR, Salzberg SL (2004) Dagchainer: a tool for mining segmental genome duplications and synteny. Bioinformatics 20(18):3643–3646CrossRef Haas BJ, Delcher AL, Wortman JR, Salzberg SL (2004) Dagchainer: a tool for mining segmental genome duplications and synteny. Bioinformatics 20(18):3643–3646CrossRef
36.
Zurück zum Zitat Huang Y, Shekhar S, Xiong H (2004) Discovering colocation patterns from spatial data sets: a general approach. IEEE Trans Knowl Data Eng 16(12):1472–1485CrossRef Huang Y, Shekhar S, Xiong H (2004) Discovering colocation patterns from spatial data sets: a general approach. IEEE Trans Knowl Data Eng 16(12):1472–1485CrossRef
37.
Zurück zum Zitat Inokuchi A, Washio T, Motoda H (2000) An apriori-based algorithm for mining frequent substructures from graph data. In: Proceedings of the European conference on principles of data mining and knowledge discovery (PKDD). Springer, vol 1910, pp 13–23 Inokuchi A, Washio T, Motoda H (2000) An apriori-based algorithm for mining frequent substructures from graph data. In: Proceedings of the European conference on principles of data mining and knowledge discovery (PKDD). Springer, vol 1910, pp 13–23
38.
Zurück zum Zitat Jiang C, Coenen F, Zito M (2013) A survey of frequent subgraph mining algorithms. Knowl Eng Rev 28(01):75–105CrossRef Jiang C, Coenen F, Zito M (2013) A survey of frequent subgraph mining algorithms. Knowl Eng Rev 28(01):75–105CrossRef
39.
Zurück zum Zitat Jiang J, Worboys M (2009) Event-based topology for dynamic planar areal objects. Int J Geogr Inf Sci 23(1):33–60CrossRef Jiang J, Worboys M (2009) Event-based topology for dynamic planar areal objects. Int J Geogr Inf Sci 23(1):33–60CrossRef
40.
Zurück zum Zitat Jiang X, Xiong H, Wang C, Tan AH (2009) Mining globally distributed frequent subgraphs in a single labeled graph. Data Knowl Eng 68(10):1034–1058CrossRef Jiang X, Xiong H, Wang C, Tan AH (2009) Mining globally distributed frequent subgraphs in a single labeled graph. Data Knowl Eng 68(10):1034–1058CrossRef
41.
Zurück zum Zitat Khan A, Yan X, Wu KL (2010) Towards proximity pattern mining in large graphs. In: Proceedings of the ACM international conference on management of data (SIGMOD). ACM Press, pp 867–878 Khan A, Yan X, Wu KL (2010) Towards proximity pattern mining in large graphs. In: Proceedings of the ACM international conference on management of data (SIGMOD). ACM Press, pp 867–878
42.
Zurück zum Zitat Kuramochi M, Karypis G (2001) Frequent subgraph discovery. In: Proceedings of the IEEE international conference on data mining (ICDM). IEEE Computer Society, pp 313–320 Kuramochi M, Karypis G (2001) Frequent subgraph discovery. In: Proceedings of the IEEE international conference on data mining (ICDM). IEEE Computer Society, pp 313–320
43.
Zurück zum Zitat Kuramochi M, Karypis G (2005) Finding frequent patterns in a large sparse graph*. Data Min Knowl Discov 11(3):243–271MathSciNetCrossRef Kuramochi M, Karypis G (2005) Finding frequent patterns in a large sparse graph*. Data Min Knowl Discov 11(3):243–271MathSciNetCrossRef
45.
Zurück zum Zitat Leskovec J, Kleinberg J, Faloutsos C (2005) Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the ACM international conference on knowledge discovery in data mining (SIGKDD). ACM, pp 177–187 Leskovec J, Kleinberg J, Faloutsos C (2005) Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the ACM international conference on knowledge discovery in data mining (SIGKDD). ACM, pp 177–187
46.
Zurück zum Zitat Lewis JA, Dube MP, Egenhofer MJ (2013) The topology of spatial scenes in r2. In: International conference on spatial information theory. Springer, pp 495–515 Lewis JA, Dube MP, Egenhofer MJ (2013) The topology of spatial scenes in r2. In: International conference on spatial information theory. Springer, pp 495–515
47.
Zurück zum Zitat Miyoshi Y, Ozaki T, Ohkawa T (2009) Frequent pattern discovery from a single graph with quantitative itemsets. In: Proceedings of the IEEE international conference on data mining workshops (ICDMW), pp 527–532 Miyoshi Y, Ozaki T, Ohkawa T (2009) Frequent pattern discovery from a single graph with quantitative itemsets. In: Proceedings of the IEEE international conference on data mining workshops (ICDMW), pp 527–532
48.
Zurück zum Zitat Mohan P, Shekhar S, Shine JA, Rogers JP (2010) Cascading spatio-temporal pattern discovery: a summary of results. In: Proceedings of the SIAM international conference on data mining (SDM), pp 327–338 Mohan P, Shekhar S, Shine JA, Rogers JP (2010) Cascading spatio-temporal pattern discovery: a summary of results. In: Proceedings of the SIAM international conference on data mining (SDM), pp 327–338
49.
Zurück zum Zitat Mohan P, Shekhar S, Shine JA, Rogers JP (2012) Cascading spatio-temporal pattern discovery. IEEE Trans Knowl Data Eng 24(11):1977–1992CrossRef Mohan P, Shekhar S, Shine JA, Rogers JP (2012) Cascading spatio-temporal pattern discovery. IEEE Trans Knowl Data Eng 24(11):1977–1992CrossRef
50.
Zurück zum Zitat Moser F, Colak R, Rafiey A, Ester M (2009) Mining cohesive patterns from graphs with feature vectors. In: Proceedings of the SIAM international conference on data mining (SDM), pp 593–604 Moser F, Colak R, Rafiey A, Ester M (2009) Mining cohesive patterns from graphs with feature vectors. In: Proceedings of the SIAM international conference on data mining (SDM), pp 593–604
51.
Zurück zum Zitat Nanopoulos A, Manolopoulos Y (2001) Mining patterns from graph traversals. Data Knowl Eng 37(3):243–266CrossRef Nanopoulos A, Manolopoulos Y (2001) Mining patterns from graph traversals. Data Knowl Eng 37(3):243–266CrossRef
52.
Zurück zum Zitat Nguyen TT, Nguyen HA, Pham NH, Al-Kofahi JM, Nguyen TN (2009) Graph-based mining of multiple object usage patterns. In: Proceedings of the the joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on the foundations of software engineering. ACM Press, pp 383–392 Nguyen TT, Nguyen HA, Pham NH, Al-Kofahi JM, Nguyen TN (2009) Graph-based mining of multiple object usage patterns. In: Proceedings of the the joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on the foundations of software engineering. ACM Press, pp 383–392
53.
Zurück zum Zitat Nijssen S, Kok JN (2004) A quickstart in frequent structure mining can make a difference. In: Proceedings of the ACM international conference on knowledge discovery and data mining (SIGKDD). ACM, pp 647–652 Nijssen S, Kok JN (2004) A quickstart in frequent structure mining can make a difference. In: Proceedings of the ACM international conference on knowledge discovery and data mining (SIGKDD). ACM, pp 647–652
54.
Zurück zum Zitat Pasquier C, Flouvat F, Sanhes J, Selmaoui-Folcher N (2017) Attributed graph mining in the presence of automorphism. Knowl Inf Syst 50(2):569–584CrossRef Pasquier C, Flouvat F, Sanhes J, Selmaoui-Folcher N (2017) Attributed graph mining in the presence of automorphism. Knowl Inf Syst 50(2):569–584CrossRef
55.
Zurück zum Zitat Pasquier N, Bastide Y, Taouil R, Lakhal L (1999) Discovering frequent closed itemsets for association rules. In: Proceedings of the international conference on database theory (ICDT). Springer, pp 398–416 Pasquier N, Bastide Y, Taouil R, Lakhal L (1999) Discovering frequent closed itemsets for association rules. In: Proceedings of the international conference on database theory (ICDT). Springer, pp 398–416
56.
Zurück zum Zitat Pei J, Han J, Mortazavi-Asl B, Wang J, Pinto H, Chen Q, Dayal U, Hsu M (2004) Mining sequential patterns by pattern-growth: the prefixspan approach. IEEE Trans Knowl Data Eng 16(11):1424–1440CrossRef Pei J, Han J, Mortazavi-Asl B, Wang J, Pinto H, Chen Q, Dayal U, Hsu M (2004) Mining sequential patterns by pattern-growth: the prefixspan approach. IEEE Trans Knowl Data Eng 16(11):1424–1440CrossRef
57.
Zurück zum Zitat Qian F, He Q, He J (2009) Mining spread patterns of spatio-temporal co-occurrences over zones. In: Proceedings of the international conference on computational science and its applications (ICCSA). Springer, vol 5593, pp 677–692 Qian F, He Q, He J (2009) Mining spread patterns of spatio-temporal co-occurrences over zones. In: Proceedings of the international conference on computational science and its applications (ICCSA). Springer, vol 5593, pp 677–692
58.
Zurück zum Zitat Sanhes J, Flouvat F, Pasquier C, Selmaoui-Folcher N, Boulicaut J (2013) Weighted path as a condensed pattern in a single attributed DAG. In: Proceedings of the international joint conference on artificial intelligence (IJCAI) Sanhes J, Flouvat F, Pasquier C, Selmaoui-Folcher N, Boulicaut J (2013) Weighted path as a condensed pattern in a single attributed DAG. In: Proceedings of the international joint conference on artificial intelligence (IJCAI)
59.
Zurück zum Zitat Sedgewick R, Wayne K (2011) Algorithms, 4th edn. Addison-Wesley, Reading Sedgewick R, Wayne K (2011) Algorithms, 4th edn. Addison-Wesley, Reading
60.
Zurück zum Zitat Selmaoui-Folcher N, Flouvat F (2011) How to use classical tree mining algorithms to find complex spatio-temporal patterns? In: Proceedings of the international conference on database and expert systems applications (DEXA). Springer, pp 107–117 Selmaoui-Folcher N, Flouvat F (2011) How to use classical tree mining algorithms to find complex spatio-temporal patterns? In: Proceedings of the international conference on database and expert systems applications (DEXA). Springer, pp 107–117
61.
Zurück zum Zitat Silva A, Meira W Jr, Zaki MJ (2012) Mining attribute-structure correlated patterns in large attributed graphs. Proceedings of the VLDB Endowment 5(5):466–477CrossRef Silva A, Meira W Jr, Zaki MJ (2012) Mining attribute-structure correlated patterns in large attributed graphs. Proceedings of the VLDB Endowment 5(5):466–477CrossRef
62.
Zurück zum Zitat Sindoni G, Stell JG (2017) The logic of discrete qualitative relations. In: Proceedings of the international conference on spatial information theory (COSIT). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, vol 86, pp 1–15 Sindoni G, Stell JG (2017) The logic of discrete qualitative relations. In: Proceedings of the international conference on spatial information theory (COSIT). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, vol 86, pp 1–15
63.
Zurück zum Zitat Termier A, Tamada Y, Numata K, Imoto S, Washio T, Higushi T, Higuchi T (2007) DigDag, a first algorithm to mine closed frequent embedded sub-DAGs. In: Proceedings of mining and learning with graphs (MLG), pp 1–5 Termier A, Tamada Y, Numata K, Imoto S, Washio T, Higushi T, Higuchi T (2007) DigDag, a first algorithm to mine closed frequent embedded sub-DAGs. In: Proceedings of mining and learning with graphs (MLG), pp 1–5
64.
Zurück zum Zitat Tsoukatos I, Gunopulos D (2001) Efficient mining of spatiotemporal patterns. In: Proceedings of the international symposium on spatial and temporal databases (SSTD). Springer, vol 2121, pp 425–442 Tsoukatos I, Gunopulos D (2001) Efficient mining of spatiotemporal patterns. In: Proceedings of the international symposium on spatial and temporal databases (SSTD). Springer, vol 2121, pp 425–442
65.
Zurück zum Zitat Uno T, Asai T, Uchida Y, Arimura H (2003) LCM: an efficient algorithm for enumerating frequent closed item sets. In: Proceedings of the IEEE international conference on data mining workshop on frequent itemset mining implementations (FIMI). CEUR-WS.org, vol 90 Uno T, Asai T, Uchida Y, Arimura H (2003) LCM: an efficient algorithm for enumerating frequent closed item sets. In: Proceedings of the IEEE international conference on data mining workshop on frequent itemset mining implementations (FIMI). CEUR-WS.org, vol 90
66.
Zurück zum Zitat Uno T, Asai T, Uchida Y, Arimura H (2004) An efficient algorithm for enumerating closed patterns in transaction databases. In: Proceedings of the international conference on discovery science (DS). Springer, pp 16–31 Uno T, Asai T, Uchida Y, Arimura H (2004) An efficient algorithm for enumerating closed patterns in transaction databases. In: Proceedings of the international conference on discovery science (DS). Springer, pp 16–31
67.
Zurück zum Zitat Wang J, Hsu W, Lee ML, Wang JTL (2004) FlowMiner: finding flow patterns in spatio-temporal databases. In: Proceedings of the IEEE international conference on tools with artificial intelligence (ICTAI). IEEE Computer Society, pp 14–21 Wang J, Hsu W, Lee ML, Wang JTL (2004) FlowMiner: finding flow patterns in spatio-temporal databases. In: Proceedings of the IEEE international conference on tools with artificial intelligence (ICTAI). IEEE Computer Society, pp 14–21
68.
Zurück zum Zitat Wang J, Hsu W, Lee ML, Sheng C (2006) A partition-based approach to graph mining. In: Proceedings of the IEEE international conference on data engineering (ICDE). IEEE Computer Society, pp 74—-74 Wang J, Hsu W, Lee ML, Sheng C (2006) A partition-based approach to graph mining. In: Proceedings of the IEEE international conference on data engineering (ICDE). IEEE Computer Society, pp 74—-74
69.
Zurück zum Zitat Washio T, Motoda H (2003) State of the art of graph-based data mining. SIGKDD Explora Newsl 5(1):59–68CrossRef Washio T, Motoda H (2003) State of the art of graph-based data mining. SIGKDD Explora Newsl 5(1):59–68CrossRef
70.
Zurück zum Zitat Washio T, Mitsunaga Y, Motoda H (2005) Mining quantitative frequent itemsets using adaptive density-based subspace clustering. In: Proceedings of the IEEE international conference on data mining (ICDM). IEEE Computer Society, pp 793–796 Washio T, Mitsunaga Y, Motoda H (2005) Mining quantitative frequent itemsets using adaptive density-based subspace clustering. In: Proceedings of the IEEE international conference on data mining (ICDM). IEEE Computer Society, pp 793–796
71.
Zurück zum Zitat Wasserman S, Faust K (1994) Social network analysis: methods and applications, vol 8. Cambridge University Press, CambridgeCrossRef Wasserman S, Faust K (1994) Social network analysis: methods and applications, vol 8. Cambridge University Press, CambridgeCrossRef
72.
Zurück zum Zitat Werth T, Dreweke A, Wörlein M, Fischer I, Philippsen M (2008) Dagma: mining directed acyclic graphs. In: Proceedings of the IADIS European conference on data mining. IADIS Press, pp 11–18 Werth T, Dreweke A, Wörlein M, Fischer I, Philippsen M (2008) Dagma: mining directed acyclic graphs. In: Proceedings of the IADIS European conference on data mining. IADIS Press, pp 11–18
73.
Zurück zum Zitat Werth T, Wörlein M, Dreweke A, Fischer I, Philippsen M (2009) Dag mining for code compaction. In: Data mining for business applications. Springer, pp 209–223 Werth T, Wörlein M, Dreweke A, Fischer I, Philippsen M (2009) Dag mining for code compaction. In: Data mining for business applications. Springer, pp 209–223
74.
Zurück zum Zitat Worboys M (2012) The maptree: a fine-grained formal representation of space. In: International conference on geographic information science. Springer, pp 298–310 Worboys M (2012) The maptree: a fine-grained formal representation of space. In: International conference on geographic information science. Springer, pp 298–310
75.
Zurück zum Zitat Yan X, Han J (2002) gSpan: Graph-bases substructure pattern mining. In: Proceedings of the IEEE international conference on data mining (ICDM). IEEE Computer Society, vol 3, pp 721–724 Yan X, Han J (2002) gSpan: Graph-bases substructure pattern mining. In: Proceedings of the IEEE international conference on data mining (ICDM). IEEE Computer Society, vol 3, pp 721–724
76.
Zurück zum Zitat Yan X, Han J (2003) CloseGraph. In: Proceedings of the ACM international conference on knowledge discovery and data mining (SIGKDD). ACM Press, vol 6, p 286 Yan X, Han J (2003) CloseGraph. In: Proceedings of the ACM international conference on knowledge discovery and data mining (SIGKDD). ACM Press, vol 6, p 286
77.
Zurück zum Zitat Yan X, Han J, Afshar R (2003) Clospan: mining: closed sequential patterns in large datasets. In: Proceedings of the SIAM international conference on data mining (SDM), pp 166–177 Yan X, Han J, Afshar R (2003) Clospan: mining: closed sequential patterns in large datasets. In: Proceedings of the SIAM international conference on data mining (SDM), pp 166–177
78.
Zurück zum Zitat Yang H, Parthasarathy S, Mehta S (2005) A generalized framework for mining spatio-temporal patterns in scientific data. In: Proceedings of the ACM international conference on knowledge discovery and data mining (SIGKDD). ACM Press, pp 716–721 Yang H, Parthasarathy S, Mehta S (2005) A generalized framework for mining spatio-temporal patterns in scientific data. In: Proceedings of the ACM international conference on knowledge discovery and data mining (SIGKDD). ACM Press, pp 716–721
Metadaten
Titel
Mining evolutions of complex spatial objects using a single-attributed Directed Acyclic Graph
verfasst von
Frédéric Flouvat
Nazha Selmaoui-Folcher
Jérémy Sanhes
Chengcheng Mu
Claude Pasquier
Jean-François Boulicaut
Publikationsdatum
24.06.2020
Verlag
Springer London
Erschienen in
Knowledge and Information Systems / Ausgabe 10/2020
Print ISSN: 0219-1377
Elektronische ISSN: 0219-3116
DOI
https://doi.org/10.1007/s10115-020-01478-9

Weitere Artikel der Ausgabe 10/2020

Knowledge and Information Systems 10/2020 Zur Ausgabe