Optimal coding method for efficient matching of hierarchical categories in publish-subscribe systems

• US 10,158,738 B2
• Filed: 12/22/2014
• Issued: 12/18/2018
• Est. Priority Date: 12/22/2014
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Xu, Bo, Stroila, Matei Nicolae
• Primary Examiner(s): Srivastava, Vivek
• Assistant Examiner(s): Khan, Atta
• Application Number:
  US14/579,017
• Publication Number:
  US 20160182669A1
• Time in Patent Office: 1,457 Days
• Field of Search: 709203
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services
• CPC Class Codes: H04L 67/55 Push-based network services
• CPC Class Codes: H04L 67/5651 Reducing the amount or size of exchanged application data

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.

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.

2. The method according to claim 1, wherein the determining the first level shortest code length of a category is taking into account the second category.

3. The method according to claim 2, wherein a number of categories that are subcategories of the first category is known priori by the network device.

4. The method according to claim 2, wherein the determining comprises identifying code bits of a code length of at least one of the first category and the one or more second categories that are not necessary for prefix matching and removing the bits from the code length.

5. The method according to claim 4, wherein the determining comprises applying a minimum code assignment for category hierarchy algorithm first to bits of the second category and then the first category to determine a shortest code length of the category tree, the shortest code length of the category tree being at least the sum of the first level shortest code length and the second level shortest code length.

6. The method according to claim 5, wherein the determining takes as input a list (DDL(x₁), DDL(x₂), . . . , DDL(x_n)), wherein x₁, x₂, . . . , x_n are the one or more second categories of the first category, and wherein DDL(x) indicates how many bits are needed to code all the second categories.

7. The method according to claim 6, comprising:

determining a number of the second categories;

for a case where the number of second categories equals 1 then let code (x₁)=0,

else for a case where the number of second categories is greater than 1 then compute a value l for each of the second categories, where l is an integer.

8. The method according to claim 7, where computing the value l for each of the second categories comprises computing:

For each 1≤

i≤

n, let

l_i=┌

log₂(Σ

_j=1ⁿ2^mj)┐

−

m_i

9. The method according to claim 7, comprising:

picking a biggest value l_k of the values l₁,l₂, . . . l_n

reducing the value l_k by 1;

determining for the value l_k if inequality is violated (i.e., if Σ

_i=1ⁿ(½

)^li>

1), wherein for a case the inequality is violated then increase l_k by 1, else compute a value l for l_k.

10. The method according to claim 9, comprising using binary tree pruning to assign codewords code (x_i) such that length(code x_i))=l_i.

11. The method according to claim 1, comprising sending, by the network device, a message comprising the assigned prefix code to the publish-subscribe system to subscribe to the at least one category of the publish-subscribe system.

12. The method according to claim 1, wherein the network device comprises one of a user equipment and a base station.

13. The method according to claim 1 performed with at least one non-transitory memory embodying computer program code, the computer program code executed by at least one processor.

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.

15. The apparatus according to claim 14, wherein the determining the first level shortest code length of a category is taking into account the second category.

16. The apparatus according to claim 15, wherein a number of categories that are subcategories of the first category is known priori by the apparatus.

17. The apparatus according to claim 15, wherein the determining comprises identifying code bits of a code length of at least one of the first category and the one or more second categories that are not necessary for prefix matching and removing the bits from the code length.

18. The apparatus according to claim 17, wherein the determining comprises applying a minimum code assignment for category hierarchy algorithm first to bits of the second category and then the first category to determine a shortest code length of the category tree, the shortest code length of the category tree being at least the sum of the first level shortest code length and the second level shortest code length.

19. The apparatus according to claim 18, wherein the determining takes as input a list (DDL(x₁), DDL(x₂), . . . , DDL(x_n)), wherein x₁, x₂, . . . , x_n are the one or more second categories of the first category, and wherein DDL(x) indicates how many bits are needed to code all the second categories.

20. The apparatus according to claim 19, wherein the at least one memory including the computer program code is configured with the at least one processor to cause the apparatus to:

determine a number of the second categories;

for a case where the number of second categories equals 1 then let code (x₁)=0,

else for a case where the number of second categories is greater than 1 then compute a value l for each of the second categories, where l is an integer.

21. The apparatus according to claim 20, where computing the value l for each of the second categories comprises computing:

For each 1≤

i≤

n, let

l_i=┌

log₂(Σ

_j=1ⁿ2^mj)┐

−

m_i

22. The apparatus according to claim 20, wherein the at least one memory including the computer program code is configured with the at least one processor to cause the apparatus to:

pick a biggest value l_k of the values l₁, l₂, . . . l_n

reduce the value l_k by 1;

determine for the value l_k if inequality is violated (i.e., if Σ

_i=1ⁿ(½

)^li>

1), wherein for a case the inequality is violated then increase l_k by 1, else compute a value l for l_k.

23. The apparatus according to claim 22, wherein the at least one memory including the computer program code is configured with the at least one processor to cause the apparatus to:

use binary tree pruning to assign codewords code (x_i) such that length(code(x_i))=l_i.

24. The apparatus according to claim 14, wherein the at least one memory including the computer program code is configured with the at least one processor to cause the apparatus to send a message comprising the assigned prefix code to the publish-subscribe system to subscribe to the at least one category of the publish-subscribe system.

25. The apparatus according to claim 14, wherein the apparatus comprises one of a user equipment and a base station.