Mechanism and apparatus of spatial encoding enabled multi-scale context join

Patent metadata

Field	Value
Publication number	US-2018032597-A1
Application number	US-201615221723-A
Country	US
Kind code	A1
Filing date	Jul 28, 2016
Priority date	Jul 28, 2016
Publication date	Feb 1, 2018
Grant date	—

Abstract

A hierarchical spatial encode structure stored on a computing device is disclosed. The hierarchical spatial encode structure includes a plurality of scale levels having a plurality of encode expressions for a multi-scale context. The encode expressions on a first of the scale levels may include a first length. The encode expressions on a second of the scale levels may include a second length greater than the first length. Each encode expression of the second of the scale levels may include one or more of the encode expressions of the first of the scale levels. A context of the first of the scale levels may have a contain/nest (contained) spatial relation to a context of the second of the scale levels.

First claim

What is claimed is:

1 . A hierarchical spatial encode structure stored on a computing device, comprising:
a plurality of scale levels comprising a plurality of encode expressions for a multi-scale context, the encode expressions on a first of the scale levels comprising a first length, the encode expressions on a second of the scale levels comprising a second length greater than the first length, each encode expression of the second of the scale levels comprising one or more of the encode expressions of the first of the scale levels, a context of the first of the scale levels having a contain/nest (contained) spatial relation to a context of the second of the scale levels.

2 . The hierarchical spatial encode structure of claim 1 , wherein the encode expressions are configured in a left-to-right format to support a left fuzzy range query of a No-SQL database.

3 . The hierarchical spatial encode structure of claim 1 , wherein the multi-scale context comprises a min bounding box (MBB) scale size for each scale level, the hierarchical spatial encode structure mapping a geometry MBB of a current context object to one or more of the scale levels.

4 . The hierarchical spatial encode structure of claim 1 , wherein one or more encode expressions on each scale level correspond to a GeoEncode table stored in a No-SQL database.

5 . A system comprising:
at least one processor; at least one data repository operatively associated with the at least one processor and configured to store a hierarchical spatial encode structure, the hierarchical spatial encode structure comprising a plurality of scale levels each having a plurality of encode expressions for a multi-scale context; memory storing instructions that, when executed by the at least one processor, configure the at least one processor to:
receive context data and to identify a scale level of the context data;
translate the received context data into the hierarchical spatial encode structure based at least in part on the identified scale level;
receive a query for one or more contexts of the hierarchical spatial encode structure, the query including a spatial scale input as a condition;
compare the spatial scale input to a scale level of the one or more contexts of the hierarchical spatial encode structure;
determine based on the comparison whether the spatial scale input is greater than, equal to, or less than the scale level for the one or more contexts;
if the spatial scale input is determined to be greater than the scale level for the one or more contexts, scale down the length of an encode expression for the one or more contexts to match the spatial scale input and submit a row key based query to the hierarchical spatial encode structure based at least in part on the scaled down length of the encode expression;
if the spatial scale input is less than the scale level for the one or more contexts, scale up the length of the encode expression for the one or more contexts to match the spatial scale input and submit a row key based query to the hierarchical spatial encode structure based at least in part on the scaled up length of the encode expression;
if the spatial scale input is the same as the scale level for the one or more contexts, submit a row key based query to the hierarchical spatial encode structure based at least in part on the length of the encode expression; and
return, based on the submitted row key based query, one or more contexts that match the query.

6 . The system of claim 5 , wherein the encode expressions of the hierarchical spatial encode structure are configured in a left-to-right format to support a left fuzzy range query of a No-SQL database.

7 . The system of claim 5 , wherein the translation of the received context data into the hierarchical spatial encode structure based at least in part on the identified scale level comprises translating two dimensional spatial contain/nest (contained) relations of the context into one-dimensional unified pre-encode expressions to support row key range queries in a No-SQL database.

8 . The system of claim 5 , wherein the one or more contexts that match the query are further filtered based on a resolution of the one or more contexts.

9 . The system of claim 5 , wherein the encode expressions on a first of the scale levels of the hierarchical spatial encode structure comprise a first length, the encode expressions on a second of the scale levels of the hierarchical spatial encode structure comprise a second length greater than the first length, and each encode expression of the second of the scale levels comprises one or more of the encode expressions of the first of the scale levels.

10 . The system of claim 5 , wherein the hierarchical spatial encode structure comprises a plurality of geoencode tables, each geoencode table corresponding to one or more of the encode expressions on a scale level and comprising context data at the scale level of the respective encode expression.

11 . The system of claim 10 , wherein the row key based query is a range scan of the geoencode tables in No-SQL.

12 . The system of claim 5 , wherein a geometry of each context comprises at least one of a polygon, a point[Grid] and a LineString.

13 . A method performed by at least one hardware processor comprising:
receiving a query for one or more contexts of a hierarchical spatial encode structure, the query comprising a spatial scale input as a condition, the hierarchical spatial encode structure comprising a plurality of scale levels each having a plurality of encode expressions for a multi-scale context; comparing the spatial scale input to a scale level of the one or more contexts of the hierarchical spatial encode structure; based on the comparison, at least one of scaling down the length of an encode expression for the one or more contexts, scaling up the length of an encode expression for the one or more contexts, or leaving the length of an encode expression for the one or more contexts unchanged, wherein the length of the encode expression is scaled down when the spatial scale input is greater than the scale level of the one or more contexts, the length of the encode expression is scaled up when the spatial scale input is less than the scale level for the one or more contexts, and the length of the encode expression is left unchanged when the spatial scale input is the same as the scale level for the one or more contexts; submitting a row key based query to the hierarchical spatial encode structure based at least in part on the scaled up, scaled down, or unchanged length of the encode expression; receiving from the hierarchical spatial encode structure one or more contexts that match the row key based query.

14 . The method of claim 13 , wherein the encode expressions of the hierarchical spatial encode structure are configured in a left-to-right format to support a left fuzzy range query of a No-SQL database.

15 . The method of claim 13 , further comprising translating two dimensional spatial contain/nest (contained) relations of the context into one-dimensional unified pre-encode expressions to support row key range queries in a No-SQL database and storing the one-dimensional unified pre-encode expression in the hierarchical spatial encode structure.

16 . The method of claim 13 , wherein the one or more contexts received from the hierarchical spatial encode structure that match the row key based query are further filtered based on a resolution of the one or more contexts.

17 . The method of claim 13 , wherein the encode expressions on a first of t

Assignees

• IBM

Inventors

• Duan Ning
• Huang Yu
• Wang zhi hu
• Zhang Xin
• Zhu Jun

Classifications

• G06F16/29 Primary

  Geographical information databases · CPC title

• G06F16/2282

  Tablespace storage structures; Management thereof · CPC title

• G06F17/30427

  Physics · mapped topic

• G06F17/30241

  Physics · mapped topic

• G06F17/30867

  Physics · mapped topic