---
_id: '12330'
abstract:
- lang: eng
  text: 'The design and implementation of efficient concurrent data structures has
    seen significant attention. However, most of this work has focused on concurrent
    data structures providing good worst-case guarantees, although, in real workloads,
    objects are often accessed at different rates. Efficient distribution-adaptive
    data structures, such as splay-trees, are known in the sequential case; however,
    they often are hard to translate efficiently to the concurrent case. We investigate
    distribution-adaptive concurrent data structures, and propose a new design called
    the splay-list. At a high level, the splay-list is similar to a standard skip-list,
    with the key distinction that the height of each element adapts dynamically to
    its access rate: popular elements “move up,” whereas rarely-accessed elements
    decrease in height. We show that the splay-list provides order-optimal amortized
    complexity bounds for a subset of operations, while being amenable to efficient
    concurrent implementation. Experiments show that the splay-list can leverage distribution-adaptivity
    for performance, and can outperform the only previously-known distribution-adaptive
    concurrent design in certain workloads.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Vitalii
  full_name: Aksenov, Vitalii
  id: 2980135A-F248-11E8-B48F-1D18A9856A87
  last_name: Aksenov
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
- first_name: Alexandra
  full_name: Drozdova, Alexandra
  last_name: Drozdova
- first_name: Amirkeivan
  full_name: Mohtashami, Amirkeivan
  last_name: Mohtashami
citation:
  ama: 'Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. The splay-list: A distribution-adaptive
    concurrent skip-list. <i>Distributed Computing</i>. 2023;36:395-418. doi:<a href="https://doi.org/10.1007/s00446-022-00441-x">10.1007/s00446-022-00441-x</a>'
  apa: 'Aksenov, V., Alistarh, D.-A., Drozdova, A., &#38; Mohtashami, A. (2023). The
    splay-list: A distribution-adaptive concurrent skip-list. <i>Distributed Computing</i>.
    Springer Nature. <a href="https://doi.org/10.1007/s00446-022-00441-x">https://doi.org/10.1007/s00446-022-00441-x</a>'
  chicago: 'Aksenov, Vitalii, Dan-Adrian Alistarh, Alexandra Drozdova, and Amirkeivan
    Mohtashami. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” <i>Distributed
    Computing</i>. Springer Nature, 2023. <a href="https://doi.org/10.1007/s00446-022-00441-x">https://doi.org/10.1007/s00446-022-00441-x</a>.'
  ieee: 'V. Aksenov, D.-A. Alistarh, A. Drozdova, and A. Mohtashami, “The splay-list:
    A distribution-adaptive concurrent skip-list,” <i>Distributed Computing</i>, vol.
    36. Springer Nature, pp. 395–418, 2023.'
  ista: 'Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. 2023. The splay-list:
    A distribution-adaptive concurrent skip-list. Distributed Computing. 36, 395–418.'
  mla: 'Aksenov, Vitalii, et al. “The Splay-List: A Distribution-Adaptive Concurrent
    Skip-List.” <i>Distributed Computing</i>, vol. 36, Springer Nature, 2023, pp.
    395–418, doi:<a href="https://doi.org/10.1007/s00446-022-00441-x">10.1007/s00446-022-00441-x</a>.'
  short: V. Aksenov, D.-A. Alistarh, A. Drozdova, A. Mohtashami, Distributed Computing
    36 (2023) 395–418.
date_created: 2023-01-22T23:00:55Z
date_published: 2023-09-01T00:00:00Z
date_updated: 2025-07-22T14:06:00Z
day: '01'
department:
- _id: DaAl
doi: 10.1007/s00446-022-00441-x
external_id:
  arxiv:
  - '2008.01009'
  isi:
  - '000913424000001'
  oaworkID:
  - w4390499170
intvolume: '        36'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2008.01009
month: '09'
oa: 1
oa_version: Preprint
oaworkID: 1
page: 395-418
publication: Distributed Computing
publication_identifier:
  eissn:
  - 1432-0452
  issn:
  - 0178-2770
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'The splay-list: A distribution-adaptive concurrent skip-list'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 36
year: '2023'
...
---
_id: '9571'
abstract:
- lang: eng
  text: As the size and complexity of models and datasets grow, so does the need for
    communication-efficient variants of stochastic gradient descent that can be deployed
    to perform parallel model training. One popular communication-compression method
    for data-parallel SGD is QSGD (Alistarh et al., 2017), which quantizes and encodes
    gradients to reduce communication costs. The baseline variant of QSGD provides
    strong theoretical guarantees, however, for practical purposes, the authors proposed
    a heuristic variant which we call QSGDinf, which demonstrated impressive empirical
    gains for distributed training of large neural networks. In this paper, we build
    on this work to propose a new gradient quantization scheme, and show that it has
    both stronger theoretical guarantees than QSGD, and matches and exceeds the empirical
    performance of the QSGDinf heuristic and of other compression methods.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Ali
  full_name: Ramezani-Kebrya, Ali
  last_name: Ramezani-Kebrya
