{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T23:51:32Z","timestamp":1763077892416,"version":"3.41.0"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,2,12]],"date-time":"2022-02-12T00:00:00Z","timestamp":1644624000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["CCF-1513944, CCF-1629403, IIS-1718450, and CCF-2005884"],"award-info":[{"award-number":["CCF-1513944, CCF-1629403, IIS-1718450, and CCF-2005884"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"<jats:p>R-tree is a foundational data structure used in spatial databases and scientific databases. With the advancement of networks and computer architectures, in-memory data processing for R-tree in distributed systems has become a common platform. We have observed new performance challenges to process R-tree as the amount of multidimensional datasets become increasingly high. Specifically, an R-tree server can be heavily overloaded while the network and client CPU are lightly loaded, and vice versa.<\/jats:p>\n          <jats:p>In this article, we present the design and implementation of Catfish, an RDMA-enabled R-tree for low latency and high throughput by adaptively utilizing the available network bandwidth and computing resources to balance the workloads between clients and servers. We design and implement two basic mechanisms of using RDMA for a client-server R-tree data processing system. First, in the fast messaging design, we use RDMA writes to send R-tree requests to the server and let server threads process R-tree requests to achieve low query latency. Second, in the RDMA offloading design, we use RDMA reads to offload tree traversal from the server to the client, which rescues the server as it is overloaded. We further develop an adaptive scheme to effectively switch an R-tree search between fast messaging and RDMA offloading, maximizing the overall performance. Our experiments show that the adaptive solution of Catfish on InfiniBand significantly outperforms R-tree that uses only fast messaging or only RDMA offloading in both latency and throughput. Catfish can also deliver up to one order of magnitude performance over the traditional schemes using TCP\/IP on 1 and 40 Gbps Ethernet. We make a strong case to use RDMA to effectively balance workloads in distributed systems for low latency and high throughput.<\/jats:p>","DOI":"10.1145\/3503513","type":"journal-article","created":{"date-parts":[[2022,2,12]],"date-time":"2022-02-12T12:31:55Z","timestamp":1644669115000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["An RDMA-enabled In-memory Computing Platform for R-tree on Clusters"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6305-8125","authenticated-orcid":false,"given":"Mengbai","family":"Xiao","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology, Shandong University, Qingdao, Shandong, China"}]},{"given":"Hao","family":"Wang","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science and Engineering, The Ohio State University, Columbus, OH, USA"}]},{"given":"Liang","family":"Geng","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science and Engineering, The Ohio State University, Columbus, OH, USA"}]},{"given":"Rubao","family":"Lee","sequence":"additional","affiliation":[{"name":"United Parallel Computing Corporation, Lewis Center, OH, USA"}]},{"given":"Xiaodong","family":"Zhang","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science and Engineering, The Ohio State University, Columbus, OH, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,2,12]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"A. M. Abdullah. 1997. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specification. https:\/\/www.iith.ac.in\/tbr\/teaching\/docs\/802.11-2007.pdf."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536227"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007608"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_3_2_6_2","unstructured":"Norbert Beckmann and Bernhard Seeger. 2008. A benchmark for multidimensional index structures. Retrieved from http:\/\/www.mathematik.uni-marburg.de\/seeger\/rrstar\/index.html."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.14778\/2904483.2904485"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191880"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303968"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2901318.2901349"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/645920.672974"},{"issue":"1","key":"e_1_3_2_12_2","first-page":"3","article-title":"RDMA reads: To use or not to use?","volume":"40","author":"Dragojevic Aleksandar","year":"2017","unstructured":"Aleksandar Dragojevic, Dushyanth Narayanan, and Miguel Castro. 2017. RDMA reads: To use or not to use?IEEE Data Eng. Bull. 40, 1 (2017), 3\u201314.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_3_2_13_2","first-page":"401","volume-title":"Proceedings of the 11th USENIX Conference on Networked Systems Design and Implementation (NSDI\u201914)","author":"Dragojevi\u0107 Aleksandar","year":"2014","unstructured":"Aleksandar Dragojevi\u0107, Dushyanth Narayanan, Orion Hodson, and Miguel Castro. 2014. FaRM: Fast remote memory. In Proceedings of the 11th USENIX Conference on Networked Systems Design and Implementation (NSDI\u201914). USENIX Association, Berkeley, CA, 401\u2013414."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815425"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113382"},{"key":"e_1_3_2_16_2","unstructured":"Google. 2005. Google Maps. Retrieved from https:\/\/maps.google.com."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_3_2_18_2","first-page":"19","article-title":"Four-Dimensional hilbert curves for R-Trees","volume":"16","author":"Haverkort Herman","year":"2008","unstructured":"Herman Haverkort and Freek V. Walderveen. 2008. Four-Dimensional hilbert curves for R-Trees. ACM J. Exp. Algorithmics 16, Article 3.4 (Nov. 2008), 19 pages.","journal-title":"ACM J. Exp. Algorithmics"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2012.65"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3127479.3132254"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCGrid.2012.141"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2011.37"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2619239.2626299"},{"key":"e_1_3_2_24_2","first-page":"437","volume-title":"Proceedings of the USENIX Conference on Usenix Annual Technical Conference (USENIX ATC\u201916)","author":"Kalia Anuj","year":"2016","unstructured":"Anuj Kalia, Michael Kaminsky, and David G. Andersen. 2016. Design guidelines for high performance RDMA systems. In Proceedings of the USENIX Conference on Usenix Annual Technical Conference (USENIX ATC\u201916). USENIX Association, Berkeley, CA, 437\u2013450."},{"key":"e_1_3_2_25_2","first-page":"185","volume-title":"Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201916)","author":"Kalia Anuj","year":"2016","unstructured":"Anuj Kalia, Michael Kaminsky, and David G. Andersen. 2016. FaSST: Fast, scalable and simple distributed transactions with two-sided (RDMA) datagram RPCs. In Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201916). USENIX Association, Berkeley, CA, 185\u2013201."},{"key":"e_1_3_2_26_2","first-page":"500","volume-title":"Proceedings of the 20th International Conference on Very Large Data Bases (VLDB\u201994)","author":"Kamel Ibrahim","year":"1994","unstructured":"Ibrahim Kamel and Christos Faloutsos. 1994. Hilbert R-tree: An improved R-tree using fractals. In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB\u201994). 500\u2013509."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2018.2823760"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSC.2021.3079580"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/645921.673305"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1997.582015"},{"key":"e_1_3_2_31_2","first-page":"37","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis","author":"Li Mingzhe","year":"2016","unstructured":"Mingzhe Li, Khaled Hamidouche, Xiaoyi Lu, Hari Subramoni, Jie Zhang, and Dhabaleswar K. Panda. 2016. Designing MPI library with on-demand paging (ODP) of infiniband: Challenges and benefits. In Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis. IEEE Press, 37."},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3458817.3476191"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.149"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3139961"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064202"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2013.78"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2304576.2304594"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/360248.360253"},{"key":"e_1_3_2_39_2","first-page":"103","volume-title":"Proceedings of the USENIX Conference on Annual Technical Conference (USENIX ATC\u201913)","author":"Mitchell Christopher","year":"2013","unstructured":"Christopher Mitchell, Yifeng Geng, and Jinyang Li. 2013. Using one-sided RDMA reads to build a fast, CPU-efficient Key-value store. In Proceedings of the USENIX Conference on Annual Technical Conference (USENIX ATC\u201913). USENIX Association, Berkeley, CA, 103\u2013114."},{"key":"e_1_3_2_40_2","series-title":"Proceedings of the USENIX Conference on Usenix Annual Technical Conference","first-page":"451","author":"Mitchell Christopher","year":"2016","unstructured":"Christopher Mitchell, Kate Montgomery, Lamont Nelson, Siddhartha Sen, and Jinyang Li. 2016. Balancing CPU and network in the cell distributed B-tree store. In Proceedings of the USENIX Conference on Usenix Annual Technical Conference (Denver, CO) (USENIX ATC\u201916). USENIX Association, Berkeley, CA, 451\u2013464."},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2015.127"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3177738"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00195"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/318898.318900"},{"key":"e_1_3_2_45_2","first-page":"27","article-title":"Rethinking distributed query execution on high-speed networks","author":"Salama Abdallah","year":"2017","unstructured":"Abdallah Salama, Carsten Binnig, Tim Kraska, Ansgar Scherp, and Tobias Ziegler. 2017. Rethinking distributed query execution on high-speed networks. Data Eng. 40, 1 (2017), 27\u201337.","journal-title":"Data Eng."},{"key":"e_1_3_2_46_2","first-page":"507","volume-title":"Proceedings of the 13th International Conference on Very Large Data Bases (VLDB\u201987)","author":"Sellis Timos K.","year":"1987","unstructured":"Timos K. Sellis, Nick Roussopoulos, and Christos Faloutsos. 1987. The R+-Tree: A dynamic index for multi-dimensional objects. In Proceedings of the 13th International Conference on Very Large Data Bases (VLDB\u201987). Morgan Kaufmann Publishers, San Francisco, CA, 507\u2013518."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183743"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064189"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007310"},{"key":"e_1_3_2_50_2","unstructured":"Mellanox Technologies. 2015. Performance Tests (perftest) package for OFED. Retrieved from https:\/\/github.com\/linux-rdma\/perftest."},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132762"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064029"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/2670979.2671002"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807614"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815419"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2019.00025"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915237"},{"key":"e_1_3_2_58_2","unstructured":"Yelp. 2004. Yelp Inc. Retrieved from https:\/\/www.yelp.com."},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055335"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3503513","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3503513","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:19Z","timestamp":1750186939000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3503513"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,12]]},"references-count":58,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3503513"],"URL":"https:\/\/doi.org\/10.1145\/3503513","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2022,2,12]]},"assertion":[{"value":"2021-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-02-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}