0
$\begingroup$

Hierarchical identifiers, labels and indexes... All can use digits as character-strings, differenciating $0$ and $00$, $1$ and $001$, but preserving all other numeric interpretations, like order ($002>001$) and freedom for represantation (some other radix).

To illustrate, suppose a typical labeling system: Geohashes are positive integer numbers with a representation where the number of digits make difference. For example the Geohash 01 is a cell identifier of a geographic location little below Ross Sea with ~115000 km², and 0001 a cell far below, with 3.5 km².

Question: what the name of this class of numeric representation where number of digits (including leading zeros) make diference?

How about sized integers, good name? There are some "official Mathematic naming rules", when a official name not exists for a mathematical structure?


NOTE

I am looking for the Mathematical name... but, if there are no one, we can use other sources.

There are in Computing the name "Fixed-width integers" (FWInt) to say for example "fixed-width integers of 64 bits", where "x bits" is the name of a subclass. So, as I show in the examples below, we need a name for the union of many subclasses of FWInt (e.g. union of FWInt of 1 bit, FWInt of 2 bits, FWInt of 3 bits... and FWInt of 8 bits).

Integers and its representations (encodings) are used extensively in Computing. The usual foundation to implent long-size integers is the arbitrary-precision integers (e.g. BigInt is a primitive Javascript datatype). So, a datatype that is an integer with controled size can be named sized BigInt.


Intuitive definitions and examples

It is a finite set (or must be a sequence?) of numeric representations... Limiting examples in 8 bits:

  • Example with binary representations: $X_1 = \{0, 1\}$   $X_2 = \{0, 00, 01, 1, 10, 11\}$   ...   $X_k$   ...   $X_8 = \{0,00,000,000, \ldots, 00000000, 00000001, \ldots, 11111111\}$

  • The same set $X_8$ without some (non-compatible) items, in radix 4 representation: $Y_8 = \{0, 00, 000, 0000, 0001, 0002, 0003, 001, 0010, 0011 \ldots, 3333\}$

Ordering the illustred elements... Well, order is arbitrary for a set, here is only to enhance "same prefix" grouping (the hierarchy) in the sequence, that is important in applications:

(size,value)   Binary representation    Radix4 representation
(1,0)          0
(2,0)          00                       0
(3,0)          000
(4,0)          0000                     00
(5,0)          00000
(6,0)          000000                   000
(7,0)          0000000
(8,0)          00000000                 0000
(8,1)          00000001                 0001
(7,1)          0000001
(8,2)          00000010                 0002
(8,3)          00000011                 0003
(6,1)          000001                   001
(7,2)          0000010
(8,4)          00000100                 0010
(8,5)          00000101                 0011
...            ...                      ...

To sort a group, less digits first. When the number of digits are equal, use the natural number order. Same is valid for some other radix. Identifiers of the cells of Geohash global grid, for example, use the radix 32 as its "standard representation".

Spatial indexes based on Hilbert curve indexes adopt radix4 to express the spatial hierarchy (recurrent split into four regions) into the radix4 digits. The cell numbering system of S2 Geometry, and many others, use it.

Trying a formal definition

Each example is a set, $X_k$, so we can suppose that we need the name of a class of sets in $k$. The table illustrated also that the elements of $X_k$ of this (named) class of sets are ordered pairs $(l,n)$ of length $l$ and numeric value $n$.

Lets check some properties:

  • Each element of this set can be mapped into a size (bits or number of digits) and a Natural number (value).   PS: the preferred term for "size of the string" is length (or bit-length).

  • The maximum bit-length of an element of $X_k$ is a finite k. In other words, using the range set $L_k=\{1, 2, \ldots, k\}$, we can say that all element of $X_k$ has a bit-length $l \in L_k$, and there are elements for each $l$.

  • The bit-length of a Natural number $n>0$ is a function $bitLength(n)=\lceil log_2(n)+1 \rceil$. The bit-length of zero is one.

Putting all together, the set $X_k$ is a class in a finite $k$:

$$X_k = \{\forall x = (l,n) ~|~ l,n \in \mathbb{N} ~\land~ bitLength(n) \le l \le k \}$$

There is also a function $toString(l,n)$ that uniquely converts the pair $(l,n)$ into a bit string of the binary representation of n, and fills the leading zeros to the length l.

Two elements $x$ and $y$ are the same when $toString(x)=toString(y)$ or when $l$ and $n$ are equal: $$x=y ~ \iff ~ l_x=l_y \land n_x=n_y$$

And, similarly, the element $x$ is greater than $y$ by a criterion based on $l$ and $n$... But it is free, we not need to impose order, there are no special compare-criterion. No criterion is valid.


I can't say the name this kind of set, but now (edited) we have a better definition of the object, $X_L$, that need a name.

