# DeepDamageNet: A two-step deep-learning model for multi-disaster building
damage segmentation and classification using satellite imagery

Irene Alisjahbana Jiawei Li Ben (Mullet) Strong Yue Zhang
Stanford University
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Satellite imagery has played an increasingly important role in post-disaster
building damage assessment. Unfortunately, current methods still rely on
manual visual interpretation, which is often time-consuming and can cause very
low accuracy. To address the limitations of manual interpretation, there has
been a significant increase in efforts to automate the process. We present a
solution that performs the two most important tasks in building damage
assessment, segmentation and classification, through deep-learning models. We
show our results submitted as part of the xView2 Challenge, a competition to
design better models for identifying buildings and their damage level after
exposure to multiple kinds of natural disasters. Our best model couples a
building identification semantic segmentation convolutional neural network
(CNN) to a building damage classification CNN, with a combined F1 score of
0.66, surpassing the xView2 challenge baseline F1 score of 0.28. We find that
though our model was able to identify buildings with relatively high accuracy,
building damage classification across various disaster types is a difficult
task due to the visual similarity between different damage levels and
different damage distribution between disaster types, highlighting the fact
that it may be important to have a probabilistic prior estimate regarding
disaster damage in order to obtain accurate predictions.

##  1 Introduction

In the past two decades, the number of natural disasters that occur worldwide
has increased dramatically, causing thousands of casualties and millions of
dollars of loss to buildings every year. It is no surprise that rapid building
damage assessment is considered to be one of the most important phases after
major disasters, aiming to evaluate the state of the buildings after a given
event. In addition to providing information to first responders for rescue
operations and relief efforts, it also provides useful information for local
government and related organizations for the estimation of economic loss and
damage distribution in the subsequent reconstruction and recovery phase
Barrington et al. (2012). Though significant efforts have been put into rapid
post-disaster assessment, it remains a very challenging task.

Traditional methods of building damage assessments rely on ground-based
surveys and field assessments to assess building damage, which involves
dispatching experts to the field to manually inspect buildings individually.
Though it is still perhaps the most reliable method of assessment, this method
is often time-consuming to apply across large geographic regions, subjective
and prone to inconsistencies in data quality Brown et al. (2015).

Technological advancements in the remote sensing field have created new
opportunities to address the limitations of field-based assessments and have
been recognized to be useful for rapid post-disaster response Rathje and Adams
(2008); Dong and Shan (2013); Taubenböck et al. (2014); Ghaffarian et al.
(2018). It enables the collection of data that is independent and rapidly
available across large geographical regions. Unfortunately, most efforts for
remote sensing-based building damage assessment today still rely on manual
visual interpretation and volunteers, which can result in very low accuracy
Loos et al. (2018). Though existing emergency mapping services such as the
Copernicus Emergency Management Service (EMS) provide damage maps a few hours
after a disaster, they are still typically carried out by human operators Nex
et al. (2019). This involves manually detecting and segmenting the buildings
before classifying them based on their damage level.

To address the limitations of manual interpretation, there has been a
significant increase in efforts to automate the process. Research has shown
that using machine learning and deep learning techniques, in particular
convolution neural networks (CNN) can achieve high accuracy. In addition, the
use of automated methods allows the independent and rapid assessment that can
easily be applied across large geographical areas. Nonetheless, most of the
work currently being done focuses on the two tasks (segmentation and
classification) separately.

To that end, the xView2 Challenge aims to automate the process of building
damage assessment from pre- and post-disaster satellite imagery through the
creation of accurate and efficient machine learning models. To support the
advancement of the automation process, the xBD dataset Gupta et al. (2019), a
new large-scale dataset containing pre- and post- disaster satellite imagery
and ground truth labels from a variety of disasters and over 160,000 buildings
was released.

Through this challenge, we present a framework to perform segmentation and
classification of buildings from pairs of pre- and post- disaster images for
the purposes of building damage assessment. In particular, we explored various
methods and model architectures that would be generalizable across various
types of natural disasters, such as earthquakes, tsunamis, floods, volcanic
eruptions, wildfires, and hurricanes. We present our results and analyses on
the advantages and limitations of using automated methods for the purposes of
building damage assessment across different disasters.

##  2 Related Work

Given its obvious advantages, damage assessment via remote sensing has become
a topic of much research in the last few decades. Verstappen Verstappen (1995)
proposed one of the original frameworks for evaluating the use of remote
sensing data in natural hazard risk reduction, and called for the use of
remote sensing tools in combating both “instantaneous” disasters like
cyclones, drought, floods, tsunamis, earthquakes, and volcanic hazards, and
“creeping” disasters like desertification. Frameworks have also been proposed
for the use of remote sensing data to predict high-risk areas, before disaster
strikes Tralli et al. (2005).

In the pre-machine learning era, practitioners relied on classical
segmentation and classification techniques for map production, e.g. a “region-
growing and knowledge-based segmentation approach” that involves merging
visually similar regions to build a disaster map Van der Sande et al. (2003).
It is only more recently that researchers have applied machine learning
techniques to this problem, with increasing degrees of success.

Thanks to the recent advancement of the object detection and segmentation
algorithms in computer vision, many CNN models have been developed and applied
for building footprint segmentation based on satellite data. Some of the most
common models include U-Net Ronneberger et al. (2015), and the more recent
feature pyramid network (FPN) Lin et al. (2017). U-Net has been successfully
used in the satellite image building segmentation challenge SpaceNet 4. Chen
et al. Chen et al. (2018a) used the FPN model for building segmentation using
the Aerial Imagery for Roof Segmentation (AIRS) dataset. This dataset contains
aerial imagery with 7.5cm resolution and contains over 220,000 buildings. The
overall performance of the FPN model was evaluated through intersection over
union (IoU) and F1-score metrics, in which they achieved a score of 0.882 and
0.937 respectively.

One limitation of using semantic segmentation for the purposes of building
damage assessment is the fact that semantic segmentation treats multiple
objects of the same class as a single entity, whereas in reality, each
building is required to be classified individually. As a result, instance
segmentation has been increasingly used, as it identifies multiple objects of
the same class as distinct individual objects Chen et al. (2018b); Iglovikov
et al. (2018). He et al. He et al. (2017) first introduced Mask R-CNN, a
framework for generating high-quality segmentation masks for each instance.
Since then, Mask R-CNN has been used for a variety of different application as
it is fast to implement and easy to generalize to different tasks including
building footprint segmentation. One such application was for CrowdAI’s
mapping challenge 2018 Mohanty (2018), aiming to segment buildings for
humanitarian assistance. Using high resolution RGB satellite images, the
challenge baseline achieved an IoU of 0.697.

In addition to building footprint segmentation, deep learning methods are
widely used to classify the building damage level. Xu et al. Xu et al. (2019)
compared four architectures to perform binary classification (damage or not
damaged) for a certain building cropped from a satellite imagery. Their
results show that a twin-tower structure to fuse the pre-disaster and post-
disaster images can improve the classification accuracy. In their experiments,
the best model used two separate CNNs to extract features of the pre- and
post-disaster images, before subtracting the extracted features along the
channel dimension. They used the area under the RoC curve (AUC) as the primary
metric of model, and achieved a score of 0.8302 AUC score on the Haiti
earthquake dataset.

As seen above, most work focuses on either segmentation or classification.
Gupta et al. Gupta et al. (2019) introduced a baseline model for the xView2
challenge that combines the segmentation and classification model. The
segmentation model is based on an altered U-Net architecture, achieving an IoU
of 0.66 and F1 score of 0.80. On the other hand, the classification model is
based on a modified ResNet50. The weighted F1 is used as the primary metric
for evaluating the overall dataset, obtaining a weighted F1 score of 0.2564.

To our knowledge, no previous work has been done to create a model that would
be generalizable to all types of natural disasters. Most work have focused on
a single disaster type. For example, Xu et al. Xu et al. (2019) trained a
model for earthquake disasters damage whereas Rudner et al. Rudner et al.
(2019) for flooded buildings. Xu et al. Xu et al. (2019) quantified how well
the models will generalize to future disasters by training and testing models
on different disaster events, and found that the AUC reduces for cross-region
results. This suggests that cross-region prediction is difficult, even within
the same disaster type (i.e earthquakes).

##  3 Dataset

###  3.1 Dataset Description

The dataset used is the xBD dataset, released to supplement the xView2
Challenge Gupta et al. (2019). A total of 2799 pairs of pre- and post-disaster
RGB satellite images are provided in the training set, whereas 933 pairs of
pre- and post- disaster satellite images are available in the test set. All
imagery is obtained from DigitalGlobe satellite with a resolution of around
0.5m ground sample distance. The size of the images are $1024\times 1024$
pixels. An example of a pre- and post- disaster image can be seen in Figure 1.

Figure 1: Pre-disaster (left) and its corresponding post-disaster satellite
image

