Multiplex communications – Wide area network – Packet switching
Patent
1995-05-15
1998-07-14
Kriess, Kevin A.
Multiplex communications
Wide area network
Packet switching
370 60, 370 54, 3642531, 3649554, 3649561, 3642832, 3642553, 395200, 3959743, G06F 704
Patent
active
057817723
ABSTRACT:
Aspects of the invention include a method of conducting a reduced length search along a search path. A node which would otherwise occur between a previous and a following node in the search path is eliminated, and information is stored as to whether, had said eliminated node been present, the search would have proceeded to the following node. During the search, a search argument is compared with the stored information, and the search effectively progresses from the previous node directly to the following node if the comparison is positive. In preferred embodiments, some nodes provide result values for the search, and a node is eliminated only if its presence would not affect the result value for the search. In another aspect, the invention features a method of conducting a two mode search of reduced length. For a first mode of the search, nodes along a search path are provided, at least some of the nodes including one or more pointers pointing to other nodes. A search argument comprising a series of search segments is provided, some values of segments of the argument corresponding to nodes along the search path, some other values of the segments relating to a second mode of the search. Indicators associated with nodes are provided, each indicator indicating the segments corresponding to the second mode. The search path is searched by processing successive search segments by inspecting the indicator associated with each node, and proceeding to the second search mode if the indicator indicates that the segment relates to the second mode.
REFERENCES:
patent: 3676851 (1972-07-01), Eastman
patent: 4384325 (1983-05-01), Slechta, Jr. et al.
patent: 4433392 (1984-02-01), Beaven
patent: 4453217 (1984-06-01), Boivie
patent: 4464650 (1984-08-01), Eastman et al.
patent: 4464718 (1984-08-01), Dixon et al.
patent: 4468728 (1984-08-01), Wang
patent: 4606002 (1986-08-01), Waismain et al.
patent: 4621362 (1986-11-01), Sy
patent: 4644496 (1987-02-01), Andrews
patent: 4706081 (1987-11-01), Hart et al.
patent: 4811337 (1989-03-01), Hart
patent: 4823111 (1989-04-01), Tsuchiya et al.
patent: 4882699 (1989-11-01), Evensen
patent: 4906991 (1990-03-01), Fiala et al.
patent: 4914571 (1990-04-01), Baratz et al.
patent: 5001755 (1991-03-01), Skret
patent: 5008882 (1991-04-01), Peterson et al.
patent: 5079767 (1992-01-01), Perlman
Ai-Suwaiyel and Horowitz ("Algorithms for Trie Compaction", ACM Trans. Database Syst., vol. 9, No. 2, Jun. 1984, pp. 243-263).
Comer and Sethi ("The Complexity of Trie Index Construction", Jour. ACM, vol. 24, No. 3, Jul. 1977, pp. 428-440).
Knuth ("Patricia" algorithm from Sorting and Searching, The Art of Computer Programming III, Addison-Wesley Publishing Co., Reading, MA, 1970 pp. 490-493.
Fredkin ("Trie Memory", Comm. ACM, vol. 3, No. 9, Sep. 1960, pp. 490-499).
Comer ("Heuristics for Trie Index Minimization", ACM Trans. Database Syst., vol. 4, No. 3, Sep. 1979, pp. 383-395) * page 387 missing.
Seifert, William M., "Bridges And Routers", IEEE Network Magazine, 1/88 vol:2 Issue 7, pp. 57-64.
Amer et al., "A Survey of Hierarchical Routing Algorithms and A New Hierachical Hybrid Adaptive Routing Algorith for Large Scale Computer Comm. Networks", Communications 1986 IEEE Int. Conf, Date: 12-15 Jun. 1988 pp. 999-1003.
J.J. Garcia-Luna-Aceves, "Routing Management in Very Large-Scale Networks", Future Generations of Computer Systems, vol. 4, No. 2, Sep. 1988, Amsterdam, NL, pp. 81-93.
P. Wolstenholme, "Filtering of Network Addresses in Real Time Sequential Decoding", IEEE Proceedings, vol. 135, No. 1/E, Jan. 1988, pp. 55-59.
R. Ramesh et al., "Variable-Depth Trie Index Optimization: Theory and Experimental Results", ACM Transactions on Database Systems, vol. 14, No. 1, Mar. 1989, pp. 41-74.
Poole Nigel T.
Varghese George
Wilkinson, III Hugh M.
Digital Equipment Corporation
Kriess Kevin A.
Toplu Lucien U.
LandOfFree
Compressed prefix matching database searching does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Compressed prefix matching database searching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compressed prefix matching database searching will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1892937