25:["$","title",null,{"children":"M4 Scalable Time Series Visualization | chris willis | Observable"}] 49:T72b,/** * M4 aggregation algorithm. * Reduce time series data in a visualization-preserving way. */ function m4( data, // input data width, // chart width in pixels time = d => d[0], // time accessor, defaults to [0] value = d => d[1] // value accessor, defaults to [1] ) { // update accessors as needed if (typeof time === 'string') { const tfield = time; time = d => d[tfield]; } if (typeof value === 'string') { const vfield = value; value = d => d[vfield]; } // ensure data is a proper array data = Array.isArray(data) ? data : Array.from(data); const n = data.length; // determine time range let tmin = time(data[0]); let tmax = tmin; for (let i = 0; i < n; ++i) { const t = time(data[i]); if (t < tmin) tmin = t; if (t > tmax) tmax = t; } const delta = tmax - tmin; // map a timestamp to an integer pixel coordinate const key = t => Math.round(width * (t - tmin) / delta); // compute min/max time and min/max value (M4!) per pixel column const agg = Array(width); for (let i = 0; i < n; ++i) { const d = data[i]; const t = time(d); const v = value(d); const k = key(t); if (agg[k] == null) { agg[k] = { tmin: t, tmin_i: i, tmax: t, tmax_i: i, vmin: v, vmin_i: i, vmax: v, vmax_i: i, }; } else { const a = agg[k]; if (t < a.tmin) { a.tmin = t; a.tmin_i = i; } if (t > a.tmax) { a.tmax = t; a.tmax_i = i; } if (v < a.vmin) { a.vmin = v; a.vmin_i = i; } if (v > a.vmax) { a.vmax = v; a.vmax_i = i; } } } // filter original data to extremal (M4) values only return data.filter((d, i) => { const t = time(d); const k = key(t); const a = agg[k]; return i === a.tmin_i || i === a.tmax_i || i === a.vmin_i || i === a.vmax_i; }); }4a:T61b,/** * MinMax aggregation algorithm. * Reduce time series data in a visualization-preserving way. */ function minmax( data, // input data width, // chart width in pixels time = d => d[0], // time accessor, defaults to [0] value = d => d[1] // value accessor, defaults to [1] ) { // update accessors as needed if (typeof time === 'string') { const tfield = time; time = d => d[tfield]; } if (typeof value === 'string') { const vfield = value; value = d => d[vfield]; } // ensure data is a proper array data = Array.isArray(data) ? data : Array.from(data); const n = data.length; // determine time range let tmin = time(data[0]); let tmax = tmin; for (let i = 0; i < n; ++i) { const t = time(data[i]); if (t < tmin) tmin = t; if (t > tmax) tmax = t; } const delta = tmax - tmin; // map a timestamp to an integer pixel coordinate const key = t => Math.round(width * (t - tmin) / delta); // compute min/max value per pixel column const agg = Array(width); for (let i = 0; i < n; ++i) { const d = data[i]; const v = value(d); const k = key(time(d)); if (agg[k] == null) { agg[k] = { vmin: v, vmin_i: i, vmax: v, vmax_i: i }; } else { const a = agg[k]; if (v < a.vmin) { a.vmin = v; a.vmin_i = i; } if (v > a.vmax) { a.vmax = v; a.vmax_i = i; } } } // filter original data to min/max values only return data.filter((d, i) => { const k = key(time(d)); const a = agg[k]; return i === a.vmin_i || i === a.vmax_i; }); }4b:[{"id":"33455a97cf9558f6db900a8d8383223db9e67fc765e148a0d696b59d9af5e5a9a0c2297645bbc459e47381d0f7e3c7e4cd0d6d103ce6996594174db2c61e4c8a","href":"https://static.observableusercontent.com/files/33455a97cf9558f6db900a8d8383223db9e67fc765e148a0d696b59d9af5e5a9a0c2297645bbc459e47381d0f7e3c7e4cd0d6d103ce6996594174db2c61e4c8a","name":"minmax.png","type":"image/png","lastModified":1694138187212.176,"size":30325}] 29:{"id":"4413ec3517518e8e","slug":null,"title":"M4 Scalable Time Series Visualization","thumbnail":"21fe0aecf165c09a3b9f437811b1cdf454daeceecd393a39bfa34d2f080146dc","access_level":"public","create_time":"$D2023-09-08T01:56:27.212Z","update_time":"$D2023-09-08T01:56:27.212Z","view_time":null,"first_public_time":"$D2023-09-08T01:56:27.212Z","has_unpublished_edits":null,"fork":{"id":"f13638339e8063e5","slug":"m4-scalable-time-series-visualization","title":"M4 Scalable Time Series Visualization","owner":{"id":"33e135341fd39b6b","login":"uwdata","name":"UW Interactive Data Lab"}},"stars":1,"starred":false,"owner":{"type":"team","id":"401763df5cbd274f","login":"3c1b59cb045555b7","name":"chris willis","avatar_url":"https://avatars-next.observableusercontent.com/a5a6f3a666131e620ed5ea3bb934681e46c635981d11b0d6dd5db28b443268df","tier":"starter_2024","bio":"","followed_by_you":false,"follows_you":false},"version":373,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"3c1b59cb045555b7","login":"3c1b59cb045555b7","name":"chris willis","avatar_url":"https://avatars-next.observableusercontent.com/a5a6f3a666131e620ed5ea3bb934681e46c635981d11b0d6dd5db28b443268df","tier":null,"bio":"","followed_by_you":false,"follows_you":false}],"members":[{"type":"individual","id":"3c1b59cb045555b7","login":"3c1b59cb045555b7","name":"chris willis","avatar_url":"https://avatars-next.observableusercontent.com/a5a6f3a666131e620ed5ea3bb934681e46c635981d11b0d6dd5db28b443268df","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"M4 Scalable Time Series Visualization","cells":[{"id":0,"value":"# M4 Scalable Time Series Visualization\n\n**TL;DR**: _Reduce large time series by a factor of 1,000 or more, but retain the same visualization you would see for the full dataset._","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":134,"value":"Imagine you sample a sensor value every 10 milliseconds... over the course of just one day, you will already have ${d3.format(',')(24 * 60 * 60 * 100)} values! Plotting this data directly seems needlessly inefficient, as many time points will be mapped to the same pixel.\n\n[`M4` (Jugel et al. '14)](http://www.vldb.org/pvldb/vol7/p797-jugel.pdf) is a technique for reducing the size of a long time series in a \"visualization preserving\" way. That is, you should not be able to see any difference between a standard time-series plot of all the data and a plot made from the much smaller dataset produced by `M4`. Moreover, `M4` does this with no date binning scheme other than the number of pixels in your plot.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":257,"value":"This notebook contains a JavaScript implementation of M4 applicable to an array of objects, to transform data before plotting with [Vega-Lite](https://observablehq.com/@uwdata/introduction-to-vega-lite) or [Observable Plot](https://observablehq.com/@observablehq/plot).\n\nTo use `M4` in your own notebooks, import it...\n\n~~~ js\nimport { m4 } from '@uwdata/m4'\n~~~\n\n...then run your data through the `m4` function prior to plotting:\n\n~~~ js\nm4(data, chartWidth, d => d.timestamp, d => d.value)\n~~~\n\n`M4` needs to know the pixel width of the plotting region (excluding axes and padding), so you want to set up your plot to control the width directly.\n\n---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":146,"value":"First, let's generate some data using a [random walk](https://en.wikipedia.org/wiki/Random_walk). Here is a random walk with just 500 steps, plotted directly:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":151,"value":"Plot.plot({\n width: dataWidth + marginLeft + marginRight,\n marginLeft,\n marginRight,\n y: { grid: true },\n marks: [\n Plot.line(randomWalk(500), { x: 't', y: 'v', stroke: 'steelblue' })\n ]\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":156,"value":"To simulate a large time series dataset, we'll take a random walk with 1 million steps:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":11,"value":"data = randomWalk(1e6)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":164,"value":"Now how should we plot the data?","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":18,"value":"## No Aggregation\n\nOne option is to plot the data as-is. The problem is that we are now drawing all 1 million points, even though our plotting space is less than 1,000 pixels wide. We would needlessly draw _over 1,000 data points for each pixel_, making our plot slow to produce – and if we're using SVG output, generating one _gigantic_ SVG!\n\nTo avoid dragging down your browser, the code below is commented out. Feel free to uncomment and run the cell to (try to) draw all 1M points...","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":82,"value":"Points: ${fmt(data.length)}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":232,"value":"// Plot.plot({\n// width: dataWidth + marginLeft + marginRight,\n// marginLeft,\n// marginRight,\n// y: { grid: true },\n// marks: [\n// Plot.line(data, { x: 't', y: 'v', stroke: 'steelblue' })\n// ]\n// })","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":100,"value":"## MinMax Aggregation\n\nIf we know the chart width ahead of time, we can bin the data _by pixel_ and compute aggregates for each pixel column. Within each pixel window, the `MinMax` aggregation method finds the minimum and maximum _y-axis_ values and then retains only the input data points that match those extrema. Here, this method reduces the data by a factor of about 1,000.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":114,"value":"Points: ${fmt(minmaxData.length)}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":111,"value":"Plot.plot({\n width: dataWidth + marginLeft + marginRight,\n marginLeft,\n marginRight,\n y: { grid: true },\n marks: [\n Plot.line(minmaxData, { x: 't', y: 'v', stroke: 'steelblue' })\n ]\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":109,"value":"minmaxData = minmax(data, dataWidth, 't', 'v')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":183,"value":"This chart renders _much_ more quickly than plotting all the data. However, `MinMax` can subtly distort the data and introduce artifacts, as illustrated on the left side of the figure below (from the [`M4` research paper](http://www.vldb.org/pvldb/vol7/p797-jugel.pdf)). We can do better with `M4`!","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":349,"value":"FileAttachment(\"minmax.png\").image()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":24,"value":"## M4 Aggregation\n\n`M4` extends `MinMax` by preserving more points per pixel column: not only min/max _y_ values, but also min/max timestamps. The algorithm computes four minimum or maximum values per pixel, hence the name `M4`.\n\nAs the `M4` authors show in their [research paper](http://www.vldb.org/pvldb/vol7/p797-jugel.pdf), these four points per pixel are sufficient to perfectly preserve the features of the time series plot. With only twice as many points as `MinMax` – a number still _significantly_ smaller than the input and bounded by the number of horizontal pixels – we can create a plot that matches what we would get if we had plotted every point.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":89,"value":"Points: ${fmt(m4Data.length)}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":236,"value":"Plot.plot({\n width: dataWidth + marginLeft + marginRight,\n marginLeft,\n marginRight,\n y: { grid: true },\n marks: [\n Plot.line(m4Data, { x: 't', y: 'v', stroke: 'steelblue' })\n ]\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":76,"value":"m4Data = m4(data, dataWidth, 't', 'v')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":276,"value":"## The `M4` Algorithm","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":217,"value":"$49","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":194,"value":"## SQL Friendly!\n\nWhile this notebook uses a direct JavaScript implementation of `M4`, a particularly nice feature of the algorithm is that it can be applied directly to modern SQL databases. Given a table or query `Q` that returns a time series with columns `t` (for the timestamp) and `v` (for the value), here is a corresponding SQL query to perform `M4`. The parameter `$w` is the chart width in pixels, while `$t1` and `$t2` are the global minimum and maximum timestamps.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":197,"value":"``` sql\nSELECT t,v FROM Q JOIN\n(SELECT round($w*(t-$t1)/($t2-$t1)) as k, --define key\n min(v) as v_min, max(v) as v_max, --get min,max\n min(t) as t_min, max(t) as t_max --get 1st,last\n FROM Q GROUP BY k) as QA --group by k\nON k = round($w*(t-$t1)/($t2-$t1)) --join on k\n AND (v = v_min OR v = v_max OR --&(min|max|\n t = t_min OR t = t_max) -- 1st|last)\n```","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":7,"value":"## Appendix","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":62,"value":"dataWidth = Math.min(720, width) - marginLeft - marginRight","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":67,"value":"marginLeft = 30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":358,"value":"marginRight = 10","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"function randomWalk(\n numPoints = 1e5,\n startValue = 0,\n stepSize = 1\n) {\n const data = [];\n let currentValue = startValue;\n for (let i = 0; i < numPoints; ++i) {\n data.push({\n t: new Date(2022, 9, 31, 0, 0, i),\n v: currentValue\n });\n currentValue += (1 - 2 * Math.random()) * stepSize;\n }\n return data;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":311,"value":"$4a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":116,"value":"fmt = d3.format(',d')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W4b","stdlib":"1"}} 24:null