DROPS

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.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.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}
}

Search Results

Documents authored by Tsichlas, Kostas

Investigation of Database Models for Evolving Graphs

Abstract

Cite as

Longest Common Subsequence on Weighted Sequences

Abstract

Cite as

Thanks for your feedback!

Could not send message