{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T14:54:39Z","timestamp":1754146479750,"version":"3.41.2"},"reference-count":27,"publisher":"National Library of Serbia","issue":"3","license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ComSIS","COMPUT SCI INF SYST","COMPUT SCI INFORM SY","COMPUTER SCI INFORM","COMSIS J"],"published-print":{"date-parts":[[2025]]},"abstract":"<jats:p>Compiling the statistics of large-scale IP address data is an essential task in network traffic measurement. The statistical results are used to evaluate the potential impact of user behaviors on network traffic. This requires algorithms that are capable of storing and retrieving a high volume of IP addresses within time and memory constraints. In this paper, we present two efficient algorithms for collecting the statistics of large-scale IP addresses that balance time efficiency and memory consumption. The proposed solutions take into account the sparse nature of the statistics of IP addresses while maintaining a dynamic balance among layered memory blocks. There are two layers in the first proposed method, each of which contains a limited number of memory blocks. Each memory block contains 256 elements of size 256?8 bytes for a 64-bit system. In contrast to built-in hash mapping functions, the proposed solution completely avoids expensive hash collisions while retaining the linear time complexity of hash-based solutions. Moreover, the mechanism dynamically determines the hash index length according to the range of IP addresses, and can balance the time and memory constraints. In addition, we propose an efficient parallel scheme to speed up the collection of statistics. The experimental results on several synthetic datasets show that the proposed method substantially outperforms the baselines with respect to time and memory space efficiency.<\/jats:p>","DOI":"10.2298\/csis241201033l","type":"journal-article","created":{"date-parts":[[2025,4,10]],"date-time":"2025-04-10T08:06:14Z","timestamp":1744272374000},"page":"927-944","source":"Crossref","is-referenced-by-count":0,"title":["Efficient algorithms for collecting the statistics of large-scale IP address data"],"prefix":"10.2298","volume":"22","author":[{"given":"Hui","family":"Liu","sequence":"first","affiliation":[{"name":"College of Electronic and Information, Foshan Polytechnic, Foshan, P.R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi","family":"Cao","sequence":"additional","affiliation":[{"name":"College of Electronic and Information, Foshan Polytechnic, Foshan, P.R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zehan","family":"Cai","sequence":"additional","affiliation":[{"name":"College of Electronic and Information, Foshan Polytechnic, Foshan, P.R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hua","family":"Mao","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Sciences, Northumbria University, Newcastle, U.K."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jie","family":"Chen","sequence":"additional","affiliation":[{"name":"College of Computer Science, Sichuan University, Chengdu, P.R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1078","reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"Abdel-Hafeez, S., Gordon-Ross, A.: An efficient o(n) comparison-free sorting algorithm. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 25(6), 1930-1942 (Jun 2017)","DOI":"10.1109\/TVLSI.2017.2661746"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"Agapitos, A., Lucas., S.M.: Evolving efficient recursive sorting algorithms. In: 2006 IEEE International Conference on Evolutionary Computation. pp. 2677-2684. Vancouver, BC, Canada (Jul 2016)","DOI":"10.1109\/CEC.2006.1688643"},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"Alhabboub, Y., Almutairi, F., Safhi, M., Alqahtani, Y., Almeedani, A., Alguwaifli, Y.: Accelerating large-scale sorting through parallel algorithms. Journal of Computer and Communications 12(1), 131-138 (Jan 2024)","DOI":"10.4236\/jcc.2024.121009"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"Cederman, D., Tsigas, P.: A practical quicksort algorithm for graphics processors. In: European Symposium on Algorithms. pp. 246-258 (2008)","DOI":"10.1007\/978-3-540-87744-8_21"},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"Chen, S., Qin, J., Xie, Y., Zhao, J., Heng, P.A.: A fast and flexible sorting algorithm with cuda. In: International Conference on Algorithms and Architectures for Parallel Processing. pp. 281- 290. Taipei, Taiwan, China (Jun 2009)","DOI":"10.1007\/978-3-642-03095-6_28"},{"key":"ref6","unstructured":"Cormen, T., C.Leiserson, Rivest, R., C.Stein: Introduction to Algorithms. MIT press (2009)"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"Faujdar, N., Ghrera, S.P.: Analysis and testing of sorting algorithms on a standard dataset. In: 2015 Fifth International Conference on Communication Systems and Network Technologies. pp. 1-10. Gwalior, India (Apr 2015)","DOI":"10.1109\/CSNT.2015.98"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"Fredman, M.L.: An intuitive and simple bounding argument for quicksort. Information Processing Letters 3(114), 137-139 (Mar 2014)","DOI":"10.1016\/j.ipl.2013.10.010"},{"key":"ref9","unstructured":"Hammad, J.: A comparative study between various sorting algorithms. International Journal of Computer Science and Network Security 15(3), 358-367 (Mar 2015)"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"Idrizi, F., Rustemi, A., Dalipi, F.: A new modified sorting algorithm: A comparison with state of the art. In: 2017 6th Mediterranean Conference on Embedded Computing. pp. 1-6. Bar, Montenegro (Jul 2017)","DOI":"10.1109\/MECO.2017.7977252"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"Jing, Y.N., Tu, P., Wang, X.P., Zhang, G.D.: Distributed-log-based scheme for ip traceback. In: The Fifth International Conference on Computer and Information Technology. pp. 711-715. Shanghai, China (Dec 2005)","DOI":"10.1109\/CIT.2005.99"},{"key":"ref12","unstructured":"Jing, Y.N., Tu, P., Wang, X.P., Zhang, G.D.: Space-efficient data structures for top-k completion. In: Proceedings of the 22nd international conference on World Wide Web. pp. 583-594. Rio de Janeiro, Brazil (May 2013)"},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"Jug\u00e9, V.: Adaptive shivers sort: an alternative sorting algorithm. ACM Transactions on Algorithms 20(4), 1-55 (Aug 2024)","DOI":"10.1145\/3664195"},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"Jukna, S., Seiwert, H.: Sorting can exponentially speed up pure dynamic programming. Information Processing Letters 159, 451-469 (Apr 2020)","DOI":"10.1016\/j.ipl.2020.105962"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"Kapur, E., Kumar, P., Gupta, S.: Proposal of a two way sorting algorithm and performance comparison with existing algorithms. International Journal of Computer Science, Engineering and Applications 2(3), 61-78 (Jun 2012)","DOI":"10.5121\/ijcsea.2012.2306"},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"Klein, S.T.: On the connection between hamming codes, heapsort and other methods. Information Processing Letters 113(17), 617-620 (May 2017)","DOI":"10.1016\/j.ipl.2013.05.013"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"Kocher, G., Agrawal, N.: Analysis and review of sorting algorithms. International Journal of Scientific Engineering and Research 2(3), 81-84 (Mar 2014)","DOI":"10.70729\/J2013181"},{"key":"ref18","doi-asserted-by":"crossref","unstructured":"Louza, F.A., Gog, S., Telles., G.P.: Optimal suffix sorting and lcp array construction for constant alphabets. Information Processing Letters 118, 30-34 (Sep 2017)","DOI":"10.1016\/j.ipl.2016.09.010"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"M\u00faller, I., Sanders, P., Lacurie, A., Lehner,W., F\u00e1rber, F.: Cache-efficient aggregation: Hashing is sorting. In: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. p. 1123-1136. Melbourne, Bictoria, Australia (May 2015)","DOI":"10.1145\/2723372.2747644"},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"Peters, H., Schulz-Hildebrandt, O., Luttenberger, N.: Fast in-place, comparison-based sorting with cuda: a study with bitonic sort. Concurrency and Computation: Practice and Experience 23(7), 681-693 (Jan 2011)","DOI":"10.1002\/cpe.1686"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"Puglisi, S.J., Smyth,W.F., Turpin, A.: The performance of linear time suffix sorting algorithms. In: Data Compression Conference. pp. 358-367. Snowbird, UT, USA, USA (Mar 2005)","DOI":"10.1109\/DCC.2005.87"},{"key":"ref22","doi-asserted-by":"crossref","unstructured":"Rusu, I.: Sorting signed permutations by reversals using link-cut trees. Information Processing Letters 132, 44-48 (Apr 2018)","DOI":"10.1016\/j.ipl.2017.12.005"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"Satish, N., Harris, M., Garland, M.: Designing efficient sorting algorithms for manycore gpus. In: 2009 IEEE International Symposium on Parallel & Distributed Processing. pp. 1-10. Rome, Italy (May 2009)","DOI":"10.1109\/IPDPS.2009.5161005"},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"Shabaz, M., Kumar, A.: Sa sorting: a novel sorting technique for large-scale data. Journal of Computer Networks and Communications pp. 1-7 (2019)","DOI":"10.1155\/2019\/3027578"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"Shutler, P.M.E., Sim, S.W., Lim, W.Y.S.: Analysis of linear time sorting algorithms. The Computer Journal 51(4), 451-469 (Jul 2008)","DOI":"10.1093\/comjnl\/bxm097"},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"Singh, D.P., Joshi, I., Choudhary, J.: Survey of gpu based sorting algorithms. International Journal of Parallel Programming 46(6), 1017-1034 (Apr 2018)","DOI":"10.1007\/s10766-017-0502-5"},{"key":"ref27","unstructured":"Yang, M., Zhang, P., Fang, J., Liu, W., Huang, C.: thsort: an efficient parallel sorting algorithm on multi-core dsps. CCF Transactions on High Performance Computing 20(4), 1-16 (Jan 2024)"}],"container-title":["Computer Science and Information Systems"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,7,18]],"date-time":"2025-07-18T09:18:22Z","timestamp":1752830302000},"score":1,"resource":{"primary":{"URL":"https:\/\/doiserbia.nb.rs\/Article.aspx?ID=1820-02142500033L"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025]]}},"URL":"https:\/\/doi.org\/10.2298\/csis241201033l","relation":{},"ISSN":["1820-0214","2406-1018"],"issn-type":[{"type":"print","value":"1820-0214"},{"type":"electronic","value":"2406-1018"}],"subject":[],"published":{"date-parts":[[2025]]}}}