Optimal coding method for efficient matching of hierarchical categories in publish-subscribe systems
First Claim
1. A method for matching publications to subscriptions of a publish-subscribe system using prefix codes having a fewest number of bits for identifying a plurality of categories having a hierarchy and corresponding to the publish-subscribe system while providing for prefix matching at an arbitrary level of the hierarchy, the method comprising:
- receiving, by a network device, a category tree comprising the plurality of categories, each category having a level, wherein the category tree corresponds to the publish-subscribe system having a length requirement of a prefix code system, the length requirement being a number of bits reserved by the publish-subscribe system for an indication of a category;
determining, by the network device, a first level category code length for each first level category of a first level of the category tree such that the length requirement of the prefix code system for the first level is not exceeded based on a number of categories of the plurality of categories that are sub-categories of the first level category, wherein a first first level category and a second first level category have first level category code lengths that are different;
assigning, by the network device, a first prefix code of the corresponding first level category code length to each category of the first level, wherein each subscription of the publish-subscribe system being stored in association with at least one first prefix code, the at least one first prefix code enabling category matching at the first level;
determining, by the network device, for each category of the first level of the category tree, a second level shortest code length for one or more second categories of the plurality of categories that correspond to a second level of the category tree and that are sub-categories of the category of the first level, the second level shortest code length being determined (a) based on a number of the one or more second categories that are sub-categories of the category of the first level and (b) such that the length requirement of the prefix code system for the second categories is not exceeded, wherein a first second level category that is a sub-category of the first first level category and a second second level category that is a sub-category of the second first level category have second level shortest code lengths that are different thereby reducing the number of bits required to provide a prefix code that enables prefix matching at an arbitrary level of the hierarchy;
assigning, by the network device, a second prefix code of the second level shortest code length to each of the second categories; and
matching at least one publication to at least one subscription based on at least one first prefix code and optionally a second prefix code associated with the at least publication and one or more first prefix codes and optionally one or more corresponding second prefix codes associated with the at least one subscription, wherein the at least one publication is provided in accordance with the matched at least one subscription via a transmission having the number of bits corresponding to the length requirement reserved for indication of a category corresponding to the at least one publication and the matched at least one subscription.
2 Assignments
0 Petitions
Accused Products
Abstract
In accordance with the exemplary embodiments of the invention there is at least a method and apparatus to determine a shortest code length of at least one category of a publish-subscribe system such that a length requirement of prefix code system for the at least one category is not exceeded; and assign a prefix code of the shortest code length to each of the at least one category of the publish-subscribe system.
-
Citations
25 Claims
-
1. A method for matching publications to subscriptions of a publish-subscribe system using prefix codes having a fewest number of bits for identifying a plurality of categories having a hierarchy and corresponding to the publish-subscribe system while providing for prefix matching at an arbitrary level of the hierarchy, the method comprising:
-
receiving, by a network device, a category tree comprising the plurality of categories, each category having a level, wherein the category tree corresponds to the publish-subscribe system having a length requirement of a prefix code system, the length requirement being a number of bits reserved by the publish-subscribe system for an indication of a category; determining, by the network device, a first level category code length for each first level category of a first level of the category tree such that the length requirement of the prefix code system for the first level is not exceeded based on a number of categories of the plurality of categories that are sub-categories of the first level category, wherein a first first level category and a second first level category have first level category code lengths that are different; assigning, by the network device, a first prefix code of the corresponding first level category code length to each category of the first level, wherein each subscription of the publish-subscribe system being stored in association with at least one first prefix code, the at least one first prefix code enabling category matching at the first level; determining, by the network device, for each category of the first level of the category tree, a second level shortest code length for one or more second categories of the plurality of categories that correspond to a second level of the category tree and that are sub-categories of the category of the first level, the second level shortest code length being determined (a) based on a number of the one or more second categories that are sub-categories of the category of the first level and (b) such that the length requirement of the prefix code system for the second categories is not exceeded, wherein a first second level category that is a sub-category of the first first level category and a second second level category that is a sub-category of the second first level category have second level shortest code lengths that are different thereby reducing the number of bits required to provide a prefix code that enables prefix matching at an arbitrary level of the hierarchy; assigning, by the network device, a second prefix code of the second level shortest code length to each of the second categories; and matching at least one publication to at least one subscription based on at least one first prefix code and optionally a second prefix code associated with the at least publication and one or more first prefix codes and optionally one or more corresponding second prefix codes associated with the at least one subscription, wherein the at least one publication is provided in accordance with the matched at least one subscription via a transmission having the number of bits corresponding to the length requirement reserved for indication of a category corresponding to the at least one publication and the matched at least one subscription. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. An apparatus comprising:
-
at least one processor; and at least one memory including computer program code, where the at least one memory and the computer program code are configured, with the at least one processor, to cause the apparatus to at least; receive a category tree comprising a plurality of categories, each category having a level, wherein the category tree corresponds to a publish-subscribe system having a length requirement of a prefix code system, the length requirement being a number of bits reserved by the publish-subscribe system for an indication of a category; determine a first level category code length of each first level category of a first level of the category tree such that the length requirement of the prefix code system for the first level is not exceeded based on a number of categories of the plurality of categories that are sub-categories of the first level category, wherein a first first level category and a second first level category have first level category code lengths that are different; assign a first prefix code of the corresponding first level category code length to each category of the first level, wherein each subscription of the publish-subscribe system being stored in association with at least one first prefix code, the at least one first prefix code enabling category matching at the first level; determine for each category of the first level of the category tree, a second level shortest code length for one or more second categories of the plurality of categories that correspond to a second level of the category tree and that are sub-categories of the category of the first level, the second level shortest code length being determined (a) based on a number of the one or more second categories that are sub-categories of the category of the first level and (b) such that the length requirement of the prefix code system for the second categories is not exceeded, wherein a first second level category that is a sub-category of the first first level category and a second second level category that is a sub-category of the second first level category have second level shortest code lengths that are different thereby reducing the number of bits required to provide a prefix code that enables prefix matching at an arbitrary level of the hierarchy; assign a second prefix code of the second level shortest code length to at least the second category; and match at least one publication to at least one subscription based on at least one first prefix code and optionally a second prefix code associated with the at least publication and one or more first prefix codes and optionally one or more corresponding second prefix codes associated with the at least one subscription, wherein the at least one publication is provided in accordance with the matched at least one subscription via a transmission having the number of bits corresponding to the length requirement reserved for indication of a category corresponding to the at least one publication and the matched at least one subscription. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25)
-
Specification