FAST COMPUTATION OF COMPACT POSET ISOMORPHISM CERTIFICATES

• US 20090216820A1
• Filed: 05/11/2007
• Published: 08/27/2009
• Est. Priority Date: 05/11/2006
• Status: Active Grant

• Current Assignee: Geistiges Eigentum Incorporated
• Original Assignee: Geistiges Eigentum Incorporated
• Inventors: Eusterbrock, Jutta
• Granted Patent: US 8,429,108 B2
• Time in Patent Office: Days
• US Class Current: 708/270
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544

Abstract

Two methods and systems for fast construction of poset isomorphism certificates are provided. Posets (partially-ordered sets) generalize graphs. The invented certificates are number sequences such that two posets are isomorphic if and only if their corresponding certificates coincide. The first method yields the (Omicron,Iota) poset isomorphism certificate. The minimal Phi-isomorphism certificate can be constructed by partitioning vertices of the graphs into Phi-ranked symmetry clusters and constructing a topological Phi-vertex ranking. Thus, symmetries in posets are detectable at low cost. In addition, the Phi-vertex ranking and a poset isomorphism certificate provide a pair of separate one-dimensional keys for poset encoding. Data objects representable as posets, which are commonly used in automated design, safety and security applications, biocomputing, management of semi-structured data, and other fields, can be stored, analyzed, indexed, and accessed using the isomorphism certificates requiring much less storage and computation time.

Claims

1-29. -29. (canceled)

30. A method for determining (Omicron,Iota) certificates for a first poset representable digital data object D₁ and a second poset representable digital data object D₂ using a computer system and assessing isomporphism, comprising the steps of:

converting the first digital data objects D₁ into a corresponding first poset P₁, and the second digital data object D₂ into a corresponding second poset P₂;

loading the first poset P₁ and the second poset P₂;

calculating isomorphism certificates Omicron-Iota(P₁) and Omicron-Iota(P₂) for the first poset P₁ and the second poset P₂, wherein the (Omicron,Iota) certificates are characterized such that determining if (Omicron(P₁),Iota(P₁)) for the first poset P₁ is equal to (Omicron(P₂),Iota(P₂)) for the second poset P₂ certifies that P₁ and P₂ are isomorphic, and further determining if (Omicron(P₁),Iota(P₁)) for the first poset P₁ is not equal to (Omicron(P₂),Iota(P₂)) for the second poset P₂, thus certifies that P₁ and P₂ are non-isomorphic, wherein for each poset P₁ and P₂ (Omicron(P),Iota(P)), are designated number sequences,

wherein for a given poset P with n vertices, the code Iota(P) is a sorted sequence of r sorted sequences Iota(P,c₁), . . . , Iota(P,c_r), where c₁, . . . , c_r refer to r cut vertices of P which have at least two immediate predecessors, and wherein, for each cut vertex, the length of Iota(P,c_k) is given by the number of immediate predecessors of c_k, and element in Iota(P,c_k) is a designated position weight, and the code Omicron(P) for a poset P encodes for each non-cut vertex the number of outgoing edges and Iota position weights.

31. The method of claim 30, wherein the first poset and the second poset individually represents one type of digital data object selected from the following types of digital data objects:

CAD model, image, vector based graphics, 3D model, the topology of a distributed multi media application;

a taxonomy, financial network, RDF document, XML document, HTML coded Web page, binary decision diagram, a linguistic expression, a logical sentence, a Boolean truth table, circuit diagram, scanned document, compiler, computer program, binary executable, VLSI layout graph, 2D chemical structure diagram, 3D chemical structure diagram, RNA sequence, DNA sequence, genetic maps, multiple sequence alignments, biopathway, stoichiometric structure of reaction system, Gene Ontology digraph, hydrocarbons, drug components, fingerprint graph, handwritten graphical symbol, communication networks, transportation network, electrical circuit, power grid, computer network, social network, the World Wide Web graph, and intranets.

32. The method of claim 30, wherein constructing an Omicron-Iota isomorphism certificate for said poset P comprises:

repeatedly Phi-poset-partitioning the poset P into a top maximal multiset forest MF and a remaining poset P′

, wherein the top maximal multiset forest MF is configured such that only designated cut vertices have multiple occurrences;

determining an (Omicron,Iota) code for the top maximal multiset forest MF and the Iota weights for the cut vertices occurring in top maximal multiset forest MF;

recursively determining a weighted (Omicron,Iota) code for the remaining poset P′

taking the previously computed Iota weights as inputs; and

concatenating the (Omicron,Iota) codes for the top maximal multiset forest MF and the (Omicron,Iota) code for the remaining poset P′

to yield an overall (Omicron,Iota) code for the poset P;

