{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T00:26:20Z","timestamp":1779323180101,"version":"3.51.4"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2006,12]]},"abstract":"<jats:p>\n            Similarity search of complex structures is an important operation in graph-related applications since exact matching is often too restrictive. In this article, we investigate the issues of\n            <jats:italic>substructure similarity search using indexed features<\/jats:italic>\n            in graph databases. By transforming the edge relaxation ratio of a query graph into the maximum allowed feature misses, our structural filtering algorithm can filter graphs without performing pairwise similarity computation. It is further shown that using either too few or too many features can result in poor filtering performance. Thus the challenge is to design an effective feature set selection strategy that could maximize the filtering capability. We prove that the complexity of optimal feature set selection is \u03a9(2\n            <jats:sup>\n              <jats:italic>m<\/jats:italic>\n            <\/jats:sup>\n            ) in the worst case, where\n            <jats:italic>m<\/jats:italic>\n            is the number of features for selection. In practice, we identify several criteria to build effective feature sets for filtering, and demonstrate that combining features with similar size and selectivity can improve the filtering and search performance significantly within a multifilter composition framework. The proposed feature-based filtering concept can be generalized and applied to searching approximate nonconsecutive sequences, trees, and other structured data as well.\n          <\/jats:p>","DOI":"10.1145\/1189769.1189777","type":"journal-article","created":{"date-parts":[[2007,1,16]],"date-time":"2007-01-16T19:38:29Z","timestamp":1168976309000},"page":"1418-1453","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":45,"title":["Feature-based similarity search in graph structures"],"prefix":"10.1145","volume":"31","author":[{"given":"Xifeng","family":"Yan","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feida","family":"Zhu","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philip S.","family":"Yu","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research Center, Hawthorne, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiawei","family":"Han","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.954600"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/28.1.235"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(97)00179-7"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_6_1","unstructured":"Garey M. and Johnson D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman & Co. New York NY.   Garey M. and Johnson D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman & Co. New York NY."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 2002 International Conference on Pattern Recognition (ICPR'02)","author":"Giugno R.","unstructured":"Giugno , R. and Shasha , D . 2002. Graphgrep: A fast and universal method for querying graphs . Proceedings of the 2002 International Conference on Pattern Recognition (ICPR'02) . 112--115. Giugno, R. and Shasha, D. 2002. Graphgrep: A fast and universal method for querying graphs. Proceedings of the 2002 International Conference on Pattern Recognition (ICPR'02). 112--115."},{"key":"e_1_2_1_8_1","first-page":"28","article-title":"Using q-grams in a dbms for approximate string processing","volume":"24","author":"Gravano L.","year":"2001","unstructured":"Gravano , L. , Ipeirotis , P. , Jagadish , H. , Koudas , N. , Muthukrishnan , S. , Pietarinen , L. , and Srivastava , D. 2001 . Using q-grams in a dbms for approximate string processing . Data Eng. Bull. 24 , 28 -- 37 . Gravano, L., Ipeirotis, P., Jagadish, H., Koudas, N., Muthukrishnan, S., Pietarinen, L., and Srivastava, D. 2001. Using q-grams in a dbms for approximate string processing. Data Eng. Bull. 24, 28--37.","journal-title":"Data Eng. Bull."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1021\/ci00009a019"},{"key":"e_1_2_1_10_1","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"Hochbaum D.","unstructured":"Hochbaum , D. 1997. Approximation Algorithms for NP-Hard Problems . PWS Publishing , Boston, MA . Hochbaum, D. 1997. Approximation Algorithms for NP-Hard Problems. PWS Publishing, Boston, MA."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the AAAI'94 Workshop on Knowledge Discovery in Databases (KDD'94)","author":"Holder L.","unstructured":"Holder , L. , Cook , D. , and Djoko , S . 1994. Substructure discovery in the subdue system . In Proceedings of the AAAI'94 Workshop on Knowledge Discovery in Databases (KDD'94) . 169--180. Holder, L., Cook, D., and Djoko, S. 1994. Substructure discovery in the subdue system. In Proceedings of the AAAI'94 Workshop on Knowledge Discovery in Databases (KDD'94). 169--180."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 9th International Conference on Extending Database Technology (EDBT'04)","author":"Kailing K.","unstructured":"Kailing , K. , Kriegel , H. , Schnauer , S. , and Seidl , T . 2004. Efficient similarity search for hierarchical data in large databases . In Proceedings of the 9th International Conference on Extending Database Technology (EDBT'04) . 676--693. Kailing, K., Kriegel, H., Schnauer, S., and Seidl, T. 2004. Efficient similarity search for hierarchical data in large databases. In Proceedings of the 9th International Conference on Extending Database Technology (EDBT'04). 676--693."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/28.1.27"},{"key":"e_1_2_1_14_1","first-page":"557","article-title":"On the selection of the kth element of an ordered set by pairwise comparisons","volume":"5","author":"Kislicyn S. S.","year":"1964","unstructured":"Kislicyn , S. S. 1964 . On the selection of the kth element of an ordered set by pairwise comparisons . Sibirskii Mat. Z. (in Russian) 5 , 557 -- 564 . Kislicyn, S. S. 1964. On the selection of the kth element of an ordered set by pairwise comparisons. Sibirskii Mat. Z. (in Russian) 5, 557--564.","journal-title":"Sibirskii Mat. Z. (in Russian)"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 2001 International Conference on Data Mining (ICDM'01)","author":"Kuramochi M.","unstructured":"Kuramochi , M. and Karypis , G . 2001. Frequent subgraph discovery . In Proceedings of the 2001 International Conference on Data Mining (ICDM'01) . 313--320. Kuramochi, M. and Karypis, G. 2001. Frequent subgraph discovery. In Proceedings of the 2001 International Conference on Data Mining (ICDM'01). 313--320."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.682179"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/375360.375365"},{"key":"e_1_2_1_18_1","volume-title":"Principles of Artificial Intelligence. Morgan Kaufmann","author":"Nilsson N.","unstructured":"Nilsson , N. 1980. Principles of Artificial Intelligence. Morgan Kaufmann , Palo Alto, CA . Nilsson, N. 1980. Principles of Artificial Intelligence. Morgan Kaufmann, Palo Alto, CA."},{"key":"e_1_2_1_19_1","volume-title":"Linear Optimization and Extensions","author":"Padberg M.","unstructured":"Padberg , M. 1995. Linear Optimization and Extensions . Springer-Verlag , Berlin, Germany . Padberg, M. 1995. Linear Optimization and Extensions. Springer-Verlag, Berlin, Germany."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.599932"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/45.6.631"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543620"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 2003 International Conference on Very Large Data Bases (VLDB'03)","author":"Srinivasa S.","unstructured":"Srinivasa , S. and Kumar , S . 2003. A platform based on the multi-dimensional data model for analysis of bio-molecular structures . In Proceedings of the 2003 International Conference on Very Large Data Bases (VLDB'03) . 975--986. Srinivasa, S. and Kumar, S. 2003. A platform based on the multi-dimensional data model for analysis of bio-molecular structures. In Proceedings of the 2003 International Conference on Very Large Data Bases (VLDB'03). 975--986."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90143-4"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/20.2.141"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.298173"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1021\/ci9800211"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007607"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066244"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1189769.1189777","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:09:20Z","timestamp":1672261760000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1189769.1189777"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,12]]}},"alternative-id":["10.1145\/1189769.1189777"],"URL":"https:\/\/doi.org\/10.1145\/1189769.1189777","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,12]]},"assertion":[{"value":"2006-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}