背景
我有一个巨大的数据集，由点（在平面上）以及每个点的时间戳组成。这是汽车 GPS 测量的集合，为我们提供了某些汽车的位置（纬度/经度）以及该汽车在那里的时间。
我想将时间序列的信息存储在网格上。也就是说，我有一个矩形网格，对于每个单元格，我想要一个单元格中有 GPS 信号的日期列表。所以，最后我希望数据是一个 2 x 2 的列表矩阵。矩阵的每个元素表示网格的一个单元格和附加的列表将包含该单元格中存在信号的日期。
这将是我必须执行的时间序列分析的理想数据表示。
问题
数据集很大。所以我想提高内存效率。要考虑的要点如下：
- 由于我使用的是常规矩形网格，并且 GPS 信号仅限于包含道路的单元格，因此大多数单元格将“未激活”，即矩阵的大部分元素将存储一个空列表（无信号）。
试图
上述说明表明空间信息可以存储在列表中，而不是矩阵中。
我们将遍历数据集，对于每个度量，查看列表中是否已存在相应的单元格，如果不存在，则将新单元格添加到激活的单元格列表中。
与基于矩阵的方法相比，这种方法有两个缺点：
计算开销：对于每个数据点，我们必须搜索整个列表以确定它所属的单元格是否已经在列表中。在矩阵方法中，我们可以很容易地确定相应元素的索引，给定点的坐标和网格的分辨率。
空间信息丢失：在矩阵方法中，很容易改变网格的分辨率，或者执行基于最近邻的操作。列表方法完全转储所有空间信息。
在这两种情况下，矩阵方法都具有复杂度，而列表方法具有复杂度。
题
因此，我希望能够找到一种不需要存储空单元格的表示，同时保留矩阵表示的优点。
PS：我知道kdTrees对最近邻搜索很有用，我只是有点担心构建它所需的时间。注释？