Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
PPS: A Low-Latency and Low-Complexity Switching Architecture Based on Packet Prefetch and Arbitration Prediction Kapitel lesen Erstes Kapitel lesen

2020 | OriginalPaper | Buchkapitel

DETER: Streaming Graph Partitioning via Combined Degree and Cluster Information

verfasst von : Cong Hu, Jiang Zhong, Qi Li, Qing Li

Erschienen in: Algorithms and Architectures for Parallel Processing

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Efficient graph partitioning plays an important role in distributed graph processing systems with the rapid growth of the scale of graph data. The quality of partitioning affects the performance of systems greatly. However, most existing vertex-cut graph partitioning algorithms only focused on degree information and ignored the cluster information of a coming edge when assigning edges. It is beneficial to assign an edge to a partition with more neighbors because keeping a dense subgraph in one partition would reduce the communication cost. In this paper, we propose DETER, an efficient vertex-cut streaming graph partitioning algorithm that takes both degree and cluster information into account when assigning an edge to one partition. Our evaluations suggest that DETER algorithm owns the ability to efficiently partition large graphs and reduce communication cost significantly compared to state-of-the-art graph partitioning algorithms.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel FANG: Fast and Efficient Successor-State Generation for Heuristic Optimization on GPUs
Nächstes Kapitel Which Node Properties Identify the Propagation Source in Networks?
Literatur
1.
2.
3.
Donnelly, G.: Super-useful Facebook statistics for (75) (2018)
4.
Fineschi, S., et al.: Metis: a novel coronagraph design for the solar orbiter mission. Proc. SPIE - Int. Soc. Opt. Eng. 8443(8), 457–469 (2012)
5.
Gonzalez, J.E., Low, Y., Gu, H., Bickson, D., Guestrin, C.: Powergraph: distributed graph-parallel computation on natural graphs. In: USENIX Conference on Operating Systems Design & Implementation (2012)
6.
Hu, K., Zeng, G., Jiang, H., Wang, W.: Partitioning big graph with respect to arbitrary proportions in a streaming manner. Future Gener. Comput. Syst. 80, 1–11 (2018)CrossRef
7.
Jain, N., Liao, G., Willke, T.L.: Graphbuilder: scalable graph ETL framework. In: International Workshop on Graph Data Management Experiences & Systems (2013)
8.
Kalnis, P., Awara, K., Jamjoom, H., Khayyat, Z.: Mizan: optimizing graph mining in large parallel systems. Technical report, King Abdullah University of Science and Technology (2012)
9.
Leskovec, J., Kleinberg, J., Faloutsos, C.: Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, pp. 177–187. ACM (2005)
10.
Low, Y., Bickson, D., Gonzalez, J., Guestrin, C., Kyrola, A., Hellerstein, J.M.: Distributed graphlab: a framework for machine learning and data mining in the cloud. Proc. VLDB Endow. 5(8), 716–727 (2012)CrossRef
11.
Malewicz, G., et al.: Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, pp. 135–146. ACM (2010)
12.
Martella, C., Logothetis, D., Loukas, A., Siganos, G.: Spinner: scalable graph partitioning in the cloud. In: IEEE International Conference on Data Engineering (2017)
13.
Mayer, C., Tariq, M.A., Mayer, R., Rothermel, K.: Graph: traffic-aware graph processing. IEEE Trans. Parallel Distrib. Syst. 29(6), 1289–1302 (2018)CrossRef
14.
Mofrad, M.H., Melhem, R., Hammoud, M.: Revolver: vertex-centric graph partitioning using reinforcement learning. In: 2018 IEEE 11th International Conference on Cloud Computing (CLOUD), pp. 818–821. IEEE (2018)
15.
Nishimura, J., Ugander, J.: Restreaming graph partitioning: simple versatile algorithms for advanced balancing. In: ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (2013)
16.
Page, L., Brin, S., Motwani, R., Winograd, T.: The pagerank citation ranking: bringing order to the web. Technical report, Stanford InfoLab (1999)
17.
Petroni, F., Querzoni, L., Daudjee, K., Kamali, S., Iacoboni, G.: HDRF: stream-based partitioning for power-law graphs. In: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pp. 243–252. ACM (2015)
18.
Prabhakaran, V., Wu, M., Weng, X., McSherry, F., Zhou, L., Haradasan, M.: Managing large graphs on multi-cores with graph awareness. In: Presented as Part of the 2012 USENIX Annual Technical Conference (USENIX ATC 2012), pp. 41–52 (2012)
19.
Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (2015). http://​networkrepositor​y.​com
20.
Stanton, I., Kliot, G.: Streaming graph partitioning for large distributed graphs. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1222–1230. ACM (2012)
21.
Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. J. ACM (JACM) 46(3), 362–394 (1999)MathSciNetCrossRef
22.
Tsourakakis, C.: Streaming graph partitioning in the planted partition model. In: Proceedings of the 2015 ACM on Conference on Online Social Networks, pp. 27–35. ACM (2015)
23.
Tsourakakis, C., Gkantsidis, C., Radunovic, B., Vojnovic, M.: Fennel: streaming graph partitioning for massive scale graphs. In: Proceedings of the 7th ACM International Conference on Web Search and Data Mining, pp. 333–342. ACM (2014)
24.
Xie, C., Yan, L., Li, W.J., Zhang, Z.: Distributed power-law graph computing: theoretical and empirical analysis. In: International Conference on Neural Information Processing Systems (2014)
25.
Xin, R.S., Gonzalez, J.E., Franklin, M.J., Stoica, I.: GraphX: a resilient distributed graph system on spark. In: First International Workshop on Graph Data Management Experiences and Systems, p. 2. ACM (2013)
26.
Yang, J., Leskovec, J.: Defining and evaluating network communities based on ground-truth. In: IEEE International Conference on Data Mining (2012)
27.
Yin, H., Benson, A.R., Leskovec, J., Gleich, D.F.: Local higher-order graph clustering. In: ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (2017)
28.
Zheng, A., Labrinidis, A., Chrysanthis, P.K., Lange, J.: Argo: architecture-aware graph partitioning. In: IEEE International Conference on Big Data (2017)
Metadaten
Titel
DETER: Streaming Graph Partitioning via Combined Degree and Cluster Information
verfasst von
Cong Hu
Jiang Zhong
Qi Li
Qing Li
Copyright-Jahr
2020
Buch
Algorithms and Architectures for Parallel Processing

Print ISBN: 978-3-030-38990-1

Electronic ISBN: 978-3-030-38991-8

Copyright-Jahr: 2020

DOI
https://doi.org/10.1007/978-3-030-38991-8_16