DROPS

Document

Scalable Data Structures (Dagstuhl Seminar 23211)

Authors: Gerth Stølting Brodal, John Iacono, László Kozma, Vijaya Ramachandran, and Justin Dallant

Published in: Dagstuhl Reports, Volume 13, Issue 5 (2023)

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 23211 "Scalable Data Structures". Data structures enable the organization, storage and retrieval of data across a variety of applications. As they are deployed at unprecedented scales, data structures can profoundly affect the efficiency of almost all computational tasks. The study of data structures thus continues to be an important and active area of research with an interplay between data structure design and analysis, developments in computer hardware, and the needs of modern applications. The extended abstracts included in this report give a snapshot of the current state of research on scalable data structures and establish directions for future developments in the field.

Cite as

Gerth Stølting Brodal, John Iacono, László Kozma, Vijaya Ramachandran, and Justin Dallant. Scalable Data Structures (Dagstuhl Seminar 23211). In Dagstuhl Reports, Volume 13, Issue 5, pp. 114-135, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{brodal_et_al:DagRep.13.5.114,
  author =	{Brodal, Gerth St{\o}lting and Iacono, John and Kozma, L\'{a}szl\'{o} and Ramachandran, Vijaya and Dallant, Justin},
  title =	{{Scalable Data Structures (Dagstuhl Seminar 23211)}},
  pages =	{114--135},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{13},
  number =	{5},
  editor =	{Brodal, Gerth St{\o}lting and Iacono, John and Kozma, L\'{a}szl\'{o} and Ramachandran, Vijaya and Dallant, Justin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.5.114},
  URN =		{urn:nbn:de:0030-drops-193676},
  doi =		{10.4230/DagRep.13.5.114},
  annote =	{Keywords: algorithms, big data, computational models, data structures, GPU computing, parallel computation}
}

Document

DOI: 10.4230/DagRep.11.1.1

Scalable Data Structures (Dagstuhl Seminar 21071)

Authors: Gerth Stølting Brodal, John Iacono, Markus E. Nebel, and Vijaya Ramachandran

Published in: Dagstuhl Reports, Volume 11, Issue 1 (2021)

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 21071 "Scalable Data Structure". Even if the field of data structures is quite mature, new trends and limitations in computer hardware together with the ever-increasing amounts of data that need to be processed raise new questions with respect to efficiency and continuously challenge the existing models of computation. Thermal and electrical power constraints have caused technology to reach "the power wall" with stagnating single processor performance, meaning that all nontrivial applications need to address scalability with multiple processors, a memory hierarchy and other communication challenges. Scalable data structures are pivotal to this process since they form the backbone of the algorithms driving these applications. The extended abstracts included in this report contain both recent state of the art advances and lay the foundation for new directions within data structures research.

Cite as

Gerth Stølting Brodal, John Iacono, Markus E. Nebel, and Vijaya Ramachandran. Scalable Data Structures (Dagstuhl Seminar 21071). In Dagstuhl Reports, Volume 11, Issue 1, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{brodal_et_al:DagRep.11.1.1,
  author =	{Brodal, Gerth St{\o}lting and Iacono, John and Nebel, Markus E. and Ramachandran, Vijaya},
  title =	{{Scalable Data Structures (Dagstuhl Seminar 21071)}},
  pages =	{1--23},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2021},
  volume =	{11},
  number =	{1},
  editor =	{Brodal, Gerth St{\o}lting and Iacono, John and Nebel, Markus E. and Ramachandran, Vijaya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.1.1},
  URN =		{urn:nbn:de:0030-drops-143481},
  doi =		{10.4230/DagRep.11.1.1},
  annote =	{Keywords: algorithms, big data, data structures, GPU computing, large data sets, models of computation, parallel algorithms}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2016.8

Finding k Simple Shortest Paths and Cycles

Authors: Udit Agarwal and Vijaya Ramachandran

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract

We present algorithms and techniques for several problems related to finding multiple simple shortest paths and cycles in a graph. Our main result is a new algorithm for finding k simple shortest paths for all pairs of vertices in a weighted directed graph G = (V, E). For k = 2 our algorithm runs in O(mn + n^2 log n) time where m and n are the number of edges and vertices in G. For k = 3 our algorithm runs in O(mn^2 + n^3 log n) time, which is almost a factor of n faster than the best previous algorithm. Our approach is based on forming suitable path extensions to find simple shortest paths; this method is different from the 'detour finding' technique used in most of the prior work on simple shortest paths, replacement paths, and distance sensitivity oracles. We present new algorithms for generating simple cycles and simple paths in G in non-decreasing order of their weight. The algorithm for generating simple paths is much faster,and uses another variant of path extensions.

Cite as

Udit Agarwal and Vijaya Ramachandran. Finding k Simple Shortest Paths and Cycles. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 8:1-8:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ISAAC.2016.8,
  author =	{Agarwal, Udit and Ramachandran, Vijaya},
  title =	{{Finding k Simple Shortest Paths and Cycles}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{8:1--8:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.8},
  URN =		{urn:nbn:de:0030-drops-67830},
  doi =		{10.4230/LIPIcs.ISAAC.2016.8},
  annote =	{Keywords: Graph Algorithms, Shortest Paths, k Simple Shortest Paths, Enumerat- ing Simple Cycles, Enumerating Simple Paths}
}

Search Results

Documents authored by Ramachandran, Vijaya

Scalable Data Structures (Dagstuhl Seminar 23211)

Abstract

Cite as

Scalable Data Structures (Dagstuhl Seminar 21071)

Abstract

Cite as

Finding k Simple Shortest Paths and Cycles

Abstract

Cite as

Thanks for your feedback!

Could not send message