The Blog of Ian Mercer.

Time Series Data Compression

In a previous post I talked about compressing time series-data using a co-linearity test. This approach worked OK but recently I came across a better approach and I've implemented it to reduce the number of data points that are collected for any sensor without losing any of the salient features of the time series data.

What's needed is an algorithm that preserves the shape of the signal, each local maximum or minimum must be preserved and each inflection point in the curve should be represented. An overall RMS difference between the compressed data and the actual data must be kept small.

I came across this great summary paper: 'An Overview of Moving Object Trajectory Compression Algorithms' which provided some of the ideas behind my latest data compression scheme. In particular a scan or sweep approach to selecting which points to keep or drop.

The entire code is below and as you can see on the graph above it does a good job capturing the salient points in the data whilst eliminating as many other points as possible.

To use the code you provide a percentage (e.g. 0.05) which expresses the delta up or down that a point can have from its actual value. At each step the algorithm fits two lines to the data points after the current start point: an upper limit and a lower limit line using the up or down delta calculated from the percentage allowed. As new points arrive, if they are within this 'cone' they replace the previous value and adjust the cone to be narrower based on their location. As that location gets ever further from the start point the cone narrows. If the points stay within the percentage threshold around some line from the start point then they keep removing and replacing the last data point. But as soon as one strays outside the cone, the algorithm keeps the last point before it and the current point and restarts the process with that as the new baseline.

Explanatory diagram

At each inflection point, local minimum, or local maximum, the algorithm saves the current point and starts looking for a new line segment. It turned out to be really simple code and it works really well. To use it you provide two call backs: one to write a value to the database and one to update the last value in the database.

There are other better off-line algorithms for trajectory compression but the beauty of this one is that it works incrementally and only updates the last data point. As such it doesn't need a lot of buffer, can run very efficiently and doesn't change the graph as you are looking at it.

    /// <summary>
    /// Trajectory compression using narrowing cones
    /// </summary>
    /// <remarks>
    /// Can update last value but can't go further back, resets when the curve changes direction
    /// </remarks>
    public class TrajectoryCompressor
    {
        private readonly double percentage;

        private double startValue;
        private long startTime;
        private double previousValue;
        private long previousTime;
        private bool hasPrevious = false;
        private double lower_slope = -1.0;
        private double upper_slope = 1.0;

        public TrajectoryCompressor(double percentage, long startTime, double startValue)
        {
            this.percentage = percentage;
            this.startTime = startTime;
            this.startValue = startValue;
        }

        public void Add(long timestamp, double value, 
            Action<long, double> write,
            Action<long, long, double> update)
        {
            if (!hasPrevious)
            {
                write(timestamp, value);
                hasPrevious = true;
                previousTime = timestamp;
                previousValue = value;
                return;
            }

            if (timestamp == previousTime)
            {
                // ignore simultaneous values
                return;
            }

            // Add allowed error to it
            double upper_estimate = (value > 0) ? value * (1.0 + percentage) : value * (1.0 - percentage);
            double lower_estimate = (value > 0) ? value * (1.0 - percentage) : value * (1.0 + percentage);

            double upper_bound = (timestamp - startTime) * upper_slope + startValue;
            double lower_bound = (timestamp - startTime) * lower_slope + startValue;

            bool outside = (value > upper_bound || value < lower_bound);

            if (outside)
            {
                // The new point is outside the cone of allowed values
                // so we allow previousValue to stand and start a new segment
                startTime = previousTime;
                startValue = previousValue;
                previousTime = timestamp;
                previousValue = value;
                hasPrevious = true;
                write(timestamp, value);          // And write out the current value

                // and calculate new min max slope
                upper_slope = (upper_estimate - startValue) / (timestamp - startTime);
                lower_slope = (lower_estimate - startValue) / (timestamp - startTime);

                return;
            }

            // value is within expected range, it can replace previous
            update(previousTime, timestamp, value);

            // Keep track of it so we can keep updating
            previousTime = timestamp;
            previousValue = value;

            // and then narrow the allowed range
            if (upper_estimate < upper_bound) upper_slope = (upper_estimate - startValue) / (timestamp - startTime);
            if (lower_estimate > lower_bound) lower_slope = (lower_estimate - startValue) / (timestamp - startTime);
        }

    }

