rucrdtw

rucrdtw: Fast time series subsequence search in R - Published in JOSS (2016)

https://github.com/pboesu/rucrdtw

Repository

R Bindings for the UCR Suite for fast time series subsequence search

README.Rmd

---
output:
  md_document:
    variant: markdown_github
---

# rucrdtw - R Bindings for the UCR Suite


```{r echo=FALSE}
knitr::opts_chunk$set(
  comment = "#>",
  collapse = TRUE,
  warning = FALSE,
  message = FALSE,
  fig.path="inst/img/"
)
```


[![R-CMD-check](https://github.com/pboesu/rucrdtw/workflows/R-CMD-check/badge.svg)](https://github.com/pboesu/rucrdtw/actions)
[![codecov](https://codecov.io/gh/pboesu/rucrdtw/branch/master/graph/badge.svg)](https://app.codecov.io/gh/pboesu/rucrdtw)
[![CRAN_Status_Badge](http://www.r-pkg.org/badges/version/rucrdtw)](https://cran.r-project.org/package=rucrdtw)
[![Peer_Reviewed_Software](https://img.shields.io/badge/Peer%20Reviewed-%E2%9C%93-green.svg)](http://doi.org/10.21105/joss.00100)
[![DOI:10.21105/joss.00100](https://img.shields.io/badge/DOI-10.21105%2Fjoss.00100-blue.svg)](http://doi.org/10.21105/joss.00100)

  
R bindings for functions from the [UCR Suite](http://www.cs.ucr.edu/~eamonn/UCRsuite.html) (Thanawin Rakthanmanon et al. 2012 SIGKDD), which enables ultrafast subsequence search under both Dynamic Time Warping and Euclidean Distance. UCR DTW is several orders of magnitudes faster than naive DTW searches. 

```{r dtw-comparison, echo=FALSE, fig.width=7}
library("rucrdtw")
set.seed(123)
rwalk <- cumsum(runif(5e3, min = -0.5, max = 0.5))
qstart <- 876
query <- rwalk[qstart:(qstart+99)]
library(dtw)
#we create a small function that executes a sliding window search
naive_dtw <- function(data, query){
  n_comps <- (length(data)-length(query)+1)
  dtw_dist <- numeric(n_comps)
  for (i in 1:n_comps){
    dtw_dist[i] <- dtw(query, data[i:(i+length(query)-1)], distance.only = TRUE, window.type="sakoechiba", window.size=5)$distance
  }
  which.min(dtw_dist)
}

benchmarks <- rbenchmark::benchmark(
  naive_1000 = naive_dtw(rwalk[1:1000], query),
  naive_2000 = naive_dtw(rwalk[1:2000], query),
  naive_5000 = naive_dtw(rwalk, query),
  ucrdtw_1000 = ucrdtw_vv(rwalk[1:1000], query, 0.05),
  ucrdtw_2000 = ucrdtw_vv(rwalk[1:2000], query, 0.05),
  ucrdtw_5000 = ucrdtw_vv(rwalk, query, 0.05),
  replications = 20)

#ensure benchmark test column is of type factor for compatibility with r-devel
benchmarks$test <- as.factor(benchmarks$test)

colors <- rep(c("#33a02c","#1f78b4"), each=3)

#plot with log1p transformed axes, as some execution times may be numerically zero
plot(log1p(benchmarks$elapsed*50) ~ benchmarks$test, cex.axis=0.7, las = 2, yaxt = "n", xlab = "", ylab = "execution time [ms]", ylim = c(0,10), medcol = colors, staplecol=colors, boxcol=colors)
axis(2, at = log1p(c(1,10,100,1000,10000)), labels = c(1,10,100,1000,10000), cex.axis = 0.7)
legend("topright", legend = c("naive DTW", "UCR DTW"), fill = c("#33a02c","#1f78b4"), bty="n")
```
      
## Installation
Install `rucrdtw` from GitHub:

```{r eval=FALSE}
install.packages("devtools")
devtools::install_github("pboesu/rucrdtw")
```

## Examples

Examples are contained in the vignette `rucrdtw`:
```{r}
library("rucrdtw")
vignette("using_rucrdtw")
```

## Citation

To cite rucrdtw in publications, please use:   

  Boersch-Supan (2016). rucrdtw: Fast time series subsequence search in R. The Journal of Open Source Software 
  http://doi.org/10.21105/joss.00100

  Rakthanmanon et al. (2012). Searching and mining trillions of time series subsequences under dynamic time warping.
  SIGKDD http://doi.org/10.1145/2339530.2339576

 
## Bug reports and contributions

Please file a github issue at https://github.com/pboesu/rucrdtw/issues if you find any problems or have feature suggestions. Contributions (via pull requests or otherwise) are welcome. Read more about how to contribute and the code of conduct for contributions [here](https://github.com/pboesu/rucrdtw/blob/master/CONTRIBUTING.md). If you don't like github you can contact the package maintainer at pboesu@gmail.com.

## License
COPYRIGHT 2012: Thanawin Rakthanmanon, Bilson Campana, Abdullah Mueen, Gustavo Batista and Eamonn Keogh. (UCR Suite source code)

COPYRIGHT 2016: Philipp Boersch-Supan (R bindings)

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

https://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Owner

JOSS Publication

rucrdtw: Fast time series subsequence search in R

Published

November 07, 2016

DOI

10.21105/joss.00100

Volume 1, Issue 7, Page 100

Authors

Philipp H. Boersch-Supan
Department of Geography and Emerging Pathogens Institute, University of Florida

Editor

Arfon Smith

Tags

Rcpp Data mining Time series

View PDF Review Thread Software Archive

GitHub Events

Committers

Last synced: 7 months ago

Issues and Pull Requests

Last synced: 6 months ago

Packages