In addition to imagery, the xBD dataset provides ground truth data that
includes the coordinates of each building polygons and the corresponding
damage scale level for each building. The damage scale level that is used in
the xBD dataset is a joint damage scale that ranges from no damage (0) to
destroyed (3). The ground truth data is only available for the training set. A
detailed description of the damage scale definition, image collection method,
annotation process and quality control of the dataset is available in Gupta et
al. (2019).

###  3.2 Dataset Statistics

The training dataset consists of 10 different disasters, ranging from
hurricanes, to earthquakes and is gathered from over 15 countries at various
times of the year. It should be noted that the number of images available for
each disaster event is highly unbalanced, with the Guatemala volcanic eruption
having the least number of images.

Though the distribution of images based on each disaster is highly imbalanced,
the number of buildings that are present in each image also varies
significantly between each disaster (Figure 2). For some disasters, there are
images where a single image contains over 1000 buildings. On the other hand,
there are disasters with images that contain less than 10 buildings (Figure
3).

Figure 2: Distribution of building damage level in training set Figure 3:
Differences in building densities

Furthermore, the damage level for the buildings in the training dataset is
also imbalanced. Non-damaged building takes up over 70% of the training data.
However, even though there are mostly non-damage buildings in the complete
training data, this distribution varies significantly between each disaster as
seen in Figure 3. For example, there are more damaged buildings compared to
non-damaged buildings for Hurricane Matthew.

##  4 Methods

###  4.1 Pre-Processing

Before splitting the xBD dataset into train/val set, we manually looked
through the dataset for features that might be problematic for our model. For
example, there were some images that are covered by clouds, causing occlusion
to some buildings. However, the statistical analysis showed that less than 1%
of the images were covered by clouds. As a result, we decided to leave those
images in our dataset.

We then split the data into training and validation with 80% to 20% ratio.
Since the hold-out test set used by the challenge is drawn from the same
disaster type distribution as the data released, our validation set was
created by preserving this distribution. For each disaster, we took 20% of the
images for the validation set, and 80% for the training set. The number of
images in the training and validation set for each disaster can be seen in
Table 1.

Disaster | Total | Train. Set | Val. Set
---|---|---|---
Guatemala Volcano | 18 | 15 | 3
Hurricane Florence | 319 | 256 | 63
Hurricane Harvey | 319 | 256 | 63
Hurricane Matthew | 238 | 191 | 47
Hurricane Michael | 343 | 191 | 68
Mexico Earthquuake | 121 | 97 | 24
Midwest Flood | 279 | 224 | 55
Palu Tsunami | 113 | 91 | 22
Santa Rosa Wildfire | 226 | 181 | 45
Socal Fire | 823 | 659 | 164
Total Images | 2799 | 2245 | 554
Table 1: Number of images in the training and validation sets based on
disaster

We recognize that even with the split generated above, the building damage
class imbalance persists. A majority of the buildings in our split dataset
will still be non-damaged buildings. In our current approach, we did not do
any further distribution of data in order to reduce this imbalance.

###  4.2 Model Architecture

We experimented with two techniques for performing the objective task. First,
we built and trained an end-to-end model, which was designed to simultaneously
perform both segmentation of building footprints and classification of damage
extent. Second, we implemented a series of two-step models, which treated
building segmentation and damage classification as two distinct tasks, with
separate models optimized for each of these tasks (Figure 4).

Figure 4: Architecture of two-step model. The pre-disaster image is fed into a
segmentation model to obtain building polygon coordinates. This result in
addition to pre- and post- disaster cropped building image is then fed into a
damage classification model to obtain the final image.

####  4.2.1 End-to-End Model

For the end-to-end model, the inputs were paired pre-disaster and post-
disaster images both of size $1024\times 1024\times 3$ and the output shows
the pixel-level classification results of size $1024\times 1024$. The
classification values ranged within 0 to 4, where 0 represents no-building and
1-4 represented different building damage levels from no-damage to destroyed,
as discussed above. The model architecture chosen here was U-Net with a
ResNet-34 encoder pre-trained on ImageNet dataset. To incorporate both pre-
disaster image and post-disaster image, two architectures were proposed
(Figure 5).

Figure 5: Architecture of end-to-end model. The pre- and disaster image is
subtracted before feeding into a U-Net to perform simultaneous segmentation
and classification.

The intuitive way to make use of the pre- and post- disaster images is to
compare the difference between them. Thus, we subtracted the pre-disaster
image pixel values from the post-disaster image to obtain a new image of size
$1024\times 1024\times 3$. This was then treated as a new input to be fed
directly to the ResNet without making any further changes.

####  4.2.2 Two-Step Model: Building Segmentation

In the two-step model, the first step is to segment the building footprint and
extract the polygon coordinates of each building. We tried two different model
architectures for this task, semantic segmentation and instance segmentation,
which are commonly used for building footprint segmentation.

Instance Segmentation: The objective of the instance segmentation is to label
each foreground pixel with a corresponding object and instance - a combination
of semantic segmentation and object detection. For this, we used Mask R-CNN He
et al. (2017). For ease of implementation, we followed the implementation from
the Facebook AI research platform Detectron2 Wu et al. (2019). The backbone
model of the Mask R-CNN is a ResNet-50 He et al. (2016) with Feature Pyramid
Network (FPN) Lin et al. (2017). A faster R-CNN Ren et al. (2015) model is
combined with the backbone model to perform the semantic segmentation and
object detection.

Semantic Segmentation: A ResNet-50 Feature Pyramid Network (the same backbone
model as the Mask R-CNN) was used to conduct the semantic segmentation of the
building footprint. The model input is the pre-disaster image and the output
is the binary mask of each image with 0 (background) and 1 (building). After
obtaining the semantic mask of each image, we outlined every single building
to extract their polygon coordinates using Imantics Imantics (2019), a Python
package.

####  4.2.3 Two step model: Building Classification

After segmentation maps were generated using the techniques outlined in the
previous section, building-by-building damage classification was performed.
The model takes as input a close cropping of an individual building in both
pre- and post-disaster images and predicts the damage level score (1 for no
damage, 4 for destroyed). The basic structure of the damage classification
model includes two CNN feature extractors which are used to pre-process the
pre- and post-disaster building images. Then the features maps can be used
alone or combined with other features to conduct the prediction.

Pre & Post Concatenation:

The damage classification model concatenating pre- and post- feature maps can
be seen in Figure 6(a). Similar to what was done by Xu et al. Xu et al.
(2019), we implemented a twin-tower model architecture which concatenates the
output features of a ResNet-50 model (pre-trained on ImageNet). This
concatenated feature map is then flattened and fed to several fully connected
layers, which outputs a damage level classification score ranging from 1 (No
damage) to 4 (Destroyed).

Pre & Post Concatenation with Disaster Prediction: As mentioned before,
different disasters in different regions will be covered in this single
prediction model. We found that the building damage characteristics of
different disasters are significantly different, which motivates us to
incorporate the disaster-type as an extra features in the Pre & Post
Concatenation model in Figure 6(b).

The xview2 dataset provides a unique disaster-type label for each training
image, which enables us to train a separate disaster type prediction models.
The disaster-type will then be represented as an one-hot vector and
concatenated with the pre- and post- features extracted from CNN and the
combined features are used for the final prediction.

Pre & Post Concatenation with SSIM: As an extension, we also experimented by
adding a third branch with additional features before concatenating and
feeding to the fully connected layers. The structural similarity index (SSIM)
was added as the additional feature, a metric that measures the similarity
between two images Wang et al. (2004).

(a) Pre & Post Concatenation

(b) Pre & Post Concatenation with Additional Features

Figure 6: Architecture of classification model. a) A twin-tower architecture
concatenates the output features of a ResNet-50 model from pre- and post-
disaster cropped building images. b) An additional third branch can be added
to include additional features.

##  5 Experiments

###  5.1 Evaluation Metrics

The evaluation metrics used to reflect the overall performance of our models
are the mean Intersection-Over-Union (mIoU) and weighted F1-score. mIoU is
specifically used for our segmentation model, as it is commonly used in
literature to evaluate segmentation models. A weighted F1 score was also used
for both the segmentation and classification models. This metric balances
precision and recall in a harmonic mean and is well-suited for imbalanced
datasets such as the xBD dataset Gupta et al. (2019).

For the purposes of the xView2 challenge, the final evaluation metric is a
combined F1 score: 30% segmentation F1 score + 70% classification F1 score.
This metric is calculated over the hold-out test dataset.

###  5.2 Results

####  5.2.1 End-to-End Model

Examples of results obtained with our end-to-end model can be seen in Figure
7. It can be seen that our model does relatively well for the segmentation
task. Our best model obtained a 0.795 F1 score on the test dataset for the
segmentation task, similar to what was obtained in the xView2 baseline model.
Our error analysis showed that we missed some small buildings and those
buildings partially hidden in the forest/water.

Figure 7: Ground truth data (left column) and model predictions (right column)
for end-to-end model. Our model accurately predicts minor damage buildings
(green) in some images while completely missing destroyed buildings (red) in
others.

