Computer Science

Computer Science ›› 2022, Vol. 49 ›› Issue (12): 283-292.doi: 10.11896/jsjkx.211000077

• Artificial Intelligence • Previous Articles     Next Articles

k-step Reachability Query Processing on Label-constrained Graph

DU Ming, XING Rui-ping, ZHOU Jun-feng, TAN Yu-ting   

  1. School of Computer Science and Technology,Donghua University,Shanghai 201620,China
  • Received:2021-10-11 Revised:2022-06-07 Published:2022-12-14
  • About author:DU Ming,born in 1975,Ph.D,associate professor.His main research interests include natural language processing,information service,and data analysis.XING Rui-ping,born in 1997,postgra-duate.Her main research interests include graph reachability and so on.
  • Supported by:
    Natural Science Foundation of Shanghai,China(20ZR1402700) and National Natural Science Foundation of China(61472339,61572421,61272124).

PDF (PC)

420

Abstract: The k-step reachability query processing on label-constrained graph is used to answer whether there is a path with a length not greater than k between two points and the labels on this path are in the specified label set.The k-step reachability query processing on label-constrained graph is widely used in reality,but there is no relevant algorithm to answer it.Therefore,the LK2H algorithm is proposed firstly.LK2H algorithm mainly consists of two steps.The first step is to build a pair of 2-Hop in-dexes containing k and label information for all vertices on the graph,and the second step is querying based on the built index.In order to return information as much as possible to the user,LK2H optimizes the results of a type of unreachable query:when the user cannot specify all the label types,and cannot give full label constraints resulting in unreachable query results,the complete label set will return to the user.Secondly,an optimization algorithm,LK2H+,is proposed.LK2H+ algorithm further reduces the index size and time of construction by building a 2-Hop index for part of vertices,and queries based on the built index.Queries require a discussion of whether query vertices are indexed or not.Finally,the test is conducted based on 15 real-world datasets.Experiment results show that both LK2H and LK2H+ algorithms can solve k-step reachability query processing on label constraint graphs efficiently and quickly.

Key words: Label-constrained graph, k-step reachability query, 2-hop index, Vertex cover, Graph theory

CLC Number: 

  • TP301