wherein constructing for the top maximal multiset forest MF, the corresponding weighted (Omicron,Iota) certificate comprises;

recursively decomposing the top maximal multiset forest MF into bipartite posets;

determining the (Omicron,Iota) codes for the bipartite posets and arranging the bipartite posets to yield the (Omicron,Iota) code for the top maximal multiset forest MF;

wherein constructing for each bipartite poset, the corresponding (Omicron,Iota) certificate comprises;

firstly recursively arranging the lower vertices into groups and assigning each groups a rank such that there is a designated group of vertices having minimal rank, any vertex of minimal rank v is characterized in that its indegree is maximal and the sorted sequence of the number of predecessors shared with each of its neighbors is maximal;

for any member of a group the sorted sequence of ranks of neighbors is identical, and for any pair of vertices v₁, v₂, if the distance of v₁ to an element of minimal rank is less than the distance of an element v₂ to an element of minimal rank, than the rank of v₁ is less than the rank of v₂, and furthermore the rank is determined by the number of common predecessors for any pair of vertices;

secondly arranging and ranking the upper vertices according to their degree, the ranks of their successors and the number of common vertices with neighbors.

33. The method of claim 30 further comprising:

comparing a plurality of digital data objects D₁, . . . , D_n by using the Omicron-Iota(Pj), j=1, . . . , n, codes of the corresponding posets P₁, . . . , P_n;

arranging D₁, . . . , D_n into sorted clusters such that;

(i) for any pair of objects D′

,D″

in the same cluster the associated Omicron-Iota codes are identical, whereby identity of (Omicron(P′

),Iota(P′

)) and (Omicron(P″

),Iota(P″

)) for a pair of posets P′

,P″

taken from the set P₁, . . . , P_n, certifies that P′

is isomorphic to P″

, and non-identity certifies that the pair P′

,P″

is non-isomorphic, and (ii) the clusters are sorted according to the ordering induced by the codes (Omicron(P),Iota(P)).

42. A device for constructing (Omicron,Iota) certificates of a set of poset representable data objects, comprising means for executing the method of claim 30, which receives a set of said digital data objects and generates the corresponding posets P for the given digital data object;

an (Omicron,Iota) Encoding Unit; and

an output device from which the result can be accessed, either for further automatic processing or for presentation to a human user.

43. The device of claim 42, further comprising an apparatus for comparing and clustering digital poset representable data objects;

the device consisting of;

means for receiving a set of said data objects and generating the corresponding set of posets P1, . . . Pn for the given set of data objects and calculating said (Omicron,Iota) certificates from the posets P1, . . . , Pn according to claim 42;

means for implementing a comparison between the posets based on their (Omicron,Iota) certificates;

a clustering unit generating sets of posets sharing identical certificates and arranges them; and

an output device from which the result can be accessed, either for further automatic processing or for presentation to a human user.

34. A method for detecting symmetric vertices of poset representable digital data objects on a computer system, comprising the steps of:

converting a digital data object D into a poset P;

loading the poset P of the digital data object;

calculating the isomorphism certificate (Omicron(P),Iota(P));

assigning to each poset vertex v of P its Phi-symmetry rank Phi-sym(v) such that symmetric vertices have identical Phi-symmetry rankings, the Phi-symmetry ranks for pairs of non-symmetric vertices differ, and the Phi-symmetry-ranking results in a strict linear order for the Phi-symmetry ranks of the vertices;

wherein for a given poset P with n vertices, the code Iota(P) is a sorted sequence of r sorted sequences Iota(P,c₁), . . . , Iota(P,c_r), where c₁, . . . , c_r refer to r cut vertices of P which have at least two immediate predecessors, and wherein, for each cut vertex, the length of Iota(P,c_k) is given by the number of immediate predecessors of c_k, and each element in Iota(P,c_k) is a designated position weight, and the code Omicron(P) for a poset P encodes for each non-cut vertex the number of outgoing edges and Iota position weights.

35. The method of claim 34, wherein the poset represents one type of object selected from the following types of objects used in the various fields of computation:

CAD model, image, vector based graphics, 3D model, the topology of a distributed multi media application;

a taxonomy, financial network, RDF document, XML document, HTML coded Web page, binary decision diagram, a linguistic expression, a logical sentence, a Boolean truth table, circuit diagram, scanned document, compiler, computer program, binary executable, VLSI layout graph, 2D chemical structure diagram, 3D chemical structure diagram, RNA sequence, DNA sequence, genetic maps, multiple sequence alignments, biopathway, stoichiometric structure of reaction system, Gene Ontology digraph, hydrocarbons, drug components, fingerprint graph, handwritten graphical symbol, communication networks, transportation network, electrical circuit, power grid, computer network, social network, the World Wide Web graph, intranets.

