Column store optimization using simplex store

Patent metadata

Field	Value
Publication number	US-9507815-B2
Application number	US-201414325259-A
Country	US
Kind code	B2
Filing date	Jul 7, 2014
Priority date	Jul 7, 2014
Publication date	Nov 29, 2016
Grant date	Nov 29, 2016

Abstract

Using index clusters to approximate coordinate values for vertices of compressed simplexes of a spatial data set, valid subspaces can be identified and used to identify other simplexes that may intersect a first simplex. Such approaches can be used for filtering, refining, etc. analysis of intersections between areas, lines, volumes, etc. within spatial data sets.

First claim

What is claimed is:

1. A computer program product comprising a non-transitory machine-readable medium storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:
defining an index cluster for a coordinate value of a vertex of a first simplex, the first simplex comprising a plurality of vertices and forming at least part of a shape within a coordinate system, a plurality of index vectors defining the first simplex, each index vector of the plurality of index vectors identifying one coordinate value within a dimensional dictionary for a dimension within the coordinate system for each vertex of the plurality of vertices, the index cluster comprising an interval within the dimensional dictionary for the coordinate value;
scanning other index vectors for the interval, the other index vectors identifying value-IDs for other coordinate values for other vertices of other simplexes in a data set, the other index vectors being different from the plurality of index vectors defining the first simplex;
identifying, based on the scanning, a subset of the other simplexes that possibly intersect the first simplex, the identifying comprising designating another simplex as a member of the subset when a comparison of the index cluster with the other index vector for the coordinate value for the other simplex returns a true value; and
promoting the subset.

2. The computer program product of claim 1 , wherein the promoting comprises presenting the subset to a user and/or utilizing the subset as a filter result.

3. The computer program product of claim 1 , wherein the promoting comprises utilizing the subset as a filter result, the utilizing comprising:
defining a new index cluster for the coordinate value of the vertex of the first simplex, the new index cluster comprising a new interval within a reduced dimensional dictionary for the coordinate value, the reduced dimensional dictionary representing only the possibly intersecting other simplexes in the subset;
re-scanning the other index vectors of the possibly intersecting other simplexes in the subset for the new interval; and
re-identifying, based on the re-scanning, a reduced subset of the possibly intersecting other simplexes in the subset, the re-identifying comprising designating a new other simplex member of the reduced subset when a comparison of the new index cluster with the other index vector for the coordinate value for the new other simplex returns a true value.

4. The computer program product of claim 1 , wherein the operations further comprise performing a spatial column join using the subset and then performing a more expensive database operation on a result of the spatial column join.

5. The computer program product of claim 1 , wherein the other simplex of the other index vector is designated as not intersecting the first simplex when the comparison of the index cluster with the other index vector for the coordinate values for the simplexes returns a false value.

6. A system comprising:
computer hardware configured to perform operations comprising:
defining an index cluster for a coordinate value of a vertex of a first simplex, the first simplex comprising a plurality of vertices and forming at least part of a shape within a coordinate system, a plurality of index vectors defining the first simplex, each index vector of the plurality of index vectors identifying one coordinate value within a dimensional dictionary for a dimension within the coordinate system for each vertex of the plurality of vertices, the index cluster comprising an interval within the dimensional dictionary for the coordinate value;
scanning other index vectors for the interval, the other index vectors identifying value-IDs for other coordinate values for other vertices of other simplexes in a data set, the other index vectors being different from the plurality of index vectors defining the first simplex;
identifying, based on the scanning, a subset of the other simplexes that possibly intersect the first simplex, the identifying comprising designating another simplex as a member of the subset when a comparison of the index cluster with the other index vector for the coordinate value for the other simplex returns a true value; and
promoting the subset.

7. The system of claim 6 , wherein the promoting comprises presenting the subset to a user and/or utilizing the subset as a filter result.

8. The system of claim 6 , wherein the promoting comprises utilizing the subset as a filter result, the utilizing comprising:
defining a new index cluster for the coordinate value of the vertex of the first simplex, the new index cluster comprising a new interval within a reduced dimensional dictionary for the coordinate value, the reduced dimensional dictionary representing only the possibly intersecting other simplexes in the subset;
re-scanning the other index vectors of the possibly intersecting other simplexes in the subset for the new interval; and
re-identifying, based on the re-scanning, a reduced subset of the possibly intersecting other simplexes in the subset, the re-identifying comprising designating a new other simplex member of the reduced subset when a comparison of the new index cluster with the other index vector for the coordinate value for the new other simplex returns a true value.

9. The system of claim 6 , wherein the operations further comprise performing a spatial column join using the subset and then performing a more expensive database operation on a result of the spatial column join.

10. The system of claim 6 , wherein the other simplex of the other index vector is designated as not intersecting the first simplex when the comparison of the index cluster with the other index vector for the coordinate values for the simplexes returns a false value.

11. The system of claim 6 , wherein the computer hardware comprises:
a programmable processor; and
a machine-readable medium comprising instructions that, when executed by the programmable processor, cause the programmable processor to perform at least some of the operations.

12. A computer-implemented method comprising:
defining an index cluster for a coordinate value of a vertex of a first simplex, the first simplex comprising a plurality of vertices and forming at least part of a shape within a coordinate system, a plurality of index vectors defining the first simplex, each index vector of the plurality of index vectors identifying one coordinate value within a dimensional dictionary for a dimension within the coordinate system for each vertex of the plurality of vertices, the index cluster comprising an interval within the dimensional dictionary for the coordinate value;
scanning other index vectors for the interval, the other index vectors identifying value-IDs for other coordinate values for other vertices of other simplexes in a data set, the other index vectors being different from the plurality of index vectors defining the first simplex;
identifying, based on the scanning, a subset of the other simplexes that possibly intersect the first simplex, the identifying comprising designating another simplex as a member of the subset when a comparison of the index cluster with the other index vector for the coordinate value for the other simplex returns a true value; and
promoting the subset.

13. The computer-implemented method of claim 12 , wherein the promoting comprises presenting the subset to a user and/or utilizing the subset as a filter result.

14. The computer-implemented method of claim 12 , wherein the promoting comprises utilizing the sub

Assignees

• Tyercha Edward-Robert
• Gildhoff Hinnerk
• Volker Lars
• Grouisborn Tim
• Kazmaier Gerrit Simon
• Sap Se

Inventors

• Tyercha Edward-Robert
• Gildhoff Hinnerk
• Volker Lars
• Grouisborn Tim
• Kazmaier Gerrit Simon

Classifications

• G06F16/2264 Primary

  Multidimensional index structures · CPC title

• G06F16/2365

  Ensuring data consistency and integrity · CPC title

• G06F17/30333 Primary

  Physics · mapped topic

• G06F17/30371

  Physics · mapped topic