Dissertation > Excellent graduate degree dissertation topics show

Research on Graph Similarity Search Based on Frequent Sub-patterns

Author: LvJinTao
Tutor: LiXueMing
School: Chongqing University
Course: Computer Software and Theory
Keywords: Graphics mining Frequent subgraph Similarity search The approximate diagram contains search
CLC: TP391.3
Type: Master's thesis
Year: 2009
Downloads: 63
Quote: 0
Read: Download Dissertation

Abstract


Since late last century, data mining as a new and effective means of information extraction, the constant attention of an increasing number of scientific researchers and research. The graph mining data mining an emerging cross-disciplinary field started in 2000 by a number of experts and scholars proposed and studied. Graphics mining is on the nature of the data mining technology to using a graphical modeling of scientific research areas and research information, and on this basis, developed new graphics suitable for all areas of the mining technology, thus promoting the development of research and production. The graphics mining the main application field of chemical and biological information science. Using a graphical modeling some areas, such as molecules, protein chain in these areas, and then through some valuable model for various scientific information centrally in the corresponding pattern data mining, and for scientific research services. Frequent subgraph mining and graphics similarity search the graphics mining in two important areas of research. Frequent subgraph mining, mining frequent appearance of some of the sub-graph or chart (also called sub-structure or mode) from a given graph data set. Frequent subgraph (mode) essentially says that some important information in the relevant fields. Graphic similarity search, i.e. in a given based on the graphic data set of the fields of information modeling query satisfy some similarity conditions graphics, in 2004, proposed by Yan et al. This search is widely used in a variety of scientific research, such as the development of new drugs, the toxicity of the compound prediction. The approximate graph contains the search as a graphic similarity search was first presented in the paper of Chen et al in 2007 contains the search, but did not study. Prior to this study only limited and precise search and traditional substructure similarity search. Traditional substructure similarity search, inquire whether a given data set contains approximately contain a given query graph model diagram. The approximate graph contains the search query graph contains or approximate contain model diagram. Since the opposite inclusion relations for traditional substructure similarity search index construction strategy of approximate diagram contains the search is no longer applicable, and this also does not include approximate Figure Search index construction algorithm. In this paper, on the basis of the well-studied typical frequent subgraph mining and graphics similarity search index construction algorithm is proposed based on the coverage and support package search index for approximate diagram construction algorithm csIndex (coverage and support based Index), The main idea csIndex the first of the frequent substructures coverage excavated from the collection of a given model diagram and support a comprehensive test, and calculated based on the coverage and support comprehensive screening capability as an index entry, and then select the sub-structure of the integrated screening capability, and index these index entries organized into a matrix indexing system. Through a variety of tests on some of the classic in the field of experimental and test data sets, the results show that, csIndex able to complete the efficient approximate graph contains the search while effectively avoid subgraph isomorphism testing subgraph isomorphism test has been shown to belong to NP-complete problem.

Related Dissertations

  1. Research on Parallel Frequent Graph Pattern Mining,TP311.13
  2. Research on Algorithms for Maximal Frequent Subgraph Mining,TP301.6
  3. Research on Algorithms for Frequent Subgraph Mining Based on Large Graph Databases,TP301.6
  4. Research on Algorithm of Graph-Based Data Mining,TP311.13
  5. Research on Algorithms for Frequent Subgraph Mining,TP301.6
  6. Algorithms for Mining Frequent Subgraphs and Its Applications in Biological Network,TP311.13
  7. The Description and Search of Chemical Structures in Scientific Documents,TP391.3
  8. An Application Research on Graph Based Link Discovery in Anti-Money Laundering,F832.2
  9. Research and Application of Mining Graph Structure Algorithm,TP311.13
  10. Research and Application on Frequent Substructure Mining Algorithms,TP311.13
  11. Research on Techniques for Mining Graph Patterns,TP311.13
  12. Research of Query Technologies on Graph Data,TP311.13
  13. Graphical Mining Based on Time-series,TP311.13
  14. The Research on a Few Key Issues in Querying Algorithms over Data Streams,TP301.6
  15. Research on Mining and Similarity Searching in Time Series Database,TP311.13
  16. Several high-dimensional data mining research on key issues,TP311.13
  17. Research and Application of Financial Multivariate Time Series Mining Methods,F830
  18. Key Technologies Research on Data Stream Mining,TP311.13
  19. Research on Key Issues of Stochastic Non-stationary Time Series Data Mining Based on Fractal Theory,TP311.13
  20. Research on Data Mining and Forecasting Methods Over Time Series Data with Complex Structure,O211.61

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > Computer applications > Information processing (information processing) > Retrieval machine
© 2012 www.DissertationTopic.Net  Mobile