iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://unpaywall.org/10.1007/978-3-031-12597-3_18
GraphGuess: Approximate Graph Processing System with Adaptive Correction | SpringerLink
Skip to main content
Springer Nature Link
Log in

GraphGuess: Approximate Graph Processing System with Adaptive Correction

  • Conference paper
  • First Online:
Euro-Par 2022: Parallel Processing (Euro-Par 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13440))

Included in the following conference series:

  • 1349 Accesses

Abstract

Graph-based data structures have drawn great attention in recent years. The large and rapidly growing trend on developing graph processing systems focuses mostly on improving the performance by preprocessing the input graph and modifying its layout. These systems usually take several hours to days to complete processing a single graph on high-end machines, let alone the overhead of pre-processing which most of the time can be dominant. Yet for most graph applications the exact answer is not always crucial, and providing a rough estimate of the final result is adequate. Approximate computing is introduced to trade off accuracy of results for computation or energy savings that could not be achieved by conventional techniques alone. In this work, we design, implement and evaluate GraphGuess, inspired from the domain of approximate graph theory and extend it to a general, practical graph processing system. GraphGuess is essentially an approximate graph processing technique with adaptive correction, which can be implemented on top of any graph processing system. We build a vertex-centric processing system based on GraphGuess, where it allows the user to trade off accuracy for better performance. Our experimental studies show that using GraphGuess can significantly reduce the processing time for large scale graphs while maintaining high accuracy .

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 59.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 79.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Abraham, I., Durfee, D., Koutis, I., Krinninger, S., Peng, R.: On fully dynamic graph sparsifiers. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 335–344. IEEE (2016). https://doi.org/10.1109/FOCS.2016.44

  2. Ahn, J., Hong, S., Yoo, S., Mutlu, O., Choi, K.: A scalable processing-in-memory accelerator for parallel graph processing. ACM SIGARCH Comput. Archit. News 43(3), 105–117 (2016). https://doi.org/10.1145/2749469.2750386

    Article  Google Scholar 

  3. Bernstein, A., et al.: Fully-dynamic graph sparsifiers against an adaptive adversary. arXiv preprint arXiv:2004.08432 (2020)

  4. Besta, M., et al.: Slim graph: practical lossy graph compression for approximate graph processing, storage, and analytics. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1–25 (2019). https://doi.org/10.1145/3295500.3356182

  5. Capelli, L.A., Hu, Z., Zakian, T.A.: iPregel: a combiner-based in-memory shared memory vertex-centric framework. In: Proceedings of the 47th International Conference on Parallel Processing Companion, pp. 1–10 (2018). https://doi.org/10.1145/3229710.3229719

  6. Ching, A.: Giraph: production-grade graph processing infrastructure for trillion edge graphs. ATPESC, ser. ATPESC 14 (2014)

    Google Scholar 

  7. Gonzalez, J.E., Low, Y., Gu, H., Bickson, D., Guestrin, C.: Powergraph: distributed graph-parallel computation on natural graphs. In: OSDI, p. 2 (2012)

    Google Scholar 

  8. Heidarshenas, A., Yesil, S., Skarlatos, D., Misailovic, S., Morrison, A., Torrellas, J.: V-Combiner: speeding-up iterative graph processing on a shared-memory platform with vertex merging. In: Proceedings of the 34th ACM International Conference on Supercomputing, pp. 1–13 (2020). https://doi.org/10.1145/3392717.3392739

  9. Iyer, A.P., Liu, Z., Jin, X., Venkataraman, S., Braverman, V., Stoica, I.: \(\{\)ASAP\(\}\): Fast, approximate graph pattern mining at scale. In: 13th \(\{\)USENIX\(\}\) Symposium on Operating Systems Design and Implementation (\(\{\)OSDI\(\}\) 18), pp. 745–761 (2018)

    Google Scholar 

  10. Iyer, A.P., et al.: Bridging the gap: towards approximate graph analytics. In: Proceedings of the 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA), p. 10. ACM (2018). https://doi.org/10.1145/3210259.3210269

  11. Jevdjic, D., Strauss, K., Ceze, L., Malvar, H.S.: Approximate storage of compressed and encrypted videos. ACM SIGOPS Operat. Syst. Rev. 51(2), 361–373 (2017). https://doi.org/10.1145/3037697.3037718

    Article  Google Scholar 

  12. Kulkarni, M., Pingali, K., Walter, B., Ramanarayanan, G., Bala, K., Chew, L.P.: Optimistic parallelism requires abstractions. ACM SIGPLAN Notices 42(6), 211–222 (2007). https://doi.org/10.1145/1250734.1250759

    Article  Google Scholar 

  13. Kyrola, A., Blelloch, G.E., Guestrin, C.: GraphChi: large-scale graph computation on just a pc. In: 11th \(\{\)USENIX\(\}\) Symposium on Operating Systems Design and Implementation (\(\{\)OSDI\(\}\) 12). USENIX (2012)

    Google Scholar 

  14. Low, Y., Gonzalez, J.E., Kyrola, A., Bickson, D., Guestrin, C.E., Hellerstein, J.: GraphLab: a new framework for parallel machine learning. arXiv preprint arXiv:1408.2041 (2014)

  15. 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). https://doi.org/10.1145/1807167.1807184

  16. McSherry, F., Isard, M., Murray, D.G.: Scalability! but at what cost? In: HotOS, vol. 15, p. 14. Citeseer (2015)

    Google Scholar 

  17. Mitliagkas, I., Borokhovich, M., Dimakis, A.G., Caramanis, C.: Frogwild!-fast pagerank approximations on graph engines. arXiv preprint arXiv:1502.04281 (2015)

  18. Mukkara, A., Beckmann, N., Abeydeera, M., Ma, X., Sanchez, D.: Exploiting locality in graph analytics through hardware-accelerated traversal scheduling. In: 2018 51st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pp. 1–14. IEEE (2018). https://doi.org/10.1109/MICRO.2018.00010

  19. Nai, L., Xia, Y., Tanase, I.G., Kim, H., Lin, C.Y.: GraphBIG: understanding graph computing in the context of industrial solutions. In: 2015 SC-International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1–12. IEEE (2015). https://doi.org/10.1145/2807591.2807626

  20. Nguyen, D., Lenharth, A., Pingali, K.: A lightweight infrastructure for graph analytics. In: Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, pp. 456–471. ACM (2013). https://doi.org/10.1145/2517349.2522739

  21. Qiao, M., Cheng, H., Chang, L., Yu, J.X.: Approximate shortest distance computing: a query-dependent local landmark scheme. IEEE Trans. Knowl. Data Eng. 26(1), 55–68 (2012). https://doi.org/10.1109/ICDE.2012.53

    Article  Google Scholar 

  22. Roy, A., Mihailovic, I., Zwaenepoel, W.: X-stream: edge-centric graph processing using streaming partitions. In: Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, pp. 472–488. ACM (2013). https://doi.org/10.1145/2517349.2522740

  23. Sarlós, T., Benczúr, A.A., Csalogány, K., Fogaras, D., Rácz, B.: To randomize or not to randomize: space optimal summaries for hyperlink analysis. In: Proceedings of the 15th International Conference on World Wide Web, pp. 297–306 (2006)

    Google Scholar 

  24. Shang, Z., Yu, J.X.: Auto-approximation of graph computing. In: Proceedings of the VLDB Endowment 7(14), 1833–1844 (2014). https://doi.org/10.14778/2733085.2733090

  25. Shin, K., Ghoting, A., Kim, M., Raghavan, H.: SWeG: lossless and lossy summarization of web-scale graphs. In: The World Wide Web Conference, pp. 1679–1690 (2019). https://doi.org/10.1145/3308558.3313402

  26. Spielman, D.A., Srivastava, N.: Graph sparsification by effective resistances. SIAM J. Comput. 40(6), 1913–1926 (2011). https://doi.org/10.1137/080734029

    Article  MathSciNet  MATH  Google Scholar 

  27. Spielman, D.A., Teng, S.H.: Spectral sparsification of graphs. SIAM J. Comput. 40(4), 981–1025 (2011). https://doi.org/10.1137/08074489X

    Article  MathSciNet  MATH  Google Scholar 

  28. Sundaram, N., et al.: GraphMat: high performance graph analytics made productive. In: Proceedings of the VLDB Endowment, vol. 8(11), 1214–1225 (2015). https://doi.org/10.14778/2809974.2809983

  29. Yuhanna, N., Evelson, B., Hopkins, B., Jedinak, E.: Techradar: enterprise dbms, q1 2014 (2013). https://www.forrester.com/report/TechRadar+Enterprise+DBMS+Q1+2014/-/E-RES106801