$\endgroup$
2
$\begingroup$

The Wikipedia article on Geohash states it is a system which

... encodes a geographic location into a short string of letters and digits.

However, this encoded string is decoded into a string of "0" and "1" bits. This represents a heirarchy using the "0" and "1" digits and thus is best described as a Binary tree where the "0" and "1" correspond to left and right subtrees. For more details consult the Wikipedia article.

To be more precise, every node in a rooted binary tree is uniquely described by the path of left and right branching choices from the root to that node. The sequence of "left" and "right" choices can be uniquely encoded into a string of "0" and "1" characters. This is not best described as a "number", although there is an ordering of the nodes using Depth-first search, for example, but other orderings are possible.

To be more clear, the set of $\{0,1\}$ strings comes equipped with a string length and, for a fixed length $\,n,\,$ the $\{0,1\}$ strings of length $\,n\,$ can be totally lexographically ordered. But more importantly, two strings of any lengths have a partial ordering where one is a prefix substring of the other. This gives rise to a topology on the set of strings. A neigborhood is all the strings that share a common prefix.

In the case of arbitrary length strings, this is related to a $p$-adic number interpretation where $p=2$ and is very similar to the construction of the Cantor set also. In both of these spaces, the topology is totally disconnected.

$\endgroup$
  • $\begingroup$ Thanks @Somos, I edited with more examples. Hilbert curve indexes also use it and can use radix4 to map the spatial hierarchy (each cell) into the sequence of digits. The binary tree is a Graph, but I imagining a (named) less complex structure that is only it: Natural sequences grouped (and ordered) by size. $\endgroup$ – Peter Krauss Feb 17 at 18:30
  • $\begingroup$ Sorry, edited again to ehance the point "it is a set" (not a Graph or other complex structure)... Well seems a set. So I need a name of a class of sets... The P-adic number have the constraint of prime numbers, my examples and now the formal definition have no constraint, only the length (in bits or digits) of the number. Also Cantor-set, have a specific semanic (based on its geometrical representation) as name, and the geometric progression as constraint in its numeric representation. $\endgroup$ – Peter Krauss Feb 17 at 19:56
  • $\begingroup$ Well, it is not bad, but for $(l,n)$ the $n$ is misleading. Any countable set of objects, by definition, can be put in 1-to-1 correspondence with a positive integer. The mapping is highly not unique. You need the string of "0" and "1" instead, or equivalently a binary tree as in the Wikipedia article. Potentially a complete binary tree. $\endgroup$ – Somos Feb 17 at 20:53
  • $\begingroup$ Hi, sorry for my English and difficulty understanding your conclusions. Now maybe I'm understanding better... I have removed the order from definition (criterion about $x>y$) to generalize, and because there are two usual criteria, the lexicographic (shown in the table) and the numeric($x>y ~ \iff ~ l_x > l_y ~ \lor ~ (l_x=l_y \land n_x > n_y)$). But it seems that, what you say, is that the complete binary tree is a good model to describe the case of the lexicographic order ... Is it? $\endgroup$ – Peter Krauss Feb 18 at 22:22
  • $\begingroup$ Yes, read the Wikipedia article "Lexicographical order" about the "Cantor space". Also Wikipedia article "Binary tree" for "full binary tree". $\endgroup$ – Somos Feb 18 at 23:49
2
$\begingroup$

I would call a geohash an encoding. It is meant to represent numeric data, but none of the numbers occurs in the geohash in any of its usual forms (such as a consecutive sequence of binary digits).

The form of the encoding is a finite, non-empty string or "word" composed of symbols from an alphabet of $22$ symbols. The set of all possible geohash encodings is a regular language. If we set $$\Sigma = \{0,1,2,3,4,5,6,7,8,9,b,c,d,e,f,g,h,j,k,m,n,p,q,r,s,t,u,v,w,x,y,z\}$$ then $\Sigma$ is the alphabet of the geohash language and the language can be written as a regular expression, $\Sigma\Sigma^*.$

The encoding has some features in common with the practice of representing a number between $0$ and $1$ using a finite number of digits to the right of a decimal point, with a precision implied by the number of digits written. For example, in the binary radix, $0.01$ would represent the number $\frac14$ with a precision $\pm\frac18,$ whereas $0.0100$ would represent the number $\frac14$ with a precision $\pm\frac{1}{32}.$ In geohashes as well, more symbols represents a finer precision, but there are two numbers involved (latitude and longitude), and while you add more digits to improve precision of a binary fraction without changing the nominal value, adding more digits to a geohash inevitably changes the centers of the ranges of possible values for latitude and longitude. The increased precision you get by adding symbols to a geohash is like the effect you would get if binary fractions such as $0.01$ were regarded as truncated to some number of bits rather than rounded, and of course the geohash add precision in two dimensions simultaneously instead of one.

