Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Improving performance and storage efficiency by merging parts of multiple search structures.

IP.com Disclosure Number: IPCOM000019204D
Original Publication Date: 2003-Sep-04
Included in the Prior Art Database: 2003-Sep-04
Document File: 5 page(s) / 117K

Publishing Venue

IBM

Abstract

Improving performance and storage efficiency by merging parts of multiple search structures.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 42% of the total text.

Page 1 of 5

  Improving performance and storage efficiency by merging parts of multiple search structures.

  A technique is proposed for optimizing the speed and storage efficiency of a search engine or similar device that performs searches on two or more different search structures.

A common approach to realize fast search operations on a single search structure consists of employing as first level in the search structure a table which is indexed by a relatively large first segment (e.g., 16 bits) of the search key [1]. Such a table will be called a direct table (DT). A second common approach is to process the entire key with a hash function and then use the hash value as an index into the DT. Either use of a DT allows to process in a first step a relatively large part of the search key, thus improving the overall search performance as compared to, for example, pure tree-based search structures, which typically process the entire search key in much smaller granularities
(e.g., 1, 2, or 4 bits). The performance improvement, however, comes at the cost of larger storage requirements: for example, a DT that is indexed by a 16 bit segment, will contain 2^16=64K slots or entries.

This proposal involves a technique for efficiently sharing a single DT among two or more different search structures, thus improving overall storage efficiency. Alternatively, the invention allows to combine the storage dedicated to separate disjoint DTs in order to form a larger single DT, allowing to process a larger first segment of the search keys, thus improving the search speed of all searches involved.

The proposal will be described using a simple example involving two different longest-matching prefix searches using a 32-bit search key. The two searches involve the following prefixes (in hexadecimal) and corresponding search results:

search 1: prefix 1: 12345h (length = 20 bits) result = P prefix 2: ABCD0123h (length = 32 bits) result = Q

search 2: prefix 1: 2345h (length = 16 bits) result = R prefix 2: ABCD0178h (length = 32 bits) result = S

Instead of creating a separate search structure for each search involving a separate DT and thus requiring a total of two DTs, the proposal allows to construct a single search structure involving only one DT.

A first application

In a first application of the proposal, the search structures are only merged at the "DT level", the remaining parts of the search structures remain unchanged and are directly "connected" to the new shared DT. This is illustrated in Figure 1 which shows an example of a combined

1

Page 2 of 5

search structure in which the DT is indexed by the first 16 bits of the search keys for both searches. The remaining 16 bits are processed successively in 4-bit segments by multi-bit-trie structures attached to the DT entries. In Figure 1, the DT will provide information related to both structures (e.g., pointers, results) together with a corresponding search type identification. This means that a DT entry can (a) be...