Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Tìm kiếm cấu trúc tương đồng hiệu quả: Một cách tiếp cận dựa trên phân vùng
Tóm tắt
Đồ thị thường được sử dụng để mô hình hóa dữ liệu phức tạp trong nhiều ứng dụng, như sinh tin học, hóa học, mạng xã hội, và nhận dạng mẫu. Một truy vấn cơ bản và quan trọng là tìm kiếm các cấu trúc tương tự một cách hiệu quả trong một bộ sưu tập đồ thị lớn. Bài báo này chủ yếu nghiên cứu tìm kiếm tương đồng đồ thị dựa trên ngưỡng với các ràng buộc khoảng cách chỉnh sửa. Các giải pháp hiện có cho vấn đề này sử dụng các cấu trúc con chồng chéo với kích thước cố định để tạo ra các ứng viên, do đó dễ bị ảnh hưởng bởi các bậc đỉnh lớn và ngưỡng khoảng cách. Trong bài báo này, chúng tôi trình bày một phương pháp dựa trên phân vùng để giải quyết vấn đề. Bằng cách chia các đồ thị dữ liệu thành các phân vùng không chồng chéo có kích thước thay đổi, ràng buộc khoảng cách chỉnh sửa được chuyển đổi thành một ràng buộc chứa đồ thị để tạo ra các ứng viên. Chúng tôi phát triển các thuật toán xử lý truy vấn hiệu quả dựa trên mô hình mới này. Hơn nữa, các kỹ thuật cắt giảm ứng viên và một thuật toán xác minh khoảng cách chỉnh sửa đồ thị cải tiến được phát triển nhằm nâng cao hiệu suất. Ngoài ra, một phương pháp phân vùng đồ thị biết đến chi phí được thiết kế để tối ưu hóa chỉ mục. Mở rộng mô hình lọc dựa trên phân vùng, chúng tôi trình bày một giải pháp cho vấn đề tìm kiếm tương đồng đồ thị top-k, trong đó các chiến lược lọc tùy chỉnh, nhìn trước và chia sẻ tính toán được vận dụng. Sử dụng cả các tập dữ liệu thực tế và tổng hợp, các thí nghiệm toàn diện cho thấy các phương pháp của chúng tôi vượt trội hơn hẳn so với các phương pháp cơ bản và các phương pháp thay thế.
Từ khóa
#đồ thị #tìm kiếm tương đồng #khoảng cách chỉnh sửa #phân vùng #tối ưu hóa chỉ mụcTài liệu tham khảo
Bi, F., Chang, L., Lin, X., Qin, L., Zhang, W.: Efficient subgraph matching by postponing Cartesian products. In: SIGMOD Conference, pp. 1199–1214 (2016)
Bunke, H., Allermann, G.: Inexact graph matching for structural pattern recognition. PRL 1(4), 245–253 (1983)
Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. IJPRAI 18(3), 265–298 (2004)
Fankhauser, S., Riesen, K., Bunke, H.: Speeding up graph edit distance computation through fast bipartite matching. In: GbRPR, pp. 102–111 (2011)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness, 1st edn. W. H. Freeman, San Francisco (1979)
Gouda, K., Arafa, M., Calders, T.: Bfst_ed: a novel upper bound computation framework for the graph edit distance. In: SISAP, pp. 3–19 (2016)
Gouda, K., Hassaan, M.: CSI_GED: an efficient approach for graph edit similarity computation. In: ICDE, pp. 265–276 (2016)
Gupta, M., Gao, J., Yan, X., Cam, H., Han, J.: Top-k interesting subgraph discovery in information networks. In: ICDE, pp. 820–831 (2014)
Han, J., Kamber, M., Pei, J.: Data Mining: Concepts and Techniques, 3rd edn. Morgan Kaufmann, Los Altos (2011)
Han, W.-S., Lee, J., Lee, J.-H.: Turbo\(_{\text{iso}}\): towards ultrafast and robust subgraph isomorphism search in large graph databases. In: SIGMOD Conference, pp. 337–348 (2013)
He, H., Singh, A.K.: Closure-Tree: an index structure for graph queries. In: ICDE, p. 38 (2006)
Jin, C., Bhowmick, S.S., Choi, B., Zhou, S.: PRAGUE: towards blending practical visual subgraph query formulation and query processing. In: ICDE, pp. 222–233 (2012)
Marín, R.M., Aguirre, N.F., Daza, E.E.: Graph theoretical similarity approach to compare molecular electrostatic potentials. J. Chem. Inf. Model. 48(1), 109–118 (2008)
Ranu, S., Hoang, M.X., Singh, A.K.: Answering top-\(k\) representative queries on graph databases. In: SIGMOD Conference, pp. 1163–1174 (2014)
Raveaux, R., Burie, J.-C., Ogier, J.-M.: A graph matching method and a graph matching distance based on subgraph assignments. PRL 31(5), 394–406 (2010)
Ren, X., Wang, J.: Exploiting vertex relationships in speeding up subgraph isomorphism over large graphs. PVLDB 8(5), 617–628 (2015)
Riesen, K., Fankhauser, S., Bunke, H.: Speeding up graph edit distance computation with a bipartite heuristic. In: MLG (2007)
Sanfeliu, A., Fu, K.-S.: A distance measure between attributed relational graphs for pattern recognition. IEEE Trans. Syst. Man Cyber. 13(3), 353–362 (1983)
Shang, H., Lin, X., Zhang, Y., Yu, J.X., Wang, W.: Connected substructure similarity search. In: SIGMOD Conference, pp. 903–914 (2010)
Shang, H., Zhang, Y., Lin, X., Yu, J.X.: Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. PVLDB 1(1), 364–375 (2008)
Ullmann, J.R.: Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism. ACM J. Exp. Algorithmics 15, 1–6 (2010)
Ullmann, J.R.: Degree reduction in labeled graph retrieval. ACM J. Exp. Algorithmics 20, 1–3 (2015)
Wang, G., Wang, B., Yang, X., Yu, G.: Efficiently indexing large sparse graphs for similarity search. IEEE Trans. Knowl. Data Eng. 24(3), 440–451 (2012)
Wang, X., Ding, X., Tung, A.K.H., Ying, S., Jin, H.: An efficient graph indexing method. In: ICDE, pp. 210–221 (2012)
Yan, X., Yu, P.S., Han, J.: Graph indexing: a frequent structure-based approach. In: SIGMOD Conference, pp. 335–346 (2004)
Yan, X., Yu, P.S., Han, J.: Substructure similarity search in graph databases. In: SIGMOD Conference, pp. 766–777 (2005)
Yang, S., Han, F., Wu, Y., Yan, X.: Fast top-k search in knowledge graphs. In: ICDE (to appear) (2016)
Yang, Z., Fu, A.W., Liu, R.: Diversified top-\(k\) subgraph querying in a large graph. In: SIGMOD Conference, pp. 1167–1182 (2016)
Zeng, Z., Tung, A.K.H., Wang, J., Feng, J., Zhou, L.: Comparing stars: on approximating graph edit distance. PVLDB 2(1), 25–36 (2009)
Zhang, K., Wang, J.T.-L., Shasha, D.: On the editing distance between undirected acyclic graphs and related problems. In: CPM, pp. 395–407 (1995)
Zhang, S., Yang, J., Jin, W.: SAPPER: subgraph indexing and approximate matching in large graphs. PVLDB 3(1), 1185–1194 (2010)
Zhao, X., Xiao, C., Lin, X., Liu, Q., Zhang, W.: A partition-based approach to structure similarity search. PVLDB 7(3), 169–180 (2013)
Zhao, X., Xiao, C., Lin, X., Wang, W., Ishikawa, Y.: Efficient processing of graph similarity queries with edit distance constraints. VLDB J. 22(6), 727–752 (2013)
Zheng, W., Zou, L., Lian, X., Wang, D., Zhao, D.: Efficient graph similarity search over large graph databases. IEEE Trans. Knowl. Data Eng. 27(4), 964–978 (2015)
Zhu, Y., Qin, L., Yu, J.X., Cheng, H.: Finding top-\(k\) similar graphs in graph databases. In: EDBT, pp. 456–467 (2012)
Zhu, Y., Yu, J.X., Qin, L.: Leveraging graph dimensions in online graph search. PVLDB 8(1), 85–96 (2014)