Digit tree optimized in memory consuption
Original Publication Date: 2001-Apr-01
Included in the Prior Art Database: 2003-Jul-23
A database with up to one million entries to support number portability by EWSD public switch accessed by call processing with a digit string as accessing key needs to be optimized between memory size limitations and realtime requirements. Such a database is mostly designed as a digit tree taking only the performance requirements into account. The memory waste mainly depends on the correlation factor of the numers entered into the database. Low correlation leads into a high branching factor at the low digit tree levels resulting in lots of database elements allocated. The inventive solution to optimize the digit tree is the so called enhanced digit tree (Figure). In the classic digit tree each node consumes a fixed amount of memory independent of the used branches. For more efficiency in memory use each database element can be a normal digit tree element (maxi block) or an enhanced digit tree element, that may contain four nodes (mini block) of the digit tree. The use of an enhanced element depends on the decrease of the branch factor under a specified value. The number of digits in a mini block can not be higher than this value. The evaluated digit is stored in the mini block itself. During the digit translation it is no longer used as offset (as in the maxi block) but has to be compared with the available mini block digits which takes processing time.