In previous sections (, ) we discussed globals as trees, in this one we will consider globals as sparse arrays.
is a type of array where most values take the same value.
In practice, there are often such large sparse arrays that it makes no sense to occupy memory with identical elements. Therefore, it is reasonable to implement sparse arrays in a way that memory is not wasted on storing identical values.
In some programming languages, sparse arrays are built into the language, , . In other programming languages, there are special libraries that allow their implementation. For C++ — and others.
Globals are good candidates for implementing sparse arrays because:
- They store values only for certain nodes and do not store values for undefined ones;
- The access interface to a node's value is very similar to how access to an element of a multidimensional array is implemented in many programming languages.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - A global is a sufficiently low-level structure for storing data, therefore it has outstanding performance characteristics (from hundreds of thousands to tens of millions of transactions per second depending on the hardware, see )
Since the global is a persistent structure, implementing sparse arrays on it makes sense when it is known in advance that the amount of RAM will be insufficient.
One of the properties of sparse array implementations is returning some default value if an access is made to an undefined cell.
This can be implemented using the function in COS. In this example, a 3-dimensional array is considered.
SET a = $GET(^a(x,y,z), defValue)In what tasks are sparse arrays required and how can globals help?
Adjacency matrix
are used to represent graphs:
It is obvious that the larger the graph, the more zeros will be in the matrix. For example, if we take a social network graph and represent it in such a matrix, it will consist almost entirely of zeros, i.e., it will be a sparse array.
Set ^m(id1, id2) = 1
Set ^m(id1, id3) = 1
Set ^m(id1, id4) = 1
Set ^m(id1) = 3
Set ^m(id2, id4) = 1
Set ^m(id2, id5) = 1
Set ^m(id2) = 2
....
In this example, we save in the global ^m the connectivity matrix, as well as the number of edges for each node (who is friends with whom and the number of friends).
If the number of elements in the graph is no more than 29 million (this number is taken as the product of 8 * ), there is an even more economical way to store such matrices — bit-strings, as their implementation optimizes large gaps in a special way.
Manipulations with bit-strings are performed by the function .
; set bit
SET $BIT(rowID, positionID) = 1
; get bit
Write $BIT(rowID, positionID)
Finite automaton transition table
Since the transition graph of a finite automaton is an ordinary graph, the finite automaton transition table is the same adjacency matrix mentioned above.
Cellular automata
The most famous cellular automaton is , which, due to its rules (when a cell has many neighbors, it dies), represents a sparse array.
Stephen Wolfram believes that cellular automata are a In 2002, he published a 1280-page book 'A New Kind of Science', where he extensively argues that advances in cellular automata are not isolated, but rather robust and significant for all fields of science.
It has been proven that any algorithm that can be executed on a computer can be implemented through a cellular automaton. Cellular automata are used to model dynamic environments and systems, to solve algorithmic problems, and for other purposes.
If we have a huge field and we need to record all intermediate states of the cellular automaton, it makes sense to use globals.
Cartography
The first thing that comes to mind when it comes to using sparse arrays is mapping tasks.
Typically, there is a lot of empty space on maps. If a map is represented as large pixels, then 71% of Earth's pixels will be occupied by the ocean. A sparse array. And if only human-made structures are plotted, then more than 95% will be empty space.
Of course, no one stores maps as raster arrays; vector representation is used.
But what do vector maps represent? They are essentially a framework consisting of points, polylines, and polygons.
In fact, a database of points and the connections between them.
One of the most ambitious mapping tasks is the mission to map our galaxy using the Gaia telescope. Metaphorically speaking, our galaxy, like the entire universe, is a continuous sparse array: vast spaces of emptiness where there are only rare small points—stars. Empty space accounts for 99.999999…….%. A database on globals—Caché—was chosen to store a map of our galaxy.
I don't know the exact structure of the globals in this project, but I can assume that it looks something like:
Set ^galaxy(b, l, d) = 1; Star number by catalog, if available
Set ^galaxy(b, l, d, "name") = "Sun"
Set ^galaxy(b, l, d, "type") = "normal"; variants include blackhole, quasar, red_dwarf, etc.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Mercury"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...
Where b, l, d are and distance to the Sun.
The flexible structure of globals allows for preserving any necessary characteristics of stars and planets, as databases based on globals are scheme-less.
Caché was chosen to store the map of our universe not only for its flexibility but also for its ability to save data streams very quickly while simultaneously creating global indices for fast searches.
Returning to Earth, mapping projects were created on globals and a fork of OpenStreetMap— .
Recently, at the geospatial indexes . We await details of the implementation from the authors of the article.
The implementation of spatial indexes on globals in OpenStreetMap XAPI
The images are taken from .
The entire Earth is divided into squares, then into sub-squares, and subsequently into sub-sub-squares, and so forth. In general, we obtain a hierarchical structure for which globals were created.
At any moment, we can almost instantly request the required square or clear it, while all sub-squares will also be returned or cleared.
A similar scheme on globals can be implemented in several ways.
Variant 1:
Set ^m(a, b, a, c, d, a, b, c, d, a, b, a, c, d, a, b, c, d, a, 1) = idFirstPoint
Set ^m(a, b, a, c, d, a, b, c, d, a, b, a, c, d, a, b, c, d, a, 2) = idSecondPoint
...Variant 2:
Set ^m('abacdabcdabacdabcda', 1) = idFirstPoint
Set ^m('abacdabcdabacdabcda', 2) = idSecondPoint
...In both cases, it is easy to request points located within a square of any level on COS/M. It will be slightly easier to clear square pieces of space at any level in the first variant, but this is rarely necessary.
Example of one of the lower-level squares:
Here are several globals from the XAPI project: index representation on globals:
Global ^way is used to store points (roads, small rivers, etc.) and polygons (closed areas: buildings, forests, etc.).
Rough classification of sparse array usage on globals.
- We store the coordinates of certain objects and their states (mapping, cellular automata)
- We store sparse matrices.
In case 2), when querying a specific coordinate where the element is not assigned a value, we must obtain the default value of the sparse array element.
The benefits we gain from storing multidimensional matrices in globals
Fast deletion and/or sampling of pieces of space that are multiples of rows, planes, cubes, etc. In cases where integer indices are used, the ability for quick deletion and/or sampling of pieces of space that are multiples of rows, planes, cubes, etc., may prove useful.
The command we can delete either a single element, a row, or even an entire plane. Thanks to the properties of globals, this happens very quickly—thousands of times faster than element-by-element deletion.
The figure shows a three-dimensional array in the global ^a and different types of deletions.
To sample pieces of space by known indices, you can use the command .
Sampling a column of the matrix into the variable Column:
; Let's define a three-dimensional sparse array 3x3x3
Set ^a(0,0,0)=1,^a(2,2,0)=1,^a(2,0,1)=1,^a(0,2,1)=1,^a(2,2,2)=1,^a(2,1,2)=1
Merge Column = ^a(2,2)
; Let’s output the variable Column
Zwrite Column
Output:
Column(0)=1
Column(2)=1
Interestingly, the variable Column also turned into a sparse array, which must also be accessed through , as default values are not stored in it.
Sampling pieces of space can also be done through a small program using the function . This is especially convenient in spaces where the indices are non-quantized (mapping).
Conclusion
Current times present new ambitious challenges. Graphs can consist of billions of vertices, maps can include billions of points, and someone might even want to launch their own universe using cellular automata (, ).
When the volume of data in sparse arrays can no longer fit into RAM, but work with it is essential, it’s worth considering implementing such projects on Globals and COS.
Thank you for your attention! We look forward to your questions and wishes in the comments.
Disclaimer: This article and my comments on it reflect my opinion and do not represent the official position of InterSystems.
Source: habr.com
