{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:24:57Z","timestamp":1750307097538,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,10,1]],"date-time":"2012-10-01T00:00:00Z","timestamp":1349049600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Comput. Entertain."],"published-print":{"date-parts":[[2012,10]]},"abstract":"<jats:p>In massively multiplayer online games (MMOGs) there is a great demand for high bandwidth connections with irregular access patterns. Such irregular demand is because players, who can vary from a few hundred to several tens of thousands, often occupy the virtual environment of the game in different ways with varying densities. Hence there is a great need for decentralized architectures with multiple servers that employ load-balancing algorithms to manage regions of the virtual environment. In such systems, each player only connects to the server that manages the region where the player's avatar is located, whereas each server is responsible for mediating the interaction between all pairs of players connected to it. Devising the proper load-balancing algorithm so that it takes spatial and variable occupations into account is a challenging problem which requires adaptive (and possibly dynamic) partitioning of the virtual environment. In this work, we propose the use of a kd-tree for partitioning the game environment into regions, and dynamically adjust the resulting subdivisions based on the distribution of avatars in the virtual environment. We compared our algorithm to competing approaches found in the literature and demonstrated that our algorithm performed better in most aspects we analyzed.<\/jats:p>","DOI":"10.1145\/2381876.2381881","type":"journal-article","created":{"date-parts":[[2012,12,11]],"date-time":"2012-12-11T13:13:42Z","timestamp":1355231622000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Adaptive load-balancing for MMOG servers using KD-trees"],"prefix":"10.1145","volume":"10","author":[{"given":"Carlos Eduardo B.","family":"Bezerra","sequence":"first","affiliation":[{"name":"Universidade Federal do Rio Grande do Sul, Porto Alegre - RS - Brasil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jo\u00e3o L. D.","family":"Comba","sequence":"additional","affiliation":[{"name":"Universidade Federal do Rio Grande do Sul, Porto Alegre - RS - Brasil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cl\u00e1udio F. R.","family":"Geyer","sequence":"additional","affiliation":[{"name":"Universidade Federal do Rio Grande do Sul, Porto Alegre - RS - Brasil"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,12,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Ahmed D. and Shirmohammadi S. 2008. A microcell oriented load balancing model for collaborative virtual environments. In VECIMS. 86--91.  Ahmed D. and Shirmohammadi S. 2008. A microcell oriented load balancing model for collaborative virtual environments. In VECIMS. 86--91.","DOI":"10.1109\/VECIMS.2008.4592758"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1230040.1230067"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Bentley J. 1975. Multidimensional binary search trees used for associative searching.  Bentley J. 1975. Multidimensional binary search trees used for associative searching.","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/570758.570761"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/DS-RT.2008.11"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11042-009-0302-z"},{"key":"e_1_2_1_7_1","unstructured":"Blizzard. 2004. World of Warcraft. http:\/\/www.worldofwarcraft.com\/.  Blizzard. 2004. World of Warcraft. http:\/\/www.worldofwarcraft.com\/."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378191.1378208"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1063723.1063731"},{"key":"e_1_2_1_10_1","unstructured":"Gravity. 2001. Raganar online. http:\/\/www.ragnarokonline.com\/.  Gravity. 2001. Raganar online. http:\/\/www.ragnarokonline.com\/."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1230040.1230058"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1016540.1016549"},{"volume-title":"Proceedings of the IEEE Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), IEEE, Washington, D.C., 96--107","author":"Knutsson B.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008653.1008681"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1053427.1053457"},{"volume-title":"Lineage ii","year":"2003","author":"Ncsoft","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/585740.585768"},{"volume-title":"Proceedings of the 4th IEEE Consumer Communications and Networking Conference (CCNC), IEEE, Washington, D.C., 763--767","author":"Rieche S.","key":"e_1_2_1_18_1"},{"volume-title":"Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann","author":"Samet H.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCGRID.2007.97"}],"container-title":["Computers in Entertainment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2381876.2381881","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2381876.2381881","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:34:46Z","timestamp":1750239286000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2381876.2381881"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["10.1145\/2381876.2381881"],"URL":"https:\/\/doi.org\/10.1145\/2381876.2381881","relation":{},"ISSN":["1544-3574"],"issn-type":[{"type":"electronic","value":"1544-3574"}],"subject":[],"published":{"date-parts":[[2012,10]]},"assertion":[{"value":"2011-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-12-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}