An Investigative Study on Cache-Oblivious Data Structures

Year : 2024 | Volume :01 | Issue : 02 | Page : 33-37
By

Dwarampudi Aiswarya

Manas Kumar Yogi

  1. Assistant Professor Department of Computer Science and Engineering, Pragati Engineering College (Autonomous), Surampalem Andhra Pradesh India
  2. Assistant Professor Department of Computer Science and Engineering, Pragati Engineering College (Autonomous), Surampalem Andhra Pradesh India

Abstract

Cache-oblivious data structures and data management systems have emerged as critical components in modern computing environments, aiming to optimize memory access patterns across different levels of the memory hierarchy without explicit knowledge of cache sizes or configurations. This study presents an overview of cache-oblivious techniques, including adaptive data structures, compression, parallel processing, and security considerations. The workexplores future directions in cache-oblivious systems, such as non-volatile memory support, graph processing, edge computing, energy efficiency, and machine learning applications. Furthermore, empirical evaluation and benchmarking methodologies are discussed to assess the practical performance of cache-oblivious solutions on diverse hardware platforms and workloads. By addressing these challenges and opportunities, cache-oblivious data structures and management systems have the potential to revolutionize memory management, storage optimization, and computational efficiency in a wide range of computing domains.

Keywords: Security and Privacy, data structures, Cache-Oblivious Algorithms,

[This article belongs to International Journal of Data Structure Studies(ijdss)]

How to cite this article: Dwarampudi Aiswarya, Manas Kumar Yogi. An Investigative Study on Cache-Oblivious Data Structures. International Journal of Data Structure Studies. 2024; 01(02):33-37.
How to cite this URL: Dwarampudi Aiswarya, Manas Kumar Yogi. An Investigative Study on Cache-Oblivious Data Structures. International Journal of Data Structure Studies. 2024; 01(02):33-37. Available from: https://journals.stmjournals.com/ijdss/article=2024/view=132878





References

  1. Arge L, Brodal GS, Fagerberg R. Cache-oblivious data structures. Handbook of data structures and applications. London: Chapman and Hall/CRC; Feb 2018. pp. 545–565.
  2. Chan TH, Guo Y, Lin WK, Shi E. Cache-oblivious and data-oblivious sorting and applications. InProceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms. 2018; 2201–2220. Society for Industrial and Applied Mathematics.
  3. Bender MA, Chowdhury RA, Das R, Johnson R, Kuszmaul W, Lincoln A, Liu QC, Lynch J, Xu H. Closing the gap between cache-oblivious and cache-adaptive analysis. InProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures. 2020 Jul 6; 63–73.
  4. Bender MA, Ebrahimi R, Hu H, Kuszmaul BC. B-trees and Cache-Oblivious B-trees with Different-Sized Atomic Keys. ACM Trans Database Syst (TODS). 2016 Jul 18;41(3):1–33.
  5. Imani M, Moeini A, Ghasemi F. On The Implementation of Recursive Data Structures for Cache-Oblivious Algorithms. Int JMechtatronEletr Comput Technol (IJMEC).2016;6(21):3032–3042.
  6. Frigo M, Leiserson CE, Prokop H, Ramachandran S. Cache-oblivious algorithms. ACM Transactions on Algorithms (TALG). Jan 2012; 8(1): 1–22.
  7. Frigo M, Strumpen V. The Cache Complexity of Multithreaded Cache Oblivious Algorithms. Theory Comput Syst. 2009;45(2):203–233.
  8. Olsen JH, Skov SC. Cache-oblivious algorithms in practice. In Department of Computer Science,Denmark:University of Copenhagen; 2002 Dec 2.
  9. Wang XS, Nayak K, Liu C, Chan TH, Shi E, Stefanov E, Huang Y. Oblivious data structures. InProceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. 2014 Nov 3; 215–226.
  10. Böhm C, Perdacher M, Plant C. Cache-oblivious loops based on a novel space-filling curve. In2016 IEEE International Conference on Big Data (Big Data). 2016 Dec 5; 17–26.

Regular Issue Subscription Review Article
Volume 01
Issue 02
Received February 6, 2024
Accepted February 8, 2024
Published February 14, 2024