- first_name: Fartash
  full_name: Faghri, Fartash
  last_name: Faghri
- first_name: Ilya
  full_name: Markov, Ilya
  last_name: Markov
- first_name: Vitalii
  full_name: Aksenov, Vitalii
  id: 2980135A-F248-11E8-B48F-1D18A9856A87
  last_name: Aksenov
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
- first_name: Daniel M.
  full_name: Roy, Daniel M.
  last_name: Roy
citation:
  ama: 'Ramezani-Kebrya A, Faghri F, Markov I, Aksenov V, Alistarh D-A, Roy DM. NUQSGD:
    Provably communication-efficient data-parallel SGD via nonuniform quantization.
    <i>Journal of Machine Learning Research</i>. 2021;22(114):1−43.'
  apa: 'Ramezani-Kebrya, A., Faghri, F., Markov, I., Aksenov, V., Alistarh, D.-A.,
    &#38; Roy, D. M. (2021). NUQSGD: Provably communication-efficient data-parallel
    SGD via nonuniform quantization. <i>Journal of Machine Learning Research</i>.
    Journal of Machine Learning Research.'
  chicago: 'Ramezani-Kebrya, Ali, Fartash Faghri, Ilya Markov, Vitalii Aksenov, Dan-Adrian
    Alistarh, and Daniel M. Roy. “NUQSGD: Provably Communication-Efficient Data-Parallel
    SGD via Nonuniform Quantization.” <i>Journal of Machine Learning Research</i>.
    Journal of Machine Learning Research, 2021.'
  ieee: 'A. Ramezani-Kebrya, F. Faghri, I. Markov, V. Aksenov, D.-A. Alistarh, and
    D. M. Roy, “NUQSGD: Provably communication-efficient data-parallel SGD via nonuniform
    quantization,” <i>Journal of Machine Learning Research</i>, vol. 22, no. 114.
    Journal of Machine Learning Research, p. 1−43, 2021.'
  ista: 'Ramezani-Kebrya A, Faghri F, Markov I, Aksenov V, Alistarh D-A, Roy DM. 2021.
    NUQSGD: Provably communication-efficient data-parallel SGD via nonuniform quantization.
    Journal of Machine Learning Research. 22(114), 1−43.'
  mla: 'Ramezani-Kebrya, Ali, et al. “NUQSGD: Provably Communication-Efficient Data-Parallel
    SGD via Nonuniform Quantization.” <i>Journal of Machine Learning Research</i>,
    vol. 22, no. 114, Journal of Machine Learning Research, 2021, p. 1−43.'
  short: A. Ramezani-Kebrya, F. Faghri, I. Markov, V. Aksenov, D.-A. Alistarh, D.M.
    Roy, Journal of Machine Learning Research 22 (2021) 1−43.
date_created: 2021-06-20T22:01:33Z
date_published: 2021-04-01T00:00:00Z
date_updated: 2024-03-06T12:22:07Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
external_id:
  arxiv:
  - '1908.06077'
file:
- access_level: open_access
  checksum: 6428aa8bcb67768b6949c99b55d5281d
  content_type: application/pdf
  creator: asandaue
  date_created: 2021-06-23T07:09:41Z
  date_updated: 2021-06-23T07:09:41Z
  file_id: '9595'
  file_name: 2021_JournalOfMachineLearningResearch_Ramezani-Kebrya.pdf
  file_size: 11237154
  relation: main_file
  success: 1
file_date_updated: 2021-06-23T07:09:41Z
has_accepted_license: '1'
intvolume: '        22'
issue: '114'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.jmlr.org/papers/v22/20-255.html
month: '04'
oa: 1
oa_version: Published Version
page: 1−43
publication: Journal of Machine Learning Research
publication_identifier:
  eissn:
  - '15337928'
  issn:
  - '15324435'
publication_status: published
publisher: Journal of Machine Learning Research
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'NUQSGD: Provably communication-efficient data-parallel SGD via nonuniform
  quantization'
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 22
year: '2021'
...
---
_id: '7214'
abstract:
- lang: eng
  text: "Background: Many cancer genomes are extensively rearranged with highly aberrant
    chromosomal karyotypes. Structural and copy number variations in cancer genomes
    can be determined via abnormal mapping of sequenced reads to the reference genome.
    Recently it became possible to reconcile both of these types of large-scale variations
    into a karyotype graph representation of the rearranged cancer genomes. Such a
    representation, however, does not directly describe the linear and/or circular
    structure of the underlying rearranged cancer chromosomes, thus limiting possible
    analysis of cancer genomes somatic evolutionary process as well as functional
    genomic changes brought by the large-scale genome rearrangements.\r\n\r\nResults:
    Here we address the aforementioned limitation by introducing a novel methodological
    framework for recovering rearranged cancer chromosomes from karyotype graphs.
    For a cancer karyotype graph we formulate an Eulerian Decomposition Problem (EDP)
    of finding a collection of linear and/or circular rearranged cancer chromosomes
    that are determined by the graph. We derive and prove computational complexities
    for several variations of the EDP. We then demonstrate that Eulerian decomposition
    of the cancer karyotype graphs is not always unique and present the Consistent
    Contig Covering Problem (CCCP) of recovering unambiguous cancer contigs from the
    cancer karyotype graph, and describe a novel algorithm CCR capable of solving
    CCCP in polynomial time. We apply CCR on a prostate cancer dataset and demonstrate
    that it is capable of consistently recovering large cancer contigs even when underlying
    cancer genomes are highly rearranged.\r\n\r\nConclusions: CCR can recover rearranged
    cancer contigs from karyotype graphs thereby addressing existing limitation in
    inferring chromosomal structures of rearranged cancer genomes and advancing our
    understanding of both patient/cancer-specific as well as the overall genetic instability
    in cancer."