However, the end-to-end model was not able to accurately classify the damage
level of each building and performed significantly worse than the baseline
model. We realized that an end-to-end model is unable to accurately capture
all the complexities of building damage levels, and therefore we proceeded to
focus on the two-step model.

####  5.2.2 Building Segmentation

As described in Section 4.2.2, we experimented with two different segmentation
architectures.

Instance segmentation: We trained a mask R-CNN model with two P100 GPUs using
a batch size of 4 and the initial learning rate of 0.01. The original high-
resolution image with dimensions $1024\times 1024\times 3$ was directly used
as the training images. The number of regions of interest (ROIs) per image was
set to be 1000. COCO instance segmentation challenge pre-trained weight was
used as the initial weight. We trained the model for 28,000 iterations.

Semantic Segmentation: We trained a ResNet-50 FPN model with two P4 GPUs. The
batch size was 16 and the initial learning rate was 0.02. Again, the original
high-resolution image with dimensions $1024\times 1024\times 3$ was directly
used as the training images. ImageNet pre-trained weight was used as the
initial weight. This time, we trained the model for 50,000 iterations.

(a) Instance segmentation results on validation set

(b) Semantic segmentation results on validation set

Figure 8: Building segmentation results on validation set. Left column is the
ground truth data. The different colors represent each labeled individual
building. a) right is the instance segmentation prediction. The different
colors represent each individually detected instance of buildings. b) right is
the semantic segmentation prediction. The prediction is a binary mask, with
background (blue) and buildings (red) is obtained.

The prediction result of the instance segmentation and semantic segmentation
model is shown in Figure 8(a) and Figure 8(b) respectively. To conduct a
consistent comparison of the two models, we computed the metric scores only
based on their predicted masks. The predicted mask of Instance segmentation
are a integration of all the individual masks of each building. We compared
the mIoU score of our models on our validation set in Table 2. In addition, we
compared our results to the xView2 challenge baseline. Though it seems that
both models performed relatively well through visual inspection (Figure 8(a)
and Figure 8(b)), the results show that our semantic segmentation model
performs significantly better than the xView2 challenge baseline as well as
our instance segmentation model.

The inferior performance of the instance segmentation model was surprising. We
realized that one of the major issue of using Mask R-CNN for instance
segmentation is its inability to detect all the buildings, particularly where
there are more than 1000 buildings in a single image. We believe that using a
larger and more complex model can improve the performance of the instance
segmentation model. However, given the difficulties of optimizing the instance
segmentation model as well as the fact that our semantic segmentation model
was able to achieve relatively accurate results, we chose the semantic
segmentation model for our final model.

Method | mIoU
---|---
xView2 Baseline | 0.78
Instance Segmentation | 0.70
Semantic Segmentation | 0.85
Table 2: Building segmentation results on the validation set. mIoU is
calculated based on the predicted binary mask of building footprint

####  5.2.3 Building Classification

As discussed in Section 4.2.3, we implemented several different architectures
for our damage classification models.

Pre & Post Concatenation: Inspired by the work done by Xu et al. Xu et al.
(2019), who studied a task highly analogous to the one we perform here, we
implemented a twin-tower model which concatenates the output features of a
ResNet-50 model from pre- and post-disaster building cropped images.

Pre & Post Concatenation with Disaster Labels: Acting off the knowledge that
expected damage level distribution is different depending on the disaster, we
added an additional feature as a third branch before concatenating and feeding
into the fully connected layers. The additional feature is a label denoting
the disaster to which a building belonged (e.g. “1" for Hurricane Matthew).
Note that these labels are not available in the xView2 test set. To
appropriately classify test set images with this model, we built an additional
CNN model to identify image disaster name based on pre- and post-disaster
imagery. This disaster name classification task was accomplished with this CNN
to a high level of accuracy, achieving 95% accuracy on the validation set.

Pre & Post Concantenation with SSIM: We experimented with adding hand-
engineered features to our models to boost performance. Here we used SSIM, a
metric that is commonly used in image processing to measure the similarity
between two images. Similar to the model with disaster label, this additional
feature is added as a third branch of our architecture before concatenation.

All models were trained using cross-entropy loss for damage classification
score. The models were trained using one NVIDIA Tesla T4 GPU with a batch size
of 500 and initial learning rate of $8\times 10^{-4}$ and were trained until
model convergence. These models were first tested for appropriate
implementation by over-training on a smaller subset of the data.

Method | Train Acc. | Val.Acc.
---|---|---
Pre & Post Concat. | 0.77 | 0.80
Pre & Post Concat. + Disaster | 0.91 | 0.86
Pre & Post Concat. + SSIM | 0.83 | 0.82
Table 3: Damage classification task results

The results of our experiments are summarized in Table 3. Counter-intuitively,
Pre & Post Concatenation model scored higher on the validation set than on the
training set. We attribute this to the model simply memorizing the damage
distribution of the dataset, rather than learning anything intrinsic about the
input image, and then benefiting from a validation set that had a slightly
more favorable distribution of building damage scores. As anticipated, the
model with the additional feature of disaster labels show a higher accuracy,
which proves that providing the model with information about which disaster a
given building came from dramatically improves performance. The model with
SSIM as additional feature also performs better than the basic Pre & Post
concatenation model, though still lower than the model with the disaster
label. This shows that though knowing the disaster improves the performance,
adding additional hand-engineered features can also help with performance.

Method | Segmentation F1 Score | Classification F1 Score | Overall F1 Score
---|---|---|---
xView2 Baseline | 0.80482 | 0.06091 | 0.28408
End-to-end Model | 0.79584 | / | 0.23875
Semantic Segmentation + |  |  |
Pre & Post Concatenation | 0.84330 | 0.51 | 0.61
Semantic Segmentation + |  |  |
Pre & Post Concatenation + Disaster | 0.84330 | 0.5873 | 0.6641
Semantic Segmentation + |  |  |
Pre & Post Concatenation + SSIM | 0.84330 | 0.54679 | 0.63574
Table 4: Summary of results submitted to the xView2 challenge Leaderboard
Figure 9: Validation results of correct damage classification predictions
Figure 10: Validation results of incorrect damage classification predictions

When visualizing our damage classification predictions, we noticed that our
model performs well if both the pre- and post-disaster images are identical in
terms of color and nadir angle. This can be seen in Figure 9. On the other
hand, the model has issues dealing with very small buildings, and when the
pairs of images were taken in very different times, causing differences in
color, shadows, and nadir angles (Figure 10).

###  5.3 Test Results

For final analysis, we performed inference on the xView2 challenge test
dataset and submitted the results to the xView2 leaderboard for scoring. These
test dataset results were generated for the End-to-End Model and the two step
models. For all two-step models, we used the output of the semantic
segmentation model, which performed better in our experiments. Because the
test set images do not include information about source disaster, we used the
separate CNN model discussed earlier to classify test images by disaster name.
These names were then included in the model which used disaster name as a
feature. Results are summarized in Table 4.

The End-to-End model performed only slightly worse than the xView2 baseline on
the segmentation part, a somewhat surprising result given the model’s
significantly less complex design. The classification f1 score of the End-to-
End model is not available, which we attribute to a submission error which
could not be resolved by the time of writing. However, due to its relatively
poor performance in training, we expect that the End-to-End model would not
perform well on the test set. Both two-step models performed better in
localization and classification compared to baseline. Our best model, a two-
step model with Pre & Post Concatenation and disaster label, scored
significantly better than baseline (overall F1 score of 0.66 versus 0.28 for
baseline).

##  6 Conclusion

In this paper, we presented a framework for building damage assessment after
natural disasters. We experimented with several different architectures that
focused on building segmentation and classification, in particular an end-to-
end model that simultaneously performs those two tasks and a two-step model.
Our approach presents one of the first attempts at creating a model that is
able to generalize to all types of natural disasters.

We submitted our results as part of the xView2 Challenge, a competition to
design better models for identifying buildings and their damage level after
exposure to multiple kinds of natural disasters. Our best model couples a
building identification semantic segmentation convolutional neural network
(CNN) to a building damage classification neural network, with a combined F1
score of 0.66, surpassing the xView2 challenge baseline F1 score of 0.28.

Our results point to several important conclusions. We found that two-step
models (segmentation and classification) that are trained individually works
better than an end-to-end model that performs the two task simultaneously.

Our best performing model included an additional feature representing the
disaster name. This result indicates two possibilities: (1) that similar
levels of damage are visually different in different disasters, or (2) given
the difficulty of the damage classification tasks, a best performing model
will rely heavily on a learned prior probability distribution for damage,
which will differ by disaster.

Though this is a huge step towards the automation of building damage
assessments for various types of natural disasters, it is clear that there is
still a lot of work to be done to increase the accuracy in the building damage
classification. Though our results suggest that training a model for each
individual disaster might boost performance in the xView2 challenge, we
realize that this will not be applicable for new disasters and real-world
applications. Instead, our results suggest developing methods that incorporate
disaster severity, region vulnerability, and other factors in the form of a
prior estimate of damage.

##  7 Acknowledgments

We would like to acknowledge the Stanford CS325B (Data for Sustainable
Development) teaching team for their continuous feedback and ideas. In
particular, we would like to thank Professor Marshall Burke, Professor David
Lobell and Stefano Ermon, as well as Robin Cheong, Matthew Tan and Burak
Uzkent.

## References

  * Barrington et al. [2012] Luke Barrington, Shubharoop Ghosh, Marjorie Greene, Shay Har-Noy, Jay Berger, Stuart Gill, Albert Yu-Min Lin, and Charles Huyck.  Crowdsourcing earthquake damage assessment using remote sensing imagery.  _Annals of Geophysics_ , 54(6), 2012.
  * Brown et al. [2015] Daniel Brown, Stephen Platt, John Bevington, Keiko Saito, Beverley Adams, Torwong Chenvidyakarn, Robin Spence, Ratana Chuenpagdee, and Amir Khan.  Monitoring and evaluating post-disaster recovery using high-resolution satellite imagery—towards standardised indicators for post-disaster recovery.  _Martin Centre: Cambridge, UK_ , 2015.
  * Rathje and Adams [2008] Ellen M Rathje and Beverley J Adams.  The role of remote sensing in earthquake science and engineering: Opportunities and challenges.  _Earthquake Spectra_ , 24(2):471–492, 2008.
  * Dong and Shan [2013] Laigen Dong and Jie Shan.  A comprehensive review of earthquake-induced building damage detection with remote sensing techniques.  _ISPRS Journal of Photogrammetry and Remote Sensing_ , 84:85–99, 2013.
  * Taubenböck et al. [2014] Hannes Taubenböck, Christian Geiß, Marc Wieland, Massimilliano Pittore, Keiko Saito, Emily So, and Michael Eineder.  The capabilities of earth observation to contribute along the risk cycle.  In _Earthquake Hazard, Risk and Disasters_ , pages 25–53. Elsevier, 2014.
  * Ghaffarian et al. [2018] Saman Ghaffarian, Norman Kerle, and Tatiana Filatova.  Remote sensing-based proxies for urban disaster risk management and resilience: A review.  _Remote sensing_ , 10(11):1760, 2018.
  * Loos et al. [2018] Sabine Loos, Karen Barns, Gitanjali Bhattacharjee, Robert Soden, Benjamin Herfort, Melanie Eckle, Cristiano Giovando, Blake Girardot, Keiko Saito, Gregory Deierlein, Anne Kiremidjian, Jack W Baker, and David Lallemant.  The Development and Uses of Crowdsourced Building Damage Information based on Remote-Sensing.  Technical Report 1, 2018.  URL https://purl.stanford.edu/bj915mt6570.
  * Nex et al. [2019] Francesco Nex, Diogo Duarte, Anne Steenbeek, and Norman Kerle.  Towards real-time building damage mapping with low-cost UAV solutions.  _Remote Sensing_ , 11(3):1–14, 2019.  ISSN 20724292.  doi:10.3390/rs11030287.
  * Gupta et al. [2019] Ritwik Gupta, Bryce Goodman, Nirav Patel, Ricky Hosfelt, Sandra Sajeev, Eric Heim, Jigar Doshi, Keane Lucas, Howie Choset, and Matthew Gaston.  Creating xbd: A dataset for assessing building damage from satellite imagery.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops_ , pages 10–17, 2019.
  * Verstappen [1995] H Th Verstappen.  Aerospace technology and natural disaster reduction.  _Advances in Space Research_ , 15(11):3–15, 1995.
  * Tralli et al. [2005] David M Tralli, Ronald G Blom, Victor Zlotnicki, Andrea Donnellan, and Diane L Evans.  Satellite remote sensing of earthquake, volcano, flood, landslide and coastal inundation hazards.  _ISPRS Journal of Photogrammetry and Remote Sensing_ , 59(4):185–198, 2005.
  * Van der Sande et al. [2003] CJ Van der Sande, SM De Jong, and APJ De Roo.  A segmentation and classification approach of ikonos-2 imagery for land cover mapping to assist flood risk and flood damage assessment.  _International Journal of applied earth observation and geoinformation_ , 4(3):217–229, 2003.
  * Ronneberger et al. [2015] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In _International Conference on Medical image computing and computer-assisted intervention_ , pages 234–241. Springer, 2015.
  * Lin et al. [2017] Tsung-Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie.  Feature pyramid networks for object detection.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 2117–2125, 2017.
  * Chen et al. [2018a] Qi Chen, Lei Wang, Yifan Wu, Guangming Wu, Zhiling Guo, and Steven L Waslander.  Aerial imagery for roof segmentation: A large-scale dataset towards automatic mapping of buildings.  _arXiv preprint arXiv:1807.09532_ , 2018a.
  * Chen et al. [2018b] Liang-Chieh Chen, Alexander Hermans, George Papandreou, Florian Schroff, Peng Wang, and Hartwig Adam.  Masklab: Instance segmentation by refining object detection with semantic and direction features.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 4013–4022, 2018b.
  * Iglovikov et al. [2018] Vladimir Iglovikov, Selim S Seferbekov, Alexander Buslaev, and Alexey Shvets.  Ternausnetv2: Fully convolutional network for instance segmentation.  In _CVPR Workshops_ , pages 233–237, 2018.
  * He et al. [2017] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask r-cnn.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2961–2969, 2017.
  * Mohanty [2018] Sharada Prasanna Mohanty.  Crowdai mapping challenge 2018 : Baseline with mask rcnn.  https://github.com/crowdai/crowdai-mapping-challenge-mask-rcnn, 2018.
  * Xu et al. [2019] Joseph Z Xu, Wenhan Lu, Zebo Li, Pranav Khaitan, and Valeriya Zaytseva.  Building damage detection in satellite imagery using convolutional neural networks.  _arXiv preprint arXiv:1910.06444_ , 2019.
  * Rudner et al. [2019] Tim GJ Rudner, Marc Rußwurm, Jakub Fil, Ramona Pelich, Benjamin Bischke, Veronika Kopačková, and Piotr Biliński.  Multi3net: segmenting flooded buildings via fusion of multiresolution, multisensor, and multitemporal satellite imagery.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 702–709, 2019.
  * Wu et al. [2019] Yuxin Wu, Alexander Kirillov, Francisco Massa, Wan-Yen Lo, and Ross Girshick.  Detectron2.  https://github.com/facebookresearch/detectron2, 2019.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * Ren et al. [2015] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  In _Advances in neural information processing systems_ , pages 91–99, 2015.
  * Imantics [2019] Imantics.  Image semantics documentation.  https://imantics.readthedocs.io/en/latest/#, 2019.
  * Wang et al. [2004] Zhou Wang, Alan C Bovik, Hamid R Sheikh, Eero P Simoncelli, et al.  Image quality assessment: from error visibility to structural similarity.  _IEEE transactions on image processing_ , 13(4):600–612, 2004.


# Benchmark Framework with Skewed Workloads

Ravil Galiev<EMAIL_ADDRESS>ITMO UniversityRussia ,  Dmitry
Ivanov<EMAIL_ADDRESS>HuaweiRussia and  Vitaly Aksenov
<EMAIL_ADDRESS>ITMO UniversityRussia

(2018)

###### Abstract.

In this work, we present a new benchmarking suite with new real-life inspired
skewed workloads to test the performance of concurrent index data structures.
We started this project to prepare workloads specifically for self-adjusting
data structures, i.e., they handle more frequent requests faster, and, thus,
should perform better than their standard counterparts. We looked over the
commonly used suites to test performance of concurrent indices trying to find
an inspiration: Synchrobench, Setbench, YCSB, and TPC — and we found several
issues with them.

The major problem is that they are not flexible: it is difficult to introduce
new workloads, it is difficult to set the duration of the experiments, and it
is difficult to change the parameters. We decided to solve this issue by
presenting a new suite based on Synchrobench.

Finally, we highlight the problem of measuring performance of data structures.
We show that the relative performance of data structures highly depends on the
workload: it is not clear which data structure is best. For that, we take
three state-of-the-art concurrent binary search trees and run them on the
workloads from our benchmarking suite. As a result, we get six experiments
with all possible relative performance of the chosen data structures.

concurrency, benchmark, data structures

††copyright: acmcopyright††journalyear: 2018††doi:
XXXXXXX.XXXXXXX††conference: Make sure to enter the correct conference title
from your rights confirmation emai; June 03–05, 2018; Woodstock, NY††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06††ccs: Software and its engineering
Software libraries and repositories††ccs: Computing methodologies Concurrent
computing methodologies

##  1\. Introduction

One of the largest open questions is how to understand which particular data
structure works better than others. The standard approach in research papers
(or in practical research) is to run the data structures on a specific set of
workloads. If the target data structure outperforms others, i.e., executes all
the operations faster on all the chosen workloads, then one can claim that
this structure is indeed better.

In this work, we consider concurrent index data structures that store keys
with values. They support three operations: 1) insert operation adds a key
with the provided value to the set and returns a previous corresponding value;
2) remove operation removes a key from the set and returns the corresponding
value; 3) get operation returns a value that corresponds to a requested key.
The operations insert and remove can be referred to as write or update
operations, and get operation can be referred to as a read operation.

