Coordinate compression: preserve order with dense integer ranks

Last updated: 5 Oct 20269 min read

tutorial

Coordinate compression replaces each distinct key in a known finite catalog with its position in sorted key order. It does not shrink a numeric value or preserve the distance between values; it preserves equality and relative order. A key-to-rank map supports exact lookup, and a sorted key array reverses a rank and finds the first known key at or above an arbitrary threshold. The source batch may contain duplicates, yet the catalog contains each distinct key once. Later algorithms can place counts or sums in a compact array indexed by rank. This version is static: adding a previously unknown key requires rebuilding the sorted catalog and any dependent index.

Operational case

Shipment weights arrive as 4700, -35, 4700, 82000, and 19. The known keys become -35, 19, 4700, 82000; 4700 maps to rank two in zero-based order and rank three maps back to 82000. A lower-bound lookup for 20 gives rank two, the first known key no smaller than 20. The two shipments weighing 4700 still occupy two records even though the catalog gives them the same rank. A consumer that uses rank differences as weight differences would make a serious mistake: the gap between 19 and 4700 is 4681, while their rank gap is one.

Working Python program

from bisect import bisect_left


class CoordinateRankCatalog:
    def __init__(self, shipment_weights):
        self.keys = sorted(set(shipment_weights))
        self.rank_by_weight = {weight: rank for rank, weight in enumerate(self.keys)}

    def rank(self, weight):
        return self.rank_by_weight[weight]

    def weight(self, rank):
        return self.keys[rank]

    def lower_bound(self, weight):
        return bisect_left(self.keys, weight)


if __name__ == "__main__":
    catalog = CoordinateRankCatalog([4700, -35, 4700, 82000, 19])
    print("keys=", catalog.keys, sep="")
    print("rank-4700=", catalog.rank(4700), sep="")
    print("first-at-least-20=", catalog.lower_bound(20), sep="")
    print("weight-at-rank-3=", catalog.weight(3), sep="")

Output

keys=[-35, 19, 4700, 82000]
rank-4700=2
first-at-least-20=2
weight-at-rank-3=82000

Time, space, and tradeoff

For N input values and U distinct keys, sorting the unique catalog costs O(N + U log U) expected time under ordinary hash-set assumptions, plus O(U) catalog storage. Building the dictionary costs O(U) expected time. Exact rank lookup is O(1) expected hash time, reverse lookup is O(1), and lower-bound lookup is O(log U). Comparisons of large or composite keys also have their own cost. If hash behavior is adversarial, dictionary and set bounds can degrade. Coordinate ranking does not solve a query alone; it supplies compact ordered positions to a frequency tree or another structure. Rebuilding after unknown keys arrive can change every later rank.

Common Mistakes

Do not mistake a dense rank for the original measurement or distance.
Do not discard duplicate source records merely because catalog keys are unique.
Do not assume an unseen key already has an exact rank.
Do not update a dependent rank index without rebuilding when the catalog changes.

Connected lessons

Compare with Fenwick frequency index: select the kth stored key, Mo ordering: count distinct scan codes across an offline query batch, Two-dimensional prefixes: constant-time static rectangle sums, then run the query workload audit and contract quiz.

Piecewise interpolation indexes: predict a bounded rank window adds a distinct structure contract to compare.

data structures

range-query-structures