article_number: '641'
article_processing_charge: No
article_type: original
author:
- first_name: Sergey
  full_name: Aganezov, Sergey
  last_name: Aganezov
- first_name: Ilya
  full_name: Zban, Ilya
  last_name: Zban
- first_name: Vitalii
  full_name: Aksenov, Vitalii
  id: 2980135A-F248-11E8-B48F-1D18A9856A87
  last_name: Aksenov
- first_name: Nikita
  full_name: Alexeev, Nikita
  last_name: Alexeev
- first_name: Michael C.
  full_name: Schatz, Michael C.
  last_name: Schatz
citation:
  ama: Aganezov S, Zban I, Aksenov V, Alexeev N, Schatz MC. Recovering rearranged
    cancer chromosomes from karyotype graphs. <i>BMC Bioinformatics</i>. 2019;20.
    doi:<a href="https://doi.org/10.1186/s12859-019-3208-4">10.1186/s12859-019-3208-4</a>
  apa: Aganezov, S., Zban, I., Aksenov, V., Alexeev, N., &#38; Schatz, M. C. (2019).
    Recovering rearranged cancer chromosomes from karyotype graphs. <i>BMC Bioinformatics</i>.
    BMC. <a href="https://doi.org/10.1186/s12859-019-3208-4">https://doi.org/10.1186/s12859-019-3208-4</a>
  chicago: Aganezov, Sergey, Ilya Zban, Vitalii Aksenov, Nikita Alexeev, and Michael
    C. Schatz. “Recovering Rearranged Cancer Chromosomes from Karyotype Graphs.” <i>BMC
    Bioinformatics</i>. BMC, 2019. <a href="https://doi.org/10.1186/s12859-019-3208-4">https://doi.org/10.1186/s12859-019-3208-4</a>.
  ieee: S. Aganezov, I. Zban, V. Aksenov, N. Alexeev, and M. C. Schatz, “Recovering
    rearranged cancer chromosomes from karyotype graphs,” <i>BMC Bioinformatics</i>,
    vol. 20. BMC, 2019.
  ista: Aganezov S, Zban I, Aksenov V, Alexeev N, Schatz MC. 2019. Recovering rearranged
    cancer chromosomes from karyotype graphs. BMC Bioinformatics. 20, 641.
  mla: Aganezov, Sergey, et al. “Recovering Rearranged Cancer Chromosomes from Karyotype
    Graphs.” <i>BMC Bioinformatics</i>, vol. 20, 641, BMC, 2019, doi:<a href="https://doi.org/10.1186/s12859-019-3208-4">10.1186/s12859-019-3208-4</a>.
  short: S. Aganezov, I. Zban, V. Aksenov, N. Alexeev, M.C. Schatz, BMC Bioinformatics
    20 (2019).
date_created: 2019-12-29T23:00:46Z
date_published: 2019-12-17T00:00:00Z
date_updated: 2023-09-06T14:51:06Z
day: '17'
ddc:
- '570'
department:
- _id: DaAl
doi: 10.1186/s12859-019-3208-4
external_id:
  isi:
  - '000511618800007'
file:
- access_level: open_access
  checksum: 7a30357efdcf8f66587ed495c0927724
  content_type: application/pdf
  creator: dernst
  date_created: 2020-01-02T16:10:58Z
  date_updated: 2020-07-14T12:47:54Z
  file_id: '7221'
  file_name: 2019_BMCBioinfo_Aganezov.pdf
  file_size: 1917374
  relation: main_file
file_date_updated: 2020-07-14T12:47:54Z
has_accepted_license: '1'
intvolume: '        20'
isi: 1
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
publication: BMC Bioinformatics
publication_identifier:
  eissn:
  - '14712105'
publication_status: published
publisher: BMC
quality_controlled: '1'
scopus_import: '1'
status: public
title: Recovering rearranged cancer chromosomes from karyotype graphs
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 20
year: '2019'
...