There exist several benchmarking suites to test concurrent index data
structures. The most popular of them are: Synchrobench (Gramoli, 2015),
Setbench (Brown et al., 2020), YCSB (Cooper et al., 2010), and TPC benchmarks
(TPC). Let us take a deeper look on them. Synchrobench is the simplest one: it
provides only an uniform workload. In the uniform workload, threads in an
infinite loop chooses a type of an operation corresponding to the probability
of write and read operations and as an argument it takes a key chosen
uniformly at random from the specified range. Synchrobench is implemented in
Java and C++ and provides a lot of state-of-the-art implementations.

Setbench is more generic. In addition to the Uniform workload, it provides the
Zipfian one — where the arguments of the operations are taken from Zipfian
distribution (Powers, 1998). Moreover, it provides one workload from both YCSB
and TPC-C. Setbench is written in C++ and provides a lot of state-of-the-art
implementations.

Now, we come to the industrially used benchmarking suites: YCSB and TPC. YCSB
provides five predefined workloads (Cooper et al., 2010):

  * •

update heavy (A): $50\%$ of updates and $50\%$ of reads, Zipfian distribution
of arguments;

  * •

read heavy (B): $5\%$ of updates and $95\%$ of reads, Zipfian distribution of
arguments;

  * •

read only (C): $100\%$ of reads, Zipfian distribution of arguments;

  * •

read latest (D): $5\%$ of inserts and $95\%$ of reads, Latest with Zipfian
distribution of arguments, i.e., the recently accessed keys have bigger
probability;

  * •

and, scan workload (E): $95\%$ of operations are scans, i.e., traverse through
all elements from a specified range, and $5\%$ of inserts with Zipfian and
Uniform distributions of arguments.

TPC is a meta-suite, i.e., a suite of suites. Its workloads are more
complicated than YCSB workloads since they use transactions in the database
which we currently do not support. However, they are more practically in
nature. The subsuites of our interest are TPC-C and TPC-H. We omit their
explanation here. However, they do not satisfy our goals and we later explain
— why.

Now, we state four reasonable requirements for the benchmarking suites that we
expect from them. At first, it should be easy to add a new workload to the
suite. Secondly, we want workloads to run for an arbitrary time, i.e., we
require infinite workloads. Thirdly, or the most specific, we want the
workloads to be: 1) taken from the real-life patterns; 2) be skewed, so that
we can use them to test self-adjusting data structures, i.e., data structures
that handle more frequent requests faster. Finally, we want to tune workload
parameters in a simple manner.

We consider each requirement one by one. For the first one, none of the
benchmarking suites satisfy us — you have to write your workload totally from
scratch including all the necessary functions, such as the logic with the
threads and their execution, the reading of the arguments, the calculation of
the statistics, etc. We find it very tedious — we tried to fix it by providing
a new modular approach to a suite that should require only to rewrite small
parts of the benchmark. In the main part, we present how easy it is to add the
skewed workload presented in (Aksenov et al., 2023) to our suite.

For the second requirement, the Uniform and Zipfian workloads from
Synchrobench and Setbench satisfy us — they can be repeated for an arbitrary
amount of time. However, YCSB and TPC workloads have a predefined number of
operations before the run. For example, consider the Latest distribution in
YCSB: a thread requests a key from the latest requested ones. Unfortunately,
we cannot choose an argument from this distribution in constant time during
the run — you need at least $\Omega(\log n)$ additional operations that could
affect the whole benchmark. Thus, the infinite workload seems to be impossible
to implement. The same happens with TPC benchmarks. In our benchmarking suite,
workloads are infinite. As an example, we present an infinite workload similar
to the Latest distribution in YCSB. See Section 4.4.

Thirdly, Synchrobench and Setbench workloads are synthetic and, thus, are
suitable only for microbenchmarking. YCSB is partly synthetic as our suite —
the workloads try to model the real-life behaviour. With TPC everything gets
more complicated: it uses some real-life traces with synthetic ones. For
example, TPC-C uses two distributions: Uniform and NURandom (non-uniform
random). We find this to be a little bit restrictive, thus, we decided to come
up with new interesting workloads related to real-life. Currently, we
implemented two: 1) Temporary Skewed Sets — the workload depends on the
current time, i.e., one wants to know the weather in the morning, to search
for a work-related data in the afternoon, and to read the news in the evening;
and 2) Creakers and Wave — the recently added elements are requested more
frequently than the old ones, i.e., musical hits are listened to more often
when they have just been released. We explain these workloads in detail in
Section 4.

Finally, all the workloads in YCSB and TPC seem to be fixed: it is really
difficult to change the parameters — there are many complicated dependencies
between them. Of course, it is not the problem with the simplest Uniform and
Zipfian workloads in Synchrobench and Setbench. We believe that the
implemented workloads in our benchmarking suite are simpler to setup.

At the end, we state a very important observation concerning the benchmarking
processes. The presented results in papers, in general, are not necessarily
fair: typically, the authors use only the “good” workloads where their data
structure outperforms others. We remind everyone to take it seriously— it is
hard to win on all possibly workloads. Thus, all the performance results
should be considered with suspicion.

To show that, we took three well-known Java implementations of binary search
trees: BCCO tree (Bronson et al., 2010), Concurrency-Friendly tree (Crain et
al., 2013), and Concurrency-Optimal tree (Aksenov et al., 2017); and presented
six workloads from our suite that show any possible relative performance
between these three data structures.

We want to end the introduction with a small discussion of our benchmark
suite. The suite currently offers several synthetic workloads out of the box,
some of which are based on real-life patterns. Right now, we have only the
Java version of the suite built on Synchrobench, but the C++ version based on
Setbench is coming soon. One can check out the Java suite by the link
https://github.com/Mr-Ravil/synchrobench.

Roadmap.  In Section 2, we present a software design of our suite and provide
an example on how one can add a new workload. In Sections 3, 4, and 5, we
describe the predefined entities in our suite which one can already use to
build more complicated workloads. In Section 6, we present that we really
cannot separate three well-known binary search trees. Finally, we conclude in
Section LABEL:sec:conclusion.

##  2\. Software Design

There are four types of entities in our benchmarking suite:

  * •

Distribution represents a distribution of a random variable;

  * •

KeyGeneratorData converts a generated value from a distribution, into a key;

  * •

KeyGenerator generates a key using several Distribution and KeyGeneratorData
entities;

  * •

ThreadLoop express the logic on how to interact with a provided index data
structure.

Typically, each benchmark depends on one ThreadLoop, that uses one
KeyGenerator, whereas the KeyGenerator utilizes several Distributions and
KeyGeneratorDatas.

Each workload in our suite have several obligatory parameters:

  * •

a working range of keys;

  * •

a size of a data structure before the benchmark;

  * •

a number of working threads during the benchmark;

  * •

a number of threads at the prefill phase;

  * •

a duration of the benchmarking process.

###  2.1. Distributions

We start with the low-level entity — Distribution. A distribution is used to
simulate some random variable. It is important to note that it generates some
value from a distribution that later translates into a key. The KeyGenerator
later uses this value in its calculations of the next key. Distribution
provides a method next() that generates a value of a random variable,
typically restricted to some range. There exists an extended version of
Distribution — MutableDistribution. Its main difference is that
MutableDistribution can change the random variable in progress by modifying
the range of keys: setRange(int range) and next(int range).

To create a Distribution object one could use a DistributionsBuilder. Please,
see an example below.

###  2.2. KeyGeneratorData

KeyGeneratorData does not have a single standard. Typically, it maintains an
array of shuffled keys from the range. Then, KeyGenerator gets a key by
feeding a value (or an index) generated by Distribution to our
KeyGeneratorData.

###  2.3. KeyGenerators

KeyGenerator should be able to generate keys for each type of operation. It
implements four methods: nextGet(), nextInsert(), nextRemove(), and
nextPrefill(). The last operation is used to prefill the index data structure
before applying operations in a ThreadLoop prefill() method. This prefill
operation is important for KeyGenerators with specific needs.

In order to simplify the creation of a new KeyGenerator object, one can use a
KeyGeneratorBuilder. It generates a KeyGenerator for each thread running a
ThreadLoop.

###  2.4. ThreadLoops

ThreadLoop is an infinite loop that decides which operation to execute next.
It is created for each thread separately and, thus, uses the corresponding
KeyGenerator. ThreadLoop has two main methods: prefill() and run(). The first
method explains how to prefill a data structure before benchmarking. The
second method explains how to choose operations and perform it during the main
phase. Default ThreadLoop randomly chooses the next operation using the
uniform distribution, receives the key for the selected operation from the
KeyGenerator, and executes it. Of course, one can implement their own version
of ThreadLoop by extending the ThreadLoopAbstract class.

