[{"_id":"11436","year":"2021","date_updated":"2022-06-07T06:53:36Z","issue":"9B","arxiv":1,"abstract":[{"lang":"eng","text":"Asynchronous distributed algorithms are a popular way to reduce synchronization costs in large-scale optimization, and in particular for neural network training. However, for nonsmooth and nonconvex objectives, few convergence guarantees exist beyond cases where closed-form proximal operator solutions are available. As training most popular deep neural networks corresponds to optimizing nonsmooth and nonconvex objectives, there is a pressing need for such convergence guarantees. In this paper, we analyze for the first time the convergence of stochastic asynchronous optimization for this general class of objectives. In particular, we focus on stochastic subgradient methods allowing for block variable partitioning, where the shared model is asynchronously updated by concurrent processes. To this end, we use a probabilistic model which captures key features of real asynchronous scheduling between concurrent processes. Under this model, we establish convergence with probability one to an invariant set for stochastic subgradient methods with momentum. From a practical perspective, one issue with the family of algorithms that we consider is that they are not efficiently supported by machine learning frameworks, which mostly focus on distributed data-parallel strategies. To address this, we propose a new implementation strategy for shared-memory based training of deep neural networks for a partitioned but shared model in single- and multi-GPU settings. Based on this implementation, we achieve on average1.2x speed-up in comparison to state-of-the-art training methods for popular image classification tasks, without compromising accuracy."}],"ec_funded":1,"month":"05","publication_identifier":{"eissn":["2374-3468"],"isbn":["9781713835974"],"issn":["2159-5399"]},"oa":1,"status":"public","date_published":"2021-05-18T00:00:00Z","oa_version":"Preprint","publication_status":"published","conference":{"end_date":"2021-02-09","location":"Virtual, Online","start_date":"2021-02-02","name":"AAAI: Conference on Artificial Intelligence"},"citation":{"short":"V. Kungurtsev, M. Egan, B. Chatterjee, D.-A. Alistarh, in:, 35th AAAI Conference on Artificial Intelligence, AAAI 2021, AAAI Press, 2021, pp. 8209–8216.","ama":"Kungurtsev V, Egan M, Chatterjee B, Alistarh D-A. Asynchronous optimization methods for efficient training of deep neural networks with guarantees. In: <i>35th AAAI Conference on Artificial Intelligence, AAAI 2021</i>. Vol 35. AAAI Press; 2021:8209-8216.","ieee":"V. Kungurtsev, M. Egan, B. Chatterjee, and D.-A. Alistarh, “Asynchronous optimization methods for efficient training of deep neural networks with guarantees,” in <i>35th AAAI Conference on Artificial Intelligence, AAAI 2021</i>, Virtual, Online, 2021, vol. 35, no. 9B, pp. 8209–8216.","chicago":"Kungurtsev, Vyacheslav, Malcolm Egan, Bapi Chatterjee, and Dan-Adrian Alistarh. “Asynchronous Optimization Methods for Efficient Training of Deep Neural Networks with Guarantees.” In <i>35th AAAI Conference on Artificial Intelligence, AAAI 2021</i>, 35:8209–16. AAAI Press, 2021.","ista":"Kungurtsev V, Egan M, Chatterjee B, Alistarh D-A. 2021. Asynchronous optimization methods for efficient training of deep neural networks with guarantees. 35th AAAI Conference on Artificial Intelligence, AAAI 2021. AAAI: Conference on Artificial Intelligence vol. 35, 8209–8216.","apa":"Kungurtsev, V., Egan, M., Chatterjee, B., &#38; Alistarh, D.-A. (2021). Asynchronous optimization methods for efficient training of deep neural networks with guarantees. In <i>35th AAAI Conference on Artificial Intelligence, AAAI 2021</i> (Vol. 35, pp. 8209–8216). Virtual, Online: AAAI Press.","mla":"Kungurtsev, Vyacheslav, et al. “Asynchronous Optimization Methods for Efficient Training of Deep Neural Networks with Guarantees.” <i>35th AAAI Conference on Artificial Intelligence, AAAI 2021</i>, vol. 35, no. 9B, AAAI Press, 2021, pp. 8209–16."},"intvolume":"        35","scopus_import":"1","main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.1905.11845"}],"project":[{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"},{"call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223"}],"author":[{"full_name":"Kungurtsev, Vyacheslav","first_name":"Vyacheslav","last_name":"Kungurtsev"},{"last_name":"Egan","first_name":"Malcolm","full_name":"Egan, Malcolm"},{"full_name":"Chatterjee, Bapi","first_name":"Bapi","last_name":"Chatterjee","id":"3C41A08A-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X"}],"day":"18","acknowledgement":"Vyacheslav Kungurtsev was supported by the OP VVV project CZ.02.1.01/0.0/0.0/16 019/0000765 “Research Center for Informatics. Bapi Chatterjee was supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No. 754411 (ISTPlus). Dan Alistarh has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML).","title":"Asynchronous optimization methods for efficient training of deep neural networks with guarantees","publisher":"AAAI Press","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"department":[{"_id":"DaAl"}],"type":"conference","date_created":"2022-06-05T22:01:52Z","page":"8209-8216","publication":"35th AAAI Conference on Artificial Intelligence, AAAI 2021","external_id":{"arxiv":["1905.11845"]},"volume":35,"quality_controlled":"1","article_processing_charge":"No"},{"quality_controlled":"1","volume":209,"external_id":{"arxiv":["2003.01697"]},"article_processing_charge":"No","department":[{"_id":"DaAl"}],"language":[{"iso":"eng"}],"type":"conference","publication":"35th International Symposium on Distributed Computing","date_created":"2021-11-07T23:01:23Z","has_accepted_license":"1","alternative_title":["LIPIcs"],"title":"Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","publisher":"Schloss Dagstuhl - Leibniz Zentrum für Informatik","file":[{"success":1,"file_size":795860,"relation":"main_file","content_type":"application/pdf","date_created":"2021-11-12T09:23:22Z","date_updated":"2021-11-12T09:23:22Z","file_name":"2021_LIPIcsDISC_BChatterjee.pdf","access_level":"open_access","file_id":"10276","creator":"cchlebak","checksum":"76546df112a0ba1166c864d33d7834e2"}],"author":[{"full_name":"Chatterjee, Bapi","last_name":"Chatterjee","id":"3C41A08A-F248-11E8-B48F-1D18A9856A87","first_name":"Bapi"},{"full_name":"Peri, Sathya","first_name":"Sathya","last_name":"Peri"},{"last_name":"Sa","first_name":"Muktikanta","full_name":"Sa, Muktikanta"}],"day":"04","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"acknowledgement":"This work was partially funded by National Supercomputing Mission, Govt. of India under the project “Concurrent and Distributed Programming primitives and algorithms for Temporal Graphs”(DST/NSM/R&D_Exascale/2021/16).\r\n","citation":{"chicago":"Chatterjee, Bapi, Sathya Peri, and Muktikanta Sa. “Brief Announcement: Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds.” In <i>35th International Symposium on Distributed Computing</i>, Vol. 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.52\">https://doi.org/10.4230/LIPIcs.DISC.2021.52</a>.","ista":"Chatterjee B, Peri S, Sa M. 2021. Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds. 35th International Symposium on Distributed Computing. DISC: Distributed Computing, LIPIcs, vol. 209, 52.","apa":"Chatterjee, B., Peri, S., &#38; Sa, M. (2021). Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds. In <i>35th International Symposium on Distributed Computing</i> (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.52\">https://doi.org/10.4230/LIPIcs.DISC.2021.52</a>","mla":"Chatterjee, Bapi, et al. “Brief Announcement: Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds.” <i>35th International Symposium on Distributed Computing</i>, vol. 209, 52, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.52\">10.4230/LIPIcs.DISC.2021.52</a>.","ama":"Chatterjee B, Peri S, Sa M. Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds. In: <i>35th International Symposium on Distributed Computing</i>. Vol 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.52\">10.4230/LIPIcs.DISC.2021.52</a>","ieee":"B. Chatterjee, S. Peri, and M. Sa, “Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds,” in <i>35th International Symposium on Distributed Computing</i>, Freiburg, Germany, 2021, vol. 209.","short":"B. Chatterjee, S. Peri, M. Sa, in:, 35th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021."},"intvolume":"       209","ddc":["000"],"file_date_updated":"2021-11-12T09:23:22Z","scopus_import":"1","date_published":"2021-10-04T00:00:00Z","oa_version":"Published Version","doi":"10.4230/LIPIcs.DISC.2021.52","conference":{"location":"Freiburg, Germany","end_date":"2021-10-08","name":"DISC: Distributed Computing","start_date":"2021-10-04"},"publication_status":"published","month":"10","oa":1,"publication_identifier":{"isbn":["9-783-9597-7210-5"],"issn":["1868-8969"]},"status":"public","_id":"10216","article_number":"52","year":"2021","abstract":[{"lang":"eng","text":"This paper reports a new concurrent graph data structure that supports updates of both edges and vertices and queries: Breadth-first search, Single-source shortest-path, and Betweenness centrality. The operations are provably linearizable and non-blocking."}],"arxiv":1,"date_updated":"2021-11-12T09:42:55Z"},{"date_published":"2021-05-18T00:00:00Z","oa_version":"Published Version","conference":{"start_date":"2021-02-02","name":"AAAI: Association for the Advancement of Artificial Intelligence","end_date":"2021-02-09","location":"Virtual"},"publication_status":"published","intvolume":"        35","citation":{"chicago":"Nadiradze, Giorgi, Ilia Markov, Bapi Chatterjee, Vyacheslav  Kungurtsev, and Dan-Adrian Alistarh. “Elastic Consistency: A Practical Consistency Model for Distributed Stochastic Gradient Descent.” In <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, 35:9037–45, 2021.","apa":"Nadiradze, G., Markov, I., Chatterjee, B., Kungurtsev, V., &#38; Alistarh, D.-A. (2021). Elastic consistency: A practical consistency model for distributed stochastic gradient descent. In <i>Proceedings of the AAAI Conference on Artificial Intelligence</i> (Vol. 35, pp. 9037–9045). Virtual.","mla":"Nadiradze, Giorgi, et al. “Elastic Consistency: A Practical Consistency Model for Distributed Stochastic Gradient Descent.” <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, vol. 35, no. 10, 2021, pp. 9037–45.","ista":"Nadiradze G, Markov I, Chatterjee B, Kungurtsev V, Alistarh D-A. 2021. Elastic consistency: A practical consistency model for distributed stochastic gradient descent. Proceedings of the AAAI Conference on Artificial Intelligence. AAAI: Association for the Advancement of Artificial Intelligence vol. 35, 9037–9045.","short":"G. Nadiradze, I. Markov, B. Chatterjee, V. Kungurtsev, D.-A. Alistarh, in:, Proceedings of the AAAI Conference on Artificial Intelligence, 2021, pp. 9037–9045.","ieee":"G. Nadiradze, I. Markov, B. Chatterjee, V. Kungurtsev, and D.-A. Alistarh, “Elastic consistency: A practical consistency model for distributed stochastic gradient descent,” in <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, Virtual, 2021, vol. 35, no. 10, pp. 9037–9045.","ama":"Nadiradze G, Markov I, Chatterjee B, Kungurtsev V, Alistarh D-A. Elastic consistency: A practical consistency model for distributed stochastic gradient descent. In: <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>. Vol 35. ; 2021:9037-9045."},"main_file_link":[{"open_access":"1","url":"https://ojs.aaai.org/index.php/AAAI/article/view/17092"}],"_id":"10432","year":"2021","date_updated":"2023-09-07T13:31:39Z","abstract":[{"lang":"eng","text":"One key element behind the recent progress of machine learning has been the ability to train machine learning models in large-scale distributed shared-memory and message-passing environments. Most of these models are trained employing variants of stochastic gradient descent (SGD) based optimization, but most methods involve some type of consistency relaxation relative to sequential SGD, to mitigate its large communication or synchronization costs at scale. In this paper, we introduce a general consistency condition covering communication-reduced and asynchronous distributed SGD implementations. Our framework, called elastic consistency, decouples the system-specific aspects of the implementation from the SGD convergence requirements, giving a general way to obtain convergence bounds for a wide variety of distributed SGD methods used in practice. Elastic consistency can be used to re-derive or improve several previous convergence bounds in message-passing and shared-memory settings, but also to analyze new models and distribution schemes. As a direct application, we propose and analyze a new synchronization-avoiding scheduling scheme for distributed SGD, and show that it can be used to efficiently train deep convolutional models for image classification."}],"arxiv":1,"issue":"10","ec_funded":1,"month":"05","oa":1,"status":"public","language":[{"iso":"eng"}],"department":[{"_id":"DaAl"}],"type":"conference","page":"9037-9045","date_created":"2021-12-09T09:21:35Z","publication":"Proceedings of the AAAI Conference on Artificial Intelligence","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"10429"}]},"external_id":{"arxiv":["2001.05918"]},"volume":35,"quality_controlled":"1","article_processing_charge":"No","project":[{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"},{"grant_number":"805223","_id":"268A44D6-B435-11E9-9278-68D0E5697425","name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020"}],"author":[{"full_name":"Nadiradze, Giorgi","first_name":"Giorgi","orcid":"0000-0001-5634-0731","id":"3279A00C-F248-11E8-B48F-1D18A9856A87","last_name":"Nadiradze"},{"full_name":"Markov, Ilia","first_name":"Ilia","last_name":"Markov","id":"D0CF4148-C985-11E9-8066-0BDEE5697425"},{"full_name":"Chatterjee, Bapi","orcid":"0000-0002-2742-4028","first_name":"Bapi","id":"3C41A08A-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"last_name":"Kungurtsev","first_name":"Vyacheslav ","full_name":"Kungurtsev, Vyacheslav "},{"full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"}],"day":"18","acknowledgement":"We would like to thank Christopher De Sa for his feedback on an earlier draft of this paper, as well as the anonymous AAAI reviewers for their useful comments. This project has received\r\nfunding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). Bapi\r\nChatterjee was supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No. 754411 (ISTPlus).","title":"Elastic consistency: A practical consistency model for distributed stochastic gradient descent","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9"},{"doi":"10.1016/j.tcs.2021.06.041","publication_status":"published","oa_version":"Submitted Version","date_published":"2021-09-13T00:00:00Z","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://publications.lib.chalmers.se/records/fulltext/232185/232185.pdf"}],"intvolume":"       886","citation":{"short":"B. Chatterjee, I. Walulya, P. Tsigas, Theoretical Computer Science 886 (2021) 27–48.","ieee":"B. Chatterjee, I. Walulya, and P. Tsigas, “Concurrent linearizable nearest neighbour search in LockFree-kD-tree,” <i>Theoretical Computer Science</i>, vol. 886. Elsevier, pp. 27–48, 2021.","ama":"Chatterjee B, Walulya I, Tsigas P. Concurrent linearizable nearest neighbour search in LockFree-kD-tree. <i>Theoretical Computer Science</i>. 2021;886:27-48. doi:<a href=\"https://doi.org/10.1016/j.tcs.2021.06.041\">10.1016/j.tcs.2021.06.041</a>","chicago":"Chatterjee, Bapi, Ivan Walulya, and Philippas Tsigas. “Concurrent Linearizable Nearest Neighbour Search in LockFree-KD-Tree.” <i>Theoretical Computer Science</i>. Elsevier, 2021. <a href=\"https://doi.org/10.1016/j.tcs.2021.06.041\">https://doi.org/10.1016/j.tcs.2021.06.041</a>.","apa":"Chatterjee, B., Walulya, I., &#38; Tsigas, P. (2021). Concurrent linearizable nearest neighbour search in LockFree-kD-tree. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2021.06.041\">https://doi.org/10.1016/j.tcs.2021.06.041</a>","mla":"Chatterjee, Bapi, et al. “Concurrent Linearizable Nearest Neighbour Search in LockFree-KD-Tree.” <i>Theoretical Computer Science</i>, vol. 886, Elsevier, 2021, pp. 27–48, doi:<a href=\"https://doi.org/10.1016/j.tcs.2021.06.041\">10.1016/j.tcs.2021.06.041</a>.","ista":"Chatterjee B, Walulya I, Tsigas P. 2021. Concurrent linearizable nearest neighbour search in LockFree-kD-tree. Theoretical Computer Science. 886, 27–48."},"abstract":[{"lang":"eng","text":"The Nearest neighbour search (NNS) is a fundamental problem in many application domains dealing with multidimensional data. In a concurrent setting, where dynamic modifications are allowed, a linearizable implementation of the NNS is highly desirable.This paper introduces the LockFree-kD-tree (LFkD-tree ): a lock-free concurrent kD-tree, which implements an abstract data type (ADT) that provides the operations Add, Remove, Contains, and NNS. Our implementation is linearizable. The operations in the LFkD-tree use single-word read and compare-and-swap (Image 1 ) atomic primitives, which are readily supported on available multi-core processors. We experimentally evaluate the LFkD-tree using several benchmarks comprising real-world and synthetic datasets. The experiments show that the presented design is scalable and achieves significant speed-up compared to the implementations of an existing sequential kD-tree and a recently proposed multidimensional indexing structure, PH-tree."}],"date_updated":"2023-08-10T14:27:43Z","year":"2021","_id":"9827","status":"public","publication_identifier":{"issn":["0304-3975"]},"oa":1,"month":"09","publication":"Theoretical Computer Science","date_created":"2021-08-08T22:01:31Z","page":"27-48","type":"journal_article","department":[{"_id":"DaAl"}],"language":[{"iso":"eng"}],"article_processing_charge":"No","article_type":"original","volume":886,"keyword":["Concurrent data structure","kD-tree","Nearest neighbor search","Similarity search","Lock-free","Linearizability"],"quality_controlled":"1","external_id":{"isi":["000694718900004"]},"day":"13","isi":1,"author":[{"full_name":"Chatterjee, Bapi","id":"3C41A08A-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-2742-4028","first_name":"Bapi"},{"first_name":"Ivan","last_name":"Walulya","full_name":"Walulya, Ivan"},{"first_name":"Philippas","last_name":"Tsigas","full_name":"Tsigas, Philippas"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publisher":"Elsevier","title":"Concurrent linearizable nearest neighbour search in LockFree-kD-tree"},{"day":"01","author":[{"last_name":"Bhatia","first_name":"Sumit","full_name":"Bhatia, Sumit"},{"full_name":"Chatterjee, Bapi","id":"3C41A08A-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-2742-4028","first_name":"Bapi"},{"first_name":"Deepak","last_name":"Nathani","full_name":"Nathani, Deepak"},{"full_name":"Kaul, Manohar","last_name":"Kaul","first_name":"Manohar"}],"isi":1,"project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"}],"file":[{"file_name":"main.pdf","date_updated":"2020-10-08T08:16:48Z","date_created":"2020-10-08T08:16:48Z","creator":"bchatter","checksum":"8951f094c8c7dae9ff8db885199bc296","file_id":"8625","access_level":"open_access","content_type":"application/pdf","relation":"main_file","success":1,"file_size":310598}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publisher":"Springer Nature","title":"A persistent homology perspective to the link prediction problem","alternative_title":["SCI"],"has_accepted_license":"1","publication":"Complex Networks and their applications VIII","page":"27-39","date_created":"2019-12-29T23:00:45Z","type":"conference","department":[{"_id":"DaAl"}],"language":[{"iso":"eng"}],"article_processing_charge":"No","volume":881,"quality_controlled":"1","external_id":{"isi":["000843927300003"]},"abstract":[{"lang":"eng","text":"Persistent homology is a powerful tool in Topological Data Analysis (TDA) to capture the topological properties of data succinctly at different spatial resolutions. For graphical data, the shape, and structure of the neighborhood of individual data items (nodes) are an essential means of characterizing their properties. We propose the use of persistent homology methods to capture structural and topological properties of graphs and use it to address the problem of link prediction. We achieve encouraging results on nine different real-world datasets that attest to the potential of persistent homology-based methods for network analysis."}],"date_updated":"2024-02-22T13:16:06Z","year":"2020","_id":"7213","status":"public","publication_identifier":{"isbn":["9783030366865"],"eissn":["18609503"],"issn":["1860949X"]},"oa":1,"month":"01","ec_funded":1,"doi":"10.1007/978-3-030-36687-2_3","conference":{"end_date":"2019-12-12","location":"Lisbon, Portugal","start_date":"2019-12-10","name":"COMPLEX: International Conference on Complex Networks and their Applications"},"publication_status":"published","oa_version":"Submitted Version","date_published":"2020-01-01T00:00:00Z","scopus_import":"1","file_date_updated":"2020-10-08T08:16:48Z","ddc":["004"],"intvolume":"       881","citation":{"chicago":"Bhatia, Sumit, Bapi Chatterjee, Deepak Nathani, and Manohar Kaul. “A Persistent Homology Perspective to the Link Prediction Problem.” In <i>Complex Networks and Their Applications VIII</i>, 881:27–39. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/978-3-030-36687-2_3\">https://doi.org/10.1007/978-3-030-36687-2_3</a>.","ista":"Bhatia S, Chatterjee B, Nathani D, Kaul M. 2020. A persistent homology perspective to the link prediction problem. Complex Networks and their applications VIII. COMPLEX: International Conference on Complex Networks and their Applications, SCI, vol. 881, 27–39.","mla":"Bhatia, Sumit, et al. “A Persistent Homology Perspective to the Link Prediction Problem.” <i>Complex Networks and Their Applications VIII</i>, vol. 881, Springer Nature, 2020, pp. 27–39, doi:<a href=\"https://doi.org/10.1007/978-3-030-36687-2_3\">10.1007/978-3-030-36687-2_3</a>.","apa":"Bhatia, S., Chatterjee, B., Nathani, D., &#38; Kaul, M. (2020). A persistent homology perspective to the link prediction problem. In <i>Complex Networks and their applications VIII</i> (Vol. 881, pp. 27–39). Lisbon, Portugal: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-36687-2_3\">https://doi.org/10.1007/978-3-030-36687-2_3</a>","short":"S. Bhatia, B. Chatterjee, D. Nathani, M. Kaul, in:, Complex Networks and Their Applications VIII, Springer Nature, 2020, pp. 27–39.","ama":"Bhatia S, Chatterjee B, Nathani D, Kaul M. A persistent homology perspective to the link prediction problem. In: <i>Complex Networks and Their Applications VIII</i>. Vol 881. Springer Nature; 2020:27-39. doi:<a href=\"https://doi.org/10.1007/978-3-030-36687-2_3\">10.1007/978-3-030-36687-2_3</a>","ieee":"S. Bhatia, B. Chatterjee, D. Nathani, and M. Kaul, “A persistent homology perspective to the link prediction problem,” in <i>Complex Networks and their applications VIII</i>, Lisbon, Portugal, 2020, vol. 881, pp. 27–39."}},{"type":"conference","language":[{"iso":"eng"}],"department":[{"_id":"DaAl"}],"date_created":"2019-02-10T22:59:17Z","page":"168-177","publication":"ACM International Conference Proceeding Series","external_id":{"isi":["000484491600019"],"arxiv":["1809.00896"]},"quality_controlled":"1","article_processing_charge":"No","isi":1,"author":[{"first_name":"Bapi","orcid":"0000-0002-2742-4028","id":"3C41A08A-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Bapi"},{"full_name":"Peri, Sathya","last_name":"Peri","first_name":"Sathya"},{"full_name":"Sa, Muktikanta","first_name":"Muktikanta","last_name":"Sa"},{"full_name":"Singhal, Nandini","first_name":"Nandini","last_name":"Singhal"}],"day":"04","publisher":"ACM","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","title":"A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries","oa_version":"Preprint","date_published":"2019-01-04T00:00:00Z","publication_status":"published","conference":{"location":"Bangalore, India","end_date":"2019-01-07","name":"ICDCN: Conference on Distributed Computing and Networking","start_date":"2019-01-04"},"doi":"10.1145/3288599.3288617","citation":{"short":"B. Chatterjee, S. Peri, M. Sa, N. Singhal, in:, ACM International Conference Proceeding Series, ACM, 2019, pp. 168–177.","ieee":"B. Chatterjee, S. Peri, M. Sa, and N. Singhal, “A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries,” in <i>ACM International Conference Proceeding Series</i>, Bangalore, India, 2019, pp. 168–177.","ama":"Chatterjee B, Peri S, Sa M, Singhal N. A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries. In: <i>ACM International Conference Proceeding Series</i>. ACM; 2019:168-177. doi:<a href=\"https://doi.org/10.1145/3288599.3288617\">10.1145/3288599.3288617</a>","chicago":"Chatterjee, Bapi, Sathya Peri, Muktikanta Sa, and Nandini Singhal. “A Simple and Practical Concurrent Non-Blocking Unbounded Graph with Linearizable Reachability Queries.” In <i>ACM International Conference Proceeding Series</i>, 168–77. ACM, 2019. <a href=\"https://doi.org/10.1145/3288599.3288617\">https://doi.org/10.1145/3288599.3288617</a>.","mla":"Chatterjee, Bapi, et al. “A Simple and Practical Concurrent Non-Blocking Unbounded Graph with Linearizable Reachability Queries.” <i>ACM International Conference Proceeding Series</i>, ACM, 2019, pp. 168–77, doi:<a href=\"https://doi.org/10.1145/3288599.3288617\">10.1145/3288599.3288617</a>.","ista":"Chatterjee B, Peri S, Sa M, Singhal N. 2019. A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries. ACM International Conference Proceeding Series. ICDCN: Conference on Distributed Computing and Networking, 168–177.","apa":"Chatterjee, B., Peri, S., Sa, M., &#38; Singhal, N. (2019). A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries. In <i>ACM International Conference Proceeding Series</i> (pp. 168–177). Bangalore, India: ACM. <a href=\"https://doi.org/10.1145/3288599.3288617\">https://doi.org/10.1145/3288599.3288617</a>"},"scopus_import":"1","main_file_link":[{"url":"https://arxiv.org/abs/1809.00896","open_access":"1"}],"_id":"5947","date_updated":"2023-08-24T14:41:53Z","abstract":[{"lang":"eng","text":"Graph algorithms applied in many applications, including social networks, communication networks, VLSI design, graphics, and several others, require dynamic modifications - addition and removal of vertices and/or edges - in the graph. This paper presents a novel concurrent non-blocking algorithm to implement a dynamic unbounded directed graph in a shared-memory machine. The addition and removal operations of vertices and edges are lock-free. For a finite sized graph, the lookup operations are wait-free. Most significant component of the presented algorithm is the reachability query in a concurrent graph. The reachability queries in our algorithm are obstruction-free and thus impose minimal additional synchronization cost over other operations. We prove that each of the data structure operations are linearizable. We extensively evaluate a sample C/C++ implementation of the algorithm through a number of micro-benchmarks. The experimental results show that the proposed algorithm scales well with the number of threads and on an average provides 5 to 7x performance improvement over a concurrent graph implementation using coarse-grained locking."}],"arxiv":1,"year":"2019","month":"01","status":"public","oa":1,"publication_identifier":{"isbn":["978-1-4503-6094-4 "]}}]