6 Search Results for "Leiserson, Charles"

Document
DOI: 10.4230/LIPIcs.ESA.2022.90
Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings

Authors: Zoe Xi and William Kuszmaul

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

Abstract
Dynamic Time Warping (DTW) is a widely used similarity measure for comparing strings that encode time series data, with applications to areas including bioinformatics, signature verification, and speech recognition. The standard dynamic-programming algorithm for DTW takes O(n²) time, and there are conditional lower bounds showing that no algorithm can do substantially better. In many applications, however, the strings x and y may contain long runs of repeated letters, meaning that they can be compressed using run-length encoding. A natural question is whether the DTW-distance between these compressed strings can be computed efficiently in terms of the lengths k and 𝓁 of the compressed strings. Recent work has shown how to achieve O(k𝓁² + 𝓁 k²) time, leaving open the question of whether a near-quadratic Õ(k𝓁)-time algorithm might exist. We show that, if a small approximation loss is permitted, then a near-quadratic time algorithm is indeed possible: our algorithm computes a (1 + ε)-approximation for DTW(x, y) in Õ(k𝓁 / ε³) time, where k and 𝓁 are the number of runs in x and y. Our algorithm allows for DTW to be computed over any metric space (Σ, δ) in which distances are O(log n)-bit integers. Surprisingly, the algorithm also works even if δ does not induce a metric space on Σ (e.g., δ need not satisfy the triangle inequality).
Cite as

