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
Document File: 3 page(s) / 31K

Publishing Venue

IBM

Abstract

1. Problem solved by this method

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 1 of 3

A method of reducing memory reqirements for multiway search trees.

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 <REF1> and for longest
prefix matching <REF2> 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 <REF2>. 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.

2. Proposed method

The proposed method replaces the sparsely populated subtable with
a dense subtable containing only occupied entries, and a
subsidiary lookup table (SLUT). The key-portion, which previously
indexed into the subtable directly, now indexes into the SLUT The
start of the SLUT is addressed by the pointer obtained by the
previous search stage. The value returned by the SLUT is the

1

Page 2 of 3

index into the dense subtable if there is a match for this key
portion, or null if there is no match. The following example
illustrates how memory is economized.

In most practical cases a subtable entry will correspond to the
word size of the machine, e.g. 32 bits.

Supposing the...