Search Results

Documents authored by Rossi, S.

Found 8 Possible Name Variants:

Rossi, S.

Document
DOI: 10.4230/DagSemProc.10081.4
Attentive Monitoring and Adaptive Control in Cognitive Robotics

Authors: E. Burattini, Alberto Finzi, S. Rossi, and Maria Carla Staffa

Published in: Dagstuhl Seminar Proceedings, Volume 10081, Cognitive Robotics (2010)

Abstract
In this work, we present an attentional system for a robotic agent capable of adapting its emergent behavior to the surrounding environment and to its internal state. In this framework, the agent is endowed with simple attentional mechanisms regulating the frequencies of sensory readings and behavior activations. The process of changing the frequency of sensory readings is interpreted as an increase or decrease of attention towards relevant behaviors and particular aspects of the external environment. In this paper, we present our framework discussing several case studies considering incrementally complex behaviors and tasks.
Cite as

E. Burattini, Alberto Finzi, S. Rossi, and Maria Carla Staffa. Attentive Monitoring and Adaptive Control in Cognitive Robotics. In Cognitive Robotics. Dagstuhl Seminar Proceedings, Volume 10081, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{burattini_et_al:DagSemProc.10081.4,
  author =	{Burattini, E. and Finzi, Alberto and Rossi, S. and Staffa, Maria Carla},
  title =	{{Attentive Monitoring and Adaptive Control in Cognitive Robotics}},
  booktitle =	{Cognitive Robotics},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10081},
  editor =	{Gerhard Lakemeyer and Hector J. Levesque and Fiora Pirri},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10081.4},
  URN =		{urn:nbn:de:0030-drops-26322},
  doi =		{10.4230/DagSemProc.10081.4},
  annote =	{Keywords: Attention, behavior-based control, robotics}
}

Rossi, Fabrice

Document
DOI: 10.4230/DagRep.5.3.1
Bridging Information Visualization with Machine Learning (Dagstuhl Seminar 15101)

Authors: Daniel A. Keim, Tamara Munzner, Fabrice Rossi, and Michael Verleysen

Published in: Dagstuhl Reports, Volume 5, Issue 3 (2015)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 15101 "Bridging Information Visualization with Machine Learning". This seminar is a successor to Dagstuhl seminar 12081 "Information Visualization, Visual Data Mining and Machine Learning" held in 2012. The main goal of this second seminar was to identify important challenges to overcome in order to build systems that integrate machine learning and information visualization.
Cite as

Daniel A. Keim, Tamara Munzner, Fabrice Rossi, and Michael Verleysen. Bridging Information Visualization with Machine Learning (Dagstuhl Seminar 15101). In Dagstuhl Reports, Volume 5, Issue 3, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{keim_et_al:DagRep.5.3.1,
  author =	{Keim, Daniel A. and Munzner, Tamara and Rossi, Fabrice and Verleysen, Michael},
  title =	{{Bridging Information Visualization with Machine Learning (Dagstuhl Seminar 15101)}},
  pages =	{1--27},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{5},
  number =	{3},
  editor =	{Keim, Daniel A. and Munzner, Tamara and Rossi, Fabrice and Verleysen, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.3.1},
  URN =		{urn:nbn:de:0030-drops-52665},
  doi =		{10.4230/DagRep.5.3.1},
  annote =	{Keywords: Information visualization, Machine learning, Visual data mining, Exploratory data analysis}
}
Document
DOI: 10.4230/DagRep.2.2.58
Information Visualization, Visual Data Mining and Machine Learning (Dagstuhl Seminar 12081)

Authors: Daniel A. Keim, Fabrice Rossi, Thomas Seidl, Michel Verleysen, and Stefan Wrobel

Published in: Dagstuhl Reports, Volume 2, Issue 2 (2012)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 12081 ``Information Visualization, Visual Data Mining and Machine Learning''. The aim of the seminar was to tighten the links between the information visualisation community and the machine learning community in order to explore how each field can benefit from the other and how to go beyond current hybridization successes.
Cite as

Daniel A. Keim, Fabrice Rossi, Thomas Seidl, Michel Verleysen, and Stefan Wrobel. Information Visualization, Visual Data Mining and Machine Learning (Dagstuhl Seminar 12081). In Dagstuhl Reports, Volume 2, Issue 2, pp. 58-83, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{keim_et_al:DagRep.2.2.58,
  author =	{Keim, Daniel A. and Rossi, Fabrice and Seidl, Thomas and Verleysen, Michel and Wrobel, Stefan},
  title =	{{Information Visualization, Visual Data Mining and Machine Learning (Dagstuhl Seminar 12081)}},
  pages =	{58--83},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{2},
  number =	{2},
  editor =	{Keim, Daniel A. and Rossi, Fabrice and Seidl, Thomas and Verleysen, Michel and Wrobel, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.2.58},
  URN =		{urn:nbn:de:0030-drops-35064},
  doi =		{10.4230/DagRep.2.2.58},
  annote =	{Keywords: Information visualization, visual data mining, machine learning, nonlinear dimensionality reduction, exploratory data analysis}
}