[1]KUMAR R,ALEXANDER T,FALOUTSOS C,et al.SocialNetworks:Looking ahead [C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Las Vegas,USA:ACM,2008:1060-1060.
[2]STANN F,HEIDEMANN J.RMST:Reliable data transport in sensor networks[C]//Proceedings of the First IEEE International Workshop on Sensor Network Protocols and Applications.Anchorage,AK,USA:IEEE,2003:102-112.
[3]WOOD P T.Query languages for graph databases[J].ACM Sigmod,2012,41(1):50-60.
[4]CHEN X,LAI L,QIN L,et al.Structsim:Querying structuralnode similarity at billion scale[C]//Proceedings of the IEEE 36th International Conference on Data Engineering(ICDE).Dallas,TX,USA:IEEE,2020:1950-1953.
[5]CHEN Y J,CHEN Y B.An efficient algorithm for answeringgraph reachability queries[C]//Proceedings of the IEEE 24th International Conference on Data Engineering.Cancun,Mexico:IEEE,2008:893-902.
[6]CHENG J,HUANG S L,WU H H,et al.TF-Label:a topological-folding labeling scheme for reachability querying in a large graph[C]//Proceedings of the 2013 ACM SIGMOD Interna-tional Conference on Management of Data.New York,USA:ACM,2013:193-204.
[7]FANG Y,YANG Y,ZHANG W,et al.Effective and efficient community search over large heterogeneous information networks[J].PVLDB,2020,13(6):2093-2107.
[8]WANG K,LIN X,QIN L,et al.Efficient bitruss decomposition for large-scale bipartite graphs[C]//Proceedings of the IEEE 36th International Conference on Data Engineering(ICDE).Dallas,TX,USA:IEEE,2020:661-672.
[9]SCHAIK S J,MOOR O D.A memory efficient reachability data structure through bit vector compression[C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data.Athens,Greece:ACM,2011:913-924.
[10]IMANE H,YAHIAOUI S,BENDJOUDI A,et al.Reachability in Big Graphs:A Distributed Indexing and Querying Approach[J].Information Sciences,2021,573:541-561.
[11]WEI H,YU J X,LU C,et al.Reachability querying:An independent permutation labeling approach[J].VLDB,2018,27(1):1-26.
[12]YU J X,CHENG J F.Graph reachability queries:A survey[M]//Managing and Mining Graph Data.Boston,MA:Sprin-ger,2010:181-215.
[13]CHOUDHARY P.A survey on social network analysis forcounterterrorism[J].International Journal of Computer Applications,2015,112(9):24-29.
[14]PENG Y,ZHANG Y,LIN X,et al.Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond[J].Proceedings of the VLDB Endowment,2020,13(6):812-825.
[15]VALSTAR L D J,FLETCHER G H L,YOSHIDA Y.Land-mark indexing for evaluation of label-constrained reachability queries[C]//Proceedings of the 2017 ACM International Conference on Management of Data.Chicago,Illinois,USA:ACM,2017:345-358.
[16]XIAN T,CHEN Z Y,LI K,et al.Efficient computation of the transitive closure size[J].Cluster Computing,2019,22(3):6517-6527.
[17]YANO Y,AKIBA T,IWATA Y,et al.Fast and scalable rea-chability queries on graphs by pruned labeling with landmarks and paths[C]//Proceedings of the 22nd ACM International Conference on Information & Knowledge Management.San Francisco,CA,USA:ACM,2013:1601-1606.
[18]BOSTJAN B,FRANTISEK K,JAN K,et al.Minimum k-pathvertex cover[J].Discrete Applied Mathematics,2011,159(12):1189-1195.
[19]VELOSO R,JUNIOR W M,CERF L P,et al.Reachability queries in very large graphs:A fast refined online search approach[C]//Proceeding of the 17th International Conference on Extending Database Technology.Athens,Greece:EDBT,2014:511-522.
[20]CHENG J,SHANG Z,CHENG H,et al.K-reach:who is in your small world[J].Proceedings of the VLDB Endowment,2012,5(11):1292-1303.
[21]JIN R M,HONG H,WANG H X,et al.Computing label-constraint reachability in graph databases [C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of data.Indianapolis,Indiana,USA:ACM,2010:123-134.
[22]HASSAN M S,AREF W G,ALY A M.Graph indexing forshortest-path finding over dynamic sub-graphs[C]//Procee-dings of the 2016 International Conference on Management of Data.San Francisco,CA,USA:ACM,2016:1183-1197.
[23]SARISHT W,PRASAD A,RANU S,et al.Efficiently answe-ring regular simple path queries on large labeled network[C]//Proceedings of the 2019 International Conference on Management of Data.2019:1463-1480.
[24]CHEN Y J,SINGH G.Graph Indexing for Efficient Evaluation of Label-constrained Reachability Queries[J].ACM Transactions on Database Systems,2021,46(2):1-50.
[25]BEAMER S,ASANOVIC K,PATTERSON D.Direction-opti-mizing Breadth-first search[J].Scientific Programming,2013,21(3/4):137-148.
[26]STEIER D M,ANDERSON A P.Depth-First Search [M]//Algorithm Synthesis:A Comparative Study.US:Springer,1989.
[27]WANG X,LIN K,DU M,et al.Efficient k-Hop Reachability Queries Processing on Directed Graphs[D].Shanghai:Donghua University,2020.
[1] CHENG Fu-hao, XU Tai-hua, CHEN Jian-jun, SONG Jing-jing, YANG Xi-bei. Strongly Connected Components Mining Algorithm Based on k-step Search of Vertex Granule and Rough Set Theory [J]. Computer Science, 2022, 49(8): 97-107.
[2] GAO Lin, DUAN Guo-lin and YAO Tao. Research on Organizational Interoperability Modeling and Evaluation Based on Graph Theory [J]. Computer Science, 2020, 47(6A): 572-576.
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem [J]. Computer Science, 2018, 45(4): 83-88.
[4] LI Jin-ze, XU Xi-rong, PAN Zi-qi and LI Xiao-jie. Improved Adaptive Spectral Clustering NJW Algorithm [J]. Computer Science, 2017, 44(Z6): 424-427.
[5] WANG Zhen-chao, ZHAO Yun and XUE Wen-ling. Resource Allocation for D2D Communications Underlaying Cellular Networks Using Directed Weighted Bipartite [J]. Computer Science, 2017, 44(9): 120-124.
[6] WANG Zhen-chao, ZHAO Yun and XUE Wen-ling. Resource Allocation for D2D Communication Underlaid Cellular Networks Using Bipartite Hypergraph [J]. Computer Science, 2017, 44(8): 82-85.
[7] LI Li-ping, ZHAO Chuan-rong, KONG De-ren and WANG Fang. Research on Unsupervised Regional Remote Sensing Image Retrieval Algorithm Based on Graph Theory [J]. Computer Science, 2017, 44(7): 315-317.
[8] SHEN Hong and LI Xiao-guang. Research on Parallel Algorithm of Image Saliency Estimation [J]. Computer Science, 2017, 44(12): 266-273.
[9] LUO Wei-dong, WANG Jian-xin and FENG Qi-long. Survey of Cycle Packing Problem [J]. Computer Science, 2017, 44(1): 1-6.
[10] WU Cong-zhong and LI Jun. Image Threshold Segmentation Algorithm Based on SUSAN Edge Information [J]. Computer Science, 2015, 42(Z11): 119-122.
[11] YANG Ge-lan,JIN Hui-xia,MENG Ling-zhong and ZHU Xing-hui. Graph-based Semi-supervised Dimensionality Reduction Algorithm [J]. Computer Science, 2014, 41(4): 280-282.
[12] HUANG Zhi-guo and LI Na. Discernibility Function-based Algorithm for Finding All Maximal Cliques [J]. Computer Science, 2014, 41(4): 248-251.
[13] LIU Ya-kun,YU Shuang-yuan and LUO Si-wei. Threshold Image Segmentation Based on Min-max Cut Algorithm [J]. Computer Science, 2014, 41(1): 95-99.
[14] . Improved Algorithm of Sticker Model in Two Special Problem [J]. Computer Science, 2012, 39(Z11): 252-255.
[15] ZHANG Hong-lie,ZHANG Guo-yin,CONG Wan-suo,HU Hai-yan. One Management Strategy of Reconfigurable Resource Using Graph Theory [J]. Computer Science, 2010, 37(12): 270-274.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.