1 Search Results for "Commins, Patty"

Document
DOI: 10.4230/LIPIcs.CPM.2020.11
Summarizing Diverging String Sequences, with Applications to Chain-Letter Petitions

Authors: Patty Commins, David Liben-Nowell, Tina Liu, and Kiran Tomlinson

Published in: LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)

Abstract
Algorithms to find optimal alignments among strings, or to find a parsimonious summary of a collection of strings, are well studied in a variety of contexts, addressing a wide range of interesting applications. In this paper, we consider chain letters, which contain a growing sequence of signatories added as the letter propagates. The unusual constellation of features exhibited by chain letters (one-ended growth, divergence, and mutation) make their propagation, and thus the corresponding reconstruction problem, both distinctive and rich. Here, inspired by these chain letters, we formally define the problem of computing an optimal summary of a set of diverging string sequences. From a collection of these sequences of names, with each sequence noisily corresponding to a branch of the unknown tree T representing the letter’s true dissemination, can we efficiently and accurately reconstruct a tree T' ≈ T? In this paper, we give efficient exact algorithms for this summarization problem when the number of sequences is small; for larger sets of sequences, we prove hardness and provide an efficient heuristic algorithm. We evaluate this heuristic on synthetic data sets chosen to emulate real chain letters, showing that our algorithm is competitive with or better than previous approaches, and that it also comes close to finding the true trees in these synthetic datasets.
Cite as

Patty Commins, David Liben-Nowell, Tina Liu, and Kiran Tomlinson. Summarizing Diverging String Sequences, with Applications to Chain-Letter Petitions. In 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 161, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{commins_et_al:LIPIcs.CPM.2020.11,
  author =	{Commins, Patty and Liben-Nowell, David and Liu, Tina and Tomlinson, Kiran},
  title =	{{Summarizing Diverging String Sequences, with Applications to Chain-Letter Petitions}},
  booktitle =	{31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-149-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{161},
  editor =	{G{\o}rtz, Inge Li and Weimann, Oren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.11},
  URN =		{urn:nbn:de:0030-drops-121367},
  doi =		{10.4230/LIPIcs.CPM.2020.11},
  annote =	{Keywords: edit distance, tree reconstruction, information propagation, chain letters}
}
  • Refine by Author
  • 1 Commins, Patty
  • 1 Liben-Nowell, David
  • 1 Liu, Tina
  • 1 Tomlinson, Kiran

  • Refine by Classification
  • 1 Applied computing → Law, social and behavioral sciences
  • 1 Mathematics of computing → Combinatorial algorithms

  • Refine by Keyword
  • 1 chain letters
  • 1 edit distance
  • 1 information propagation
  • 1 tree reconstruction

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

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