Method for ordering subscriber records of wireless communication networks

• US 6,224,477 B1
• Filed: 12/28/1998
• Issued: 05/01/2001
• Est. Priority Date: 12/28/1998
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Xu, Jim, Liu, Julie Y. C., Ho, Joseph S. M.
• Primary Examiner(s): Trost, William G.
• Assistant Examiner(s): Tran, Congvan
• Application Number:
  US09/221,357
• Time in Patent Office: 855 Days
• Field of Search: 455/433, 455/416, 455/422, 455/414, 455/435, 455/332, 455/418, 455/424, 455/560, 707/3, 707/10
• US Class Current: 455/433
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]
• CPC Class Codes: H04W 8/06 Registration at serving network Location Register, VLR or user mobility server
• CPC Class Codes: H04W 8/18 Processing of user or subscriber data, e.g. subscribed services, user preferences or user profiles; Transfer of user or subscriber data

Abstract

A method for ordering subscriber records in a location database stored in at least one of a Visitor Location Register (VLR) or a Home Location Register (HLR) of a wireless communications network by ordering the subscriber records in subsets according to the access rates of the records. Records within the respective subsets are then ordered in a middle-rootage order based on the subscriber ID of each subscriber record. The subscriber records are then inserted into a binary tree in subset order beginning with the subset containing subscriber records having the highest access rate. This method enables subscriber records to be more economically stored and used than is possible using conventional binary trees and, thereby, increases network capacity.

Claims

1. A method for ordering subscriber records in a location database stored in at least one of a Visitor Location Register (VLR) or a Home Location Register (HLR) of a communications network, the method comprising, for each location database:

a) partitioning the subscriber records into subsets according to the access rate of each respective record, wherein each respective subset contains all subscriber records having a particular access rate associated with the respective subset; and

b) inserting the subscriber records of each subset into a binary tree in subset sequence according to the access rate associated with each respective subset, beginning with the subset containing subscriber records having the highest access rate, and finishing with the subset containing subscriber records having the lowest access rate and, within each respective subset, the subscriber records according to a middle-rootage order based on an identification number associated with each respective subscriber record, beginning with a median subscriber record.

2. The method of claim 1 wherein the step of inserting the subscriber records of each subset into a binary tree further comprises:

defining a variable n as a positive integer;

generate an optimal binary tree using the subscriber records of the n subsets containing subscriber records having the highest access rate, based on an identification number and access rate associated with each respective subscriber record; and

inserting into the binary tree the subscriber records of each subset, having an access rate less than the n subsets containing subscriber records having the highest access rate, in subset sequence according to the access rate associated with each respective subset, beginning with the subset containing subscriber records having the highest access rate, and finishing with the subset containing subscriber records having the lowest access rate and, within each respective subset, the subscriber records according to a middle-rootage order based on an identification number associated with each respective subscriber record, beginning with a median subscriber record.

3. The method of claim 2 wherein n is computed to ensure that at least a predetermined minimum number of records are used to form a root of the binary tree.

4. The method of claim 1 wherein the binary tree is a high-frequency rootage (“

HFR”

) tree.

5. The method of claim 1 further comprising:

storing for each subscriber record in the location database an access counter defining a numerical value;

incrementing by one the numerical value of the access counter associated with a respective subscriber record each time the respective subscriber record is accessed during a predetermined period of time; and

equating the access rate of each respective subscriber record to the numerical value of the access counter associated with each respective subscriber record.

6. The method of claim 1 wherein the step of inserting the subscriber records of each respective subset according to a middle-rootage order further comprises, for each respective subset:

a) defining a generation X counter, where X is a variable;

b) identifying a median subscriber record in the respective subset wherein the difference between the number of subscriber records in the respective subset having a subscriber identity number which is numerically less than the subscriber identity number of the median subscriber record, and the number of subscriber records having a subscriber identity number which is numerically greater than the subscriber identity number of the median subscriber record, is not greater than one record;

c) transferring the median subscriber record from the respective subset to the binary tree so that the binary search property of the binary tree is preserved;

d) partitioning the respective subset into a generation X lower subset of ordered subscriber records and a generation X upper subset of ordered subscriber records;

e) identifying the median subscriber record in each generation X lower subset and in each generation X upper subset, and transferring the identified median subscriber records to the binary tree so that the binary search property of the binary tree is preserved;

f) determining whether all subscriber records have been transferred to the binary tree;

g) upon a determination that all subscriber records have not been transferred to the binary tree, partitioning each generation X lower subset and each generation X upper subset into a generation (X+1) lower subset of ordered subscriber records and a generation (X+1) upper subset of ordered subscriber records; and

h) incrementing X by 1 and returning to the step of identifying the median subscriber record in each generation X lower subset and in each generation X upper subset.