Rossi, Matti

Document
DOI: 10.4230/DagRep.7.3.99
Opportunities and Risks of Blockchain Technologies (Dagstuhl Seminar 17132)

Authors: Roman Beck, Christian Becker, Juho Lindman, and Matti Rossi

Published in: Dagstuhl Reports, Volume 7, Issue 3 (2017)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17132 "Opportunities and Risks of Blockchain Technologies". Blockchain-based applications such as Bitcoin or Ethereum are emerging technologies, but a dramatic increase in industrial and academic interest in the technology is evident. Start-­ups and large financial players are working intensely on blockchain-based applications, making this one of the most promising drivers of financial innovation. However, the design and implementation of blockchain-based systems requires deep technical know-how in various areas, as well as consideration of economic and societal issues. These opportunities and challenges provided the starting point for the Dagstuhl Seminar where we analyzed and synthesized the current body of knowledge on the emerging landscape of blockchain technologies. We linked cryptographic economic systems to already established research streams around trust-related issues in payment systems and digital currencies, and digital asset management.
Cite as

Roman Beck, Christian Becker, Juho Lindman, and Matti Rossi. Opportunities and Risks of Blockchain Technologies (Dagstuhl Seminar 17132). In Dagstuhl Reports, Volume 7, Issue 3, pp. 99-142, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{beck_et_al:DagRep.7.3.99,
  author =	{Beck, Roman and Becker, Christian and Lindman, Juho and Rossi, Matti},
  title =	{{Opportunities and Risks of Blockchain Technologies (Dagstuhl Seminar 17132)}},
  pages =	{99--142},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{3},
  editor =	{Beck, Roman and Becker, Christian and Lindman, Juho and Rossi, Matti},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.3.99},
  URN =		{urn:nbn:de:0030-drops-73637},
  doi =		{10.4230/DagRep.7.3.99},
  annote =	{Keywords: bitcoin, blockchain, cryptocurrencies, trust networks, trust platforms}
}
Document
DOI: 10.4230/DagRep.2.3.67
Open Models as a Foundation of Future Enterprise Systems (Dagstuhl Seminar 12131)

Authors: Robert B. France, Ulrich Frank, Andreas Oberweis, Matti Rossi, and Stefan Strecker

Published in: Dagstuhl Reports, Volume 2, Issue 3 (2012)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 12131 ``Open Models as a Foundation of Future Enterprise Systems''. Research on open models introduces a new model of collaboration among researchers, developers, and prospective users of reference enterprise models-leading to the prospect of shaping future enterprise systems. This seminar brought together researchers and practitioners with expertise in a broad range of fields including conceptual modelling, model-driven engineering, enterprise systems, software architectures, and modelling tool development. The seminar mixed short presentations on the attendees' perspectives on open models with keynote presentations and working groups on selected research issues. Topics discussed include the shape of future enterprise systems amalgamated with open reference enterprise models, business domains to be addressed in first open models, requirements towards a technical infrastructure as well as organisational issues of open model initiatives. The seminar's discussions benefitted from the different perspectives of attendees on the common topic, raised important new questions on open models, and brought to light overlooked aspects important to future research activities.
Cite as

Robert B. France, Ulrich Frank, Andreas Oberweis, Matti Rossi, and Stefan Strecker. Open Models as a Foundation of Future Enterprise Systems (Dagstuhl Seminar 12131). In Dagstuhl Reports, Volume 2, Issue 3, pp. 67-85, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{france_et_al:DagRep.2.3.67,
  author =	{France, Robert  B. and Frank, Ulrich and Oberweis, Andreas and Rossi, Matti and Strecker, Stefan},
  title =	{{Open Models as a Foundation of Future Enterprise Systems (Dagstuhl Seminar 12131)}},
  pages =	{67--85},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{2},
  number =	{3},
  editor =	{France, Robert  B. and Frank, Ulrich and Oberweis, Andreas and Rossi, Matti and Strecker, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.3.67},
  URN =		{urn:nbn:de:0030-drops-35379},
  doi =		{10.4230/DagRep.2.3.67},
  annote =	{Keywords: Enterprise Modelling, Enterprise Systems, Reference Model, Meta Modeling, Method Engineering, Information Systems Architectures}
}
Document
DOI: 10.4230/DagSemProc.08412.6
Action Design Research - An Integrative Research Method for Studying Design

Authors: Matti Rossi

Published in: Dagstuhl Seminar Proceedings, Volume 8412, Perspectives Workshop: Science of Design: High-Impact Requirements for Software-Intensive Systems (2009)