Related Stories

Home Automation

I've been working on home automation for over 15 years and I'm close to achieving my goal which is a house that understands where everyone is at all times, can predict where you are going next and can control lighting, heating and other systems without you having to do or say anything. That's a true "smart home".

Ian Mercer
Ian Mercer

Bluetooth Tracking Project

My year long Bluetooth project that won the $20,000 HCI and Microsoft competition during lockdown has continued to grow and now reliably tracks how many people are in the house and outside and can locate any device down to room level.

Ian Mercer
Ian Mercer

Digital Twins are never identical

Digital Twin are an online representation of a real world object, a copy of its properties in the digital world and a way to send updated and commands to it. In effect I've been making them for years but now they have a trendy name.

Ian Mercer
Ian Mercer

Home Automation Sensors

An overview of the many sensors I've experimented with for home automation including my favorite under-floor strain gauge, through all the usual PIR, beam and contact sensors to some more esoteric devices like an 8x8 thermal camera.

Ian Mercer
Ian Mercer

Why smarthomes are hard

Why automated learning is hard for a smart home. The perils of over-fitting, under-fitting and how the general unpredictable nature of life makes it hard to build a system that learns your behavior.

Ian Mercer
Ian Mercer

Collinearity test for sensor data compression

One way to reduce the volume of sensor data is to remove redundant points. In a system with timestamped data recorded on an irregular interval we can achieve this by removing co-linear points.

Ian Mercer
Ian Mercer

3d Printed ESP32 Brick

ESP32 provides a great platform for sensors around the house but by the time you've added a USB power brick, cable and enclosure it's quite messy. I wanted a device that I could just plug in with no exposed wires and no mounting needed so I designed one in OpenSCAD.

Ian Mercer
Ian Mercer

Filtering techniques

Filtering raw data is essential for a reliable home automation system. Here are some of the many ways you can filter sensor data.

Ian Mercer
Ian Mercer

Bluetooth Sensing for Home Automation

Bluetooth sensing for home automation is a great proxy for people counting as it can detect and locate each cellphone in the house. iBeacons attached to tools, cars and pets can provide a 'find my anything' feature too.

Ian Mercer
Ian Mercer

Gas sensors

Gas sensors come in many different flavors including CO2, VOC and particulate sensors.

Ian Mercer
Ian Mercer

Humidity Sensors (DHT11, DHT22, AM2320)

Humidity sensors are great for controlling extractor fans in bathrooms and other damp spaces.

Ian Mercer
Ian Mercer

Light sensors for Home Automation

Having at least one light sensor is critical for any home automation system that controls lightng. Lights need to be turned on when it's dark not at specific times of day, especially here in Seattle when it can be dark and cloudy at any time of day.

Ian Mercer
Ian Mercer

Microwave Doppler Sensors (RCWL-0516)

Microwave doppler sensors can be found in some alarm sensors but there are also available very cheaply as a separate component. They offer exceptional range but suffer from false triggers requiring a probailistic approach to people sensing.

Ian Mercer
Ian Mercer

Optical-beam sensors

Optical-beam sensors are reliable and can cover a long-distance such as across a garage or aisle-way. When they include multiple-beams they have good false-trigger rejection.

Ian Mercer
Ian Mercer

PIR Sensors for Home Automation

PIR sensors are cheap and easy to use but they suffer from slow response times and low repeat rates.

Ian Mercer
Ian Mercer

Strain-gauges

Strain-gauges are my top-rated sensor for home automation because they are invisible, reliable and can be tuned to detect people and ignore pets.

Ian Mercer
Ian Mercer

Temperature sensors for home automation

Temperature sensors I've experimented with for home automation.

Ian Mercer
Ian Mercer

Event blocks

Home automation systems need to respond to events in the real world. Sometimes it's an analog value, sometimes it's binary, rarely is it clean and not susceptible to problems. Let's discuss some of the ways to convert these inputs into actions.

Ian Mercer
Ian Mercer

Logistic function - convert values to probabilities

Another super useful function for handling sensor data and converting to probabilities is the logistic function 1/(1+e^-x). Using this you can easily map values onto a 0.0-1.0 probability range.

Ian Mercer
Ian Mercer

