Browse Prior Art Database

A method of reducing memory reqirements for multiway search trees.

IP.com Disclosure Number: IPCOM000014243D
Original Publication Date: 2001-Jan-01
Included in the Prior Art Database: 2003-Jun-19

Publishing Venue

IBM

Abstract

1. Problem solved by this method Multiway tree or trie searching is a method of speeding up searches compared to searching on binary trees or tries since a larger part of the search key is used at each step. It has been used successfully for both direct matching and for longest prefix matching At each stage of such a search the base address of a linear subtable of places in the data base is located using a pointer obtained from the previous stage. A portion of the search key is then used to index into this subtable to obtain the data therein. If there is an entry in the database matching the search key up to and including this stage, then the location will contain a pointer to the base address of a new subtable for the next stage of the search. Otherwise there may be no entry in the database matching the search key up to and including the current stage. In this case the located entry in the subtable will contain a null indicator or be "empty" and the search can be stopped. The method of searching can be very fast since large portions of the search key can be tested at each stage; fewer stages are therefore needed. The disadvantage is that the larger the portion of the search key which is tested at each stage, the larger are the subtables into which this key-portion indexes. For sparsely populated portions of the tree many or most of the entries in a subtable could be empty leading to a large amount of unused memory. In densely populated areas of the database, there will be little wasted storage. In very sparsely populated areas where at most 1 or 2 entries per subtable are occupied there also exists economical storage mechanisms . The proposed method aims to significantly reduce storage requirements for subtables in which perhaps about 10% to 50% of the entries are occupied. To make a complete searching scheme, the proposed method would be combined with these other two techniques in order to have efficient memory utilisation over a greater range of database characteristics.