Abstract
It is the premise of this position paper that a combination of design research and action research can be very useful for studying high performance designs. However, there has been a separation between the two approaches. A growing body of literature is recognizing these cross fertilization possibilities between AR and DR. Researchers argue for similarity between the two (J'rvinen 2007; Lee 2007; Figueiredo and Cunha 2007) as well as caution against fusion (Iivari 2007). Others suggest a middle ground stating that in some situations and contexts, the two may be integrated (Cole et al. 2005; Sein et al. 2007).
Cite as

Matti Rossi. Action Design Research - An Integrative Research Method for Studying Design. In Perspectives Workshop: Science of Design: High-Impact Requirements for Software-Intensive Systems. Dagstuhl Seminar Proceedings, Volume 8412, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{rossi:DagSemProc.08412.6,
  author =	{Rossi, Matti},
  title =	{{Action Design Research - An Integrative Research Method for Studying Design}},
  booktitle =	{Perspectives Workshop: Science of Design: High-Impact Requirements for Software-Intensive Systems},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8412},
  editor =	{Matthias Jarke and Kalle Lyytinen and John Mylopoulos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08412.6},
  URN =		{urn:nbn:de:0030-drops-19827},
  doi =		{10.4230/DagSemProc.08412.6},
  annote =	{Keywords: Action research, Design research, Proactive research}
}

Rossi, Francesca

Document
Invited Talk
DOI: 10.4230/LIPIcs.CP.2024.2
Thinking Fast and Slow in AI: A Cognitive Architecture to Augment Both AI and Human Reasoning (Invited Talk)

Authors: Francesca Rossi

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
AI systems are very useful in practically every sector, but they also have several limitations, mostly related to the lack of reasoning capabilities. According to the fast and slow thinking theory of human decision making, we can say that data-driven AI, including generative AI, are providing fast thinking capabilities, but they do not have slow thinking ones. Existing cognitive theories of human decision making, such as the thinking fast and slow theory, can provide insights on how to advance AI systems towards some of these capabilities. In this talk I will present a general architecture, called SOFAI, that is based on fast/slow solvers and a meta-cognitive component that provides a centralized governance of the solvers. I will describe two instances of this architecture, for constrained grid navigation and planning, showing experimentally that SOFAI generates better decisions than each of the individual solvers. Emerging behavior related to adaptability, skill learning, and cognitive control are also showed in the analysis of SOFAI’s behavior. I will also describe how the thinking fast and slow theory can help design a value-based human-machine collaborative decision environment.
Cite as

Francesca Rossi. Thinking Fast and Slow in AI: A Cognitive Architecture to Augment Both AI and Human Reasoning (Invited Talk). In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{rossi:LIPIcs.CP.2024.2,
  author =	{Rossi, Francesca},
  title =	{{Thinking Fast and Slow in AI: A Cognitive Architecture to Augment Both AI and Human Reasoning}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.2},
  URN =		{urn:nbn:de:0030-drops-206874},
  doi =		{10.4230/LIPIcs.CP.2024.2},
  annote =	{Keywords: Artificial Intelligence, Meta-reasoning}
}
Document
Invited Paper
DOI: 10.4230/LIPIcs.CONCUR.2016.2
Ethical Preference-Based Decision Support Systems (Invited Paper)

Authors: Francesca Rossi

Published in: LIPIcs, Volume 59, 27th International Conference on Concurrency Theory (CONCUR 2016)

