Ajwani, Deepak

Thumbnail Image
Preferred name
Ajwani, Deepak
Official Name
Ajwani, Deepak

Research Output

Filters

3
3
Reset filters

Settings

Now showing 1 - 3 of 3
  • Publication
    I/O-efficient Hierarchical Diameter Approximation
    (Springer, 2012-10)
    Ajwani, Deepak 
    ;
    Meyer, Ulrich 
    ;
    Veith, David 
    Computing diameters of huge graphs is a key challenge in complex network analysis. As long as the graphs fit into main memory, diameters can be efficiently approximated (and frequently even exactly determined) using heuristics that apply a limited number of BFS traversals. If the input graphs have to be kept and processed on external storage, even a single BFS run may cause an unacceptable amount of time-consuming I/O-operations. Meyer [17] proposed the first parameterized diameter approximation algorithm with fewer I/Os than that required for exact BFS traversal. In this paper we derive hierarchical extensions of this randomized approach and experimentally compare their trade-offs between actually achieved running times and approximation ratios. We show that the hierarchical approach is frequently capable of producing surprisingly good diameter approximations in shorter time than BFS. We also provide theoretical and practical insights into worst-case input classes.
      402Scopus© Citations 3
  • Publication
    Realistic Computer Models
    (Springer, 2010-01-01)
    Ajwani, Deepak 
    ;
    Meyerhenke, Henning 
    Many real-world applications involve storing and processing large amounts of data. These data sets need to be either stored over the memory hierarchy of one computer or distributed and processed over many parallel computing devices or both. In fact, in many such applications, choosing a realistic computation model proves to be a critical factor in obtaining practically acceptable solutions. In this chapter, we focus on realistic computation models that capture the running time of algorithms involving large data sets on modern computers better than the traditional RAM (and its parallel counterpart PRAM) model.
      883Scopus© Citations 3
  • Publication
    On Computational Models for Flash Memory Devices
    (Springer, 2009-08-20)
    Ajwani, Deepak 
    ;
    Beckmann, Andreas 
    ;
    Jacob, Riko 
    ;
    et al. 
    Flash memory-based solid-state disks are fast becoming the dominant form of end-user storage devices, partly even replacing the traditional hard-disks. Existing two-level memory hierarchy models fail to realize the full potential of flash-based storage devices. We propose two new computation models, the general flash model and the unit-cost model, for memory hierarchies involving these devices. Our models are simple enough for meaningful algorithm design and analysis. In particular, we show that a broad range of existing external-memory algorithms and data structures based on the merging paradigm can be adapted efficiently into the unit-cost model. Our experiments show that the theoretical analysis of algorithms on our models corresponds to the empirical behavior of algorithms when using solid-state disks as external memory.
      415Scopus© Citations 14