公开(公告)号：DE69422935T2

公开(公告)日：2000-08-17

申请号：DE69422935

申请日：1994-06-30

Applicant: IBM

Inventor： DOERINGER WILLIBALD ,  DYKEMAN DOUGLAS ,  KARJOTH GUENTER ,  NASSEHI MEHDI ,  SHARMA B

IPC: G06F17/30 ,  H04L45/74

Abstract: PCT No. PCT/EP94/02135 Sec. 371 Date Dec. 17, 1996 Sec. 102(e) Date Dec. 17, 1996 PCT Filed Jun. 30, 1994 PCT Pub. No. WO96/00945 PCT Pub. Date Jan. 11, 1996The building, maintenance, and use of a database is described having a trie-like structure for storing entries and retrieving an at least partial match, preferably the longest partial match, or all partial matches of a search argument (input key) from said entries, said database having nodes (20), with each node containing first link information (21) leading to at least one previous node (parent pointer) and second link information (25,26) leading to at least one following node (child pointer), at least a stored key (entry, 23, 24), or a combination, thereof. The particular structure of the nodes allows a two-step search process, in which segments of a search argument are firstly used to determine a search path through the trie-like database, said search path being backtracked in the second part of the search. During the second part of the search the entire search argument is compared to entries stored in the nodes until a match is found. The described database allows an efficient use of memories and is advantageously applied to fast data retrieval, in particular related to communication within computer networks. No recursive procedures are applied.

公开(公告)号：DE69422935D1

公开(公告)日：2000-03-09

申请号：DE69422935

申请日：1994-06-30

Applicant: IBM

Inventor： DOERINGER WILLIBALD ,  DYKEMAN DOUGLAS ,  KARJOTH GUENTER ,  NASSEHI MEHDI ,  SHARMA B

IPC: G06F17/30 ,  H04L45/74

Abstract: PCT No. PCT/EP94/02135 Sec. 371 Date Dec. 17, 1996 Sec. 102(e) Date Dec. 17, 1996 PCT Filed Jun. 30, 1994 PCT Pub. No. WO96/00945 PCT Pub. Date Jan. 11, 1996The building, maintenance, and use of a database is described having a trie-like structure for storing entries and retrieving an at least partial match, preferably the longest partial match, or all partial matches of a search argument (input key) from said entries, said database having nodes (20), with each node containing first link information (21) leading to at least one previous node (parent pointer) and second link information (25,26) leading to at least one following node (child pointer), at least a stored key (entry, 23, 24), or a combination, thereof. The particular structure of the nodes allows a two-step search process, in which segments of a search argument are firstly used to determine a search path through the trie-like database, said search path being backtracked in the second part of the search. During the second part of the search the entire search argument is compared to entries stored in the nodes until a match is found. The described database allows an efficient use of memories and is advantageously applied to fast data retrieval, in particular related to communication within computer networks. No recursive procedures are applied.