Abstract
The future will see autonomous intelligent systems acting in the same environment as humans, in areas as diverse as driving, assistive technology, and health care. Think of self-driving cars, companion robots, and medical diagnosis support systems. Also, humans and machines will often need to work together and agree on common decisions. Thus hybrid collective decision making systems will be in great need. In these scenarios, both machines and collective decision making systems should follow some form of moral values and ethical principles (appropriate to where they will act but always aligned to humans'). In fact, humans would accept and trust more machines that behave as ethically as other humans in the same environment. Also, these principles would make it easier for machines to determine their actions and explain their behavior in terms understandable by humans. Moreover, often machines and humans will need to make decisions together, either through consensus or by reaching a compromise. This would be facilitated by shared moral values and ethical principles. In this paper we introduce some issues in embedding morality into intelligent systems. A few research questions are defined, with the hope that the discussion raised by the questions will shed some light onto the possible answers.
Cite as

Francesca Rossi. Ethical Preference-Based Decision Support Systems (Invited Paper). In 27th International Conference on Concurrency Theory (CONCUR 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 59, pp. 2:1-2:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{rossi:LIPIcs.CONCUR.2016.2,
  author =	{Rossi, Francesca},
  title =	{{Ethical Preference-Based Decision Support Systems}},
  booktitle =	{27th International Conference on Concurrency Theory (CONCUR 2016)},
  pages =	{2:1--2:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-017-0},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{59},
  editor =	{Desharnais, Jos\'{e}e and Jagadeesan, Radha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2016.2},
  URN =		{urn:nbn:de:0030-drops-61870},
  doi =		{10.4230/LIPIcs.CONCUR.2016.2},
  annote =	{Keywords: preferences, decision making, multi-agent systems}
}
Document
DOI: 10.4230/DagSemProc.07431.1
07431 Abstracts Collection – Computational Issues in Social Choice

Authors: Ulle Endriss, Jérôme Lang, Francesca Rossi, and Tuomas Sandholm

Published in: Dagstuhl Seminar Proceedings, Volume 7431, Computational Issues in Social Choice (2007)

Abstract
From the 21st to the 26th of October 2007, the Dagstuhl Seminar 07431 on ``Computational Issues in Social Choice'' was held at the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their recent research, and ongoing work and open problems were discussed. The abstracts of the talks given during the seminar are collected in this paper. The first section summarises the seminar topics and goals in general. Links to full papers are provided where available.
Cite as

Ulle Endriss, Jérôme Lang, Francesca Rossi, and Tuomas Sandholm. 07431 Abstracts Collection – Computational Issues in Social Choice. In Computational Issues in Social Choice. Dagstuhl Seminar Proceedings, Volume 7431, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{endriss_et_al:DagSemProc.07431.1,
  author =	{Endriss, Ulle and Lang, J\'{e}r\^{o}me and Rossi, Francesca and Sandholm, Tuomas},
  title =	{{07431 Abstracts Collection – Computational Issues in Social Choice}},
  booktitle =	{Computational Issues in Social Choice},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7431},
  editor =	{Ulle Endriss and J\'{e}r\^{o}me Lang and Francesca Rossi and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07431.1},
  URN =		{urn:nbn:de:0030-drops-12736},
  doi =		{10.4230/DagSemProc.07431.1},
  annote =	{Keywords: Computational social choice, voting theory, fair division, mechanism design, coalition formation, complexity theory, preference representation, algorithms}
}
Document
DOI: 10.4230/DagSemProc.07431.2
07431 Executive Summary – Computational Issues in Social Choice

Authors: Ulle Endriss, Jérôme Lang, Francesca Rossi, and Tuomas Sandholm

Published in: Dagstuhl Seminar Proceedings, Volume 7431, Computational Issues in Social Choice (2007)

Abstract
Computational social choice is an interdisciplinary field of study at the interface of social choice theory and computer science, with knowledge flowing in either direction. On the one hand, computational social choice is concerned with importing concepts and procedures from social choice theory for solving questions that arise in computer science and AI application domains. This is typically the case for managing societies of autonomous agents, which calls for negotiation and voting procedures. On the other hand, computational social choice is concerned with importing notions and methods from computer science for solving questions originally stemming from social choice, for instance by providing new perspectives on the problem of manipulation and control in elections. This Dagstuhl Seminar has been devoted to the presentation of recent results and an exchange of ideas in this growing research field.
Cite as

Ulle Endriss, Jérôme Lang, Francesca Rossi, and Tuomas Sandholm. 07431 Executive Summary – Computational Issues in Social Choice. In Computational Issues in Social Choice. Dagstuhl Seminar Proceedings, Volume 7431, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{endriss_et_al:DagSemProc.07431.2,
  author =	{Endriss, Ulle and Lang, J\'{e}r\^{o}me and Rossi, Francesca and Sandholm, Tuomas},
  title =	{{07431 Executive Summary – Computational Issues in Social Choice}},
  booktitle =	{Computational Issues in Social Choice},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7431},
  editor =	{Ulle Endriss and J\'{e}r\^{o}me Lang and Francesca Rossi and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07431.2},
  URN =		{urn:nbn:de:0030-drops-12749},
  doi =		{10.4230/DagSemProc.07431.2},
  annote =	{Keywords: Computational social choice, voting theory, fair division, mechanism design, coalition formation, complexity theory, preference representation, algorithms}
}

Rossi, Alfred

Document
DOI: 10.4230/LIPIcs.ISAAC.2017.28
Temporal Hierarchical Clustering

Authors: Tamal K. Dey, Alfred Rossi, and Anastasios Sidiropoulos

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
We study hierarchical clusterings of metric spaces that change over time. This is a natural geo- metric primitive for the analysis of dynamic data sets. Specifically, we introduce and study the problem of finding a temporally coherent sequence of hierarchical clusterings from a sequence of unlabeled point sets. We encode the clustering objective by embedding each point set into an ultrametric space, which naturally induces a hierarchical clustering of the set of points. We enforce temporal coherence among the embeddings by finding correspondences between successive pairs of ultrametric spaces which exhibit small distortion in the Gromov-Hausdorff sense. We present both upper and lower bounds on the approximability of the resulting optimization problems.
Cite as

Tamal K. Dey, Alfred Rossi, and Anastasios Sidiropoulos. Temporal Hierarchical Clustering. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 28:1-28:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.ISAAC.2017.28,
  author =	{Dey, Tamal K. and Rossi, Alfred and Sidiropoulos, Anastasios},
  title =	{{Temporal Hierarchical Clustering}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{28:1--28:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.28},
  URN =		{urn:nbn:de:0030-drops-82519},
  doi =		{10.4230/LIPIcs.ISAAC.2017.28},
  annote =	{Keywords: clustering, hierarchical clustering, multi-objective optimization, dynamic metric spaces, moving point sets, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.34
Temporal Clustering

Authors: Tamal K. Dey, Alfred Rossi, and Anastasios Sidiropoulos

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
We study the problem of clustering sequences of unlabeled point sets taken from a common metric space. Such scenarios arise naturally in applications where a system or process is observed in distinct time intervals, such as biological surveys and contagious disease surveillance. In this more general setting existing algorithms for classical (i.e. static) clustering problems are not applicable anymore. We propose a set of optimization problems which we collectively refer to as temporal clustering. The quality of a solution to a temporal clustering instance can be quantified using three parameters: the number of clusters k, the spatial clustering cost r, and the maximum cluster displacement delta between consecutive time steps. We consider spatial clustering costs which generalize the well-studied k-center, discrete k-median, and discrete k-means objectives of classical clustering problems. We develop new algorithms that achieve trade-offs between the three objectives k, r, and delta. Our upper bounds are complemented by inapproximability results.
Cite as

Tamal K. Dey, Alfred Rossi, and Anastasios Sidiropoulos. Temporal Clustering. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.ESA.2017.34,
  author =	{Dey, Tamal K. and Rossi, Alfred and Sidiropoulos, Anastasios},
  title =	{{Temporal Clustering}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{34:1--34:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.34},
  URN =		{urn:nbn:de:0030-drops-78567},
  doi =		{10.4230/LIPIcs.ESA.2017.34},
  annote =	{Keywords: clustering, multi-objective optimization, dynamic metric spaces, moving point sets, approximation algorithms, hardness of approximation}
}

Rossi, Mirko

Document
DOI: 10.4230/LIPIcs.ESA.2022.19
Sparse Temporal Spanners with Low Stretch

Authors: Davide Bilò, Gianlorenzo D'Angelo, Luciano Gualà, Stefano Leucci, and Mirko Rossi

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
A temporal graph is an undirected graph G = (V,E) along with a function λ : E → ℕ^+ that assigns a time-label to each edge in E. A path in G such that the traversed time-labels are non-decreasing is called a temporal path. Accordingly, the distance from u to v is the minimum length (i.e., the number of edges) of a temporal path from u to v. A temporal α-spanner of G is a (temporal) subgraph H that preserves the distances between any pair of vertices in V, up to a multiplicative stretch factor of α. The size of H is measured as the number of its edges. In this work, we study the size-stretch trade-offs of temporal spanners. In particular we show that temporal cliques always admit a temporal (2k-1)-spanner with Õ(kn^{1+1/k}) edges, where k > 1 is an integer parameter of choice. Choosing k = ⌊log n⌋, we obtain a temporal O(log n)-spanner with Õ(n) edges that has almost the same size (up to logarithmic factors) as the temporal spanner given in [Casteigts et al., JCSS 2021] which only preserves temporal connectivity. We then turn our attention to general temporal graphs. Since Ω(n²) edges might be needed by any connectivity-preserving temporal subgraph [Axiotis et al., ICALP'16], we focus on approximating distances from a single source. We show that Õ(n/log(1+ε)) edges suffice to obtain a stretch of (1+ε), for any small ε > 0. This result is essentially tight in the following sense: there are temporal graphs G for which any temporal subgraph preserving exact distances from a single-source must use Ω(n²) edges. Interestingly enough, our analysis can be extended to the case of additive stretch for which we prove an upper bound of Õ(n² / β) on the size of any temporal β-additive spanner, which we show to be tight up to polylogarithmic factors. Finally, we investigate how the lifetime of G, i.e., the number of its distinct time-labels, affects the trade-off between the size and the stretch of a temporal spanner.
Cite as

Davide Bilò, Gianlorenzo D'Angelo, Luciano Gualà, Stefano Leucci, and Mirko Rossi. Sparse Temporal Spanners with Low Stretch. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ESA.2022.19,
  author =	{Bil\`{o}, Davide and D'Angelo, Gianlorenzo and Gual\`{a}, Luciano and Leucci, Stefano and Rossi, Mirko},
  title =	{{Sparse Temporal Spanners with Low Stretch}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.19},
  URN =		{urn:nbn:de:0030-drops-169575},
  doi =		{10.4230/LIPIcs.ESA.2022.19},
  annote =	{Keywords: temporal spanners, temporal graphs, graph sparsification, approximate distances}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.12
Single-Source Shortest p-Disjoint Paths: Fast Computation and Sparse Preservers

Authors: Davide Bilò, Gianlorenzo D'Angelo, Luciano Gualà, Stefano Leucci, Guido Proietti, and Mirko Rossi

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
Let G be a directed graph with n vertices, m edges, and non-negative edge costs. Given G, a fixed source vertex s, and a positive integer p, we consider the problem of computing, for each vertex t≠ s, p edge-disjoint paths of minimum total cost from s to t in G. Suurballe and Tarjan [Networks, 1984] solved the above problem for p = 2 by designing a O(m+nlog n) time algorithm which also computes a sparse single-source 2-multipath preserver, i.e., a subgraph containing 2 edge-disjoint paths of minimum total cost from s to every other vertex of G. The case p ≥ 3 was left as an open problem. We study the general problem (p ≥ 2) and prove that any graph admits a sparse single-source p-multipath preserver with p(n-1) edges. This size is optimal since the in-degree of each non-root vertex v must be at least p. Moreover, we design an algorithm that requires O(pn² (p + log n)) time to compute both p edge-disjoint paths of minimum total cost from the source to all other vertices and an optimal-size single-source p-multipath preserver. The running time of our algorithm outperforms that of a natural approach that solves n-1 single-pair instances using the well-known successive shortest paths algorithm by a factor of Θ(m/(np)) and is asymptotically near optimal if p = O(1) and m = Θ(n²). Our results extend naturally to the case of p vertex-disjoint paths.
Cite as

Davide Bilò, Gianlorenzo D'Angelo, Luciano Gualà, Stefano Leucci, Guido Proietti, and Mirko Rossi. Single-Source Shortest p-Disjoint Paths: Fast Computation and Sparse Preservers. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 12:1-12:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.STACS.2022.12,
  author =	{Bil\`{o}, Davide and D'Angelo, Gianlorenzo and Gual\`{a}, Luciano and Leucci, Stefano and Proietti, Guido and Rossi, Mirko},
  title =	{{Single-Source Shortest p-Disjoint Paths: Fast Computation and Sparse Preservers}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{12:1--12:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.12},
  URN =		{urn:nbn:de:0030-drops-158221},
  doi =		{10.4230/LIPIcs.STACS.2022.12},
  annote =	{Keywords: multipath spanners, graph sparsification, edge-disjoint paths, min-cost flow}
}
Document
DOI: 10.4230/LIPIcs.FUN.2018.8
On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games

Authors: Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti, and Mirko Rossi

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
Peg Duotaire is a two-player version of the classical puzzle called Peg Solitaire. Players take turns making peg-jumping moves, and the first player which is left without available moves loses the game. Peg Duotaire has been studied from a combinatorial point of view and two versions of the game have been considered, namely the single- and the multi-hop variant. On the other hand, understanding the computational complexity of the game is explicitly mentioned as an open problem in the literature. We close this problem and prove that both versions of the game are PSPACE-complete. We also prove the PSPACE-completeness of other peg-jumping games where two players control pegs of different colors.
Cite as

Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti, and Mirko Rossi. On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.FUN.2018.8,
  author =	{Bil\`{o}, Davide and Gual\`{a}, Luciano and Leucci, Stefano and Proietti, Guido and Rossi, Mirko},
  title =	{{On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.8},
  URN =		{urn:nbn:de:0030-drops-87994},
  doi =		{10.4230/LIPIcs.FUN.2018.8},
  annote =	{Keywords: peg duotaire, pspace-completeness, peg solitaire, two-player games}
}

Rossi, Enrico

Document
DOI: 10.4230/LIPIcs.ECRTS.2019.24
A Bandwidth Reservation Mechanism for AXI-Based Hardware Accelerators on FPGAs

Authors: Marco Pagani, Enrico Rossi, Alessandro Biondi, Mauro Marinoni, Giuseppe Lipari, and Giorgio Buttazzo

Published in: LIPIcs, Volume 133, 31st Euromicro Conference on Real-Time Systems (ECRTS 2019)

Abstract
Hardware platforms for real-time embedded systems are evolving towards heterogeneous architectures comprising different types of processing cores and dedicated hardware accelerators, which can be implemented on silicon or dynamically deployed on FPGA fabric. Such accelerators typically access a shared memory to exchange a significant amount of data with other processing elements. Existing COTS solutions focus on maximizing the overall throughput of the system, rather than guaranteeing the timing constraints of individual hardware accelerators. This paper presents the AXI budgeting unit (ABU), a hardware-based solution to implement a bandwidth reservation mechanism on top of the AMBA AXI standard infrastructure for hardware accelerators deployed on FPGAs. An accurate and tractable model, as well as the corresponding analysis, are also proposed to bound the response time of hardware accelerators in the presence of ABUs, in order to verify whether they can complete before their deadlines. Finally, a set of experiments are reported to evaluate the proposed approach on a state-of-the-art platform, namely the Zynq-7020 by Xilinx. The resource consumption of the ABU has been quantified to be less than 1% of the total FPGA resources of the Zynq-7020.
Cite as

Marco Pagani, Enrico Rossi, Alessandro Biondi, Mauro Marinoni, Giuseppe Lipari, and Giorgio Buttazzo. A Bandwidth Reservation Mechanism for AXI-Based Hardware Accelerators on FPGAs. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 133, pp. 24:1-24:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{pagani_et_al:LIPIcs.ECRTS.2019.24,
  author =	{Pagani, Marco and Rossi, Enrico and Biondi, Alessandro and Marinoni, Mauro and Lipari, Giuseppe and Buttazzo, Giorgio},
  title =	{{A Bandwidth Reservation Mechanism for AXI-Based Hardware Accelerators on FPGAs}},
  booktitle =	{31st Euromicro Conference on Real-Time Systems (ECRTS 2019)},
  pages =	{24:1--24:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-110-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{133},
  editor =	{Quinton, Sophie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2019.24},
  URN =		{urn:nbn:de:0030-drops-107611},
  doi =		{10.4230/LIPIcs.ECRTS.2019.24},
  annote =	{Keywords: AXI Bus, Bandwidth Reservation, Hardware Acceleration, FPGA}
}

Rossi, Massimiliano

Document
DOI: 10.4230/LIPIcs.SEA.2022.16
RLBWT Tricks

Authors: Nathaniel K. Brown, Travis Gagie, and Massimiliano Rossi

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)

Abstract
Until recently, most experts would probably have agreed we cannot backwards-step in constant time with a run-length compressed Burrows-Wheeler Transform (RLBWT), since doing so relies on rank queries on sparse bitvectors and those inherit lower bounds from predecessor queries. At ICALP '21, however, Nishimoto and Tabei described a new, simple and constant-time implementation. For a permutation π, it stores an O (r)-space table - where r is the number of positions i where either i = 0 or π (i + 1) ≠ π (i) + 1 - that enables the computation of successive values of π(i) by table look-ups and linear scans. Nishimoto and Tabei showed how to increase the number of rows in the table to bound the length of the linear scans such that the query time for computing π(i) is constant while maintaining O (r)-space. In this paper we refine Nishimoto and Tabei’s approach, including a time-space tradeoff, and experimentally evaluate different implementations demonstrating the practicality of part of their result. We show that even without adding rows to the table, in practice we almost always scan only a few entries during queries. We propose a decomposition scheme of the permutation π corresponding to the LF-mapping that allows an improved compression of the data structure, while limiting the query time. We tested our implementation on real-world genomic datasets and found that without compression of the table, backward-stepping is drastically faster than with sparse bitvector implementations but, unfortunately, also uses drastically more space. After compression, backward-stepping is competitive both in time and space with the best existing implementations.
Cite as

Nathaniel K. Brown, Travis Gagie, and Massimiliano Rossi. RLBWT Tricks. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{brown_et_al:LIPIcs.SEA.2022.16,
  author =	{Brown, Nathaniel K. and Gagie, Travis and Rossi, Massimiliano},
  title =	{{RLBWT Tricks}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{16:1--16:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.16},
  URN =		{urn:nbn:de:0030-drops-165500},
  doi =		{10.4230/LIPIcs.SEA.2022.16},
  annote =	{Keywords: Compressed String Indexes, Repetitive Text Collections, Burrows-Wheeler Transform}
}
Document
DOI: 10.4230/LIPIcs.SEA.2022.22
Computing Maximal Unique Matches with the r-Index

Authors: Sara Giuliani, Giuseppe Romana, and Massimiliano Rossi

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)

Abstract
In recent years, pangenomes received increasing attention from the scientific community for their ability to incorporate population variation information and alleviate reference genome bias. Maximal Exact Matches (MEMs) and Maximal Unique Matches (MUMs) have proven themselves to be useful in multiple bioinformatic contexts, for example short-read alignment and multiple-genome alignment. However, standard techniques using suffix trees and FM-indexes do not scale to a pangenomic level. Recently, Gagie et al. [JACM 20] introduced the r-index that is a Burrows-Wheeler Transform (BWT)-based index able to handle hundreds of human genomes. Later, Rossi et al. [JCB 22] enabled the computation of MEMs using the r-index, and Boucher et al. [DCC 21] showed how to compute them in a streaming fashion. In this paper, we show how to augment Boucher et al.’s approach to enable the computation of MUMs on the r-index, while preserving the space and time bounds. We add additional O(r) samples of the longest common prefix (LCP) array, where r is the number of equal-letter runs of the BWT, that permits the computation of the second longest match of the pattern suffix with respect to the input text, which in turn allows the computation of candidate MUMs. We implemented a proof-of-concept of our approach, that we call MUM-PHINDER, and tested on real-world datasets. We compared our approach with competing methods that are able to compute MUMs. We observe that our method is up to 8 times smaller, while up to 19 times slower when the dataset is not highly repetitive, while on highly repetitive data, our method is up to 6.5 times slower and uses up to 25 times less memory.
Cite as

Sara Giuliani, Giuseppe Romana, and Massimiliano Rossi. Computing Maximal Unique Matches with the r-Index. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{giuliani_et_al:LIPIcs.SEA.2022.22,
  author =	{Giuliani, Sara and Romana, Giuseppe and Rossi, Massimiliano},
  title =	{{Computing Maximal Unique Matches with the r-Index}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.22},
  URN =		{urn:nbn:de:0030-drops-165568},
  doi =		{10.4230/LIPIcs.SEA.2022.22},
  annote =	{Keywords: Burrows-Wheeler Transform, r-index, maximal unique matches, bioinformatics, pangenomics}
}
Document
DOI: 10.4230/LIPIcs.WABI.2020.9
Fast and Efficient Rmap Assembly Using the Bi-Labelled de Bruijn Graph

Authors: Kingshuk Mukherjee, Massimiliano Rossi, Leena Salmela, and Christina Boucher

Published in: LIPIcs, Volume 172, 20th International Workshop on Algorithms in Bioinformatics (WABI 2020)

Abstract
Genome wide optical maps are high resolution restriction maps that give a unique numeric representation to a genome. They are produced by assembling hundreds of thousands of single molecule optical maps, which are called Rmaps. Unfortunately, there exists very few choices for assembling Rmap data. There exists only one publicly-available non-proprietary method for assembly and one proprietary method that is available via an executable. Furthermore, the publicly-available method, by Valouev et al. (2006), follows the overlap-layout-consensus (OLC) paradigm, and therefore, is unable to scale for relatively large genomes. The algorithm behind the proprietary method, Bionano Genomics' Solve, is largely unknown. In this paper, we extend the definition of bi-labels in the paired de Bruijn graph to the context of optical mapping data, and present the first de Bruijn graph based method for Rmap assembly. We implement our approach, which we refer to as rmapper, and compare its performance against the assembler of Valouev et al. (2006) and Solve by Bionano Genomics on data from three genomes - E. coli, human, and climbing perch fish (Anabas Testudineus). Our method was the only one able to successfully run on all three genomes. The method of Valouev et al. (2006) only successfully ran on E. coli and Bionano Solve successfully ran on E. coli and human but not on the fish genome. Moreover, on the human genome rmapper was at least 130 times faster than Bionano Solve, used five times less memory and produced the highest genome fraction with zero mis-assemblies.
Cite as

Kingshuk Mukherjee, Massimiliano Rossi, Leena Salmela, and Christina Boucher. Fast and Efficient Rmap Assembly Using the Bi-Labelled de Bruijn Graph. In 20th International Workshop on Algorithms in Bioinformatics (WABI 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 172, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{mukherjee_et_al:LIPIcs.WABI.2020.9,
  author =	{Mukherjee, Kingshuk and Rossi, Massimiliano and Salmela, Leena and Boucher, Christina},
  title =	{{Fast and Efficient Rmap Assembly Using the Bi-Labelled de Bruijn Graph}},
  booktitle =	{20th International Workshop on Algorithms in Bioinformatics (WABI 2020)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-161-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{172},
  editor =	{Kingsford, Carl and Pisanti, Nadia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2020.9},
  URN =		{urn:nbn:de:0030-drops-127982},
  doi =		{10.4230/LIPIcs.WABI.2020.9},
  annote =	{Keywords: optical maps, de Bruijn graph, assembly}
}
Document
DOI: 10.4230/LIPIcs.SEA.2020.12
Pattern Discovery in Colored Strings

Authors: Zsuzsanna Lipták, Simon J. Puglisi, and Massimiliano Rossi

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
We consider the problem of identifying patterns of interest in colored strings. A colored string is a string in which each position is colored with one of a finite set of colors. Our task is to find substrings that always occur followed by the same color at the same distance. The problem is motivated by applications in embedded systems verification, in particular, assertion mining. The goal there is to automatically infer properties of the embedded system from the analysis of its simulation traces. We show that the number of interesting patterns is upper-bounded by 𝒪(n²) where n is the length of the string. We introduce a baseline algorithm with 𝒪(n²) running time which identifies all interesting patterns for all colors in the string satisfying certain minimality conditions. When one is interested in patterns related to only one color, we provide an algorithm that identifies patterns in 𝒪(n²log n) time, but is faster than the first algorithm in practice, both on simulated and on real-world patterns.
Cite as

Zsuzsanna Lipták, Simon J. Puglisi, and Massimiliano Rossi. Pattern Discovery in Colored Strings. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{liptak_et_al:LIPIcs.SEA.2020.12,
  author =	{Lipt\'{a}k, Zsuzsanna and Puglisi, Simon J. and Rossi, Massimiliano},
  title =	{{Pattern Discovery in Colored Strings}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.12},
  URN =		{urn:nbn:de:0030-drops-120862},
  doi =		{10.4230/LIPIcs.SEA.2020.12},
  annote =	{Keywords: property testing, suffix tree, pattern mining}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact