US Patent Application No: 2003/0236,793

Number of patents in Portfolio can not be more than 2000

Compressed prefix tree structure and method for traversing a compressed prefix tree

Stats

ATTORNEY / AGENT: (SPONSORED)
 

Importance

Loading Importance Indicators... loading....

Abstract

A compressed prefix tree data structure is provided that allows large prefix trees and Virtual Private Network (VPN) trees to be placed in external memory, while minimizing the number of memory reads needed to reach a result. The compressed prefix tree data structure represents one or more bonsai trees, where each bonsai tree is a portion of a prefix tree containing two or more nodes that can be coded into a single data word (codeword). Each codeword is stored in a portion of the external memory (e.g., 16 bytes of DRAM), and retrieved as a unit for processing. Thus, each external DRAM call can retrieve multiple nodes of a prefix tree, reducing the time required for traversing the prefix tree.

Loading the Abstract Image... loading....

First Claim

Related Publications

Loading Related Publications... loading....

Patent Owner(s)

Patent OwnerAddressTotal Patents
ERICSSON INC.RESEARCH TRIANGLE PARK, NC1665

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Karlsson, Tobias Rockville, MD 15 50

Patent Citation Ranking

Forward Cites

Patent Info (Count) # Cites Year
 
AT&T CORP. (4)
6,928,485 Method for network-aware clustering of clients in a network 27 2000
7,219,160 Method for fast network-aware clustering 5 2000
7,296,089 Method for improving web performance by adapting servers based on client cluster characterization 8 2002
7,191,168 Fast prefix matching of bounded strings 2 2002
 
NETLOGIC MICROSYSTEMS, INC. (3)
7,831,626 Integrated search engine devices having a plurality of multi-way trees of search keys therein that share a common root node 4 2007
7,987,205 Integrated search engine devices having pipelined node maintenance sub-engines therein that support database flush operations 1 2007
8,086,641 Integrated search engine devices that utilize SPM-linked bit maps to reduce handle memory duplication and methods of operating same 1 2008
 
SAP AG (2)
7,403,495 Method and system for compressing a tree 1 2004
8,203,972 Method and system for compressing a tree 1 2008
 
FUJITSU LIMITED (1)
8,122,064 Computer program, method, and apparatus for data sorting 0 2007
 
IM2, Inc. (1)
7,672,958 Method and system to identify records that relate to a pre-defined context in a data set 1 2005
 
QUALCOMM INCORPORATED (1)
8,004,431 Fast parsing of variable-to-fixed-length codes 0 2009