String lookup using three-transition tree structure

Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/6298

Title:	String lookup using three-transition tree structure
Authors:	Luk, RWP Wong, WT
Issue Date:	17-Sep-2013
Source:	US Patent 8,538,999 B2. Washington, DC: US Patent and Trademark Office, 2013.
Abstract:	A tree data structure for storing strings of searchable data divided into substrings has at least one first type node that has a substring associated with it and at least one second type node that does not having a substring associated with it. A second type node is directly linked to a first type node by a fail transition. A first type node is directly linked to a second type node by a match transition. An IP address lookup system has memory for storing a tree data structure and a controller for storing and loading an incoming IP address. The system has a finite state machine having three stages including a first stage for loading the IP address and performing a length calculation, a second stage for searching the data structure to find a match, and a third stage for determine the next-hop address index.
Rights:	Assignee: The Hong Kong Polytechnic University.
Appears in Collections:	Patent

File	Description	Size	Format
us8538999b2.pdf		1.42 MB	Adobe PDF	View/Open

Show full item record

42

Last Week
2

Last month

Citations as of Jun 4, 2023

20

Citations as of Jun 4, 2023

Check