Search Results

Documents authored by Sakai, Yoshifumi

Document
DOI: 10.4230/LIPIcs.CPM.2024.26
A Data Structure for the Maximum-Sum Segment Problem with Offsets

Authors: Yoshifumi Sakai

Published in: LIPIcs, Volume 296, 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)

Abstract
Consider a variant of the maximum-sum segment problem for a sequence X₀ of n real numbers, which asks an arbitrary contiguous subsequence of X_a that maximizes the sum of its elements for any given real number a, where X_a is the sequence obtained by subtracting a from each element in X₀. Although this problem can be solved in O(n) time from scratch for any given X₀ and a, appropriate data structures for X₀ could support efficient queries of the solution for arbitrary a. We propose an O(n log² n)-time, O(n)-space algorithm that takes X₀ as input and outputs such a data structure supporting O(log n)-time queries.
Cite as

Yoshifumi Sakai. A Data Structure for the Maximum-Sum Segment Problem with Offsets. In 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 296, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{sakai:LIPIcs.CPM.2024.26,
  author =	{Sakai, Yoshifumi},
  title =	{{A Data Structure for the Maximum-Sum Segment Problem with Offsets}},
  booktitle =	{35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-326-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{296},
  editor =	{Inenaga, Shunsuke and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2024.26},
  URN =		{urn:nbn:de:0030-drops-201361},
  doi =		{10.4230/LIPIcs.CPM.2024.26},
  annote =	{Keywords: algorithms, sequence of real numbers, maximum-sum segment}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.6
A Reduction of the Dynamic Time Warping Distance to the Longest Increasing Subsequence Length

Authors: Yoshifumi Sakai and Shunsuke Inenaga

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
The similarity between a pair of time series, i.e., sequences of indexed values in time order, is often estimated by the dynamic time warping (DTW) distance, instead of any in the well-studied family of measures including the longest common subsequence (LCS) length and the edit distance. Although it may seem as if the DTW and the LCS(-like) measures are essentially different, we reveal that the DTW distance can be represented by the longest increasing subsequence (LIS) length of a sequence of integers, which is the LCS length between the integer sequence and itself sorted. For a given pair of time series of n integers between zero and c, we propose an integer sequence that represents any substring-substring DTW distance as its band-substring LIS length. The length of the produced integer sequence is O(c⁴ n²) or O(c² n²) depending on the variant of the DTW distance used, both of which can be translated to O(n²) for constant cost functions. To demonstrate that techniques developed under the LCS(-like) measures are directly applicable to analysis of time series via our reduction of DTW to LIS, we present time-efficient algorithms for DTW-related problems utilizing the semi-local sequence comparison technique developed for LCS-related problems.
Cite as

Yoshifumi Sakai and Shunsuke Inenaga. A Reduction of the Dynamic Time Warping Distance to the Longest Increasing Subsequence Length. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{sakai_et_al:LIPIcs.ISAAC.2020.6,
  author =	{Sakai, Yoshifumi and Inenaga, Shunsuke},
  title =	{{A Reduction of the Dynamic Time Warping Distance to the Longest Increasing Subsequence Length}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.6},
  URN =		{urn:nbn:de:0030-drops-133508},
  doi =		{10.4230/LIPIcs.ISAAC.2020.6},
  annote =	{Keywords: algorithms, dynamic time warping distance, longest increasing subsequence, semi-local sequence comparison}
}
Document
DOI: 10.4230/LIPIcs.CPM.2018.1
Maximal Common Subsequence Algorithms

Authors: Yoshifumi Sakai

Published in: LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018)

Abstract
A common subsequence of two strings is maximal, if inserting any character into the subsequence can no longer yield a common subsequence of the two strings. The present article proposes a (sub)linearithmic-time, linear-space algorithm for finding a maximal common subsequence of two strings and also proposes a linear-time algorithm for determining if a common subsequence of two strings is maximal.
Cite as

Yoshifumi Sakai. Maximal Common Subsequence Algorithms. In 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 105, pp. 1:1-1:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{sakai:LIPIcs.CPM.2018.1,
  author =	{Sakai, Yoshifumi},
  title =	{{Maximal Common Subsequence Algorithms}},
  booktitle =	{29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018)},
  pages =	{1:1--1:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-074-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{105},
  editor =	{Navarro, Gonzalo and Sankoff, David and Zhu, Binhai},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.1},
  URN =		{urn:nbn:de:0030-drops-87079},
  doi =		{10.4230/LIPIcs.CPM.2018.1},
  annote =	{Keywords: algorithms, string comparison, longest common subsequence, constrained longest common subsequence}
}
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 About DROPS Imprint Privacy Contact