Efficient Representation of (spatially sparse) spatial time series

Question

Background

I have a huge dataset consisting of points (on a plane) together with a timestamp for each point. This is a collection of car GPS measures, giving us the location (latitude/longitude) of some car and the time at which that car was there.

I would like to store the time-series’ information on a grid. That is, I have a rectangular grid, and for each cell, I would like to have a list of the dates at which there was a GPS signal in the cell. So, in the end I would like the data to be a 2 by 2 matrix of lists. Each element of the matrix representing a cell of the grid and the attached list would contain the dates at which there was a signal in that cell.

This would be the ideal data representation for the time-series analysis I will have to perform.

Problem

The dataset is huge. So I would like to be more memory-efficient. The main point to consider is the following:

• Since I’m using a regular rectangular grid and GPS signal is confined to cells containing roads, most of the cells will be “unactivated”, i.e most of the elements of the matrix will store an empty list (no signal).

Attempt

The above remark suggests that the spatial information could be stored into a list, instead of a matrix.
We would iterate over the dataset, for each measure look if the corresponding cell already exists in the list, and if not append a new cell to the list of activated cells.

This approach has two drawbacks compared to the matrix-based one:

1. Computational overhead: For each datapoint, we have to search a whole list to determine if the cell it belongs to is already in the list. In the matrix approach, we can easily determine the index of the corresponding element, given the coordinates of the point and the resolution of the grid.

2. Loss of spatial information: In the matrix approach, it is simple to change the resolution of the grid, or perform nearest neighbor based operations. The list aproach completely dumps all spatial information.

In both cases, the matrix approach has $\mathcal{O}(1)$ complexity, whereas the list one has $\mathcal{O}(n)$ complexity.

Question

I would thus like to be able to find a representation which doesn’t need to store empty cells, while at the same time retaining the advantages of the matrix representation.

---

P.S.: I know kdTrees would be good for nearest-neighbor search, I'm just a little concerned about the time needed to build it. Comments?

Answer 1

The dataset is huge. So I would like to be more memory-efficient. The main point to consider is the following:

• […] most of the cells will be “unactivated”, i.e most of the elements of the matrix will store an empty list (no signal).

This sounds as if an array of lists (or variably sized arrays) is just fine. In this case, the crucial factor for memory storage is not the size of your dataset but the size of the grid: Not all your lists need to have the same length. In fact, all you have to store for an empty grid point is a null pointer.

Of course, if your grid is so large that you cannot even store the respective number of null pointers, you do indeed have a problem.

Answer 2

You should define what nearest neighbor operations you are looking to perform and give a ballpark estimate of how big the dataset is.

In terms of data structures, you could also consider using a hash table with a spatial hash function. Given you are representing things with a regular grid, you can easily create a hash function and develop an efficient $O(1)$ search structure while also representing things in a sparse fashion. Using this data structure, it should take one pass through your $n$ pieces of data and place them into the search structure in a way you can easily search them up based on their grid cell. Depending on what nearest neighbor operations you are doing, this hash table approach could still be sufficient.

With respect to KD Trees, they will take some time to build but they usually are pretty quick (though obviously the size of your dataset does influence this). Assuming your dataset doesn't change, you could also store the sorted KD Tree into memory and just read it in directly. Also, assuming you build a roughly balanced KD Tree, the search for nearest neighbors can be quite efficient being on the order of $O(log(n))$.