{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:16:41Z","timestamp":1779175001180,"version":"3.51.4"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:p>\n            Arbitrage is a challenging data science problem characterized by rapidly fluctuating price discrepancies across multiple markets, necessitating real-time solutions. To overcome the challenge, we model it as a\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -hop negative cycle detection problem in graphs and introduce RICH: Real-time Identification of negative Cycles for High-efficiency arbitrage. RICH is a novel framework that leverages color-coding and dynamic programming to accelerate the identification of negative-weight cycles without exhaustive graph traversal. Additionally, RICH incorporates encoding techniques and graph reduction to minimize computational overhead while maintaining probabilistic guarantees. Our extensive experiments on real-world datasets demonstrate that RICH is up to 32.69\u00d7 faster than state-of-the-art methods, enabling timely arbitrage execution while outperforming existing methods in both speed and accuracy. We further validate its effectiveness in identifying arbitrage opportunities in cryptocurrency markets and foreign exchange markets.\n          <\/jats:p>","DOI":"10.14778\/3749646.3749678","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T17:55:06Z","timestamp":1757008506000},"page":"4081-4089","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["RICH: Real-Time Identification of Negative Cycles for High-Efficiency Arbitrage"],"prefix":"10.14778","volume":"18","author":[{"given":"Bingqiao","family":"Luo","sequence":"first","affiliation":[{"name":"National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiaxin","family":"Jiang","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuhang","family":"Chen","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junyi","family":"Hou","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cheng Jun","family":"Tey","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ziyang","family":"Qiu","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bingsheng","family":"He","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Spencer","family":"Xiao","sequence":"additional","affiliation":[{"name":"Tokka Labs"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominic","family":"Ong","sequence":"additional","affiliation":[{"name":"Tokka Labs"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wee Howe","family":"Ang","sequence":"additional","affiliation":[{"name":"Tokka Labs"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Ethereum Average Block Time Chart. https:\/\/etherscan.io\/chart\/blocktime Accessed","year":"2024","unstructured":"[n.d.]. Ethereum Average Block Time Chart. https:\/\/etherscan.io\/chart\/blocktime Accessed: December 8, 2024."},{"key":"e_1_2_1_2_1","unstructured":"Hayden Adams Noah Zinsmeister and Dan Robinson. 2020. Uniswap V2 Core. Whitepaper. https:\/\/uniswap.org\/whitepaper.pdf Accessed: 2024-12-04."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_4_1","volume-title":"On a routing problem. Quarterly of applied mathematics 16, 1","author":"Bellman Richard","year":"1958","unstructured":"Richard Bellman. 1958. On a routing problem. Quarterly of applied mathematics 16, 1 (1958), 87\u201390."},{"key":"e_1_2_1_5_1","volume-title":"International Conference on Financial Cryptography and Data Security. Springer, 238\u2013249","author":"Berg Jan Arvid","year":"2022","unstructured":"Jan Arvid Berg, Robin Fritsch, Lioba Heimbach, and Roger Wattenhofer. 2022. An empirical study of market inefficiencies in Uniswap and SushiSwap. In International Conference on Financial Cryptography and Data Security. Springer, 238\u2013249."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190050102"},{"key":"e_1_2_1_7_1","volume-title":"Negative-weight single-source shortest paths in near-linear time. In 2022 IEEE 63rd annual symposium on foundations of computer science (FOCS)","author":"Bernstein Aaron","unstructured":"Aaron Bernstein, Danupon Nanongkai, and Christian Wulff-Nilsen. 2022. Negative-weight single-source shortest paths in near-linear time. In 2022 IEEE 63rd annual symposium on foundations of computer science (FOCS). IEEE, 600\u2013611."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00038"},{"key":"e_1_2_1_9_1","unstructured":"Rohit Chandra. 2001. Parallel programming in OpenMP. Morgan kaufmann."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1093\/rfs\/hhy097"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3682028"},{"key":"e_1_2_1_12_1","first-page":"2","article-title":"Shortest-path feasibility algorithms: An experimental evaluation","volume":"14","author":"Cherkassky Boris V","year":"2010","unstructured":"Boris V Cherkassky, Loukas Georgiadis, Andrew V Goldberg, Robert E Tarjan, and Renato F Werneck. 2010. Shortest-path feasibility algorithms: An experimental evaluation. Journal of Experimental Algorithmics (JEA) 14 (2010), 2\u20137.","journal-title":"Journal of Experimental Algorithmics (JEA)"},{"key":"e_1_2_1_13_1","volume-title":"Negative-cycle detection algorithms. Mathematical Programming 85, 2","author":"Cherkassky Boris V","year":"1999","unstructured":"Boris V Cherkassky and Andrew V Goldberg. 1999. Negative-cycle detection algorithms. Mathematical Programming 85, 2 (1999)."},{"key":"e_1_2_1_14_1","volume-title":"Remeasuring the Arbitrage and Sandwich Attacks of Maximal Extractable Value in Ethereum. arXiv preprint arXiv:2405.17944","author":"Chi Tianyang","year":"2024","unstructured":"Tianyang Chi, Ningyu He, Xiaohui Hu, and Haoyu Wang. 2024. Remeasuring the Arbitrage and Sandwich Attacks of Maximal Extractable Value in Ethereum. arXiv preprint arXiv:2405.17944 (2024)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316329"},{"key":"e_1_2_1_16_1","volume-title":"Finance","author":"Dybvig Philip H","unstructured":"Philip H Dybvig and Stephen A Ross. 1989. Arbitrage. In Finance. Springer, 57\u201371."},{"key":"e_1_2_1_17_1","volume-title":"SoK: Transparent Dishonesty: front-running attacks on Blockchain. CoRR abs\/1902.05164","author":"Eskandari Shayan","year":"2019","unstructured":"Shayan Eskandari, Seyedehmahsa Moosavi, and Jeremy Clark. 2019. SoK: Transparent Dishonesty: front-running attacks on Blockchain. CoRR abs\/1902.05164 (2019). arXiv:1902.05164 http:\/\/arxiv.org\/abs\/1902.05164"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-43725-1_13"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02288320"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11071-019-05335-5"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00552-1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792231179"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Andrew V Goldberg and Tomasz Radzik. 1993. A heuristic improvement of the Bellman-Ford algorithm. Citeseer.","DOI":"10.1016\/0893-9659(93)90022-F"},{"key":"e_1_2_1_25_1","volume-title":"Finding all bounded-length simple cycles in a directed graph. arXiv preprint arXiv:2105.10094","author":"Gupta Anshul","year":"2021","unstructured":"Anshul Gupta and Toyotaro Suzumura. 2021. Finding all bounded-length simple cycles in a directed graph. arXiv preprint arXiv:2105.10094 (2021)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jimonfin.2014.05.001"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3570690.3570696"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204007"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.64"},{"key":"e_1_2_1_30_1","volume-title":"METIS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices.","author":"Karypis George","year":"1997","unstructured":"George Karypis and Vipin Kumar. 1997. METIS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. (1997)."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1080\/0015198X.2020.1733902"},{"key":"e_1_2_1_32_1","unstructured":"Bingqiao Luo Jiaxin Jiang and Yuhang Chen et al. 2025. RICH: Real-Time Identification of Negative Cycles for High-Efficiency Arbitrage. Technical Report. Technical Report. Available online at https:\/\/drive.google.com\/drive\/folders\/13VD_zcsp2TPs1R3eG1JVG91mV6JBaQlm?usp=sharing. Accessed on May 31 2025."},{"key":"e_1_2_1_33_1","first-page":"28490","article-title":"Multi-Chain Graphs of Graphs: A New Approach to Analyzing Blockchain Datasets","volume":"37","author":"Luo Bingqiao","year":"2024","unstructured":"Bingqiao Luo, Zhen Zhang, Qian Wang, and Bingsheng He. 2024. Multi-Chain Graphs of Graphs: A New Approach to Analyzing Blockchain Datasets. Advances in Neural Information Processing Systems 37 (2024), 28490\u201328514.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_34_1","volume-title":"32nd USENIX Security Symposium (USENIX Security 23)","author":"McLaughlin Robert","year":"2023","unstructured":"Robert McLaughlin, Christopher Kruegel, and Giovanni Vigna. 2023. A large scale study of the ethereum arbitrage ecosystem. In 32nd USENIX Security Symposium (USENIX Security 23). 3295\u20133312."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808703"},{"key":"e_1_2_1_36_1","volume-title":"Proc. of the International Symposium on the Theory of Switching","author":"Moore Edward F","year":"1959","unstructured":"Edward F Moore. 1959. The shortest path through a maze. In Proc. of the International Symposium on the Theory of Switching. Harvard University Press, 285\u2013292."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3372716.3372720"},{"key":"e_1_2_1_38_1","volume-title":"Extracting godl [sic] from the salt mines: Ethereum miners extracting value. arXiv preprint arXiv:2203.15930","author":"Piet Julien","year":"2022","unstructured":"Julien Piet, Jaiden Fairoze, and Nicholas Weaver. 2022. Extracting godl [sic] from the salt mines: Ethereum miners extracting value. arXiv preprint arXiv:2203.15930 (2022)."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP46214.2022.9833734"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_1_41_1","unstructured":"Igor Radovanovic. [n.d.]. Crypto Arbitrage Guide. https:\/\/algotrading101.com\/learn\/crypto-arbitrage-guide\/. Accessed: 2025-01-30."},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Stephen A Ross. 2013. The arbitrage theory of capital asset pricing. In Handbook of the fundamentals of financial decision making: Part I. World Scientific 11\u201330.","DOI":"10.1142\/9789814417358_0001"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457290"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202017"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3487553.3524201"},{"key":"e_1_2_1_46_1","volume-title":"BriDe Arbitrager: Enhancing Arbitrage in Ethereum 2.0 via Bribery-enabled Delayed Block Production. arXiv preprint arXiv:2407.08537","author":"Yang Hulin","year":"2024","unstructured":"Hulin Yang, Mingzhe Li, Jin Zhang, Alia Asheralieva, Qingsong Wei, and Siow Mong Rick Goh. 2024. BriDe Arbitrager: Enhancing Arbitrage in Ethereum 2.0 via Bribery-enabled Delayed Block Production. arXiv preprint arXiv:2407.08537 (2024)."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654982"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICBC59979.2024.10634351"},{"key":"e_1_2_1_49_1","first-page":"18769","article-title":"Live graph lab: Towards open, dynamic and real transaction graphs with NFT","volume":"36","author":"Zhang Zhen","year":"2023","unstructured":"Zhen Zhang, Bingqiao Luo, Shengliang Lu, and Bingsheng He. 2023. Live graph lab: Towards open, dynamic and real transaction graphs with NFT. Advances in Neural Information Processing Systems 36 (2023), 18769\u201318793.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP40001.2021.00113"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3749646.3749678","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T03:36:15Z","timestamp":1757043375000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3749646.3749678"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7]]},"references-count":50,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["10.14778\/3749646.3749678"],"URL":"https:\/\/doi.org\/10.14778\/3749646.3749678","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,7]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}