Abstract
The input/output complexity, which is the complexity of data exchange between the main memory and the external memory, has been elaborately studied by a lot of former researchers. However, the existing works failed to consider the input/output complexity in a computation model point of view. In this paper we remedy this by proposing three variants of Turing machine that include external memory and the mechanism of exchanging data between main memory and external memory. Based on these new models, the input/output complexity is deeply studied. We discuss the relationship between input/output complexity and the other complexity measures such as time complexity and parameterized complexity, which is not considered by former researchers. We also define the external access trace complexity, which reflects the physical behavior of magnetic disks and gives a theoretical evidence of IO-efficient algorithms.
This work was supported by the National Natural Science Foundation of China under grants 61832003, 61972110, U1811461, and National Key Research and Development Program of China under grants 2021YFF1200100 and 2021YFF1200104.
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
Aggarwal, A., Alpern, B., Chandra, A., Snir, M.: A model for hierarchical memory. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pp. 305–314 (1987)
Aggarwal, A., Vitter, J.S.: The input/output complexity of sorting and related problems. Commun. ACM 31(9), 1116–1127 (1988)
Alexander, W., Copeland, G.: Process and dataflow control in distributed data-intensive systems. ACM SIGMOD Rec. 17(3), 90–98 (1988)
Alpern, B., Carter, L., Feig, E., Selker, T.: The uniform memory hierarchy model of computation. Algorithmica 12(2), 72–109 (1994)
Armen, C.: Bounds on the separation of two parallel disk models. In: Proceedings of the Fourth Workshop on I/O in Parallel and Distributed Systems: Part of the Federated Computing Research Conference, pp. 122–127 (1996)
Copeland, G., Alexander, W., Boughter, E., Keller, T.: Data placement in bubba. In: Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, pp. 99–108 (1988)
Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity, vol. 4. Springer, Cham (2013)
Elworth, R.L., et al.: To petabytes and beyond: recent advances in probabilistic and signal processing algorithms and their application to metagenomics. Nucleic Acids Res. 48(10), 5217–5234 (2020)
Gao, X., Li, J., Miao, D., Liu, X.: Recognizing the tractability in big data computing. Theor. Comput. Sci. 838, 195–207 (2020)
Gorton, I., Greenfield, P., Szalay, A., Williams, R.: Data-intensive computing in the 21st century. Computer 41(4), 30–32 (2008)
Johnston, W.E.: High-speed, wide area, data intensive computing: a ten year retrospective. In: Proceedings the Seventh International Symposium on High Performance Distributed Computing (Cat. No. 98TB100244), pp. 280–291. IEEE (1998)
Kouzes, R.T., Anderson, G.A., Elbert, S.T., Gorton, I., Gracio, D.K.: The changing paradigm of data-intensive computing. Computer 42(1), 26–34 (2009)
Ma, H., Li, J., Gao, X., Gao, T.: Turing machines with two-level memory: a deep look into the input/output complexity (2022). https://arxiv.org/abs/2208.09803
Maheshwari, A., Zeh, N.: A survey of techniques for designing I/O-efficient algorithms. In: Meyer, U., Sanders, P., Sibeyn, J. (eds.) Algorithms for Memory Hierarchies. LNCS, vol. 2625, pp. 36–61. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36574-5_3
O’Neil, P., Cheng, E., Gawlick, D., O’Neil, E.: The log-structured merge-tree (LSM-tree). Acta Informatica 33(4), 351–385 (1996). https://doi.org/10.1007/s002360050048
Pagh, R., Silvestri, F.: The input/output complexity of triangle enumeration. In: Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 224–233 (2014)
Pagh, R., Stöckel, M.: The input/output complexity of sparse matrix multiplication. In: Schulz, A.S., Wagner, D. (eds) European Symposium on Algorithms, vol. 8737, pp. 750–761. Springer, Cham (2014). https://doi.org/10.1007/978-3-662-44777-2_62
Pandis, I.: The evolution of amazon redshift. Proc. VLDB Endowment 14(12), 3162–3174 (2021)
Raju, B., et al.: Big data, machine learning, and artificial intelligence: a field guide for neurosurgeons. J. Neurosurg. 1(aop), 1–11 (2020)
Ruemmler, C., Wilkes, J.: UNIX Disk Access Patterns. Hewlett-Packard Laboratories, Palo Alto (1992)
Simitci, H., Reed, D.A.: A comparison of logical and physical parallel I/O patterns. Int. J. High Perform. Comput. Appl. 12(3), 364–380 (1998)
Ullman, J.D., Yannakakis, M.: The input/output complexity of transitive closure. Ann. Math. Artif. Intell. 3(2), 331–360 (1991)
Vitter, J.S.: External memory algorithms and data structures: dealing with massive data. ACM Comput. Surv. (CsUR) 33(2), 209–271 (2001)
Zhang, Y.Q.: Dram (h): a parallel computation model for high performance numerical computing. Chin. J. Comput.-Chin. Ed. 26(12), 1660–1670 (2003)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Ma, H., Li, J., Gao, X., Gao, T. (2022). Turing Machines with Two-Level Memory: A Deep Look into the Input/Output Complexity. In: Zhang, Y., Miao, D., Möhring, R. (eds) Computing and Combinatorics. COCOON 2022. Lecture Notes in Computer Science, vol 13595. Springer, Cham. https://doi.org/10.1007/978-3-031-22105-7_18
Download citation
DOI: https://doi.org/10.1007/978-3-031-22105-7_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-22104-0
Online ISBN: 978-3-031-22105-7
eBook Packages: Computer ScienceComputer Science (R0)