Zoe Xi and William Kuszmaul. Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 90:1-90:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{xi_et_al:LIPIcs.ESA.2022.90,
  author =	{Xi, Zoe and Kuszmaul, William},
  title =	{{Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{90:1--90:19},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.90},
  URN =		{urn:nbn:de:0030-drops-170281},
  doi =		{10.4230/LIPIcs.ESA.2022.90},
  annote =	{Keywords: Dynamic time warping distance, approximation algorithms, run-length encodings, computational geometry}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.7
1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete

Authors: Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
Consider n²-1 unit-square blocks in an n × n square board, where each block is labeled as movable horizontally (only), movable vertically (only), or immovable - a variation of Rush Hour with only 1 × 1 cars and fixed blocks. We prove that it is PSPACE-complete to decide whether a given block can reach the left edge of the board, by reduction from Nondeterministic Constraint Logic via 2-color oriented Subway Shuffle. By contrast, polynomial-time algorithms are known for deciding whether a given block can be moved by one space, or when each block either is immovable or can move both horizontally and vertically. Our result answers a 15-year-old open problem by Tromp and Cilibrasi, and strengthens previous PSPACE-completeness results for Rush Hour with vertical 1 × 2 and horizontal 2 × 1 movable blocks and 4-color Subway Shuffle.
Cite as

Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff. 1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{brunner_et_al:LIPIcs.FUN.2021.7,
  author =	{Brunner, Josh and Chung, Lily and Demaine, Erik D. and Hendrickson, Dylan and Hesterberg, Adam and Suhl, Adam and Zeff, Avi},
  title =	{{1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.7},
  URN =		{urn:nbn:de:0030-drops-127681},
  doi =		{10.4230/LIPIcs.FUN.2021.7},
  annote =	{Keywords: puzzles, sliding blocks, PSPACE-hardness}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.19
Train Tracks with Gaps

Authors: William Kuszmaul

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
We identify a tradeoff curve between the number of wheels on a train car, and the amount of track that must be installed in order to ensure that the train car is supported by the track at all times. The goal is to build an elevated track that covers some large distance 𝓁, but that consists primarily of gaps, so that the total amount of feet of train track that is actually installed is only a small fraction of 𝓁. In order so that the train track can support the train at all points, the requirement is that as the train drives across the track, at least one set of wheels from the rear quarter and at least one set of wheels from the front quarter of the train must be touching the track at all times. We show that, if a train car has n sets of wheels evenly spaced apart in its rear and n sets of wheels evenly spaced apart in its front, then it is possible to build a train track that supports the train car but uses only Θ(𝓁 / n) feet of track. We then consider what happens if the wheels on the train car are not evenly spaced (and may even be configured adversarially). We show that for any configuration of the train car, with n wheels in each of the front and rear quarters of the car, it is possible to build a track that supports the car for distance 𝓁 and uses only O((𝓁 log n)/n) feet of track. Additionally, we show that there exist configurations of the train car for which this tradeoff curve is asymptotically optimal. Both the upper and lower bounds are achieved via applications of the probabilistic method. The algorithms and lower bounds in this paper provide simple illustrative examples of many of the core techniques in probabilistic combinatorics and randomized algorithms. These include the probabilistic method with alterations, the use of McDiarmid’s inequality within the probabilistic method, the algorithmic Lovász Local Lemma, the min-hash technique, and the method of conditional probabilities.
Cite as

William Kuszmaul. Train Tracks with Gaps. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 19:1-19:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kuszmaul:LIPIcs.FUN.2021.19,
  author =	{Kuszmaul, William},
  title =	{{Train Tracks with Gaps}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{19:1--19:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.19},
  URN =		{urn:nbn:de:0030-drops-127800},
  doi =		{10.4230/LIPIcs.FUN.2021.19},
  annote =	{Keywords: probabilistic method, algorithms, trains, Lov\'{a}sz Local Lemma, McDiarmid’s Inequality}
}
Document
DOI: 10.4230/DagSemProc.04301.1
04301 Abstracts Collection – Cache-Oblivious and Cache-Aware Algorithms

Authors: Lars Arge, Michael A. Bender, Erik Demaine, Charles Leiserson, and Kurt Mehlhorn

Published in: Dagstuhl Seminar Proceedings, Volume 4301, Cache-Oblivious and Cache-Aware Algorithms (2005)

Abstract
The Dagstuhl Seminar 04301 ``Cache-Oblivious and Cache-Aware Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl, from 18.07.2004 to 23.07.2004. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Lars Arge, Michael A. Bender, Erik Demaine, Charles Leiserson, and Kurt Mehlhorn. 04301 Abstracts Collection – Cache-Oblivious and Cache-Aware Algorithms. In Cache-Oblivious and Cache-Aware Algorithms. Dagstuhl Seminar Proceedings, Volume 4301, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{arge_et_al:DagSemProc.04301.1,
  author =	{Arge, Lars and Bender, Michael A. and Demaine, Erik and Leiserson, Charles and Mehlhorn, Kurt},
  title =	{{04301 Abstracts Collection – Cache-Oblivious and Cache-Aware Algorithms}},
  booktitle =	{Cache-Oblivious and Cache-Aware Algorithms},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4301},
  editor =	{Lars Arge and Michael A. Bender and Erik Demaine and Charles Leiserson and Kurt Mehlhorn},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04301.1},
  URN =		{urn:nbn:de:0030-drops-1576},
  doi =		{10.4230/DagSemProc.04301.1},
  annote =	{Keywords: Cache oblivious , cache aware , external memory , I/O-efficient algorithms , data structures}
}
Document
DOI: 10.4230/DagSemProc.04301.2
A Simple Algorithm for I/O-efficiently Pruning Dense Spanners

Authors: Joachim Gudmundsson and Jan Vahrenhold

Published in: Dagstuhl Seminar Proceedings, Volume 4301, Cache-Oblivious and Cache-Aware Algorithms (2005)

Abstract
Given a geometric graph $G=(S,E)$ in $R^d$ with constant dilation $t$, and a positive constant $\epsilon$, we show how to construct a $(1+\epsilon)$-spanner of $G$ with $O(|S|)$ edges using $O(sort(|E|))$ I/O operations.
Cite as

Joachim Gudmundsson and Jan Vahrenhold. A Simple Algorithm for I/O-efficiently Pruning Dense Spanners. In Cache-Oblivious and Cache-Aware Algorithms. Dagstuhl Seminar Proceedings, Volume 4301, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:DagSemProc.04301.2,
  author =	{Gudmundsson, Joachim and Vahrenhold, Jan},
  title =	{{A Simple Algorithm for I/O-efficiently Pruning Dense Spanners}},
  booktitle =	{Cache-Oblivious and Cache-Aware Algorithms},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4301},
  editor =	{Lars Arge and Michael A. Bender and Erik Demaine and Charles Leiserson and Kurt Mehlhorn},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04301.2},
  URN =		{urn:nbn:de:0030-drops-1566},
  doi =		{10.4230/DagSemProc.04301.2},
  annote =	{Keywords: No keywords}
}
Document
DOI: 10.4230/DagSemProc.04301.3
The Priority R-Tree: A Practically Efficient and Worst-Case-Optimal R-Tree

