Optimizational Methods for Index Construction on Big Graphs

详细信息    查看全文

• 关键词：Big graphs ; Distance queries ; Index construction ; Incremental updates ; Cliques
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：10065
• 期：1
• 页码：292-305
• 全文大小：343 KB
• 参考文献：1.Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: Hierarchical hub labelings for shortest paths. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 24–35. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-33090-2_​4 CrossRef
  2.Akiba, T., Iwata, Y., Yoshida, Y.: Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pp. 349–360. ACM (2013)
  3.Akiba, T., Iwata, Y., Yoshida, Y.: Dynamic and historical shortest-path distance queries on large evolving networks by pruned landmark labeling. In: Proceedings of the 23rd International Conference on World Wide Web, pp. 237–248. ACM (2014)
  4.Chen, W., Sommer, C., Teng, S.H., Wang, Y.: A compact routing scheme and approximate distance oracle for power-law graphs. ACM Trans. Algorithms 9(1), 615–630 (2012)MathSciNet CrossRef MATH
  5.Christoforaki, M., Suel, T.: Estimating pairwise distances in large graphs. In: Proceedings of 2014 IEEE International Conference on Big Data, pp. 335–344. IEEE (2014)
  6.Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1338–1355. SIAM (2003)
  7.Dave, V.S., Hasan, M.A.: TopCom: index for shortest distance query in directed graph. In: Chen, Q., Hameurlain, A., Toumani, F., Wagner, R., Decker, H. (eds.) DEXA 2015. LNCS, vol. 9261, pp. 471–480. Springer, Heidelberg (2015). doi:10.​1007/​978-3-319-22849-5_​32 CrossRef
  8.Fu, A.W.C., Wu, H., Cheng, J., Wong, R.C.W.: IS-LABEL: an independent-set based labeling scheme for point-to-point distance querying. PVLDB 6(6), 457–468 (2013)
  9.Geisberger, R., Sanders, P., Schultes, D., Delling, D.: Contraction hierarchies: faster and simpler hierarchical routing in road networks. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 319–333. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-68552-4_​24 CrossRef
  10.Greco, S., Molinaro, C., Pulice, C.: Efficient maintenance of all-pairs shortest distances. In: Proceedings of the 28th International Conference on Scientific and Statistical Database Management, pp. 95–106. ACM (2016)
  11.Jiang, M., Fu, A.W.C., Wong, R.C.W.: Exact top-k nearest keyword search in large networks. In: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pp. 393–404. ACM (2015)
  12.Jiang, M., Fu, A.W.C., Wong, R.C.W., Xu, Y.: Hop doubling label indexing for point-to-point distance querying on scale-free networks. PVLDB 7(12), 1203–1214 (2014)
  13.Jin, R., Ruan, N., Xiang, Y., Lee, V.: A highway-centric labeling approach for answering distance queries on large sparse graphs. In: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, pp. 445–456. ACM (2012)
  14.Lin, Y., Chen, X., Lui, J.: I/O efficient algorithms for exact distance queries on disk-resident dynamic graphs. In: Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 440–447. ACM (2015)
  15.Potamias, M., Bonchi, F., Castillo, C., Gionis, A.: Fast shortest path distance estimation in large networks. In: Proceedings of the 18th ACM Conference on Information and Knowledge Management, pp. 867–876. ACM (2009)
  16.Qiao, M., Cheng, H., Chang, L., Yu, J.X.: Approximate shortest distance computing: a query-dependent local landmark scheme. TKDE 26(1), 55–68 (2014)
  17.Zhu, A.D., Ma, H., Xiao, X., Luo, S., Tang, Y., Zhou, S.: Shortest path and distance queries on road networks: towards bridging theory and practice. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pp. 857–868. ACM (2013)
  
• 作者单位：Peiyang Li (16)
  Xia Xie (16)
  Hai Jin (16)
  Hanhua Chen (16)
  Xijiang Ke (16)
  
  16. Services Computing Technology and System Lab, Big Data Technology and System Lab, Cluster and Grid Computing Lab, School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, 430074, China
  
• 丛书名：Advances in Services Computing
• ISBN：978-3-319-49178-3
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：10065

文摘

Many indexes have been designed to solve the problem of the point-to-point distance query on big graphs. In this paper, we design an incremental updating method for the index construction on dynamic graphs. The results show that the method is much time-saving compared with the way of index reconstruction. We also propose an exact method for distance labeling focused on undirected unweighted dense graphs. A kind of tight substructure named clique commonly exists in some dense graphs, such as social networks and communication networks. We take advantage of the cliques to compress the index. The experiments show that the technique can save index space and bring about comparable query time.