Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-09-22
2003-12-09
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06662184
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
This invention relates to a data structure apparatus in the form of a binary digital tree and method of searching and modifying the data structure. More particularly, this invention relates to building a routing table that allows both specific and general entries, and incorporates a data structure in the form of a modified Practical Algorithm to Retrieve Information Coded in Alphanumeric Tree (“Patricia Tree”) for building, searching and modifying the routing table with wildcard support. The invention further incorporates procedures for searching and modifying the wildcard routing table, wherein the procedures include filters and flags for focusing the scope of the search, and insert and delete procedures for modifying the table without affecting the integrity of any ongoing searches.
2. Description of the Prior Art
In recent years the world has come into the electronic era. A global network of interconnected computers now allows people from all over the world to communicate via electronic mail messages and to establish locations on the network for dissemination of information. As such, the ability to send and receive messages in a reasonable amount of time is becoming more cumbersome as the network continues to experience rapid growth.
Sending of electronic mail and exploring the global electronic network require proper routing of network messages to their intended destinations. Almost all transactions conducted on the global electronic network involve an exchange of messages between one computer and another. Every computer connected into the global computer network has at least one network address, and similar to a postal address for standard mail delivery, the network address is necessary to accommodate correct delivery of electronic messages through the network. When an application on an individual computer sends a network message, there are three possible scenarios that may occur: the message could be addressed to another application that runs on the same computer, the message could be addressed to a different computer that can be accessed directly, or the message could be addressed to a distant computer that requires the assistance of the global electronic network to be reached. In a conventional application, the first scenario is equivalent to handing a letter to a person who lives in the same house, the second scenario is equivalent to carrying a letter to a person who lives in the same building or neighborhood, and the third scenario is equivalent to sending a letter to the post office for delivery. Accordingly, for each of the scenarios the network must decide which case is applicable to the message and take the appropriate action.
Each computer recognizes its own address(es) and delivers internal messages immediately. A standard desktop computer has one network interface for direct connection to a local network. The standard network interface for a personal computer is in the form of an Ethernet card or a dial-up modem. In addition, a desktop computer may be a part of a local area network (“LAN”) wherein messages addressed to any of the other computers on the LAN remain within the LAN. These messages are recognized as being targeted at addresses that are part of the LAN and are delivered within the LAN. However, for messages that are not being transmitted to addresses within a LAN, the computer requires locating an appropriate gateway for message delivery, wherein the gateway is a computer within the network that accepts messages for delivery to more distant locations. Use of the proper gateway for sending messages to distant computers is paramount for timely delivery of messages. The routing of messages involves effective selection of an outbound network interface. Frequently, the network traffic within the global electronic network favors the selection of gateways for routing of messages to the proper end destination. This may translate into the use of multiple gateways which act as delivery conduits which the messages pass through prior to reaching the intended destination. Accordingly, with the abundance of network addresses a simple table with entry of every address within the global electronic network is neither an effective nor efficient tool for managing delivery of messages over the global electronic network.
Conventional tables for storing data, such as words and numbers, contain only exact entries. Some tables only support searches for exact and complete values, while other tables support searches for inexact values as well. An inexact value may come in the form of a wildcard which can stand for any symbol or string of symbols. Routing tables generally contain inexact entries and support only searching with an exact target, wherein the search always begins with an exact and complete address. Accordingly, in using wildcard values in a routing table it is important to develop and/or utilize a data structure for efficiently building the tables.
Data structures in the form of trees are known as efficient tools for building routing tables and supporting searches beginning with a known prefix. A tree is a data structure accessed first at the root node. Each subsequent node can be either an internal node with further subsequent nodes or an external node with no further nodes existing under the node. An internal node refers to or has links to one or more descending or child nodes and is referred to as the parent of its child nodes, and external nodes are commonly referred to as leaves. The root node is usually depicted at the top of the tree structure and the external nodes are depicted at the bottom.
Tree structures are often defined by the characteristics of the tree. For example, a Binary Tree is a tree with at most two children for each node. A Digital Tree is a rooted tree where the leaves represent strings of digital symbols. The Patricia Tree is a Digital Tree with suppression of one way branching that prohibits keys which are strict prefixes of other branches. In general, a Patricia Tree is always a digital tree, but only a binary tree when the symbol alphabet is binary. The internal nodes represent a common prefix to a set of strings, and each child of that node corresponds to a choice of the next symbol to follow the common prefix. A Patricia Tree can take the form of both a Binary Tree and a Digital Tree where all internal nodes have at least two children.
As mentioned above, a Patricia Tries is an acronym for “Practical Algorithm to Retrieve Information Coded in Alphanumeric” and is suitable for dealing with extremely long variable length keys such as titles or phrases stored within a large bulk file. The Patricia Tree adheres to two primary concepts. The first of these concepts is the concept of semi-infinite strings. These are strings with a particular starting position in a document which are then considered to continue indefinitely in the forward direction of the string. The second concept is that of being based on symbol-by-symbol comparison of data. In an algorithm developed for traversing such a tree, the decision on traversal direction is taken based on the value of the alphabetic symbol currently in consideration.
Within the Patricia Tree structure, internal nodes where there exists only one choice of the next symbol are omitted from the data structure. Patricia Trees keep track of the missing nodes by recording the distance from the beginning of the string at every node of the tree. The basic idea behind a Patricia Tree is to build a Digital Tree that avoids one-way branching by including in each node the number of symbols to skip over before making the next test. A Patricia Tree does not search for strict equality between key and argument, rather it will determine whether or not there exists a key beginning with the argument and proceed from there. More specifically, the Patricia Tree considers a single symbol at each internal node, and makes a comparison for string equality only at an external node. Accordingly, since traditional routing of electronic messages on a global computer network is
International Business Machines - Corporation
Lieberman Rochelle
Metjahic Safet
Thai Hanh
LandOfFree
Lock-free wild card search data structure and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Lock-free wild card search data structure and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lock-free wild card search data structure and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3129484