7. The method of claim 1 wherein the VLR is collocated with a Mobile Switching Center (MSC).

8. The method of claim 1 wherein the VLR is collocated with a Mobile Switching Center (MSC) of a communications network.

9. The method of claim 1 further comprising the step performed prior to the step of partitioning:

a) using in-order traversal to order the subscriber records in a binary tree into a linear array in ascending order of the subscriber ID of each respective record; and

b) sorting the subscriber records according to the access rate of each respective record using a method that preserves the order of the respective subscriber records with the same access rate.

10. The method of claim 1 further comprising the step performed prior to the step of partitioning:

a) using in-order traversal to order the subscriber records in a binary tree into a linear array in ascending order of the subscriber ID of each respective record; and

b) sorting the subscriber records according to the access rate of the respective record using one of a radix-sort method or a counting-sort method.

11. A method for ordering subscriber records stored in a location database stored in at least one of a Visitor Location Register (VLR) or a Home Location Register (HLR) of a telecommunications network, the method comprising, for each location database:

a) apportioning the subscriber records into at least a first subset of subscriber records and at least a second subset of subscriber records, wherein each of the records contained in the first subset of subscriber records has an access rate exceeding the access rate of each of the records of the second subset;

b) generating a balanced binary tree from subscriber records contained in the first subset of subscriber records;

c) ordering the subscriber records in the second subset of subscriber records in a middle-rootage order; and

d) inserting the subscriber records ordered in the middle-rootage order into the balanced binary tree for retrieval through a subsequent binary search.

12. The method of claim 11 wherein the balanced binary tree is a high-frequency rootage (“

HFR”

) tree.

13. The method of claim 11 further comprising:

storing for each subscriber record in the location database an access counter defining a numerical value;

incrementing by one the numerical value of the access counter associated with a respective subscriber record each time the respective subscriber record is accessed during a predetermined period of time; and

equating the access rate of each respective subscriber record to the numerical value of the access counter associated with each respective subscriber record.

14. The method of claim 11 wherein the step of generating a balanced binary tree using subscriber records contained in the first subset of subscriber records further comprises:

a) ordering the subscriber records in the first subset of subscriber records in a middle-rootage order; and

b) inserting the subscriber records of the first subset of subscriber records ordered in a middle-rootage order into the balanced binary tree for retrieval through a subsequent binary search.

15. The method of claim 11 wherein the step of generating a balanced binary tree using subscriber records contained in the first subset of subscriber records further comprises:

a) defining a generation X counter, where X is a variable;

b) identifying a median subscriber record in the first subset wherein the difference between the number of subscriber records in the first subset having a subscriber identity number which is numerically less than the subscriber identity number of the median subscriber record, and the number of subscriber records having a subscriber identity number which is numerically greater than the subscriber identity number of the median subscriber record, is not greater than one record;

c) transferring the median subscriber record from the first subset to the binary tree so that the binary search property of the binary tree is preserved;

d) partitioning the first subset into a generation X lower subset of ordered subscriber records and a generation X upper subset of ordered subscriber records;

e) identifying the median subscriber record in each generation X lower subset and in each generation X upper subset, and transferring the identified median subscriber records to the binary tree so that the binary search property of the binary tree is preserved;

f) determining whether all subscriber records contained by the first subset have been transferred to the binary tree;

g) upon a determination that all subscriber records contained by the first subset have not been transferred to the binary tree, partitioning each generation X lower subset and each generation X upper subset into a generation (X+1) lower subset of ordered subscriber records and a generation (X+1) upper subset of ordered subscriber records; and

h) incrementing X by 1 and returning to the step of identifying the median subscriber record in each generation X lower subset and in each generation X upper subset.

16. The method of claim 11 wherein a subscriber identity number is uniquely associated with each subscriber record, and the steps of ordering and inserting further comprise:

a) defining a generation X counter, where X is a variable;

b) identifying a median subscriber record in the second subset wherein the difference between the number of subscriber records in the second subset having a subscriber identity number which is numerically less than the subscriber identity number of the median subscriber record, and the number of subscriber records having a subscriber identity number which is numerically greater than the subscriber identity number of the median subscriber record, is not greater than one record;

c) transferring the median subscriber record from the second subset to the binary tree so that the binary search property of the binary tree is preserved;

d) partitioning the second subset into a generation X lower subset of ordered subscriber records and a generation X upper subset of ordered subscriber records;

e) identifying the median subscriber record in each generation X lower subset and in each generation X upper subset, and transferring the identified median subscriber records to the binary tree so that the binary search property of the binary tree is preserved;

f) determining whether all subscriber records contained by the second subset have been transferred to the binary tree;

g) upon a determination that all subscriber records contained by the second subset have not been transferred to the binary tree, partitioning each generation X lower subset and each generation X upper subset into a generation (X+1) lower subset of ordered subscriber records and a generation (X+1) upper subset of ordered subscriber records; and

