Patent ID: 8429108

Claim:
A fast computer-implemented method for computing compact numerical (Omicron,Iota) isomorphism certificates for one or more poset-representable digital data objects D.sub. 1 , . . . D.sub.n with inherent poset structures P.sub. 1 , . . . P.sub.n, providing means for certifying isomorphism between two poset structures, if their corresponding (Omicron,Iota) certificates match, thus enabling structure-based access to complex and large data sets, as well as comparison, sorting and clustering thereof to be performed by efficient numerical operations on said certificates derived from and representing the data objects contained in these data sets, comprising successively for j=1, . . . n, the steps of: loading a poset-representable digital data object D.sub.j and extracting the inherent poset structure P.sub.j; computing the isomorphism certificate (Omicron(P.sub.j),Iota(P.sub.j)) for the poset P.sub.j; storing the isomorphism certificate (Omicron(P.sub.j),Iota(P.sub.j)) in a storage medium, wherein a poset-representable data object D.sub.j can be construed as being composed of a set of components c.sub. 1 , . . . c.sub.m which are represented as the vertices of the poset, and a partial order relation defined on the set of components which expresses relevant features of the data object D.sub.j, and further wherein for each poset P.sub.j: (Omicron(P.sub.j),Iota(P.sub.j)) a pair of number sequences is designated whose total length is proportional to the number of edges in P.sub.j, and the code Iota(P.sub.j) is a concatenation of r sorted sequences Iota(P,c.sub. 1 ), . . . , Iota(P,c.sub.r), where c.sub. 1 , . . . , c.sub.r are r cut vertices of P.sub.j which have at least two immediate predecessors, and wherein, for each cut vertex c.sub.k, each incoming edge is associated with a position weight, the length of Iota(P.sub.j,c.sub.k) is given by the number of incoming edges, and each element in Iota(P.sub.j,c.sub.k) is a position weight, and the code Omicron(P.sub.j) for a poset P represents for each non-cut vertex the number of outgoing edges and Iota position weights for outgoing edges to cut vertices and wherein said position weights particularly quantify the subposets in which the edges occur and numerical relationships among cut vertices, and wherein said position weights are associated with integers representing distances, and further wherein the (Omicron(P.sub.j),Iota(P.sub.j)) certificate canonically represents a set of poset-representable digital data objects in the plurality D.sub. 1 , . . . D.sub.n which have poset structures isomorphic to P.sub.j.