2 Search Results for "Tsichlas, Kostas"

Document
DOI: 10.4230/LIPIcs.TIME.2021.6
Investigation of Database Models for Evolving Graphs

Authors: Alexandros Spitalas, Anastasios Gounaris, Kostas Tsichlas, and Andreas Kosmatopoulos

Published in: LIPIcs, Volume 206, 28th International Symposium on Temporal Representation and Reasoning (TIME 2021)

Abstract
We deal with the efficient implementation of storage models for time-varying graphs. To this end, we present an improved approach for the HiNode vertex-centric model based on MongoDB. This approach, apart from its inherent space optimality, exhibits significant improvements in global query execution times, which is the most challenging query type for entity-centric approaches. Not only significant speedups are achieved but more expensive queries can be executed as well, when compared to an implementation based on Cassandra due to the capability to exploit indices to a larger extent and benefit from in-database query processing.
Cite as

Alexandros Spitalas, Anastasios Gounaris, Kostas Tsichlas, and Andreas Kosmatopoulos. Investigation of Database Models for Evolving Graphs. In 28th International Symposium on Temporal Representation and Reasoning (TIME 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 206, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{spitalas_et_al:LIPIcs.TIME.2021.6,
  author =	{Spitalas, Alexandros and Gounaris, Anastasios and Tsichlas, Kostas and Kosmatopoulos, Andreas},
  title =	{{Investigation of Database Models for Evolving Graphs}},
  booktitle =	{28th International Symposium on Temporal Representation and Reasoning (TIME 2021)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-206-8},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{206},
  editor =	{Combi, Carlo and Eder, Johann and Reynolds, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2021.6},
  URN =		{urn:nbn:de:0030-drops-147821},
  doi =		{10.4230/LIPIcs.TIME.2021.6},
  annote =	{Keywords: Temporal Graphs, Indexing}
}
Document
DOI: 10.4230/LIPIcs.CPM.2020.19
Longest Common Subsequence on Weighted Sequences

Authors: Evangelos Kipouridis and Kostas Tsichlas

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

Abstract
We consider the general problem of the Longest Common Subsequence (LCS) on weighted sequences. Weighted sequences are an extension of classical strings, where in each position every letter of the alphabet may occur with some probability. Previous results presented a PTAS and noticed that no FPTAS is possible unless P=NP. In this paper we essentially close the gap between upper and lower bounds by improving both. First of all, we provide an EPTAS for bounded alphabets (which is the most natural case), and prove that there does not exist any EPTAS for unbounded alphabets unless FPT=W[1]. Furthermore, under the Exponential Time Hypothesis, we provide a lower bound which shows that no significantly better PTAS can exist for unbounded alphabets. As a side note, we prove that it is sufficient to work with only one threshold in the general variant of the problem.
Cite as

Evangelos Kipouridis and Kostas Tsichlas. Longest Common Subsequence on Weighted Sequences. In 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 161, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kipouridis_et_al:LIPIcs.CPM.2020.19,
  author =	{Kipouridis, Evangelos and Tsichlas, Kostas},
  title =	{{Longest Common Subsequence on Weighted Sequences}},
  booktitle =	{31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)},
  pages =	{19:1--19: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.19},
  URN =		{urn:nbn:de:0030-drops-121443},
  doi =		{10.4230/LIPIcs.CPM.2020.19},
  annote =	{Keywords: WLCS, LCS, weighted sequences, approximation algorithms, lower bound}
}
  • Refine by Author
  • 2 Tsichlas, Kostas
  • 1 Gounaris, Anastasios
  • 1 Kipouridis, Evangelos
  • 1 Kosmatopoulos, Andreas
  • 1 Spitalas, Alexandros

  • Refine by Classification
  • 1 Information systems → Database design and models
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Problems, reductions and completeness
  • 1 Theory of computation → W hierarchy

  • Refine by Keyword
  • 1 Indexing
  • 1 LCS
  • 1 Temporal Graphs
  • 1 WLCS
  • 1 approximation algorithms
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2020
  • 1 2021

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