Download references

Acknowledgements

This work was supported in part by CRISP, one of six centers in JUMP, a Semiconductor Research Corporation (SRC) program sponsored by DARPA and NSF grants 1909004, 1714389, 1912495, 1629915, 1629129, 1763681.

Author information

Authors and Affiliations

  1. Pennsylvania State University, State College, USA

    Morteza Ramezani, Mahmut T. Kandemir & Anand Sivasubramaniam

Authors
  1. Morteza Ramezani
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mahmut T. Kandemir
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Anand Sivasubramaniam
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Morteza Ramezani .

Editor information

Editors and Affiliations

  1. University of Glasgow, Glasgow, UK

    José Cano

  2. University of Glasgow, Glasgow, UK

    Phil Trinder

Rights and permissions

Reprints and permissions

Copyright information

© 2022 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Ramezani, M., Kandemir, M.T., Sivasubramaniam, A. (2022). GraphGuess: Approximate Graph Processing System with Adaptive Correction. In: Cano, J., Trinder, P. (eds) Euro-Par 2022: Parallel Processing. Euro-Par 2022. Lecture Notes in Computer Science, vol 13440. Springer, Cham. https://doi.org/10.1007/978-3-031-12597-3_18

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-12597-3_18

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-12596-6

  • Online ISBN: 978-3-031-12597-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation