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

See full text

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

See full text

Family

Loading Family data... loading....

Patent Owner(s)

Patent OwnerAddressTotal Patents
ERICSSON INC.RESEARCH TRIANGLE PARK, NC1435

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Karlsson, Tobias Rockville, MD 18 88

Cited Art Landscape

  • No Cited Art to Display

Patent Citation Ranking

Forward Cite Landscape

Patent Info (Count) # Cites Year
 
QUALCOMM INCORPORATED (1)
* 8,004,431 Fast parsing of variable-to-fixed-length codes 14 2009
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (1)
* 2013/0326,065 WORKLOAD BALANCING BETWEEN NODES IN A CLUSTER AS REQUIRED BY ALLOCATIONS OF IP ADDRESSES WITHIN A CLUSTER 0 2012
 
NETLOGIC MICROSYSTEMS, INC. (4)
8,886,677 Integrated search engine devices that support LPM search operations using span prefix masks that encode key prefix length 0 2007
7,831,626 Integrated search engine devices having a plurality of multi-way trees of search keys therein that share a common root node 5 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 2 2008
 
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
 
FUJITSU LIMITED (1)
* 8,122,064 Computer program, method, and apparatus for data sorting 0 2007
 
HUAWEI TECHNOLOGIES CO., LTD. (1)
8,711,014 Methods and devices for creating, compressing and searching binary tree 0 2012
 
AT&T CORP. (4)
* 6,928,485 Method for network-aware clustering of clients in a network 42 2000
7,219,160 Method for fast network-aware clustering 13 2000
7,296,089 Method for improving web performance by adapting servers based on client cluster characterization 21 2002
7,191,168 Fast prefix matching of bounded strings 6 2002
* Cited By Examiner