But those are all just details of the encoding. The encoded sequence of symbols is still a word of a regular language.


If you must think of the geohash as a single numeral (rather than as an encoding of several numbers), I think it is better to think of it as a radix-$32$ fractional number between $0$ and $1.$ In the same way that the digits in a decimal number such as $0.9543$ divide the interval $[0,1)$ into ten equal-sized pieces, then divide each of those pieces into ten equal-sized pieces, and so forth, the digits of a geohash divide the entire surface of the earth into $32$ pieces (not equal in area, but with equal ranges of latitude and longitude), then divide each of those pieces into $32$ pieces, and so forth.

There is still the question of what to call any of these numbers. Some people would call the hexadecimal number $0.0\mathrm f0\mathrm f0\mathrm f$ a "decimal fraction in base sixteen," which is a little bit strange because the word decimal means "base ten." A better generic term might be radix fraction.


It seems to me that the attempt to interpret a geohash as an integer is pretty much meaningless, except in the sense that any encoding of any information in a string of symbols can be interpreted as an integer, especially when it is stored in a computer. In fact the entire text of the question, if it is stored in a single contiguous block of bytes on a server somewhere, could be interpreted as a single very large integer. If we further specify "an integer of $n$ bits" then we are describing a very specific encoding (there's that word again!) of an integer in a particular binary format.

A BigInt in computing is also an encoding, not a number, especially if the implementation allows for leading zeros. If we applied semantics like the semantics of BigInt to geohashes, $00000000$ would be equal to $0.$ The only difference is that $00000000$ takes more space in memory.

The other thing about writing integers in radix representation is that the rightmost digit of the representation always has the same significance. But in the geohashes $01$ and $0001,$ the rightmost symbol of $0001$ has much less significance than the rightmost symbol of $01.$ On the other hand, like radix representations of both integers and the interval $[0,1),$ the leftmost symbol of a geohash is always the most significant symbol in the representation.


The recent edits to the question, however, have rendered it incoherent and self-contradictory. The "numeric order" you ask for is not possible. What you have shown in the table is lexicographic order, in which there are (in theory) infinitely many strings between $00000000$ and $00000001.$ The only way to limit the number of "in-between" strings to a finite number is to set a fixed maximum allowed length of the string, which I suspect does not agree with the definition of a geohash and I am almost sure does not agree with the definition of Hilbert curves. As for "any radix," that's a bit awkward for Hilbert strings, whereas a geohash in a radix that is not a power of two would pose some real difficulties trying to figure out what it meant, and even a geohash in a radix that is a different power of two could describe regions on the earth that never occur in the radix-$32$ geohash (and vice versa).

$\endgroup$
  • $\begingroup$ Hi David, thanks (!). Yes, encode is a good name for a big and generic class, and my $X_L$ is into it... But encode samantic lost the "number semantic", that I whant to preserve and I imagine that is now better expressed in the question. Radix and alphabet are free choices, even in Geohash the cell identifier is a "sized Natural number", no mater if using base32 or other radix. See the link of S2 geometry withe cell ID in other system, where the focus is not the encode (public view) but the value of the ID. $\endgroup$ – Peter Krauss Feb 18 at 0:24
  • $\begingroup$ Perhaps a descriptive title, *natural numbers with controled size for encoding use". $\endgroup$ – Peter Krauss Feb 18 at 1:19
  • $\begingroup$ The problem is that encodings such as geohashes and Hilbert curves do not have the "number semantics" you're looking for, especially integer semantics. I'm going to say "encoding" is still the best word because that is how people use it. I have tried to explain this a little further by extending the answer. $\endgroup$ – David K Feb 18 at 2:05
  • $\begingroup$ Thanks again. I will correct the order description (the formal comparison criteria is correct) and the use of the term "any radix" (a hierarchy in radix 4 like Hilbert curve is compatible only with radix 8, 16 or 64). About Geohashes and S2, they are only examples, but as you is deepening the subject, it is worth commenting: Goehash use the interval bisections to represent hierarchical cells structure, but it is not a fraction, it is a kind of an integer counter of cells – the LatLong information is interleaving bit by bit. $\endgroup$ – Peter Krauss Feb 18 at 8:55
  • $\begingroup$ ... (continuing) Idem S2 index of Hilbert Curves, it is an integer counter of cells. S2 cell identifier (S2cellID) is a 64-bit integer numbering system that, after 3 bits for cube-face representation, is a radix4 number that "implicitly encodes both the position of a cell and its subdivision level" as expressed in the link, or in this other illustration. So, returning to the focus of the question, even these complex-semantic examples, they are expressed as integer counters (a very special encoding). $\endgroup$ – Peter Krauss Feb 18 at 9:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.