No description, website, or topics provided.
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.

Railway Adaptive Storage for Interaction Graphs


This repository contains an adaptive disk layout called the railway layout for optimizing disk block storage for interaction graphs. The key idea is to divide blocks into one or more sub-blocks, where each sub-block contains a subset of the attributes, but the entire graph structure is replicated within each sub-block. This improves query I/O, at the cost of increased storage overhead. We introduce optimal ILP formulations for partitioning disk blocks into sub-blocks with overlapping and non-overlapping attributes. Additionally, we present greedy heuristic approaches that can scale better compared to the ILP alternatives, yet achieve close to optimal query I/O. To demonstrate the benefits of the railway layout, we provide an extensive experimental study comparing our approach to a few baseline alternatives.

  1. The partitioning algorithm depends on the Gurobi optimizer library. This is available for free under an academic license. Follow the instructions at: to install Gurobi.

  2. First fetch and build boost using libc++

  3. We expect this libc++ boost to be installed at '/opt/local/libcpp-software'

    mkdir tmp
    cd tmp
    tar -zxvf boost_1_57_0.tar.gz
    cd boost_1_57_0
    ./ --prefix=/opt/local/libcpp-software
    sudo ./b2 toolset=clang cxxflags="-stdlib=libc++" linkflags="-stdlib=libc++" --layout=tagged  install
    cd ../../
    rm -fr tmp

  4. Second, build the dependent libraries included in the 'ext' directory. These are the 'leveldb' and the 'libspatialindex' libraries

  5. Enter into the external software dir

    cd ext/src

  6. Build leveldb

    cd leveldb
    CC=clang CXX=clang++ CXXFLAGS="-std=c++11 -stdlib=libc++" make -j 4
    cd ..

  7. Build libspatialindex

    cd libspatialindex
    CC=clang CXX=clang++  CXXFLAGS="-std=c++11 -stdlib=libc++" ./configure --prefix $(cd ../..; pwd)
    make -j 4
    make install
    cd ..

  8. Build gtest

    cd gtest
    CC=clang CXX=clang++  CXXFLAGS="-std=c++11 -stdlib=libc++" ./configure --prefix $(cd ../..; pwd)
    cp -fr include/gtest ../../include
    cp lib/.libs/libgtest* ../../lib/

  9. Go back to the top level

    cd ../..

  10. Third, build libintergdb

    cd libintergdb
    make -j 4
    cd ..

  11. Last, run a test application

    cd test/SimpleTest