ATAN curve for probabilities

In a home automation system we often want to convert a measurement into a probability. The ATAN curve is one of my favorite curves for this as it's easy to map overything onto a 0.0-1.0 range.

Ian Mercer
Ian Mercer

Home Construction Advice

Several years ago we did a major remodel. I did all of the finish electrical myself and supervised all of the rough-in electrical. I also put in all of the electrical system and water in our barn. I have opinions ...

Ian Mercer
Ian Mercer

T-Mobile home internet

I'm testing a T-Mobile Home Internet device as a backup to XFinity and a way to offload half our monthly traffic to avoid the XFinity 1.2TB cap

Ian Mercer
Ian Mercer

Bluetooth

One of my inventions recently won a $20k global competition for applications that could help in a pandemic. It uses Bluetooth to count people.

Ian Mercer
Ian Mercer

Probabilistic Home Automation

A probabilistic approach to home automation models the probability that each room is occupied and how many people are in that room.

Ian Mercer
Ian Mercer

Multiple hypothesis tracking

A statistical approach to understanding which rooms are occupied in a smart house

Ian Mercer
Ian Mercer

A state machine for lighting control

An if-this-then-that style rules machine is insufficient for lighting control. This state machine accomplishes 90% of the correct behavior for a light that is controlled automatically and manually in a home automation system.

Ian Mercer
Ian Mercer

Home Automation States

Understanding the many different 'states' a house can have is critical to creating great home automation

Ian Mercer
Ian Mercer

Graphing gigabytes of home automation data with tableau

Some interesting charts from the gigabytes of data my home automation system produces

Ian Mercer
Ian Mercer

iBeacons for Home Automation

My investigations into using iBeacons for home automation

Ian Mercer
Ian Mercer

iBeacon meetup in Seattle - January 2015

My notes on the iBeacon meetup in Seattle held in January 2015

Ian Mercer
Ian Mercer

Home Automation Systems as a Graph

Using nodes and links to represent a home and all the devices in it

Ian Mercer
Ian Mercer

N-Gram Analysis of Sensor Events in Home Automation

Using n-gram analysis to spot patterns in sensor activations

Ian Mercer
Ian Mercer

Xamarin Forms Application For Home Automation

Building a Xamarin Forms application to control my home automation system

Ian Mercer
Ian Mercer

The Internet of Hubs (and things)

Maybe it should be called the Internet of Hubs instead

Ian Mercer
Ian Mercer

Showing home status with just a single RGB LED

Multicolored LEDs can convey a lot of information in a small space

Ian Mercer
Ian Mercer

A wireless sensor network using Moteino boards

The diminutive Arduino boards include a powerful transmitter/receiver

Ian Mercer
Ian Mercer

JSON Patch - a C# implementation

Ian Mercer
Ian Mercer

The home as a user interface

Ian Mercer
Ian Mercer

A RESTful API for sensor data

POSTing data to a home automation system from Arduino devices

Ian Mercer
Ian Mercer

The Internet of Boilers

An experiment to measure every aspect of an HVAC / boiler system

Ian Mercer
Ian Mercer

VariableWithHistory - making persistence invisible, making history visible

A novel approach to adding history to variables in a programming language

Ian Mercer
Ian Mercer

A Quantified House - My Talk to the Seattle Quantified Self Meetup

My talk to the Seattle Quantified Self meetup

Ian Mercer
Ian Mercer

Integrating an Android phone into my home automation system

Some new features for my home automation using an Android phone

Ian Mercer
Ian Mercer

Before there was the web there was BeebTel

Just thought I should mention that I built a web-like system before the web existed

Ian Mercer
Ian Mercer

My first programme [sic]

At the risk of looking seriously old, here's something found on a paper tape

Ian Mercer
Ian Mercer

The Internet of Dogs

Connecting our dog into the home automation

Ian Mercer
Ian Mercer

GreenGoose Review

A review of the now defunct GreenGoose sensor system

Ian Mercer
Ian Mercer

Home power meters revisited

Ian Mercer
Ian Mercer

Finally got the 1U Atom Server racked up

Ian Mercer
Ian Mercer

Timelapse video using the GoPro HD Hero

Ian Mercer
Ian Mercer

Home Automation Calendar Integration

