{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T16:25:21Z","timestamp":1776356721811,"version":"3.51.2"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2014,8,27]],"date-time":"2014-08-27T00:00:00Z","timestamp":1409097600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2014,12]]},"DOI":"10.1007\/s00446-014-0229-0","type":"journal-article","created":{"date-parts":[[2014,8,26]],"date-time":"2014-08-26T17:23:19Z","timestamp":1409073799000},"page":"393-417","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["The CB tree: a practical concurrent self-adjusting search tree"],"prefix":"10.1007","volume":"27","author":[{"given":"Yehuda","family":"Afek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boris","family":"Korenfeld","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"Morrison","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,8,27]]},"reference":[{"key":"229_CR1","unstructured":"Project Gutenberg. http:\/\/www.gutenberg.org\/"},{"key":"229_CR2","doi-asserted-by":"crossref","unstructured":"Afek, Y., Kaplan, H., Korenfeld, B., Morrison, A., Tarjan, R.E.: CBTree: a practical concurrent self-adjusting search tree. In: Proceedings of the 26th International Conference on Distributed Computing (DISC 2012), Volume 7611 of LNCS, pp. 1\u201315. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-33651-5_1"},{"key":"229_CR3","doi-asserted-by":"crossref","unstructured":"Aspnes, J., Attiya, H., Censor, K.: Max registers, counters, and monotone circuits. In: Proceedings of the 28th ACM Symposium on Principles of Distributed Computing. PODC \u201909, pp. 36\u201345. ACM, New York, NY (2009)","DOI":"10.1145\/1582716.1582728"},{"issue":"2","key":"229_CR4","doi-asserted-by":"crossref","first-page":"25:1","DOI":"10.1145\/1721837.1721841","volume":"6","author":"J Aspnes","year":"2010","unstructured":"Aspnes, J., Censor, K.: Approximate shared-memory counting despite a strong adversary. ACM Trans. Algorithms 6(2), 25:1\u201325:23 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"229_CR5","doi-asserted-by":"crossref","unstructured":"Baer, J.-L.: Weight-balanced trees. In: American Federation of Information Processing Societies: 1975 National Computer Conference. AFIPS \u201975, pp. 467\u2013472. ACM, New York, NY (1975)","DOI":"10.1145\/1499949.1500040"},{"issue":"1","key":"229_CR6","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/s00453-004-1138-6","volume":"42","author":"A Bagchi","year":"2005","unstructured":"Bagchi, A., Buchsbaum, A.L., Goodrich, M.T.: Biased skip lists. Algorithmica 42(1), 31\u201348 (2005)","journal-title":"Algorithmica"},{"key":"229_CR7","unstructured":"Bayer, R., Schkolnick, M.: Concurrency of operations on b-trees. In: Stonebraker, M. (ed.) Readings in Database Systems, pp. 129\u2013139. Morgan Kaufmann Publishers Inc., San Francisco, CA (1988)"},{"key":"229_CR8","doi-asserted-by":"crossref","unstructured":"Bent, S.W., Sleator, D.D., Tarjan, R.E.: Biased 2\u20133 trees. In: Proceedings of the 21st Annual Symposium on Foundations of Computer Science. FOCS \u201980, pp. 248\u2013254. IEEE Computer Society, Washington, DC (1980)","DOI":"10.1109\/SFCS.1980.15"},{"key":"229_CR9","doi-asserted-by":"crossref","unstructured":"Bronson, N.G., Casper, J., Chafi, H., Olukotun, K.: A practical concurrent binary search tree. In: Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. PPoPP \u201910, pp. 257\u2013268. ACM, New York, NY (2010)","DOI":"10.1145\/1693453.1693488"},{"issue":"5","key":"229_CR10","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1109\/TNET.2004.836125","volume":"12","author":"L Cherkasova","year":"2004","unstructured":"Cherkasova, L., Gupta, M.: Analysis of enterprise media server workloads: access patterns, locality, content evolution, and rates of change. IEEE\/ACM Trans. Netw. 12(5), 781\u2013794 (2004)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"229_CR11","unstructured":"The CAIDA UCSD Anonymized Internet Traces 2011 \u2013 20110324. http:\/\/www.caida.org\/data\/passive\/passive_2011_dataset.xml"},{"key":"229_CR12","doi-asserted-by":"crossref","unstructured":"Crain, T., Gramoli, V., Raynal, M.: A speculation-friendly binary search tree. In: Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. PPoPP \u201912, pp. 161\u2013170. ACM, New York, NY (2012)","DOI":"10.1145\/2145816.2145837"},{"key":"229_CR13","doi-asserted-by":"crossref","unstructured":"Crain, T., Gramoli, V., Raynal, M.: A contention-friendly binary search tree. In: Proceedings of the 19th International European Conference on Parallel Processing. Euro-Par\u201913, pp. 229\u2013240. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-40047-6_25"},{"key":"229_CR14","doi-asserted-by":"crossref","unstructured":"Crain, T., Gramoli, V., Raynal, M.: No hot spot non-blocking skip list. In: IEEE 33rd International Conference on Distributed Computing Systems (ICDCS), ICDCS\u201913, pp. 196\u2013205 (2013)","DOI":"10.1109\/ICDCS.2013.42"},{"key":"229_CR15","doi-asserted-by":"crossref","unstructured":"Dice, D., Lev, Y., Moir, M.: Scalable statistics counters. In: Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures. SPAA \u201913, pp. 43\u201352. ACM, New York, NY (2013)","DOI":"10.1145\/2486159.2486182"},{"key":"229_CR16","doi-asserted-by":"crossref","unstructured":"Ellen, F., Fatourou, P., Ruppert, E., van Breugel, F.: Non-blocking binary search trees. In: Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. PODC \u201910, pp. 131\u2013140. ACM, New York, NY (2010)","DOI":"10.1145\/1835698.1835736"},{"key":"229_CR17","doi-asserted-by":"crossref","first-page":"3139","DOI":"10.1002\/j.1538-7305.1983.tb03469.x","volume":"62","author":"J Feigenbaum","year":"1983","unstructured":"Feigenbaum, J., Tarjan, R.E.: Two new kinds of biased search trees. Bell Syst. Tech. J. 62, 3139\u20133158 (1983)","journal-title":"Bell Syst. Tech. J."},{"key":"229_CR18","doi-asserted-by":"crossref","unstructured":"Gill, P., Arlitt, M., Li, Z., Mahanti, A.: YouTube traffic characterization: a view from the edge. In: Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement. IMC \u201907, pp. 15\u201328. ACM, New York, NY (2007)","DOI":"10.1145\/1298306.1298310"},{"key":"229_CR19","doi-asserted-by":"crossref","unstructured":"Hanke, S., Ottmann, T., Soisalon-Soininen, E.: Relaxed balanced red-black trees. In: Proceedings of the 3rd Italian Conference on Algorithms and Complexity, pp. 193\u2013204. Springer, Berlin (1997)","DOI":"10.1007\/3-540-62592-5_72"},{"key":"229_CR20","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Lev, Y., Luchangco, V., Shavit, N.: A simple optimistic skiplist algorithm. In: Proceedings of the 14th International Conference on Structural Information and Communication Complexity. SIROCCO\u201907, pp. 124\u2013138. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-72951-8_11"},{"key":"229_CR21","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/78969.78972","volume":"12","author":"MP Herlihy","year":"1990","unstructured":"Herlihy, M.P., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. (TOPLAS) 12, 463\u2013492 (1990)","journal-title":"ACM Trans. Program. Lang. Syst. (TOPLAS)"},{"key":"229_CR22","volume-title":"The Art of Computer Programming, Volume 3: Sorting and Searching","author":"DE Knuth","year":"1998","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume 3: Sorting and Searching. Addison Wesley Longman Publishing Co. Inc., Redwood City, CA (1998)"},{"issue":"3","key":"229_CR23","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1109\/65.844496","volume":"14","author":"A Mahanti","year":"2000","unstructured":"Mahanti, A., Williamson, C., Eager, D.: Traffic analysis of a web proxy caching hierarchy. IEEE Netw. 14(3), 16\u201323 (2000)","journal-title":"IEEE Netw."},{"issue":"3","key":"229_CR24","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1051\/ita\/1981150301831","volume":"15","author":"K Mehlhorn","year":"1981","unstructured":"Mehlhorn, K.: Arbitrary weight changes in dynamic trees. RAIRO Theor. Inf. Appl. (Informatique Th\u00e9orique et Applications) 15(3), 183\u2013211 (1981)","journal-title":"RAIRO Theor. Inf. Appl. (Informatique Th\u00e9orique et Applications)"},{"key":"229_CR25","unstructured":"Munro, Ian: J., Papadakis, T., Sedgewick, R.: Deterministic skip lists. In: Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA \u201992, pp. 367\u2013375. Society for Industrial and Applied Mathematics, Philadelphia, PA (1992)"},{"key":"229_CR26","doi-asserted-by":"crossref","unstructured":"Nievergelt, J., Reingold, E.M.: Binary search trees of bounded balance. In: Proceedings of the Fourth Annual ACM symposium on Theory of Computing. STOC \u201972, pp. 137\u2013142. ACM, New York, NY (1972)","DOI":"10.1145\/800152.804906"},{"key":"229_CR27","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/78973.78977","volume":"33","author":"W Pugh","year":"1990","unstructured":"Pugh, W.: Skip lists: a probabilistic alternative to balanced trees. Commun. ACM 33, 668\u2013676 (1990)","journal-title":"Commun. ACM"},{"key":"229_CR28","unstructured":"Savochkin, A.V.: Linux inetpeer: storage for permanent information about peers. net\/ipv4\/inetpeer.c, Linux kernel source code (2013)"},{"key":"229_CR29","volume-title":"Algorithms in C++, Parts 1\u20134: Fundamentals, Data Structure, Sorting, Searching","author":"R Sedgewick","year":"1998","unstructured":"Sedgewick, R.: Algorithms in C++, Parts 1\u20134: Fundamentals, Data Structure, Sorting, Searching, 3rd edn. Addison-Wesley Professional, Reading, MA (1998)","edition":"3"},{"key":"229_CR30","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1007\/BF01940876","volume":"16","author":"R Seidel","year":"1996","unstructured":"Seidel, R., Aragon, C.R.: Randomized search trees. Algorithmica 16, 464\u2013497 (1996). doi: 10.1007\/s004539900061","journal-title":"Algorithmica"},{"key":"229_CR31","unstructured":"Sleator, D.D.: Splay tree implementation. http:\/\/www.link.cs.cmu.edu\/splay"},{"key":"229_CR32","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM 32, 652\u2013686 (1985)","journal-title":"J. ACM"},{"issue":"2","key":"229_CR33","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1137\/0606031","volume":"6","author":"RE Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Amortized computational complexity. SIAM J. Algebraic Discret. Methods 6(2), 306\u2013318 (1985)","journal-title":"SIAM J. Algebraic Discret. Methods"},{"key":"229_CR34","unstructured":"Zink, M., Suh, K., Gu, Y., Kurose, J.: Watch global, cache local: YouTube network traffic at a campus network: measurements and implications. In: Proceedings of the 15th SPIE\/ACM Multimedia Computing and Networking Conference, 6818:28 (2008)"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-014-0229-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-014-0229-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-014-0229-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,14]],"date-time":"2019-08-14T05:51:06Z","timestamp":1565761866000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-014-0229-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,27]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2014,12]]}},"alternative-id":["229"],"URL":"https:\/\/doi.org\/10.1007\/s00446-014-0229-0","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8,27]]}}}