36. The method of claim 34, wherein constructing an Omicron-Iota isomorphism certificate for said poset P comprises:

repeatedly Phi-poset-partitioning the poset P into a top maximal multiset forest MF and a remaining poset, wherein the top maximal multiset forest MF is configured such that only designated cut vertices have multiple occurrences;

determining an (Omicron,Iota) code for the top maximal multiset forest MF and the Iota weights for the cut vertices occurring in maximal multiset forest MF;

recursively determining a weighted (Omicron,Iota) code for the remaining poset taking the previously computed Iota weights as inputs; and

concatenating the (Omicron,Iota) codes for the top maximal multiset forest MF and the remaining poset to yield an overall (Omicron,Iota) code for the poset P;

wherein constructing for the top maximal multiset forest, the corresponding (Omicron,Iota) certificate comprises;

recursively decomposing the top maximal multiset forest into bipartite posets;

determining the (Omicron,Iota) codes for the bipartite posets and arranging the bipartite posets to yield the (Omicron,Iota) code for the top maximal multiset forest,

wherein the step of assigning each vertex its Phi-symmetry rank comprises;

assigning a minimum Phi-symmetry weight to a poset root;

arranging the poset into layers such that vertices assigned to a given layer have identical minimum distance to the root;

sorting the layers such that the vertices on a preceding layer have a smaller minimum distance to the root than vertices on a succeeding layer;

successively assigning for each layer all vertices belonging to a layer Phi-symmetry weights, wherein assigning starts with the root and proceeds through the layers from a top layer to a bottom layer; and

assigning each vertex a particular Phi-symmetry ranking starting with the vertices having maximal distance to the root;

wherein the vertices are assigned Phi-symmetry weights in such a way that the symmetry weights at a preceding layer are less than the weights at a succeeding layer; and

wherein for each layer the Phi-symmetry weight of a first vertex is less than the Phi-symmetry weight of a second vertex if the sorted Phi-symmetry weights of the predecessors of the first vertex lexicographically precede the sorted Phi-symmetry weights of the predecessors of the second vertex; and

further wherein the Phi-symmetry weight of the first vertex is identical to the Phi-symmetry weight of the second vertex if the sorted Phi-symmetry weights of the predecessors of the first vertex are identical to the sorted Phi-symmetry weights of the predecessors of the second vertex; and

further wherein the Phi-symmetry weight of a first cut vertex is less than or identical to the Phi-symmetry weight of a second cut vertex if the Iota code of the first vertex is less than or identical to the Iota code of the second vertex; and

further wherein the Phi-symmetry weight of the first cut vertex is less than the Phi-symmetry weight of the second non-cut vertex if and only if there exists a predecessor of the first vertex such that its Phi-symmetry weight is less than the Phi-symmetry weight of the predecessor of the second vertex;

wherein the vertices are assigned Phi-symmetry rankings in such a way that the Phi-symmetry rankings at a preceding layer are less than the Phi-symmetry rankings at a succeeding layer; and

wherein for each layer the Phi-symmetry ranking of a first vertex is less than the Phi-symmetry ranking of a second vertex if the sorted Phi-symmetry rankings of the successors of the first vertex lexicographically precede the sorted Phi-symmetry rankings of the successors of the second vertex; and

further wherein the Phi-symmetry ranking of the first vertex is identical to the Phi-symmetry ranking of the second vertex if the sorted Phi-symmetry rankings of the successors of the first vertex are identical to the sorted Phi-symmetry rankings of the successors of the second vertex; and

further wherein the Phi-symmetry rankings of vertices without successors coincide with the Phi-symmetry weights of vertices without successors.

37. The method of claim 34 further comprising a method for arranging the elements of a poset representable data object in a strict linear order by constructing for each vertex v of the related poset its topological Phi-alpha-rank Phi-alpha(v);

wherein the construction of the topological Phi-alpha ranks for each vertex of the poset comprises the following steps;

assigning the root the minimum Phi-alpha rank;

arranging the vertices into layers by proceeding from the poset root vertex to the vertices having maximal distance from the root, wherein the poset root determines the minimum layer, on each layer the vertices have the same maximal distance to the root;

the layers are sorted such that the vertices on a preceding layer have a smaller distance to the root than vertices on a succeeding layer;

for each vertex on a preceding layer the Phi-alpha-rank is less than any Phi-alpha-rank for a vertex on a succeeding layer;

on each layer a first vertex precedes a second vertex according to the Phi-alpha-ranking if the Phi-symmetry ranking of the first vertex precedes the Phi-symmetry ranking of the second vertex;

