Browse Prior Art Database

Digit tree optimized in memory consuption

IP.com Disclosure Number: IPCOM000017591D
Original Publication Date: 2001-Apr-01
Included in the Prior Art Database: 2003-Jul-23
Document File: 1 page(s) / 17K

Publishing Venue

Siemens

Related People

Tom Grielens: AUTHOR [+2]

Abstract

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.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

-� � 167� � -

Information / Kommunikation

Digit tree optimized in memory consuption

Idee: Tom Grielens, B-Lille; Leen Nelen, B-Halle-Zoersel

A database with up to one million entries to support number portability by EWSD public switchaccessed by call processing with a digit string as accessing key needs to be optimized betweenmemory size limitations and realtime requirements. Such a database is mostly designed as a digittree taking only the performance requirements into account. The memory waste mainly dependson the correlation factor of the numers entered into the database. Low correlation leads into ahigh 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 theclassic digit tree each node consumes a fixed amount of memory independent of the usedbranches. For more efficiency in memory use each database element can be a normal digit treeelement (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 factorunder a specified value. The number of digits in a mini block can not be higher than this value. Theevaluated digit is stored in the mini block itself. During the digit translation it is no longer used asoffset (as in the maxi block) but has to be compared with the available mini block digits whichtakes processing time.

Flexibility was built in the concept in order to allow minimum memory consumption� or maximumperformance. The tree has a classic part and an enhanced part the limits of which are a result ofan optimization between the two targets.

A database with up to one million entries to support number portability by EWSD public switchaccessed by call processing with a digit string as accessing key needs to be optimized betweenmemory size limitations and realtime requirements. Such a database is mostly designed as a d...