Abstract
With the tremendous development of data acquisition technology, massive observation data have been accumulated in scientific disciplines. As the difference between the successive observations only changes slightly, it is critical to utilize multi-version data management technology to compress data to minimize both storage and recreation. However, the existing work on this field only optimizes the total storage and recreation costs, but ignores the recreation cost of some special versions. Consequently, in this paper, we investigate the trade-off among all of three metrics, including total storage cost, total recreation cost, and the maximum recreation cost for each version. We formulate two problems, including (1) discover a storage plan to lower the total recreation and the individual recreation if the total storage is limited; (2) find a storage plan to minimize the total storage with restricted total recreation and individual recreation. To solve above problems, we model all versions with a directed graph and then devise two efficient algorithms based on spanning tree. A series of experiments indicate that our proposals are effective and efficient in dealing with the problems.
Supported by the National Key Research and Development Program of China (2016YFB1000905), NSFC (61532021, U1501252, U1401256 and 61402180).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Large Synoptic Survey Telescope. http://www.lsst.org/
Baumann, P.: Standardizing big earth datacubes. In: 2017 IEEE International Conference on Big Data (Big Data), pp. 67–73. IEEE (2017)
Bhattacherjee, S., Chavan, A., Huang, S., Deshpande, A., Parameswaran, A.: Principles of dataset versioning: exploring the recreation/storage tradeoff. VLDB Endow. 8(12), 1346–1357 (2015)
Chan, T.N., Yiu, M.L., Hua, K.A.: Efficient sub-window nearest neighbor search on matrix. IEEE Trans. Knowl. Data Eng. 29(4), 784–797 (2017)
Chavan, A., Deshpande, A.: DEX: query execution in a delta-based storage system. In: Proceedings of the 2017 ACM International Conference on Management of Data, pp. 171–186. ACM (2017)
Cormen, T.H.: Introduction to Algorithms. MIT press, Cambridge (2009)
Cudré-Mauroux, P., Kimura, H., Lim, K.T., Rogers, J., Simakov, R., Soroush, E., Velikhov, P., Wang, D.L., Balazinska, M., Becla, J., et al.: A demonstration of SciDB: a science-oriented DBMS. VLDB Endow. 2(2), 1534–1537 (2009)
Gosain, A., Saroha, K.: Storage structure for handling schema versions in temporal data warehouses. In: Sa, P.K., Sahoo, M.N., Murugappan, M., Wu, Y., Majhi, B. (eds.) Progress in Intelligent Computing Techniques: Theory, Practice, and Applications. AISC, vol. 518, pp. 501–511. Springer, Singapore (2018). https://doi.org/10.1007/978-981-10-3373-5_50
Li, J., Kawashima, H., Tatebe, O.: Efficient window aggregate method on array database system. J. Inf. Process. 24(6), 867–877 (2016)
Prim, R.C.: Shortest connection networks and some generalizations. Bell Labs Tech. J. 36(6), 1389–1401 (1957)
Rusu, F., Cheng, Y.: A survey on array storage, query languages, and systems. arXiv preprint arXiv:1302.0103 (2013)
Seering, A., Cudre-Mauroux, P., Madden, S., Stonebraker, M.: Efficient versioning for scientific array databases. In: 2012 IEEE 28th International Conference on Data Engineering (ICDE), pp. 1013–1024. IEEE (2012)
Soroush, E., Balazinska, M.: Time travel in a scientific array database. In: 29th Data Engineering (ICDE), pp. 98–109. IEEE (2013)
Soroush, E., Balazinska, M., Krughoff, S., Connolly, A.: Efficient iterative processing in the SciDB parallel array engine. In: 27th International Conference on Scientific and Statistical Database Management, p. 39. ACM (2015)
Soroush, E., Balazinska, M., Wang, D.: ArrayStore: a storage manager for complex parallel array processing. In: 2011 ACM SIGMOD International Conference on Management of data, pp. 253–264. ACM (2011)
Tansel, A.U., Clifford, J., Gadia, S.K., Jajodia, S., Segev, A., Snodgrass, R.T. (eds.): Temporal Databases: Theory, Design, and Implementation. Benjamin/Cummings, San Francisco
Zhang, Y., Xu, F., Frise, E., Wu, S., Yu, B., Xu, W.: DataLab: a version data management and analytics system. In: 2nd International Workshop on BIG Data Software Engineering, pp. 12–18. ACM (2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Zhang, Y., Liu, H., Jin, C., Guo, Y. (2018). Storage and Recreation Trade-Off for Multi-version Data Management. In: Cai, Y., Ishikawa, Y., Xu, J. (eds) Web and Big Data. APWeb-WAIM 2018. Lecture Notes in Computer Science(), vol 10988. Springer, Cham. https://doi.org/10.1007/978-3-319-96893-3_30
Download citation
DOI: https://doi.org/10.1007/978-3-319-96893-3_30
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-96892-6
Online ISBN: 978-3-319-96893-3
eBook Packages: Computer ScienceComputer Science (R0)