{"id":{"repo_id":"usf","oai_identifier":"oai:digitalcommons.usf.edu:etd-8097"},"canonical_url":"https://search.ndltd.org/etd/usf/oai:digitalcommons.usf.edu:etd-8097","repository":{"repo_id":"usf","name":"University of South Florida","base_url":"https://digitalcommons.usf.edu/do/oai/"},"display":{"title":"Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs","abstract":"In recent years, the popularity of graph databases has grown rapidly. This paper focuses on single-graph as an effective model to represent information and its related graph mining techniques. In frequent pattern mining in a single-graph setting, there are two main problems: support measure and search scheme. In this paper, we propose a novel framework for constructing support measures that brings together existing minimum-image-based and overlap-graph-based support measures. Our framework is built on the concept of occurrence / instance hypergraphs. Based on that, we present two new support measures: minimum instance (MI) measure and minimum vertex cover (MVC) measure, that combine the advantages of existing measures. In particular, we show that the existing minimum-image-based support measure is an upper bound of the MI measure, which is also linear-time computable and results in counts that are close to number of instances of a pattern. Although the MVC measure is NP-hard, it can be approximated to a constant factor in polynomial time. We also provide polynomial-time relaxations for both measures and bounding theorems for all presented support measures in the hypergraph setting. We further show that the hypergraph-based framework can unify all support measures studied in this paper. This framework is also flexible in that more variants of support measures can be defined and profiled in it.","abstract_html":"In recent years, the popularity of graph databases has grown rapidly. This paper focuses on single-graph as an effective model to represent information and its related graph mining techniques. In frequent pattern mining in a single-graph setting, there are two main problems: support measure and search scheme. In this paper, we propose a novel framework for constructing support measures that brings together existing minimum-image-based and overlap-graph-based support measures. Our framework is built on the concept of occurrence / instance hypergraphs. Based on that, we present two new support measures: minimum instance (MI) measure and minimum vertex cover (MVC) measure, that combine the advantages of existing measures. In particular, we show that the existing minimum-image-based support measure is an upper bound of the MI measure, which is also linear-time computable and results in counts that are close to number of instances of a pattern. Although the MVC measure is NP-hard, it can be approximated to a constant factor in polynomial time. We also provide polynomial-time relaxations for both measures and bounding theorems for all presented support measures in the hypergraph setting. We further show that the hypergraph-based framework can unify all support measures studied in this paper. This framework is also flexible in that more variants of support measures can be defined and profiled in it.","abstract_has_math":false,"creators":["Meng, Jinghan"],"institution":"University of South Florida","degree_name":"Master of Science (M.S.)","degree_level":"Thesis","degree_discipline":"Engineering","degree_department":null,"school":null,"contributors":["Yicheng Tu, Ph.D.","Yao Liu, Ph.D.","Paul Rosen, Ph.D."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-06-26T07:00:00Z","date_published":"2017-06-26T07:00:00Z","updated_at":"2026-11-19T08:42:41Z","subjects":["Data Mining","Vertex Overlap","Anti-monotonic","Linear Programming","Hypergraph","Computer Sciences"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.usf.edu/etd/6900","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.usf.edu/etd/6900","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.usf.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.usf.edu%3Aetd-8097","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Yicheng Tu, Ph.D.","Yao Liu, Ph.D.","Paul Rosen, Ph.D."]},{"key":"dc:creator","label":"Author","values":["Meng, Jinghan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-06-26T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis","M.S."]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (M.S.)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of South Florida"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Data Mining","Vertex Overlap","Anti-monotonic","Linear Programming","Hypergraph","Computer Sciences"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.usf.edu/etd/6900"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In recent years, the popularity of graph databases has grown rapidly. This paper focuses on single-graph as an effective model to represent information and its related graph mining techniques. In frequent pattern mining in a single-graph setting, there are two main problems: support measure and search scheme. In this paper, we propose a novel framework for constructing support measures that brings together existing minimum-image-based and overlap-graph-based support measures. Our framework is built on the concept of occurrence / instance hypergraphs. Based on that, we present two new support measures: minimum instance (MI) measure and minimum vertex cover (MVC) measure, that combine the advantages of existing measures. In particular, we show that the existing minimum-image-based support measure is an upper bound of the MI measure, which is also linear-time computable and results in counts that are close to number of instances of a pattern. Although the MVC measure is NP-hard, it can be approximated to a constant factor in polynomial time. We also provide polynomial-time relaxations for both measures and bounding theorems for all presented support measures in the hypergraph setting. We further show that the hypergraph-based framework can unify all support measures studied in this paper. This framework is also flexible in that more variants of support measures can be defined and profiled in it."]},{"key":"dc:title","label":"Title","values":["Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs"]}]}],"canonical_facts":{"dc:contributor":["Yicheng Tu, Ph.D.","Yao Liu, Ph.D.","Paul Rosen, Ph.D."],"dc:creator":["Meng, Jinghan"],"dc:date":["2017-06-26T07:00:00Z"],"dc:description":["In recent years, the popularity of graph databases has grown rapidly. This paper focuses on single-graph as an effective model to represent information and its related graph mining techniques. In frequent pattern mining in a single-graph setting, there are two main problems: support measure and search scheme. In this paper, we propose a novel framework for constructing support measures that brings together existing minimum-image-based and overlap-graph-based support measures. Our framework is built on the concept of occurrence / instance hypergraphs. Based on that, we present two new support measures: minimum instance (MI) measure and minimum vertex cover (MVC) measure, that combine the advantages of existing measures. In particular, we show that the existing minimum-image-based support measure is an upper bound of the MI measure, which is also linear-time computable and results in counts that are close to number of instances of a pattern. Although the MVC measure is NP-hard, it can be approximated to a constant factor in polynomial time. We also provide polynomial-time relaxations for both measures and bounding theorems for all presented support measures in the hypergraph setting. We further show that the hypergraph-based framework can unify all support measures studied in this paper. This framework is also flexible in that more variants of support measures can be defined and profiled in it."],"dc:identifier":["https://digitalcommons.usf.edu/etd/6900"],"dc:subject":["Data Mining","Vertex Overlap","Anti-monotonic","Linear Programming","Hypergraph","Computer Sciences"],"dc:title":["Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs"],"thesis:degree_discipline":["Engineering"],"thesis:degree_level":["Thesis","M.S."],"thesis:degree_name":["Master of Science (M.S.)"],"thesis:institution_name":["University of South Florida"]},"updated_at":"2026-11-19T08:42:41Z"}