Ian Mercer
Ian Mercer

Web site crawler and link checker (free)

Ian Mercer
Ian Mercer

Smart home energy savings - update for 2010

Ian Mercer
Ian Mercer

A smart power strip

Ian Mercer
Ian Mercer

What does a Smart House do at Halloween?

My favorite home automation features for Halloween

Ian Mercer
Ian Mercer

Home Automation Top Features

Ian Mercer
Ian Mercer

Weather Forecasting for Home Automation

Ian Mercer
Ian Mercer

I should have created Four Square ...

Ian Mercer
Ian Mercer

How can I tell if my house is smart?

Ian Mercer
Ian Mercer

Asian Gadgets

Ian Mercer
Ian Mercer

A great video explaining the Semantic Web

Ian Mercer
Ian Mercer

Interesting Twitter Posts March 15th-

Ian Mercer
Ian Mercer

Twitter links for Week beginning March 8th

Ian Mercer
Ian Mercer

Home Automation Block Diagram

Ian Mercer
Ian Mercer

Elliott 803 - An Early Computer

Ian Mercer
Ian Mercer

Facebook, social gaming and points

Ian Mercer
Ian Mercer

Useful Twitter links Feb 8-Feb 15 2010

Ian Mercer
Ian Mercer

World's Smartest House Demonstration

Ian Mercer
Ian Mercer

Looking forward to the new year and our new datacenter

Historical note about moving my servers into a datacenter

Ian Mercer
Ian Mercer

When will people learn to backup?

A rant about RAID

Ian Mercer
Ian Mercer

Future proof your home with a new conduit system?

Running conduit can be expensive but maybe you don't need one to every room

Ian Mercer
Ian Mercer

Balloon Boy was much ado about nothing - Twitter

Some of the more witty comments on Twitter about the Balloon Boy hoax

Ian Mercer
Ian Mercer

Shortened URLs should be treated like a Codec ...

Expanding URLs would help users decide whether or not to click a link

Ian Mercer
Ian Mercer

Tagging File Systems

Isn't it time we stopped knowing which drive our file is on?

Ian Mercer
Ian Mercer

WMPnetwk.exe started using 50% of my CPU

Uninstalling Windows Media Player - the end of an era

Ian Mercer
Ian Mercer

Introducing Jigsaw menus

A novel UI for menus that combines a breadcrumb and a menu in one visual metaphor

Ian Mercer
Ian Mercer

Amazon Instance vs Dedicated Server comparison

Some benchmark performance for Amazon vs a dedicated server

Ian Mercer
Ian Mercer

Agile Software Development is Like Sailing

You cannot tack too often when sailing or you get nowhere. Agile is a bit like that.

Ian Mercer
Ian Mercer

AntiVirus Software is the Worst Software!

When your anti-virus software starts stealing your personal data, it's time to remove it!

Ian Mercer
Ian Mercer

Second Drobo Update

At this point things were looking up for my Drobo

Ian Mercer
Ian Mercer

It's all about disk speed

Why disk speed is the most critical aspect for most modern PCs and servers

Ian Mercer
Ian Mercer

Comcast woes and a new monitoring utility

Monitoring a cable modem using its HTML management interface

Ian Mercer
Ian Mercer

Core duo desktop machine runs cool

Ian Mercer
Ian Mercer

Giving up on Internet Explorer

Ian Mercer
Ian Mercer

New Home Automation Server

Ian Mercer
Ian Mercer

Dell upgrades - a pricey way to go

Ian Mercer
Ian Mercer

World's Smartest House

Over 15 years of experimentation with home automation

Ian Mercer
Ian Mercer

The Grideye 8x8 camera sensor

Experiments with an 8x8 IR camera for privacy-preserving people detection using cameras.

Ian Mercer
Ian Mercer

World's Smartest House Videos

A collection of videos about my smart home efforts

Ian Mercer
Ian Mercer

CCTV Cameras as Home Automation Sensors

CCTV cameras are an option for detecting people but within the home there are privacy concerns that need to be addressed.

Ian Mercer
Ian Mercer

Pressure Sensors for Home Automation

Pressure sensors can detect HVAC system operation and could potentially detect clogged filters.

Ian Mercer
Ian Mercer