Browse Prior Art Database

Method for Fast Search Operation on Stand-Alone Search Structure

IP.com Disclosure Number: IPCOM000016215D
Original Publication Date: 2002-Aug-11
Included in the Prior Art Database: 2003-Jun-21

Publishing Venue

IBM

Abstract

This proposal involves a technique for improving the search performance of a software-based search engine by minimizing of the number of memory accesses per lookup, while maintaining a stand-alone data structure that contains all the information needed to perform an update operation. The proposal relates specifically to a search engine that is based on the BART (Balanced Routing Table) search algorithm, developed by the same author. The BaRT algorithm is described in detail in [1][2]. The technique will be explained using the example shown in Fig. 1 (which is Fig. 10 in [1] for a description see this paper). The tables at levels 2 and 3 (indexed by search key segments 2 and 3) are compressed tables, containing complete prefix information in the form of test values and test masks. IPv4 destination address