Spatial-temporal storage including a geometric translation
A spatial-temporal storage method, system, and non-transitory computer readable medium, include, in a first layer, a geometric translation circuit configured to split spatial-temporal information into row keys and translate a geometry query into a range scan, and a multi-scan optimization circuit configured to compute an optimal read strategy to optimize the range scan translated by the geometric translation circuit into a series of block starting offsets and block sizes, and, in a second layer, a block grouping circuit configured to allow grouping of blocks in the second layer while preserving spatial data locality when splits of spatial-temporal information occur in the first layer.
1. A spatial-temporal storage system, comprising:
a processor; and
a memory, the memory storing instructions to cause the processor to perform:
in a first layer of a quad tree,
internally implementing Moore encoding to translate geometry queries into range scans by traversing deeper into the quad tree if the geometry queries partially overlap with an area; and
aggregately minimizing, via read amplification including read area amplification, read volume amplification, and redundant read phenomena, input and output latencies of the range scans generated by a same geometry query of the geometry queries using dynamic programming in the first layer; and
in a second layer of the quad tree,
deploying block grouping to preserve data locality benefits when regions in the geometry queries are split during a moving hotspot.
2. The spatial-temporal storage system of claim 1 , wherein, in the second layer, the employing groups the data to group spatial-temporal information such that data corresponding to a first group in a first server is replicated to create a replica and the replica is placed in a second group in a second server where the replicas of a same group are stored in a same physical server at the second server.
3. The spatial-temporal storage system of claim 2 , wherein, when retrieving the split spatial-temporal information for the moving hotspot in the second layer, the block grouping splits the replica into multiple daughters on different physical servers at the second server to make use of resources on the different physical servers.
4. The spatial-temporal storage system of claim 2 , wherein the spatial-temporal information is split so as to have uniform density in the first server and the second server.
5. The spatial-temporal storage system of claim 1 , further comprising, in the first layer, determining if the optimal read strategy is greater than a predetermined threshold.
6. The spatial-temporal storage system of claim 1 , wherein the deployment of the block grouping specifies replica groups when writing data into the second layer, and
wherein replicas in a same group are placed into a same data node.
7. The spatial-temporal storage system of claim 6 , wherein block sizes are set to respect splits such that a daughter region server including one of the multiple daughters is moved into a remote physical server.
8. The spatial-temporal storage system of claim 1 , wherein the Moore encoding occurs on each node of the quad tree,
wherein, in the second layer of the quad tree, the same quad-tree is used to calculate tiles in the quad tree that intersect with the geometry of the first layer of the quad tree, and
wherein the block comprises a meta block and a data block, the data block being different than the meta block.
9. A non-transitory computer-readable recording medium recording a spatial-temporal storage program, the program causing a computer to perform:
in a first layer of a quad tree,
internally implementing Moore encoding to translate geometry queries into range scans by traversing deeper into the quad tree if the geometry queries partially overlap with an area; and
aggregately minimizing, via read amplification including read area amplification, read volume amplification, and redundant read phenomena, input and output latencies of the range scans generated by a same geometry query of the geometry queries using dynamic programming in the first layer; and
in a second layer of the quad tree,
deploying block grouping to preserve data locality benefits when regions in the geometry queries are split during a moving hotspot.
10. The non-transitory computer-readable recording medium of claim 9 , wherein, in the second layer, the employing groups the data to group spatial-temporal information such that data corresponding to a first group in a first server is replicated to create a replica and the replica is placed in a second group in a second server where the replicas of a same group are stored in a same physical server at the second server.
11. The non-transitory computer-readable recording medium of claim 9 , wherein, when retrieving the split spatial-temporal information for the moving hotspot in the second layer, the block grouping splits the replica into multiple daughters on different physical servers at the second server to make use of resources on the different physical servers.
12. The non-transitory computer-readable recording medium of claim 9 , further comprising, in the first layer, determining if the optimal read strategy is greater than a predetermined threshold.
13. The non-transitory computer-readable recording medium of claim 9 , wherein the deployment of the block grouping specifies replica groups when writing data into the second layer, and
wherein replicas in a same group are placed into a same data node.
14. The non-transitory computer-readable recording medium of claim 13 , wherein block sizes are set to respect splits such that a daughter region server including one of the multiple daughters is moved into a remote physical server.
15. The non-transitory computer-readable recording medium of claim 9 , wherein the spatial-temporal information is split so as to have uniform density in the first server and the second server.
16. A spatial-temporal storage method, comprising:
in a first layer of a quad tree,
internally implementing Moore encoding to translate geometry queries into range scans by traversing deeper into the quad tree if the geometry queries partially overlap with an area; and
aggregately minimizing, via read amplification including read area amplification, read volume amplification, and redundant read phenomena, input and output latencies of the range scans generated by a same geometry query of the geometry queries using dynamic programming in the first layer; and
in a second layer of the quad tree,
deploying block grouping to preserve data locality benefits when regions in the geometry queries are split during a moving hotspot.
17. The spatial-temporal storage method of claim 16 , wherein, in the second layer, the employing groups the data to group spatial-temporal information such that data corresponding to a first group in a first server is replicated to create a replica and the replica is placed in a second group in a second server where the replicas of a same group are stored in a same physical server at the second server.
18. The spatial-temporal storage method of claim 16 , wherein, when retrieving the split spatial-temporal information for the moving hotspot in the second layer, the block grouping splits the replica into multiple daughters on different physical servers at the second server to make use of resources on the different physical servers.
19. The spatial-temporal storage method of claim 16 , further comprising, in the first layer, determining if the optimal read strategy is greater than a predetermined threshold.
20. The spatial-temporal storage method of claim 16 , wherein the deployment of the block grouping specifies replica groups when writing data into the second layer, and
wherein replicas in a same group are placed into a same data node.