Note that ThreadLoop also calculates different statistics, for example, the
number of successful operations. This is important for the benchmark in order
to compare different data structures and check their correctness.

###  2.5. Example

As an example, we explain on how to implement the skewed read-update workload
from (Aksenov et al., 2023) in our suite. We start with a brief description of
that workload.

This workload is specified by five parameters $n-w-x-y-s$:

  * •

$n$, the size of the workset of keys;

  * •

$w\%$, the amount of updates performed;

  * •

$x\%$ of get operations choose a key uniformly at random from a random subset
of keys of proportion $y\%$, while other get operations choose a random key
from the rest of the set;

  * •

insert and remove operation choose a key uniformly at random from a random
subset of keys of proportion $s\%$.

We explain what these parameters mean in the terms of the entities described
earlier. The first parameter, $n$, mentioned in section 2, is the range of
keys. The second parameter, $w$, is the probability to choose an update
(insert and erase) operation in the ThreadLoop. Parameters $x$ and $y$ affect
three entities at once: Distribution, KeyGeneratorData, and KeyGenerator. For
get operation, the Distribution generates a random variable from $[0;y\cdot
n)$ uniformly with a probability of $x\%$ and a random variable from $[y\cdot
n,n)$ uniformly with a probability of $100-x\%$. We name this distribution the
Skewed Uniform Distribution. As a KeyGeneratorData we take just a shuffled
array. Using these Distribution and Data, the KeyGenerator generates a key for
get operations. Finally, in a similar manner, we can explain a parameter $s$.

Now, we give a more detailed description of all entities used in this
workload.

####  2.5.1. Distribution

In this workload we need two distributions: a Uniform Distribution and a
Skewed Uniform Distribution explained above. The Uniform Distribution is quite
simple and is available out of the box in the benchmarking suite. Thus, we
explain on how to implement the Skewed Uniform Distribution. Together with
Data, it is used to generate the keys for get operations in the KeyGenerator.

To start with, we need to add the distribution type to the DistributionType
enum:

⬇

enum DistributionType:

{...}, SKEWED_UNIFORM

Then, we need to provide parameters $x\%$ and $y\%$ to this distribution. For
that, we need to create a parameters object:

⬇

class SkewedUniformParameters:

double HOT_SIZE = 0 // y%

double HOT_PROB = 0 // x%

The user needs to write a parser for the command line in DistributionBuilder
in order to extract the parameters for our Distribution:

We are ready to implement SkewedUniformDistribution. Since we need to choose a
value uniformly from both sets $[0,y\cdot n)$ and $[y\cdot n,n)$,
corresponding to $x\%$ and $100-x\%$, one can use just two different Uniform
Distribution objects.

⬇

class SkewedUniformDistribution

implements Distribution:

int hotLength

double hotProb

UniformDistribution hotDist

UniformDistribution coldDist

Random random

int next():

if (random.nextDouble() < hotProb):

return hotDist.next()

else:

return hotLength + coldDist.next()

Distribution returns only a random variable value, not an operation argument.
We need to use KeyGeneratorData to translate this value into a key.

To finish with the implementation of the new Distribution, the user should
write a specific builder in DistributionBuilder (by default,
DistributionBuilder builds the UniformDistribution).

⬇

Distribution getDistribution(int range):

switch (this.distributionType) {

case SKEWED_UNIFORM:

int hotLength = parameters.HOT_SIZE * range;

return new SkewedUniformDistribution(

hotLength,

parameters.HOT_PROB,

new DistributionBuilder()

.getDistribution(hotLength),

new DistributionBuilder()

.getDistribution(range - hotLength))

case {...}

####  2.5.2. KeyGenerator

After the Distribution, we can implement a new KeyGenerator, EXAMPLE_KEYGEN.
We should notify the system about its existence by appending into
KeyGeneratorType enum:

⬇

enum KeyGeneratorType:

{...}, EXAMPLE_KEYGEN

KeyGenerator takes three parameters: $x$, $y$, and $s$, discussed above. $x$,
$y$ are used for the Skewed Uniform Distribution and $s$ is used for the
Uniform Distribution.

At first, we need to provide the parameters to a KeyGenerator. We use build()
function to set up all Distributions.

⬇

class ExampleParameters extends Parameters:

DistributionBuilder getDistBuilder =

new DistributionBuilder(SKEWED_UNIFORM)

DistributionBuilder updateDistBuilder =

new DistributionBuilder(UNIFORM)

double x, y, s

void build():

super.build()

getDistBuilder.setParameters(

new SkewedUniformParameters(x, y))

Then, one should implement the interface of the KeyGenerator:

⬇

interface KeyGenerator:

int nextRead()

int nextInsert()

int nextErase()

int nextPrefill()

Since the Distribution returns random variables, the KeyGenerator needs a tool
to convert them into keys and that is KeyGeneratorData. In this case, the
KeyGeneratorData takes all keys from the entire range and shuffles them. Then,
KeyGenerator takes the index generated by the Distribution and passes it to
the KeyGeneratorData that returns the corresponding key. In our case, we need
two KeyGeneratorData for read and update operations separately.

⬇

class ExampleKeyGenerator implements KeyGenerator:

KeyGeneratorData getData

KeyGeneratorData updateData

Distribution getDist

Distribution updateDist

int nextGet():

return getData.get(getDist.next())

int nextInsert():

return updateData.get(updateDist.next())

int nextRemove():

return updateData.get(updateDist.next())

KeyGeneratorBuilder is the next step in the implementation of the
KeyGenerator. The generateKeyGenerators() method creates an array of
ExampleKeyGenerator, one for each thread, and initializes them:

⬇

class ExampleKeyGeneratorBuilder

extends KeyGeneratorBuilder:

KeyGenerator[] generateKeyGenerators():

KeyGenerator[] keygens =

new KeyGenerator[parameters.numThreads]

KeyGeneratorData getData =

new KeyGeneratorData(parameters)

KeyGeneratorData updateData =

new KeyGeneratorData(parameters)

for (i = 0; i < parameters.numThreads; i++):

keygens[i] = new ExampleKeyGenerator(

getData, updateData,

parameters.getDistBuilder

.getDistribution(parameters.range),

parameters.upadeteDistBuilder

.getDistribution(parameters.s *

parameters.range))

return keygens

At the end, the user should add his KeyGenerator to
the parseKeyGenerator() method in Parameters class.

####  2.5.3. ThreadLoop

The implementation of a new ThreadLoop consists of four parts: 1) an
implementation of the ThreadLoopAbstract class, i.e., run() and prefill()
operations; 2) an implementation of the ThreadLoopParameters interface with a
list of parameters and parseArg() operation; 3) add the new ThreadLoop to the
parseThreadLoop() method in Parameters class; and 4) add the new ThreadLoop
through initThreads() method in the main Test class.

The ThreadLoop interface exports two main methods: run() and prefill(). The
run method is pretty simple: while the stop flag is false, the method selects
a next operation, executes it, and collects statistics. The prefill() method
takes an AtomicInteger prefillSize as an argument. Its value indicates how
many keys are left to add. This variable is an AtomicInteger since we should
allow to prefill the structure with several threads. Here is an example of its
implementation:

⬇

void prefill(AtomicInteger prefillSize):

while (prefillSize.get() > 0):

int curSize = prefillSize.decrementAndGet()

int v = keygen.nextPrefill()

if (curSize < 0

|| bench.putIfAbsent(v, v) != null):

prefillSize.incrementAndGet()

One can say that prefill() should be performed sequentially, not concurrently
by different threads — here, we point to the discussion by Brown et al.
(Kharal and Brown, 2022). If one still wants the prefill to be sequential,
there is a possibility — the user need to set the number of prefilling threads
to one.

##  3\. Implemented Distributions

In this Section, we overview Distributions provided in our benchmark out of
the box.

###  3.1. Uniform Distribution

In the Uniform Distribution, a random value is generated with equal
probability from a specified range. The Uniform Distribution implements
MutableDistribution interface since it does not restrict the range of values.
In other words, we can generate a random value using random.nextInt(range).

###  3.2. Skewed Uniform Distribution

The Skewed Uniform Distribution was explained above, in section 2.5.1.

###  3.3. Zipfian Distribution

The Zipfian Distribution is based on Zipf’s law (Powers, 1998).

##  4\. Implemented KeyGenerators

In this section, all KeyGeneratorData objects generate an array of keys from
the entire range and shuffles it (2.5.2). When choosing an argument a
KeyGenerator sends an index, i.e., a generated value by a Distribution, to the
KeyGeneratorData and gets the corresponding key. User can enable non-shuffle
mode for such KeyGeneratorData implementations.

###  4.1. Default KeyGenerator

