{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,18]],"date-time":"2024-07-18T01:36:27Z","timestamp":1721266587836},"reference-count":32,"publisher":"IGI Global","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,1,1]]},"abstract":"<p>Although there have been many compression schemes for reducing data effectively, most schemes do not consider the reordering of data. In the case of unordered data, if the users change the data order in a given data set, the compression ratio may be improved compared to the original compression before reordering data. However, in the case of ordered data, the users need a mapping table that maps the original position to the changed position in order to recover the original order. Therefore, reordering ordered data may be disadvantageous in terms of space. In this paper, the authors consider two compression schemes, run-length encoding and bucketing scheme as bases for showing the impact of data reordering in compression schemes. Also, the authors propose various optimization techniques related to data reordering. Finally, the authors show that the compression schemes with data reordering are better than the original compression schemes in terms of the compression ratio.<\/p>","DOI":"10.4018\/jdm.2014010101","type":"journal-article","created":{"date-parts":[[2014,6,27]],"date-time":"2014-06-27T12:18:44Z","timestamp":1403871524000},"page":"1-28","source":"Crossref","is-referenced-by-count":2,"title":["Compression Schemes with Data Reordering for Ordered Data"],"prefix":"10.4018","volume":"25","author":[{"given":"Chun-Hee","family":"Lee","sequence":"first","affiliation":[{"name":"Department of Computer Science, KAIST (Korea Advanced Institute of Science and Technology), Daejeon, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chin-Wan","family":"Chung","sequence":"additional","affiliation":[{"name":"Department of Computer Science, KAIST (Korea Advanced Institute of Science and Technology), Daejeon, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"2432","reference":[{"key":"jdm.2014010101-0","doi-asserted-by":"crossref","unstructured":"Abadi, D. J., Madden, S., & Ferreira, M. (2006). Integrating compression and execution in column-oriented database systems. In Proceedings of the ACM SIGMOD International Conference on Management of Data, Chicago, IL (pp. 671\u2013682).","DOI":"10.1145\/1142473.1142548"},{"key":"jdm.2014010101-1","doi-asserted-by":"crossref","unstructured":"Apaydin, T., Tosun, A. S., & Ferhatosmanoglu, H. (2008). Analysis of basic data reordering techniques. In Proceedings of the Scientific and Statistical Database Management Conference (SSDBM), Hong Kong, China (pp. 517-524).","DOI":"10.1007\/978-3-540-69497-7_33"},{"key":"jdm.2014010101-2","doi-asserted-by":"crossref","unstructured":"Blandford, D., & Blelloch, G. (2002). Index compression through document reordering. In Proceedings of the Data Compression Conference (DCC), Snowbird, UT (pp. 342-351).","DOI":"10.1109\/DCC.2002.999972"},{"key":"jdm.2014010101-3","doi-asserted-by":"crossref","unstructured":"Buragohain, C., Shrivastava, N., & Suri, S. (2007). Space efficient streaming algorithms for the maximum error histogram. In Proceedings of the International Conference on Data Engineering (ICDE), Istanbul, Turkey (pp. 1026\u20131035).","DOI":"10.1109\/ICDE.2007.368961"},{"key":"jdm.2014010101-4","author":"M.Burrows","year":"1994","journal-title":"Block-sorting lossless data compression algorithm"},{"key":"jdm.2014010101-5","unstructured":"Chen, H., Li, J., & Mohapatra, P. (2004). RACE: Time series compression with rate adaptivity and error bound for sensor networks. In Proceedings of the IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), Fort Lauderdale, FL (pp. 124-133)."},{"key":"jdm.2014010101-6","doi-asserted-by":"crossref","unstructured":"Chen, Y., Dong, G., Han, J., Wah, B. W., & Wan, J. (2002). Multi-dimensional regression analysis of time-series data stream. In Proceedings of the Very Large Data Bases (VLDB), Hong Kong, China (pp. 323-334).","DOI":"10.1016\/B978-155860869-6\/50036-6"},{"key":"jdm.2014010101-7","unstructured":"DataSet. (2012). Earth climate and weather. Retrieved October 1, 2012, from http:\/\/www-k12.atmos.washington.edu\/k12\/grayskies\/"},{"key":"jdm.2014010101-8","doi-asserted-by":"crossref","unstructured":"Degermark, M., Engan, M., Nordgren, B., & Pink, S. (1996). Low-loss tcp\/ip header compression for wireless networks. In Proceedings of the International Conference on Mobile Computing and Networking (MOBICOM), Rye (pp. 1\u201314).","DOI":"10.1145\/236387.236388"},{"key":"jdm.2014010101-9","doi-asserted-by":"crossref","unstructured":"Deligiannakis, A., Kotidis, Y., & Roussopoulos, N. (2004). Compressing historical information in sensor networks. In Proceedings of the ACM SIGMOD International Conference on Management of Data, Paris, France (pp. 527-538).","DOI":"10.1145\/1007568.1007628"},{"key":"jdm.2014010101-10","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0173-5"},{"key":"jdm.2014010101-11","doi-asserted-by":"publisher","DOI":"10.1109\/18.119733"},{"key":"jdm.2014010101-12","doi-asserted-by":"crossref","unstructured":"Elmeleegy, H., Elmagarmid, A. K., Cecchet, E., Aref, W. G., & Zwaenepoel, W. (2009). Online piece-wise linear approximation of numerical streams with precision guarantees. In Proceedings of the VLDB Endowment (PVLDB), Lyon, France (pp. 145-156).","DOI":"10.14778\/1687627.1687645"},{"key":"jdm.2014010101-13","doi-asserted-by":"crossref","unstructured":"Gandhi, S., Nath, S., Suri, S., & Lie, J. (2009). GAMPS: Compressing multi sensor data by grouping and amplitude scaling. In Proceedings of the ACM SIGMOD International Conference on Management of Data, Providence, RI (pp. 771-784).","DOI":"10.1145\/1559845.1559926"},{"key":"jdm.2014010101-14","doi-asserted-by":"crossref","unstructured":"Goldstein, J., Ramakrishnan, R., & Shaft, U. (1998). Compressing relations and indexes. In Proceedings of the International Conference on Data Engineering (ICDE), Orlando, FL (pp. 370\u2013379).","DOI":"10.1109\/ICDE.1998.655800"},{"key":"jdm.2014010101-15","doi-asserted-by":"crossref","unstructured":"Graefe, G., & Shapiro, L. D. (1991). Data compression and database performance. In Proceedings of the ACM\/IEEE-CS Symp. On Applied Computing (pp. 22\u201327).","DOI":"10.1109\/SOAC.1991.143840"},{"key":"jdm.2014010101-16","doi-asserted-by":"crossref","unstructured":"Hai, P. N., Lenco, D., Poncelet, P., & Teisseire, M. (2013). Mining representative movement patterns through compression. Advances in Knowledge Discovery and Data mining, 7818, 314-326.","DOI":"10.1007\/978-3-642-37453-1_26"},{"key":"jdm.2014010101-17","unstructured":"Iyer, B. R., & Wilhite, D. (1994). Data compression support in databases. In Proceedings of the Very Large Data Bases (VLDB), Santiago, Chile, (pp. 695\u2013704)."},{"key":"jdm.2014010101-18","doi-asserted-by":"crossref","unstructured":"Johnson, D., Krishnan, S., Chhugani, J., Kumar, S., & Venkatasubramanian, S. (2004). Compressing large boolean matrices using reordering techniques. In Proceedings of the Very Large Data Bases (VLDB), Toronto, Canada (pp. 13-23).","DOI":"10.1016\/B978-012088469-8.50005-X"},{"key":"jdm.2014010101-19","unstructured":"Johnson, T. (1999). Performance measurements of compressed bitmap indice. In Proceedings of the Very Large Data Bases (VLDB), Edinburgh, Scotland (pp. 278-289)."},{"key":"jdm.2014010101-20","doi-asserted-by":"crossref","unstructured":"Korn, F., Jagadish, H. V., & Faloutsos, C. (1997). Efficiently supporting ad hoc queries in large datasets of time sequences. In Proceedings of the ACM SIGMOD International Conference on Management of Data, Tucson, AZ (pp. 289-300).","DOI":"10.1145\/253262.253332"},{"key":"jdm.2014010101-21","doi-asserted-by":"crossref","unstructured":"Liu, W., Kan, A., Chan, J., Bailey, J., Leckie, C., Pei, J., & Ramamohanarao, K. (2012). On compressing weighted time-evolving graphs. In Proceedings of the ACM International Conference on Information and Knowledge Management (CIKM), Maui, HI (pp. 2319-2322).","DOI":"10.1145\/2396761.2398630"},{"key":"jdm.2014010101-22","doi-asserted-by":"crossref","unstructured":"Ouyang, Z., Memon, N., Suel, T., & Trendafilov, D. (2002). Cluster-based delta compression of a collection of files. In Proceedings of the International Conference on Web Information Systems Engineering (WISE), Singapore (pp. 257-268).","DOI":"10.1109\/WISE.2002.1181662"},{"key":"jdm.2014010101-23","author":"W. B.Pennebaker","year":"1993","journal-title":"Still image data compression standards"},{"key":"jdm.2014010101-24","doi-asserted-by":"crossref","unstructured":"Pinar, A., Tao, T., & Ferhatosmanoglu, H. (2005). Compressing bitmap indices by data reorganization. In Proceedings of the International Conference on Data Engineering (ICDE), Tokyo, Japan (pp. 310-321).","DOI":"10.1109\/ICDE.2005.35"},{"key":"jdm.2014010101-25","author":"K. R.Rao","year":"1990","journal-title":"Discrete cosine transforms - Algorithms, advantages, applications"},{"key":"jdm.2014010101-26","unstructured":"Ray, G., Haritsa, J. R., & Seshadri, S. (1995). Database compression: A performance enhancement tool. In Proceedings of the International Conference on Management of Data (COMAD), Pune, India."},{"key":"jdm.2014010101-27","doi-asserted-by":"crossref","unstructured":"Reeves, G., Liu, J., Nath, S., & Zhao, F. (2009). Managing massive time series streams with multi-scale compressed trickles. In Proceedings of the VLDB Endowment (PVLDB), Lyon, France (pp. 97-108).","DOI":"10.14778\/1687627.1687639"},{"key":"jdm.2014010101-28","author":"D.Salomon","year":"2004","journal-title":"Data compression: The complete reference"},{"key":"jdm.2014010101-29","doi-asserted-by":"crossref","unstructured":"Toivonen, H., Zhou, F., Hartikainen, A., & Hinkka, A. (2011). Compression of weighted graphs. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA (pp. 965-973).","DOI":"10.1145\/2020408.2020566"},{"key":"jdm.2014010101-30","unstructured":"Wikipedia. (2012). Run-legnth encoding. Retrieved October 1, 2012, from http:\/\/en.wikipedia.org\/wiki\/Run-length_encoding"},{"key":"jdm.2014010101-31","doi-asserted-by":"publisher","DOI":"10.4018\/jdm.2006070102"}],"container-title":["Journal of Database Management"],"original-title":[],"language":"ng","link":[{"URL":"https:\/\/www.igi-global.com\/viewtitle.aspx?TitleId=109930","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T20:09:54Z","timestamp":1654114194000},"score":1,"resource":{"primary":{"URL":"https:\/\/services.igi-global.com\/resolvedoi\/resolve.aspx?doi=10.4018\/jdm.2014010101"}},"subtitle":[""],"short-title":[],"issued":{"date-parts":[[2014,1,1]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"URL":"https:\/\/doi.org\/10.4018\/jdm.2014010101","relation":{},"ISSN":["1063-8016","1533-8010"],"issn-type":[{"value":"1063-8016","type":"print"},{"value":"1533-8010","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1,1]]}}}