Abstract
There is a growing need to perform a diverse set of real-time analytics (batch and stream analytics) on evolving graphs to deliver the values of big data to users. The key requirement from such applications is to have a data store to support their diverse data access efficiently, while concurrently ingesting fine-grained updates at a high velocity. Unfortunately, current graph systems, either graph databases or analytics engines, are not designed to achieve high performance for both operations; rather, they excel in one area that keeps a private data store in a specialized way to favor their operations only. To address this challenge, we have designed and developed GraphOne, a graph data store that abstracts the graph data store away from the specialized systems to solve the fundamental research problems associated with the data store design. It combines two complementary graph storage formats (edge list and adjacency list) and uses dual versioning to decouple graph computations from updates. Importantly, it presents a new data abstraction, GraphView, to enable data access at two different granularities of data ingestions (called data visibility) for concurrent execution of diverse classes of real-time graph analytics with only a small data duplication. Experimental results show that GraphOne is able to deliver 11.40× and 5.36× average speedup in ingestion rate against LLAMA and Stinger, the two state-of-the-art dynamic graph systems, respectively. Further, they achieve an average speedup of 8.75× and 4.14× against LLAMA and 12.80× and 3.18× against Stinger for BFS and PageRank analytics (batch version), respectively. GraphOne also gains over 2,000× speedup against Kickstarter, a state-of-the-art stream analytics engine in ingesting the streaming edges and performing streaming BFS when treating first half as a base snapshot and rest as streaming edge in a synthetic graph. GraphOne also achieves an ingestion rate of two to three orders of magnitude higher than graph databases. Finally, we demonstrate that it is possible to run concurrent stream analytics from the same data store.
- [n.d.]. Friendster Network Dataset—KONECT. Retrieved from http://konect.uni-koblenz.de/networks/friendster.Google Scholar
- [n.d.]. Titan Graph Database. Retrieved from https://github.com/thinkaurelius/titan.Google Scholar
- [n.d.]. Twitter (MPI) Network Dataset—KONECT. Retrieved from http://konect.uni-koblenz.de/networks/twitter_mpi. http://konect.uni-koblenz.de/networks/twitter_mpi.Google Scholar
- [n.d.]. Web Graphs. Retrieved from http://webdatacommons.org/hyperlinkgraph/2012-08/download.html. http://webdatacommons.org/hyperlinkgraph/2012-08/download.html.Google Scholar
- Daniel J. Abadi, Yanif Ahmad, Magdalena Balazinska, Ugur Cetintemel, Mitch Cherniack, Jeong-Hyon Hwang, Wolfgang Lindner, Anurag Maskey, Alex Rasin, Esther Ryvkina, et al. 2005. The design of the borealis stream processing engine. In Proceedings of the Conference on Innovative Data Systems Research (CIDR’05), Vol. 5. 277--289.Google Scholar
- Daniel J. Abadi, Don Carney, Ugur Cetintemel, Mitch Cherniack, Christian Convey, Sangdon Lee, Michael Stonebraker, Nesime Tatbul, and Stan Zdonik. 2003. Aurora: A new model and architecture for data stream management. VLDB J. 12, 2 (2003), 12039.Google ScholarDigital Library
- Zhiyuan Ai, Mingxing Zhang, Yongwei Wu, Xuehai Qian, Kang Chen, and Weimin Zheng. 2017. Squeezing out all the value of loaded data: An out-of-core graph processing system with reduced disk I/O. In Proceedings of the 2017 USENIX Annual Technical Conference (USENIX ATC’17). 125--137.Google Scholar
- Leman Akoglu, Hanghang Tong, and Danai Koutra. 2015. Graph based anomaly detection and description: A survey. Data Min. Knowl. Discov. 29, 3 (1 May 2015), 626--688.Google ScholarDigital Library
- Reka Albert, Hawoong Jeong, and Albert-Laszlo Barabási. 1999. Internet: Diameter of the world-wide web. Nature 401, 6749 (9 Sept. 1999), 130--131. DOI:https://doi.org/10.1038/43601Google Scholar
- Darko Anicic, Paul Fodor, Sebastian Rudolph, and Nenad Stojanovic. 2011. EP-SPARQL: A unified language for event processing and stream reasoning. In Proceedings of the 20th International Conference on World Wide Web. ACM, 635--644.Google ScholarDigital Library
- S. Beamer, K. Asanovic, and D. Patterson. 2012. Direction-optimizing breadth-first search. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC’12).Google Scholar
- Bibek Bhattarai, Hang Liu, and H. Howie Huang. 2019. CECI: Compact embedding cluster index for scalable subgraph matching. In Proceedings of the 2019 International Conference on Management of Data (SIGMOD’19).Google Scholar
- Ulrik Brandes. 2001. A faster algorithm for betweenness centrality*. J. Math. Sociol. 25, 2 (2001), 163--177.Google ScholarCross Ref
- Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry C. Li, et al. 2013. TAO: Facebook’s distributed data store for the social graph. In Proceedings of the USENIX Annual Technical Conference. 49--60.Google ScholarDigital Library
- Deepayan Chakrabarti, Yiping Zhan, and Christos Faloutsos. 2004. R-MAT: A recursive model for graph mining. In Proceedings of the SIAM International Conference on Data Mining (SDM’04).Google ScholarCross Ref
- Rong Chen, Jiaxin Shi, Yanzhe Chen, and Haibo Chen. 2015. PowerLyra: Differentiated graph computation and partitioning on skewed graphs. In Proceedings of the 10th European Conference on Computer Systems. DOI:https://doi.org/10.1145/2741948.2741970Google ScholarDigital Library
- Raymond Cheng, Ji Hong, Aapo Kyrola, Youshan Miao, Xuetian Weng, Ming Wu, Fan Yang, Lidong Zhou, Feng Zhao, and Enhong Chen. 2012. Kineograph: Taking the pulse of a fast-changing and connected world. In Proceedings of the 7th ACM European Conference on Computer Systems.Google ScholarDigital Library
- Sutanay Choudhury, Lawrence B. Holder, George Chin, Khushbu Agarwal, and John Feo. 2015. A selectivity based approach to continuous pattern detection in streaming graphs. In Proceedings of the 18th International Conference on Extending Database Technology (EDBT’15).Google Scholar
- James Cipar, Greg Ganger, Kimberly Keeton, Charles B. Morrey III, Craig A. N. Soules, and Alistair Veitch. 2012. LazyBase: Trading freshness for performance in a scalable database. In Proceedings of the 7th ACM European Conference on Computer Systems. ACM, 169--182.Google ScholarDigital Library
- Dong Dai, Wei Zhang, and Yong Chen. 2017. IOGP: An incremental online graph partitioning algorithm for distributed graph databases. In Proceedings of the 26th International Symposium on High-Performance Parallel and Distributed Computing. ACM, 219--230.Google ScholarDigital Library
- Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. 2019. Low-latency graph streaming using compressed purely-functional trees. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, 918--934.Google ScholarDigital Library
- David Easley and Jon Kleinberg. 2010. Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press.Google ScholarDigital Library
- David Ediger, Robert McColl, Jason Riedy, and David A. Bader. 2012. Stinger: High performance data structure for streaming graphs. In Proceedings of the 2012 IEEE Conference on High Performance Extreme Computing (HPEC’12). IEEE, 1--5.Google Scholar
- Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. 1999. On power-law relationships of the internet topology. In ACM SIGCOMM Computer Communication Review, Vol. 29. ACM, 251--262.Google ScholarDigital Library
- FlockDB. 2010. Retrieved from https://blog.twitter.com/engineering/en_us/a/2010/introducing-flockdb.html.Google Scholar
- Graph Compute with Neo4j. 2016. Retrieved from https://neo4j.com/blog/graph-compute-neo4j-algorithms-spark-extensions/.Google Scholar
- Graph500. [n.d.]. Retrieved from http://www.graph500.org/.Google Scholar
- Wentao Han, Youshan Miao, Kaiwei Li, Ming Wu, Fan Yang, Lidong Zhou, Vijayan Prabhakaran, Wenguang Chen, and Enhong Chen. 2014. Chronos: A graph engine for temporal graph analysis. In Proceedings of the European Conference on Computer Systems (EuroSys’14).Google Scholar
- Wook-Shin Han, Sangyeon Lee, Kyungyeol Park, Jeong-Hoon Lee, Min-Soo Kim, Jinha Kim, and Hwanjo Yu. 2013. TurboGraph: A fast parallel graph engine handling billion-scale graphs in a single PC. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Google ScholarDigital Library
- Sungpack Hong, Hassan Chafi, Edic Sedlar, and Kunle Olukotun. 2012. Green-Marl: A DSL for easy and efficient graph analysis. In ACM SIGARCH Computer Architecture News.Google Scholar
- Yang Hu, Pradeep Kumar, Guy Swope, and H. Howie Huang. 2017. Trix: Triangle counting at extreme scale. In Proceedings of the 2017 IEEE High Performance Extreme Computing Conference (HPEC’17). IEEE, 1--7.Google Scholar
- Yang Hu, Hang Liu, and H. Howie Huang. 2018. TriCore: Parallel triangle counting on GPUs. In Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis. IEEE Press, 14.Google Scholar
- Bernardo A. Huberman and Lada A. Adamic. 1999. Internet: Growth dynamics of the world-wide web. Nature 401, 6749 (1999), 131--132. DOI:https://doi.org/10.1038/43604Google Scholar
- Anand Padmanabha Iyer, Li Erran Li, Tathagata Das, and Ion Stoica. 2016. Time-evolving graph processing at scale. In Proceedings of the 4th International Workshop on Graph Data Management Experiences and Systems. ACM, 5.Google ScholarDigital Library
- Hawoong Jeong, Bálint Tombor, Réka Albert, Zoltan N. Oltvai, and A.-L. Barabási. 2000. The large-scale organization of metabolic networks. Nature 407, 6804 (2000), 651--654.Google ScholarCross Ref
- Yuede Ji, Hang Liu, and H. Howie Huang. 2018. iSpan: Parallel identification of strongly connected components with spanning trees. In Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis. IEEE Press, 58.Google Scholar
- Xiaoen Ju, Dan Williams, Hani Jamjoom, and Kang G. Shin. 2016. Version traveler: Fast and memory-efficient version switching in graph processing systems. In Proceedings of the 2016 USENIX Annual Technical Conference (USENIX ATC’16). USENIX Association, 523--536.Google Scholar
- U. Kang, Hanghang Tong, Jimeng Sun, Ching-Yung Lin, and Christos Faloutsos. 2011. GBASE: A scalable and general graph management system. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Google ScholarDigital Library
- Alexander D. Kent. 2015. Comprehensive, Multi-Source Cyber-Security Events. Los Alamos National Laboratory. DOI:https://doi.org/10.17021/1179829Google Scholar
- Alexander D. Kent, Lorie M. Liebrock, and Joshua C. Neil. 2015. Authentication graphs: Analyzing user behavior within an enterprise network. Comput. Secur. 48 (2015), 150--166. https://doi.org/10.1016/j.cose.2014.09.001Google ScholarDigital Library
- Udayan Khurana and Amol Deshpande. 2013. Efficient snapshot retrieval over historical graph data. In Proceedings of the 2013 IEEE 29th International Conference on Data Engineering (ICDE’13). IEEE, 997--1008.Google ScholarDigital Library
- Kangnyeon Kim, Tianzheng Wang, Ryan Johnson, and Ippokratis Pandis. 2016. Ermia: Fast memory-optimized database system for heterogeneous workloads. In Proceedings of the 2016 International Conference on Management of Data. ACM, 1675--1687.Google ScholarDigital Library
- David Knoke and Song Yang. 2008. Social Network Analysis. Vol. 154. Sage.Google Scholar
- Jay Kreps, Neha Narkhede, Jun Rao, et al. 2011. Kafka: A distributed messaging system for log processing. In Proceedings of the International Workshop on Networking Meets Databases (NetDB’11). 1--7.Google Scholar
- Pradeep Kumar and H. Howie Huang. 2016. G-Store: High-performance graph store for trillion-edge processing. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC’16).Google Scholar
- Pradeep Kumar and H. Howie Huang. 2017. Falcon: Scaling IO performance in multi-SSD volumes. In Proceedings of the 2017 USENIX Annual Technical Conference (USENIX ATC’17). USENIX Association, 41--53.Google Scholar
- Pradeep Kumar and H. Howie Huang. 2017. SafeNVM: A non-volatile memory store with thread-level page protection. In Proceedings of the IEEE International Congress on Big Data (BigData Congress’17). IEEE, 65--72.Google Scholar
- Pradeep Kumar and H. Howie Huang. 2019. GraphOne: A data store for real-time analytics on evolving graphs. In Proceedings of the 17th USENIX Conference on File and Storage Technologies (FAST’19).Google Scholar
- Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. 2010. What is twitter, a social network or a news media? In Proceedings of the Conference of the World Wide Web (WWW’10).Google ScholarDigital Library
- A. Kyrola, G. Blelloch, and C. Guestrin. 2012. Graphchi: Large-scale graph computation on just a PC. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI’12).Google Scholar
- Kartik Lakhotia, Rajgopal Kannan, Sourav Pati, and Viktor Prasanna. 2019. GPOP: A cache and memory-efficient framework for graph processing over partitions. In Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming (PPoPP’19). ACM, New York, NY, 393--394. DOI:https://doi.org/10.1145/3293883.3299108Google ScholarDigital Library
- Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2005. Graphs over time: Densification laws, shrinking diameters and possible explanations. In Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. ACM, 177--187.Google ScholarDigital Library
- Heng Lin, Xiaowei Zhu, Bowen Yu, Xiongchao Tang, Wei Xue, Wenguang Chen, Lufei Zhang, Torsten Hoefler, Xiaosong Ma, Xin Liu, et al. 2018. ShenTu: Processing multi-trillion edge graphs on millions of cores in seconds. In Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis. IEEE Press, 56.Google ScholarDigital Library
- Hang Liu and H. Howie Huang. 2015. Enterprise: Breadth-first graph traversal on GPUs. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC’15).Google Scholar
- Hang Liu and H. Howie Huang. 2017. Graphene: Fine-grained IO management for graph computing. In Proceedings of the 15th USENIX Conference on File and Storage Technologies (FAST’17).Google ScholarDigital Library
- Hang Liu, H. Howie Huang, and Yang Hu. 2016. iBFS: Concurrent breadth-first search on GPUs. In Proceedings of the SIGMOD International Conference on Management of Data.Google ScholarDigital Library
- Yucheng Low, Danny Bickson, Joseph Gonzalez, Carlos Guestrin, Aapo Kyrola, and Joseph M. Hellerstein. 2012. Distributed graphlab: A framework for machine learning and data mining in the cloud. Proc. VLDB Endow. 5, 8 (2012), 716--727.Google ScholarDigital Library
- Steffen Maass, Changwoo Min, Sanidhya Kashyap, Woonhak Kang, Mohan Kumar, and Taesoo Kim. 2017. Mosaic: Processing a trillion-edge graph on a single machine. In Proceedings of the 12th European Conference on Computer Systems (EuroSys’17).Google ScholarDigital Library
- Peter Macko, Virendra J. Marathe, Daniel W. Margo, and Margo I. Seltzer. 2015. LLAMA: Efficient graph analytics using large multiversioned arrays. In Proceedings of the 2015 IEEE 31st International Conference on Data Engineering (ICDE’15). IEEE, 363--374.Google Scholar
- Jasmina Malicevic, Baptiste Lepers, and Willy Zwaenepoel. 2017. Everything you always wanted to know about multicore graph processing but were afraid to ask. In Proceedings of the 2017 USENIX Annual Technical Conference (USENIX ATC’17). USENIX Association, Santa Clara, CA, 631--643. https://www.usenix.org/conference/atc17/technical-sessions/presentation/malicevic.Google Scholar
- Mugilan Mariappan and Keval Vora. 2019. GraphBolt: Dependency-driven synchronous processing of streaming graphs. In Proceedings of the 14th European Conference on Computer Systems (EuroSys’19). ACM, 25.Google ScholarDigital Library
- Robert Campbell McColl, David Ediger, Jason Poovey, Dan Campbell, and David A. Bader. 2014. A performance evaluation of open source graph databases. In Proceedings of the 1st Workshop on Parallel Programming for Analytics Applications (PPAA’14). ACM, New York, NY, 11--18. DOI:https://doi.org/10.1145/2567634.2567638Google Scholar
- Frank McSherry, Michael Isard, and Derek G. Murray. 2015. Scalability! but at what COST?. In Proceedings of the 15th Workshop on Hot Topics in Operating Systems (HotOS XV).Google Scholar
- Frank McSherry, Derek Gordon Murray, Rebecca Isaacs, and Michael Isard. 2018. Differential dataflow. In Proceedings of the Conference on Innovative Data Systems Research (CIDR’18).Google Scholar
- Derek G. Murray, Frank McSherry, Rebecca Isaacs, Michael Isard, Paul Barham, and Martín Abadi. 2013. Naiad: A timely dataflow system. In Proceedings of the 24th ACM Symposium on Operating Systems Principles (SOSP’13).Google ScholarDigital Library
- Neo4j Inc. 2016. Retrieved from https://neo4j.com/.Google Scholar
- Donald Nguyen, Andrew Lenharth, and Keshav Pingali. 2013. A lightweight infrastructure for graph analytics. In Proceedings of the ACM Symposium on Operating Systems Principles (SOSP’13).Google ScholarDigital Library
- Orient Database. 2016. Retrieved from https://orientdb.com/.Google Scholar
- Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. The pagerank citation ranking: Bringing order to the web. Stanford InfoLab.Google Scholar
- James Reinders. 2007. Intel Threading Building Blocks (1 ed.). O’Reilly 8 Associates, Inc., Sebastopol, CA.Google Scholar
- Chenghui Ren, Eric Lo, Ben Kao, Xinjie Zhu, and Reynold Cheng. 2011. On querying historical evolving graph sequences. Proc. VLDB Endow. 4, 11 (2011), 726--737.Google ScholarDigital Library
- Ian Robinson, Jim Webber, and Emil Eifrem. 2013. Graph Databases. O’Reilly Media.Google Scholar
- Daniel M. Romero, Brendan Meeder, and Jon Kleinberg. 2011. Differences in the mechanics of information diffusion across topics: idioms, political hashtags, and complex contagion on twitter. In Proceedings of the 20th International Conference on World Wide Web. ACM, 695--704.Google ScholarDigital Library
- A. Roy, L. Bindschaedler, J. Malicevic, and W. Zwaenepoel. 2015. Chaos: Scale-out graph processing from secondary storage. In Proceedings of the ACM Symposium on Operating Systems Principles (SOSP’15). ACM.Google Scholar
- A. Roy, I. Mihailovic, and W. Zwaenepoel. 2013. X-stream: Edge-centric graph processing using streaming partitions. In Proceedings of the ACM Symposium on Operating Systems Principles (SOSP’15). ACM.Google Scholar
- Scott Sallinen, Keita Iwabuchi, Suraj Poudel, Maya Gokhale, Matei Ripeanu, and Roger Pearce. 2016. Graph colouring as a challenge problem for dynamic graph processing on distributed systems. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE Press, 30.Google ScholarDigital Library
- Jiwon Seo, Jongsoo Park, Jaeho Shin, and Monica S Lam. 2013. Distributed socialite: A datalog-based language for large-scale graph analysis. Proc. VLDB Endow. 6, 14 (2013), 1906--1917.Google ScholarDigital Library
- Martin Sevenich, Sungpack Hong, Oskar van Rest, Zhe Wu, Jayanta Banerjee, and Hassan Chafi. 2016. Using domain-specific languages for analytic graph databases. Proc. VLDB Endow. 9, 13 (Sep. 2016), 1257--1268. DOI:https://doi.org/10.14778/3007263.3007265Google ScholarDigital Library
- Bin Shao, Haixun Wang, and Yatao Li. 2013. Trinity: A distributed graph engine on a memory cloud. In Proceedings of the SIGMOD International Conference on Management of Data.Google ScholarDigital Library
- Feng Sheng, Qiang Cao, Haoran Cai, Jie Yao, and Changsheng Xie. 2018. GraPU: Accelerate streaming graph analysis through preprocessing buffered updates. In Proceedings of the ACM Symposium on Cloud Computing (SoCC’18).Google ScholarDigital Library
- Xiaogang Shi, Bin Cui, Yingxia Shao, and Yunhai Tong. 2016. Tornado: A system for real-time iterative analysis over evolving data. In Proceedings of the 2016 International Conference on Management of Data. ACM, 417--430.Google ScholarDigital Library
- Julian Shun and Guy E. Blelloch. 2013. Ligra: A lightweight graph processing framework for shared memory. In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP’13).Google Scholar
- Manuel Then, Timo Kersten, Stephan Günnemann, Alfons Kemper, and Thomas Neumann. 2017. Automatic algorithm transformation for efficient multi-snapshot analytics on temporal graphs. Proc. VLDB Endow. 10, 8 (2017), 877--888.Google ScholarDigital Library
- M. J. M. Turcotte, A. D. Kent, and C. Hash. 2017. Unified host and network data set. In Data Science for Cyber-Security. World Scientific. DOI:10.1142/9781786345646_001Google Scholar
- Keval Vora, Rajiv Gupta, and Guoqing Xu. 2017. Kickstarter: Fast and accurate computations on streaming graphs via trimmed approximations. In Proceedings of the 22nd International Conference on Architectural Support for Programming Languages and Operating Systems. ACM, 237--251.Google ScholarDigital Library
- Guozhang Wang, Wenlei Xie, Alan J. Demers, and Johannes Gehrke. 2013. Asynchronous large-scale graph processing made easy. In Proceedings of the Conference on Innovative Data Systems Research (CIDR’13), Vol. 13. 3--6.Google Scholar
- Ming Wu, Fan Yang, Jilong Xue, Wencong Xiao, Youshan Miao, Lan Wei, Haoxiang Lin, Yafei Dai, and Lidong Zhou. 2015. GRAM: Scaling graph computation to the trillions. In Proceedings of the 6th ACM Symposium on Cloud Computing.Google ScholarDigital Library
- Wenlei Xie, Yuanyuan Tian, Yannis Sismanis, Andrey Balmin, and Peter J. Haas. 2015. Dynamic interaction graphs with probabilistic edge decay. In Proceedings of the 2015 IEEE 31st International Conference on Data Engineering (ICDE’15). IEEE, 1143--1154.Google Scholar
- Da Yan, Yuzhen Huang, Miao Liu, Hongzhi Chen, James Cheng, Huanhuan Wu, and Chengcui Zhang. 2018. GraphD: Distributed vertex-centric graph processing beyond the memory limit. IEEE Trans. Parallel Distrib. Syst. 29, 1 (2018), 99--114.Google ScholarDigital Library
- Kai Zeng, Jiacheng Yang, Haixun Wang, Bin Shao, and Zhongyuan Wang. 2013. A distributed graph engine for web scale RDF data. In Proceedings of the 39th International Conference on Very Large Data Bases (PVLDB’13). VLDB Endowment.Google ScholarDigital Library
- Kaiyuan Zhang, Rong Chen, and Haibo Chen. 2015. NUMA-aware graph-structured analytics. ACM SIGPLAN Not. 50, 8 (2015), 183--193.Google ScholarDigital Library
- Wei Zhang, Yong Chen, and Dong Dai. 2018. AKIN: A streaming graph partitioning algorithm for distributed graph storage systems. In Proceedings of the 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. IEEE Press, 183--192.Google ScholarDigital Library
- Yunhao Zhang, Rong Chen, and Haibo Chen. 2017. Sub-millisecond stateful stream querying over fast-evolving linked data. In Proceedings of the 26th Symposium on Operating Systems Principles. ACM, 614--630.Google ScholarDigital Library
- Da Zheng, Disa Mhembere, Randal Burns, Joshua Vogelstein, Carey E. Priebe, and Alexander S. Szalay. 2015. FlashGraph: Processing billion-node graphs on an array of commodity SSDs. In Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST’15).Google ScholarDigital Library
- Xiaowei Zhu, Wenguang Chen, Weimin Zheng, and Xiaosong Ma. 2016. Gemini: A computation-centric distributed graph processing system. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI’16). 301--316.Google Scholar
- Xiaowei Zhu, Wentao Han, and Wenguang Chen. 2015. GridGraph: Large-scale graph processing on a single machine using 2-level hierarchical partitioning. In Proceedings of the USENIX Conference on Usenix Annual Technical Conference.Google Scholar
Index Terms
- GraphOne: A Data Store for Real-time Analytics on Evolving Graphs
Recommendations
GRAPHONE: a data store for real-time analytics on evolving graphs
FAST'19: Proceedings of the 17th USENIX Conference on File and Storage TechnologiesThere is a growing need to perform real-time analytics on evolving graphs in order to deliver the values of big data to users. The key requirement from such applications is to have a data store to support their diverse data access efficiently, while ...
SnappyData: A Hybrid Transactional Analytical Store Built On Spark
SIGMOD '16: Proceedings of the 2016 International Conference on Management of DataIn recent years, our customers have expressed frustration in the traditional approach of using a combination of disparate products to handle their streaming, transactional and analytical needs. The common practice of stitching heterogeneous environments ...
Independence---domination duality
Given a system G=(G"1,G"2,...,G"m) of m graphs on the same vertex set V, define the ''joint independence number''@a"@?(G) as the maximal size of a set which is independent in all graphs G"i. Let also @c"@?(G) be the ''collective domination number'' of ...
Comments