Spatial-temporal storage system, method, and recording medium

Patent metadata

Field	Value
Publication number	US-12547594-B2
Application number	US-202117482651-A
Country	US
Kind code	B2
Filing date	Sep 23, 2021
Priority date	Mar 8, 2016
Publication date	Feb 10, 2026
Grant date	Feb 10, 2026

Abstract

A spatial-temporal storage method, system, and non-transitory computer readable medium include dynamically managing a plurality of region servers for querying spatiotemporal data in noSQL databases.

First claim

What is claimed is:

1 . A spatial-temporal storage system, comprising:
a processor; a memory, the memory storing instructions to cause the processor to perform:
managing a plurality of region servers based on a result of querying spatial-temporal data in noSQL databases, wherein the noSQL databases are organized into a 3D table of rows, columns and cell version, wherein each column belongs to a column family, wherein the 3D table is stored as a key-value store that consists of row key, column family key, column qualifier, and timestamp, and wherein the key-value store contains the data stored in a cell, wherein each region of the plurality of region servers is served by an HRegion instance, wherein the HRegion instance manages each column family using a store, and wherein each store contains a memory storage and multiple store files;
sorting and flushing all key-value pairs, in the memory storage, into a new store when the memory storage reaches a pre-defined flush threshold;
splitting the HRegion instance into two daughter regions when a size of the store increases beyond a threshold, wherein the two daughter regions initially create reference files pointing back to the multiple store files of their past parent region, thus achieving responsive elasticity;
calculating scan ranges via a geometric translation circuit that applies a Moore-curve based geo-location encoding algorithm, wherein a space of a geometric query is recursively divided into tiles using a quad-tree, and wherein the tiles are encoded using a space filling curve, and wherein the Moore-curve based geo-location encoding algorithm preserves spatial continuity on the memory storage for put, get, and scan queries;
casting, by the geometric translation circuit, 2D coordinates (x, y) into a one-dimensional key space to store the spatial-temporal data;
utilizing smaller database blocks to reduce read volume amplification; and
optimizing scan ranges of a same geometry query aggregately, such that multiple database blocks are fetched within fewer disk read operations.

2 . The spatial-temporal storage system of claim 1 , wherein the plurality of region servers are managed via a group-based replica placement policy to guarantee data locality during region splits, and
wherein the group-based replica placement policy divides parts of the spatial-temporal data into multiple shards based on user-defined pre-split keys.

3 . A non-transitory computer-readable recording medium recording a spatial-temporal storage program, the spatial-temporal storage program causing a computer to perform:
managing a plurality of region servers based on a result of querying spatial-temporal data in noSQL databases, wherein the noSQL databases are organized into a 3D table of rows, columns and cell version, wherein each column belongs to a column family, wherein the 3D table is stored as a key-value store that consists of row key, column family key, column qualifier, and timestamp, and wherein the key-value store contains the data stored in a cell, wherein each region of the plurality of region servers is served by an HRegion instance, wherein the HRegion instance manages each column family using a store, and wherein each store contains a memory storage and multiple store files; sorting and flushing all key-value pairs, in the memory storage, into a new store when the memory storage reaches a pre-defined flush threshold; splitting the HRegion instance into two daughter regions when a size of the store increases beyond a threshold, wherein the two daughter regions initially create reference files pointing back to the multiple store files of their past parent region, thus achieving responsive elasticity; calculating scan ranges via a geometric translation circuit that applies a Moore-curve based geo-location encoding algorithm, wherein a space of a geometric query is recursively divided into tiles using a quad-tree, and wherein the tiles are encoded using a space filling curve, and wherein the Moore-curve based geo-location encoding algorithm preserves spatial continuity on the memory storage for put, get, and scan queries; casting, by the geometric translation circuit, 2D coordinates (x, y) into a one-dimensional key space to the store spatial-temporal data; utilizing smaller database blocks to reduce read volume amplification; and optimizing scan ranges of a same geometry query aggregately, such that multiple database blocks are fetched within fewer disk read operations.

4 . The non-transitory computer-readable recording medium of claim 3 , wherein the plurality of region servers are managed via a group-based replica placement policy to guarantee data locality during region splits, and
wherein the group-based replica placement policy divides parts of the spatial-temporal data into multiple shards based on user-defined pre-split keys.

5 . A spatial-temporal storage method, comprising:
managing a plurality of region servers based on a result of querying spatial-temporal data in noSQL databases, wherein the noSQL databases are organized into a 3D table of rows, columns and cell version, wherein each column belongs to a column family, wherein the 3D table is stored as a key-value store that consists of row key, column family key, column qualifier, and timestamp, and wherein the key-value store contains the data stored in a cell, wherein each region of the plurality of region servers is served by an HRegion instance, wherein the HRegion instance manages each column family using a store, and wherein each store contains a memory storage and multiple store files; sorting and flushing all key-value pairs, in the memory storage, into a new store when the memory storage reaches a pre-defined flush threshold; splitting the HRegion instance into two daughter regions when a size of the store increases beyond a threshold, wherein the two daughter regions initially create reference files pointing back to the multiple store files of their past parent region, thus achieving responsive elasticity; calculating scan ranges via a geometric translation circuit that applies a Moore-curve based geo-location encoding algorithm, wherein a space of a geometric query is recursively divided into tiles using a quad-tree, and wherein the tiles are encoded using a space filling curve, and wherein the Moore-curve based geo-location encoding algorithm preserves spatial continuity on the memory storage for put, get, and scan queries; casting, by the geometric translation circuit, 2D coordinates (x, y) into a one-dimensional key space to store the spatial-temporal data; utilizing smaller database blocks to reduce read volume amplification; and optimizing scan ranges of a same geometry query aggregately, such that multiple database blocks are fetched within fewer disk read operations.

6 . The spatial-temporal storage method of claim 5 , wherein the plurality of region servers are managed via a group-based replica placement policy to guarantee data locality during region splits, and
wherein the group-based replica placement policy divides parts of the spatial-temporal data into multiple shards based on user-defined pre-split keys.

Assignees

• IBM

Inventors

• Ganti Raghu Kiran
• Li Shen
• Srivatsa Mudhakar

Classifications

• G06F16/2264

  Multidimensional index structures · CPC title

• G06F16/221

  Column-oriented storage; Management thereof · CPC title

• G06F16/2477

  Temporal data queries · CPC title

• G06F16/9537

  Spatial or temporal dependent retrieval, e.g. spatiotemporal queries · CPC title

• G06F16/2453

  Query optimisation · CPC title