Optimal Coding Method for Efficient Matching Of Hierarchical Categories In Publish-Subscribe Systems

• US 20160182669A1
• Filed: 12/22/2014
• Published: 06/23/2016
• 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
• Granted Patent: US 10,158,738 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 comprising:

determining, by a network device, 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

assigning, by the network device, a prefix code of the shortest code length to each of the at least one category of the publish-subscribe system.

2. The method according to claim 1, wherein each category includes at least one subcategory, and wherein the determining the shortest code length of a category is taking into account the at least one subcategory.

3. The method according to claim 2, wherein an amount of the at least one subcategories 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 category and the subcategory 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 subcategory and then the category to determine the shortest code length of the at least one category.

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 children of x, wherein the children comprise subcategories, and wherein DDL(x) indicates how many bits are needed to code all the children of x.

7. The method according to claim 6, comprising:

determining a number of children of x;

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

else for a case where the number of children of x>

1 then compute a value l for each of the children of x, where l is an integer.

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

For each 1≦

i≦

n, let

l_i=┌

log₂(Σ

_i=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;

determine a shortest code length of at least one category of a publish-subscribe system such that a maximum 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.

15. The apparatus according to claim 14, wherein each category includes at least one subcategory, and wherein the determining the shortest code length of a category is taking into account the at least one subcategory.

16. The apparatus according to claim 15, wherein an amount of the at least one subcategories 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 category and the subcategory 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 subcategory and then the category to determine the shortest code length of the at least one category.

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 children of x, wherein the children comprise subcategories, and wherein DDL(x) indicates how many bits are needed to code all the children of x.

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 children of x;

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

else for a case where the number of children of x>

1 then compute a value I for each of the children of x, where l is an integer.

21. The apparatus according to claim 20, where computing the value l for each of the children of x 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ⁿ(½

)ⁱⁱ>

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.