The Default KeyGenerator accepts one of the existing distributions as input
and selects the next key based on this distribution from KeyGeneratorData.

###  4.2. Skewed Sets KeyGenerator

Now, we present the Skewed Sets KeyGenerator which is an improvement of the
KeyGenerator described in section 2.5.2.

This KeyGenerator uses two SkewedUniformDistributions separately for read and
update operations. It takes the following parameters:

  * •

$rp\%$ of read operations are performed on a random subset of keys of
proportion $rs\%$ where a key is taken uniformly. All other read operations
are performed on the rest of the set.

  * •

$wp\%$ of update operations are performed on a random subset of keys of
proportion $ws\%$ where a key is taken uniformly. All other update operations
are performed on the rest of the set.

  * •

$inter\%$ of keys are in the intersection of the working sets of read and
update operations.

###  4.3. Temporary Skewed Sets KeyGenerator

The TemporarySkewedKeyGenerator is motivated by the fact that a user may want
to ask frequently different subsets of keys in different periods of time. For
example, one wants to know the weather in the morning, search for a work-
related data in the afternoon, and read the news in the evening. To simulate
this, the Temporary Skewed Sets KeyGenerator has two types of states:

  * •

$k$-th _excited_ state — the keys are selected using $k$-th
SkewedUniformDistribution, i.e., there is a hot set of keys.

  * •

a _dormant_ state — all keys are selected with the UniformDistribution. This
state happens between $k$-th and $k+1$-th excited states.

Please, note that this workload is infinite — the excited states are chosen in
a cyclic manner, i.e., after the latest _excited_ state we get into the first
one again through the dormant state.

The TemporarySkewedKeyGenerator uses the following parameters:

  * •

$state$-$count$ — a total number of excited states in the workload;

  * •

$ht$ — the default duration of an excited state (the duration is specified in
number of iterations);

  * •

$rt$ — the default duration of a dormant state;

  * •

during the $i$-th excited state, $p_{i}\%$ of operations are performed on
$s_{i}\%$ of keys, and $100-p_{i}\%$ of operations are performed on the rest
of the set;

  * •

$ht_{i}$ — the duration of the $i$-th excited state, if necessary to set
explicitly;

  * •

$rt_{i}$ — the duration of the dormant state after $i$-th excited state, if
necessary to set explicitly.

###  4.4. Creakers and Wave KeyGenerator

The Creakers and Wave Key Generator is based on the observation that the
recently inserted keys are requested more often. They become obsolete over
time and, consequently, are rarely requested. This workload is similar to
workload D from YCSB with the Latest distribution: where more frequently
accessed keys have higher probability to be an argument in the future.

For example, musical hits are listened to more often when they have just been
released. Then, something new is released and the old is listened to less. To
simulate this behaviour, the Creakers and Wave KeyGenerator has an entity
Wave. The Wave is a subset of all keys from the range with a head and a tail.
When it generates a new key, it adheres to the following rules:

  * •

nextRemove() — the Wave returns the key of the current tail and moves this
tail by one;

  * •

nextInsert() — we choose the key, next to the head of the Wave, and make it a
new head;

  * •

nextGet() — we select a key from the Wave with some specified distribution.

As a default, Wave uses the Zipfian Distribution, where the closer the key is
to the head, the greater the probability of being selected. Since there is a
limit on the range of elements, to make the workload infinite the Wave moves
in a cyclic manner over a working set of keys. Besides the Wave there is an
entity called Creakers. This is a subset of keys that are requested rarely but
permanently. This entity is needed to check how well the data structure copes
with such keys in the presence of rapidly growing and equally rapidly
discarded keys from the Wave.

The Creakers and Wave KeyGenerator has the following parameters:

  * •

$cp\%$ of operations are performed on $cs\%$ of keys (Creakers entity), and
$100-cp\%$ are performed on the Wave entity;

  * •

The Wave is initialized with $ws\%$ of keys;

  * •

$c$-$age$ get operations are performed on the Creakers entity during warmup
before the benchmarking;

  * •

$c$-$distribution$ — a distribution of keys in the Creakers entity, the
Uniform distribution by default;

  * •

$w$-$distribution$ — a mutable distribution of keys in the Wave entity: the
Zipfian distribution with $\alpha=1$ by default.

All threads share the Wave head and tail.

One could argue that this workload is a copy of workload D from YCSB. There
are two observations that highlight the differences. At first, our workload is
infinite, while YCSB is predefined. There is no doubt that one can make YCSB
work infinity, but the corresponding generator cannot generate a key with a
time complexity of $O(1)$ in the runtime. This definitely affects the
workload. Secondly, we added Creakers to our workload. Logically, nothing
should really change — we just added some small permanent loads that always
happen to the systems. However, it is a huge change for self-adjusting data
structures (Aksenov et al., 2023; Afek et al., 2014). The known
implementations store a counter for each element, i.e., how many it was
requested. The bigger the counter the faster the element is accessed. The
problem occurs when elements are removed and lose their their whole counter.
Thus, if we consider infinite execution, Creakers will have the largest
counters, while the elements from the Wave will have smaller counters due to
the insertion and removals. Obviously, this has a huge impact on the
performance of the aforementioned index implementations.

###  4.5. Leafs Handshake KeyGenerator

In the Leafs Handshake Key Generator, the key selection for an insert
operation is based on the argument of the previous remove operation.
Intuitively, the closer the key to the last removed one, the more probability
that this key will be selected to insert. It accepts the following parameters:

  * •

$get$-$distribution$ — a distribution of keys for a get operation (by default,
the Uniform distribution);

  * •

$remove$-$distribution$ — a distribution of keys for a remove operation (by
default, the Uniform distribution);

  * •

$insert$-$distribution$ — a mutable distribution of keys for an insert
operation (by default, the Zipfian distribution with $\alpha=1$).

##  5\. Implemented ThreadLoops

###  5.1. Default ThreadLoop

The Default ThreadLoop selects the next operation with some fixed constant
probability. It accepts the following parameters:

  * •

$ui\%$ of operations are insert operations;

  * •

$ue\%$ of operations are remove operations.

###  5.2. Temporary Operations ThreadLoop

The Temporary Operations ThreadLoop selects the next operation depending on a
time interval. It accepts the following parameters:

  * •

$temp$-$oper$-$count$ — a number of different intervals;

  * •

$ot_{i}$ — a duration of $i$-th interval in the number of operations;

  * •

$ui_{i}\%$ of operations are insert operations during the $i$-th interval;

  * •

$ue_{i}\%$ of operations are remove operations during the $i$-th interval;

Time intervals are repeated cyclically, giving an infinite workload .

##  6\. Separation of Binary Search Trees

Our benchmark is written in Java and it is available at the link
https://github.com/Mr-Ravil/synchrobench.

We consider three commonly-known binary search tree (BST) implementations in
Java. Our main goal is to show that using our workloads we can show any
possible different relative performance, i.e., there is no obvious winner.
There are six possibilities, since we have only three data structures.

###  6.1. Implementations

We take the three most effective binary search tree (BST) implementations
written in Java:

  * •

A BCCO BST by Bronson et al. (Bronson et al., 2010).

  * •

A Contention-Friendly (CF) BST by Gramoli et al. (Crain et al., 2013).

  * •

A Concurrency-Optimal (CO) BST by Aksenov et al. (Aksenov et al., 2017).

All of them are partially-external and the the main difference between them is
how they handle physical removal and rotation. In the BCCO-BSTa working thread
always removes nodes physically and rotates subtrees, if necessary. In the CF-
BSTa working thread makes only logical removals. However, there is a special
daemon thread responsible for physical removals and rotations. In the CO-BSTa
thread performs physical removal immediately but does not perform rotations at
all.

Looking on the experiments from the previous papers using the workloads from
Synchrobench, e.g., (Aksenov et al., 2017), one could decide that Concurrency-
Optimal is the superior one, the runner-up is Contention-Friendly, and the
last one is BCCO. Obviously, it should not be the case on all the possible
workloads because: 1) CO does not make rotations at all, leading to longer
traversals; 2) CF should perform worse on the larger trees, since the daemon
thread could not catch up with changes. We show that it is indeed the case:
depending on the workload we can see different relative performance. Prior to
that, we must introduce a small change to the Concurrency-Friendly
implementation that sometimes improves performance by a large amount.

####  6.1.1. Concurrency-Friendly Improvement

During the experiments, we found that it is possible to improve the daemon
thread algorithm. In the Synchrobench implementation, the thread attempts to
remove the node first, and, then, runs recursively. However, we can go
recursively to children, and only after that we can restructure the node
itself.

Thus, if there are $N$ elements in the tree and all of them are logically
removed, in our algorithm the daemon requires one call of a recursive
restructure function. While the daemon thread from the Synchrobench version
requires $\log N$ calls leading to $\sum\limits_{i=1}^{\log
N}(2^{i}-1)=2N-\log N-2$ operations. We could conclude that the daemon thread
algorithm from Synchrobench is almost twice as slow, which may affect the
overall throughput. In the experiments, we call our implementation as Fixed
Concurrency-Friendly version.