or their Phi-symmetry rankings are identical and the sorted sequence of the Phi-alpha rankings of the successors of the first vertex lexicographically precedes the sorted sequence of the Phi-alpha rankings of the successors of the second vertex;

or their Phi-symmetry ranks are identical, the first and second vertex have no successors and the first vertex is less than the second vertex by an arbitrary provided alpha order on the vertex set.

38. The method of claim 37, further comprising a method for constructing a Phi-poset isomorphism certificate for a poset representable data object D, whereby the corresponding poset P is converted into the Phi-code Phi(P), including the steps of:

successively mapping all relations (x,y) of the poset P into pairs (Phi-alpha(x),Phi-alpha(y));

lexicographically sorting the list of pairs such that the smallest pairs appear first; and

concatenating the sorted list of pairs, wherein for each poset P′

with vertices {1, . . . n} and P′

˜

P;

Phi(P)<

₌P′

resulting in Phi-code Phi(P) being minimal.

39. The method of claim 38, further comprising:

a method for certifying isomorphism or non-isomorphism for a first and second poset representable data object D′

,D″

comprising;

receiving a first and second posets P′

,P″

;

constructing a first and second Phi-isomorphism certificate Phi(P′

),Phi(P″

);

comparing Phi(P′

) and Phi(P″

); and

certifying isomorphism of the pair of posets P′

,P″

when the corresponding pairs of lexicographic isomorphism codes are identical, or certifying non-isomorphism of the pair of posets P′

,P″

when the corresponding pairs of lexicographic isomorphism codes are not identical.

40. The method of claim 39, further comprising:

a method for constructing the canonical Phi-alpha-isomorphism between a pair of posets P′

,P″

, including;

receiving a pair of posets P′

,P″

;

certifying isomorphism of the pair of posets P′

,P″

;

accessing the topological Phi-alpha rankings Phi-alpha(P′

,V′

), Phi-alpha(P″

,V″

);

constructing the Phi-alpha-isomorphism between the pair of posets P′

,P″

by mapping the i-th element of Phi-alpha(P′

,V′

) onto the i-th element of Phi-alpha(P″

,V″

), wherein i passes through 1 to the cardinality of the vertex set.

41. The method of claim 40, further comprising a method for encrypting a poset representable data object D by two separate keys, the Phi-alpha-sort (P) of the vertices of the corresponding poset P, and the poset isomorphism certificate Phi(P).

44. A device for detecting symmetries of poset representable data objects, providing the ability to execute the method of claim 34, comprising:

means for receiving a set of said data objects and generating the corresponding posets P for the given data object;

an (Omicron,Iota) Encoding Unit for constructing said (Omicron,Iota) certificate from the given poset P;

a Phi-symmetry ranking unit for computing the Phi-symmetry ranks of the vertices of the given poset P; and

an output device from which the result can be accessed, either for further automatic processing or for presentation to a human user.

45. The device of claim 44, further comprising means for arranging the elements of a poset representable data object in a strict linear order by constructing for each vertex v of the related poset its topological Phi-alpha-rank Phi-alpha(v).

46. The device of claim 45, further comprising means for constructing for a poset representable data object the Phi-poset isomorphism certificate.

47. The device of claim 46, further comprising means for outputting for a poset representable data object D two separate keys, the Phi-alpha-sort (P) of the vertices of the corresponding poset P, and the poset isomorphism certificate Phi(P).

48. A computerized system for indexing one or a plurality of poset representable data sets, comprising:

a processor; and

a primary storage media containing a code segment for receiving at least one structured or semi-structured object and corresponding information, the objects being capable of being represented by a poset;

a code segment for creating poset data sets from the structured or semi-structured objects and corresponding information;

a code segment for constructing an isomorphism certificate for the created poset data sets;

a code segment for indexing the objects with the said Omicron-Iota isomorphism certificates;

a code segment for arranging the objects according to the lexicographic order induced by the said isomorphism certificate corresponding to each object; and

a code segment for storing the Omicron-Iota indexed objects in a machine readable storage medium.

49. The system of claim 48, further comprising a secondary storage media and a search engine, said search engine having code segments configured for receiving a query expression, wherein the search query expression specifies a desired structured or semi-structured object by structural and content constraints or a query-by-example method, the objects being capable of being represented by a poset;

transforming the query expression into a query poset;

encoding the query poset by an Omicron-Iota isomorphism certificate;

retrieving references to data sets having said isomorphism certificates that partially or completely match the query expression from a plurality of data sets in the secondary storage media;

ranking the retrieved references according to the distance of each retrieved reference to the query expression; and

generating an ordered list of retrieved references to relevant objects that can be retrieved from the primary storage media.