Substructure similarity measurement in chinese recipes

ABSTRACT

Improving the precision of information retrieval has been a challenging issue on Chinese Web. As exemplified by Chinese recipes on the Web, it is not easy/natural for people to use keywords (e.g. recipe names) to search recipes, since the names can be literally so abstract that they do not bear much, if any, information on the underlying ingredients or cooking methods. In this paper, we investigate the underlying features of Chinese recipes, and based on workflow-like cooking procedures, we model recipes as graphs. We further propose a novel similarity measurement based on the frequent patterns, and devise an effective filtering algorithm to prune unrelated data so as to support efficient on-line searching. Benefiting from the characteristics of graphs, frequent common patterns can be mined from a cooking graph database. So in our prototype system called RecipeView, we extend the subgraph mining algorithm FSG to cooking graphs and combine it with our proposed similarity measurement, resulting in an approach that well caters for specific users' needs. Our initial experimental studies show that the filtering algorithm can efficiently prune unrelated cooking graphs without affecting the retrieval performance and the similarity measurement gets a relatively higher precision/recall against its counterparts

REFERENCES

• 1: Horst Bunke , Kim Shearer, A graph distance metric based on the maximal common subgraph, Pattern Recognition Letters, v.19 n.3-4, p.255-259, March 1998 [doi>10.1016/S0167-8655(97)00179-7]
• 2: Cook, D. J., and Holder, L. B. Substructure discovery using minimum description length and background knowledge. Journal of Artificial Intelligence Research 1 (1994), 231--255.
• 3: Conte, D., Guidobaldi, C., and Sansone, C. A comparison of three maximum common subgraph algorithms on a large database of labeled graphs. In Proc. of the 4th IAPR International Workshop on Graph Based Representations in Pattern Recognition (GbRPR), York, UK, 2003, pp. 589--607.
• 4: Surnjani Djoko , Diane J. Cook , Lawrence B. Holder, An Empirical Study of Domain Knowledge and Its Benefits to Substructure Discovery, IEEE Transactions on Knowledge and Data Engineering, v.9 n.4, p.575-586, July 1997 [doi>10.1109/69.617051]
• 5: Government News. http://www.cq.xinhua.org/food/200801/15/content_12221389.htm
• 6: Homepage ChemIDPlus. http://chem.sis.nlm.nih.gov/chemidplus/.
• 7: Homepage Simpack. http://www.ifi.unizh.ch/ddis/simpack.html.
• 8: Akihiro Inokuchi , Takashi Washio , Hiroshi Motoda, An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.13-23, September 13-16, 2000
• 9: Emre Karakoc , Artem Cherkasov , S. Cenk Sahinalp, Novel approaches for small biomolecule classification and structural similarity search, ACM SIGKDD Explorations Newsletter, v.9 n.1, June 2007 [doi>10.1145/1294301.1294307]
• 10: Michihiro Kuramochi , George Karypis, Frequent Subgraph Discovery, Proceedings of the 2001 IEEE International Conference on Data Mining, p.313-320, November 29-December 02, 2001
• 11: Li, Y., Meng, X., Wang, L., and Li, Q. RecipeCrawler: collecting recipe data from www incrementally. In Proc. of the 7th International Conference on Web-Age Information Management (WAIM), Hong Kong, China, 2006, pp. 263--274.
• 12: Wang, L., Li, Q. A personalized recipe database system with user-centered adaptation and tutoring support. In ACM SIGMOD Ph.D. workshop on Innovative database research (IDAR), 2007.
• 13: Bruno T. Messmer , Horst Bunke, A New Algorithm for Error-Tolerant Subgraph Isomorphism Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.5, p.493-504, May 1998 [doi>10.1109/34.682179]
• 14: G. Salton , A. Wong , C. S. Yang, A vector space model for automatic indexing, Communications of the ACM, v.18 n.11, p.613-620, Nov. 1975 [doi>10.1145/361219.361220]
• 15: Sanfeliu, A., and Fu, K. S. A distance measure between attributed relational graphs for pattern recognition. IEEE Transactions on Systems, Man and Cybernetics 13, 5 (1983), 353--362.
• 16: Dennis Shasha , Jason T. L. Wang , Rosalba Giugno, Algorithmics and applications of tree and graph searching, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543620]
• 17: Esko Ukkonen, Approximate string-matching with q-grams and maximal matches, Theoretical Computer Science, v.92 n.1, p.191-211, Jan. 6, 1992 [doi>10.1016/0304-3975(92)90143-4]
• 18: J. R. Ullmann, An Algorithm for Subgraph Isomorphism, Journal of the ACM (JACM), v.23 n.1, p.31-42, Jan. 1976 [doi>10.1145/321921.321925]
• 19: Wang, L. CookRecipe - towards a versatile and fully-fledged recipe analysis and learning system. Ph.D. thesis, Department of Computer Science, City University of Hong Kong, Hong Kong (Jan. 2008).
• 20: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.721, December 09-12, 2002
• 21: Xifeng Yan , Philip S. Yu , Jiawei Han, Graph indexing based on discriminative frequent structure analysis, ACM Transactions on Database Systems (TODS), v.30 n.4, p.960-993, December 2005 [doi>10.1145/1114244.1114248]
• 22: Xifeng Yan , Philip S. Yu , Jiawei Han, Substructure similarity search in graph databases, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066244]
• 23: Rui Yang , Panos Kalnis , Anthony K. H. Tung, Similarity evaluation on tree-structured data, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066243]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering; Search process

General Terms:
Algorithms, Measurement

Keywords:
cooking graph, filtering, recipes, similarity measurement, subgraph mining