h) incrementing X by 1 and returning to the step of identifying the median subscriber record in each generation X lower subset and in each generation X upper subset.

17. The method of claim 11 wherein the VLR is collocated with a Mobile Switching Center (MSC).

18. The method of claim 11 wherein the VLR is collocated with a Mobile Switching Center (MSC) of a telecommunications network.

19. The method of claim 11 further comprising the step performed prior to the step of apportioning:

a) using in-order traversal to order the subscriber records in a binary tree into a linear array in ascending order of the subscriber ID of each record; and

b) sorting the subscriber records according to the access rate of the respective record using a sorting method that preserves the order of the subscriber records with the same access rate.

20. The method of claim 11 further comprising the step performed prior to the step of apportioning:

a) using in-order traversal to order the subscriber records in a binary tree into a linear array in ascending order of the subscriber ID of each record; and

b) sorting the subscriber records according to the access rate of the respective record using one of a radix-sort method or a counting-sort method.

21. A method for ordering subscriber records in a location database stored in at least one of a Visitor Location Register (VLR) or a Home Location Register (HLR) of a wireless communications network, the method comprising, for each location database:

a) partitioning the subscriber records into subsets according to the access rate of each respective record, wherein each respective subset contains all subscriber records having a particular access rate associated with the respective subset; and

b) defining a variable n as a positive integer;

c) inserting into an optimal binary tree the subscriber records of the n subsets containing subscriber records having the highest access rate, based on an identification number and the access rate associated with each respective subscriber record; and

d) inserting into the binary tree the subscriber records of each subset, having an access rate less than the n subsets containing subscriber records having the highest access rate, in subset sequence according to the access rate associated with each respective subset, beginning with the subset containing subscriber records having the highest access rate, and finishing with the subset containing subscriber records having the lowest access rate and, within each respective subset, the subscriber records according to a middle-rootage order based on an identification number associated with each respective subscriber record, beginning with a median subscriber record.

22. The method of claim 21 wherein n is computed to ensure that at least a predetermined minimum number of records are used to form a root of the binary tree.

23. The method of claim 21 wherein the binary tree is a high-frequency rootage (“

HFR”

) tree.

24. The method of claim 21 further comprising:

storing for each subscriber record in the location database an access counter defining a numerical value;

incrementing by one the numerical value of the access counter associated with a respective subscriber record each time the respective subscriber record is accessed during a predetermined period of time; and

equating the access rate of each respective subscriber record to the numerical value of the access counter associated with each respective subscriber record.

25. The method of claim 21 wherein the step of inserting the subscriber records of each respective subset according to a middle-rootage order further comprises, for each respective subset:

a) defining a generation X counter, where X is a variable;

b) identifying a median subscriber record in the respective subset wherein the difference between the number of subscriber records in the respective subset having a subscriber identity number which is numerically less than the subscriber identity number of the median subscriber record, and the number of subscriber records having a subscriber identity number which is numerically greater than the subscriber identity number of the median subscriber record, is not greater than one record;

c) transferring the median subscriber record from the respective subset to the binary tree so that the binary search property of the binary tree is preserved;

d) partitioning the respective subset into a generation X lower subset of ordered subscriber records and a generation X upper subset of ordered subscriber records;

e) identifying the median subscriber record in each generation X lower subset and in each generation X upper subset, and transferring the identified median subscriber records to the binary tree so that the binary search property of the binary tree is preserved;

f) determining whether all subscriber records have been transferred to the binary tree;

g) upon a determination that all subscriber records have not been transferred to the binary tree, partitioning each generation X lower subset and each generation X upper subset into a generation (X+1) lower subset of ordered subscriber records and a generation (X+1) upper subset of ordered subscriber records; and

h) incrementing X by 1 and returning to the step of identifying the median subscriber record in each generation X lower subset and in each generation X upper subset.

26. The method of claim 21 wherein the VLR is collocated with a Mobile Switching Center (MSC).

27. The method of claim 21 wherein the VLR is collocated with a Mobile Switching Center (MSC) of a communications network.

28. The method of claim 21 further comprising the step performed prior to the step of partitioning:

a) using in-order traversal to order the subscriber records in a binary tree into a linear array in ascending order of the subscriber ID of each respective record; and

b) sorting the subscriber records according to the access rate of each respective record using a method that preserves the order of the respective subscriber records with the same access rate.

29. The method of claim 21 further comprising the step performed prior to the step of partitioning:

a) using in-order traversal to order the subscriber records in a binary tree into a linear array in ascending order of the subscriber ID of each respective record; and

b) sorting the subscriber records according to the access rate of the respective record using one of a radix-sort method or a counting-sort method.