###  6.2. Experimental Results

We evaluateed workloads on two-processor Intel Xeon Gold 6240R with $24$ cores
each, giving $48$ cores in total. We show results starting from 16 working
threads, since this is the most interesting part. Each plot has four graphs:
blue (CO), yellow (Fixed CF), green (CF), and red (BCCO). OX axis represents
the number of used threads, and OY axis represents the throughput, i.e., the
number of operations performed in one second. Each point in plots is the
result of an experiment performed $10$ times for $10$ seconds.

####  6.2.1. Uniform and Zipfian Workloads

Uniform and Zipfian Workloads are the most common workloads. We run it with
the following parameters: range is $10^{4}$ (for Uniform) and $10^{5}$ (for
Zipfian) and update ratio is $20\%$ (for Uniform) and $5\%$ (for Zipfian).
$insert$ ratio is equal to $remove$ ratio.

Figure 1. Uniform Workload with range $10^{4}$ and update ratio $20\%$

The results can be seen on Figures 1 and 2. Both workloads have the same
resulting pattern: CO-CF-B, i.e., the first – Concurrency-Optimal, the second
— Concurrency-Friendly, and the third — BCCO.

Figure 2. Zipfian Workload with $\alpha=1$, range $10^{5}$ and update ratio
$5\%$.

####  6.2.2. Infinite Leafs Handshake Workload

Since BCCO-BST always rotates and removes physically, one expects it to be too
far behind in terms of throughput. But that does not mean that it works badly
on any workload. We present the Infinite Leafs Handshake Workload that is
based on the Leafs Handshake KeyGenerator 4.5 and the Temporary Operations
ThreadLoop 5.2. It has three time intervals: 1) the filling interval — there
are more insertions than removal; 2) the read interval — there are only read
operations; 3) the cleaning interval — there are more removals than
insertions.

During the filling interval, for one removed node, two new neighbors are
inserted. During the reading interval, the working threads just read the keys
uniformly at random. During the cleaning interval, the working threads remove
nodes uniformly at random from the tree to restore its original size. This
phase is added to make the workload infinite.

The first experiment (Figure 3) is run with parameters: range is $10^{5}$,
temp-oper-count is $3$; $ot_{0}=ot_{2}=10000$, $ot_{1}=5000$;
$ui_{0}=ue_{2}=60\%$; $ui_{2}=ue_{0}=40\%$; $ui_{1}=ue_{1}=0\%$; get and
remove distributions are uniform distributions; insert distribution is a
Zipfian distribution with $\alpha=2$. It gives us the relative performance of
CF-CO-B.

Figure 3. Infinite Leafs Handshake Workload with range $10^{5}$.

The second experiment (Figure 4) is run with parameters: range is $10^{7}$;
temp-oper-count is $2$; $ot_{0}=ot_{1}=20000$; $ui_{0}=ue_{1}=90\%$;
$ui_{1}=ue_{0}=10\%$; get and remove distributions are Uniform; and insert-
distribution is a Zipfian distribution with $\alpha=0.99$. It gives us the
relative of performance B-CO-CF.

Figure 4. Infinite Leafs Handshake Workload with range $10^{7}$.

The third experiment (Figure 5) is run with parameters: range is $10^{8}$;
temp-oper-count is $3$; $ot_{0}=ot_{1}=ot_{2}=100000$; $ui_{0}=ue_{2}=80\%$;
$ui_{2}=ue_{0}=20\%$; $ui_{1}=ue_{1}=0\%$; get and remove distributions are
Uniform; insert distribution is a Zipfian distribution with $\alpha=0.99$. It
gives us the relative performance of CO-B-CF.

Figure 5. Infinite Leafs Handshake Workload with range $10^{8}$

From the results, it can be seen that CF-BST lags far behind at large ranges
(Figures 4 and 5), while at small ranges it behaves about the same or better
than others (Figure 3).This happens because the daemon thread does not catch
up with remove operations and the tree has a longer traversal length. Also,
CO-BST and BCCO-BST behave differently at large ranges. The less skew between
insert and remove operations, the better CO-BST handles the workload. This is
because with more skew there are more chances that the tree will grow non-
uniformly, which makes the CO-BST perform poorly.

####  6.2.3. Non-shuffle Wave Workload

The Non-shuffle Wave Workload is based on Creakers and Wave KeyGenerator 4.4
without the Creakers and the shuffle in KeyGeneratorData. This workload adds
new keys to the edge of the tree disrupting the balance. That leads to the
performance problems of poorly balanced trees.

The first experiment (Figure 6) is run with parameters: range is $10^{6}$;
$ws=20\%$; update ratio is $5\%$; $w$-$distribution$ — Zipfian distribution
with $\alpha=1$; and $cp=0\%$. It gives us the relative performance of CF-B-
CO.

Figure 6. Non-shuffle Wave Workload with range $10^{6}$.

This result is again related to the fact that the BCCO-BST always rotates
which is not the case of CF-BST and CO-BST.

The second experiment (Figure 7) is run with parameters: range is $5\cdot
10^{3}$; $ws=10\%$; write ratio is $20\%$; $w$-$distribution$ — Zipfian
distribution with $\alpha=1$; $cp=0\%$. It gives us the relative performance
of B-CF-CO.

Figure 7. Non-shuffle Wave Workload with range $5\cdot 10^{3}$.

This result is related to the fact that the tree size is quite small, which is
why the daemon thread in CF-BST manages to balance the tree quickly.

###  6.3. Summary

As a result we obtained all six relative performances of three data
structures: B-CF-CO on Figure 7, B-CO-CF on Figure 4, CF-B-CO on Figure 6, CF-
CO-B on Figure 3, CO-B-CF on Figure 5, and CO-CF-B on Figures 1 and 2.

##  7\. Conclusion

In this work, we presented a new benchmarking suite that tries to solve issues
that appeared in other known suites. There we introduced several workloads
inspired by real-life. At the end, we showed the most important observation of
the paper. The benchmarking process of different data structures is a really
complicated problem and it should be done with care: depending on the workload
one can get totally “contradictory” results that can affect the conclusion
about the performance.

As for future work, we want to polish the suite for Java and prepare the
similar suite for C++.

## References

  * (1)
  * TPC ([n. d.) ]TPC [n. d.].  TPC benchmarks.  https://www.tpc.org/.
  * Afek et al. (2014) Yehuda Afek, Haim Kaplan, Boris Korenfeld, Adam Morrison, and Robert E Tarjan. 2014.  The CB tree: a practical concurrent self-adjusting search tree.  _Distributed computing_ 27, 6 (2014), 393–417.
  * Aksenov et al. (2023) Vitaly Aksenov, Dan Alistarh, Alexandra Drozdova, and Amirkeivan Mohtashami. 2023.  The splay-list: A distribution-adaptive concurrent skip-list.  _Distributed Computing_ (2023), 1–24.
  * Aksenov et al. (2017) Vitaly Aksenov, Vincent Gramoli, Petr Kuznetsov, Anna Malova, and Srivatsan Ravi. 2017.  A concurrency-optimal binary search tree. In _Euro-Par 2017: Parallel Processing: 23rd International Conference on Parallel and Distributed Computing, Santiago de Compostela, Spain, August 28–September 1, 2017, Proceedings 23_. Springer, 580–593.
  * Bronson et al. (2010) Nathan G Bronson, Jared Casper, Hassan Chafi, and Kunle Olukotun. 2010.  A practical concurrent binary search tree.  _ACM Sigplan Notices_ 45, 5 (2010), 257–268.
  * Brown et al. (2020) Trevor Brown, Aleksandar Prokopec, and Dan Alistarh. 2020\.  Non-blocking interpolation search trees with doubly-logarithmic running time. In _Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming_. 276–291.
  * Cooper et al. (2010) Brian F Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010\.  Benchmarking cloud serving systems with YCSB. In _Proceedings of the 1st ACM symposium on Cloud computing_. 143–154.
  * Crain et al. (2013) Tyler Crain, Vincent Gramoli, and Michel Raynal. 2013\.  A contention-friendly binary search tree. In _Euro-Par 2013 Parallel Processing: 19th International Conference, Aachen, Germany, August 26-30, 2013. Proceedings 19_. Springer, 229–240.
  * Gramoli (2015) Vincent Gramoli. 2015\.  More than you ever wanted to know about synchronization: Synchrobench, measuring the impact of the synchronization on concurrent algorithms. In _Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming_. 1–10.
  * Kharal and Brown (2022) Rosina Kharal and Trevor Brown. 2022.  Performance Anomalies in Concurrent Data Structure Microbenchmarks.  _arXiv preprint arXiv:2208.08469_ (2022).
  * Powers (1998) David MW Powers. 1998\.  Applications and explanations of Zipf’s law. In _New methods in language processing and computational natural language learning_.