Authors: Lars Arge, Mark de Berg, Herman J. Haverkort, and Ke Yi

Published in: Dagstuhl Seminar Proceedings, Volume 4301, Cache-Oblivious and Cache-Aware Algorithms (2005)

Abstract
The query efficiency of a data structure that stores a set of objects, can normally be assessed by analysing the number of objects, pointers etc. looked at when answering a query. However, if the data structure is too big to fit in main memory, data may need to be fetched from disk. In that case, the query efficiency is easily dominated by moving the disk head to the correct locations, rather than by reading the data itself. To reduce the number of disk accesses, once can group the data into blocks, and strive to bound the number of different blocks accessed rather than the number of individual data objects read. An R-tree is a general-purpose data structur that stores a hierarchical grouping of geometric objects into blocks. Many heuristics have been designed to determine which objects should be grouped together, but none of these heuristics could give a guarantee on the resulting worst-case query time. We present the Priority R-tree, or PR-tree, which is the first R-tree variant that always answers a window query by accessing $O((N/B)^{1-1/d} + T/B)$ blocks, where $N$ is the number of $d$-dimensional objects stored, $B$ is the number of objects per block, and $T$ is the number of objects whose bounding boxes intersect the query window. This is provably asymptotically optimal. Experiments show that the PR-tree performs similar to the best known heuristics on real-life and relatively nicely distributed data, but outperforms them significantly on more extreme data.
Cite as

Lars Arge, Mark de Berg, Herman J. Haverkort, and Ke Yi. The Priority R-Tree: A Practically Efficient and Worst-Case-Optimal R-Tree. In Cache-Oblivious and Cache-Aware Algorithms. Dagstuhl Seminar Proceedings, Volume 4301, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{arge_et_al:DagSemProc.04301.3,
  author =	{Arge, Lars and de Berg, Mark and Haverkort, Herman J. and Yi, Ke},
  title =	{{The Priority R-Tree: A Practically Efficient and Worst-Case-Optimal R-Tree}},
  booktitle =	{Cache-Oblivious and Cache-Aware Algorithms},
  pages =	{1--26},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4301},
  editor =	{Lars Arge and Michael A. Bender and Erik Demaine and Charles Leiserson and Kurt Mehlhorn},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04301.3},
  URN =		{urn:nbn:de:0030-drops-1554},
  doi =		{10.4230/DagSemProc.04301.3},
  annote =	{Keywords: R-Trees}
}
  • Refine by Author
  • 2 Arge, Lars
  • 2 Kuszmaul, William
  • 1 Bender, Michael A.
  • 1 Brunner, Josh
  • 1 Chung, Lily
  • Show More...

  • Refine by Classification
  • 1 Theory of computation
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Cache oblivious
  • 1 Dynamic time warping distance
  • 1 I/O-efficient algorithms
  • 1 Lovász Local Lemma
  • 1 McDiarmid’s Inequality
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 3 2005
  • 2 2020
  • 1 2022

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