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, NC1444

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

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

Cited Art Landscape

Patent Info (Count) # Cites Year
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (2)
* 5,655,129 Character-string retrieval system and method 46 1995
* 5,774,081 Approximated multi-symbol arithmetic coding method and apparatus 17 1995
 
LONGSAND LIMITED (1)
* 5,983,180 Recognition of sequential data using finite state sequence models organized in a tree structure 43 1998
 
Bull HN Information Systems Inc. (1)
* 5,202,986 Prefix search tree partial key branching 88 1989
 
CALIFORNIA INSTITUTE OF TECHNOLOGY (1)
* 2002/0176,494 Lossless and near-lossless source coding for multiple access networks 7 2002
 
EFFNET HOLDING AB (1)
* 6,266,706 Fast routing lookup system using complete prefix tree, bit vector, and pointers in a routing table for determining where to route IP datagrams 79 1998
 
Canon Kabushiki Kaisha (1)
* 2003/0208,473 Browsing electronically-accessible resources 27 2000
* Cited By Examiner

Patent Citation Ranking

Forward Cite Landscape

Patent Info (Count) # Cites Year
 
QUALCOMM INCORPORATED (2)
* 8,004,431 Fast parsing of variable-to-fixed-length codes 20 2009
* 2010/0141,489 FAST PARSING OF VARIABLE-TO-FIXED-LENGTH CODES 14 2009
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (3)
* 9,264,396 Workload balancing between nodes in a cluster as required by allocations of IP addresses within a cluster 0 2012
* 2013/0326,065 WORKLOAD BALANCING BETWEEN NODES IN A CLUSTER AS REQUIRED BY ALLOCATIONS OF IP ADDRESSES WITHIN A CLUSTER 0 2012
* 9,276,899 Workload balancing between nodes in a cluster as required by allocations of IP addresses within a cluster 0 2013
 
SAP SE (3)
* 7,403,495 Method and system for compressing a tree 1 2004
8,203,972 Method and system for compressing a tree 5 2008
* 2009/0043,796 METHOD AND SYSTEM FOR COMPRESSING A TREE 1 2008
 
Fatlens Inc. (1)
* 2006/0161,569 Method and system to identify records that relate to a pre-defined context in a data set 2 2005
 
IM2, Inc. (1)
* 7,672,958 Method and system to identify records that relate to a pre-defined context in a data set 2 2005
 
FUJITSU LIMITED (2)
* 8,122,064 Computer program, method, and apparatus for data sorting 1 2007
* 2008/0114,765 Computer program, method, and apparatus for data sorting 2 2007
 
BROADCOM CORPORATION (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 6 2007
* 7,987,205 Integrated search engine devices having pipelined node maintenance sub-engines therein that support database flush operations 2 2007
8,086,641 Integrated search engine devices that utilize SPM-linked bit maps to reduce handle memory duplication and methods of operating same 3 2008
 
HUAWEI TECHNOLOGIES CO., LTD. (1)
8,711,014 Methods and devices for creating, compressing and searching binary tree 0 2012
 
AT&T CORP. (6)
* 6,928,485 Method for network-aware clustering of clients in a network 85 2000
7,219,160 Method for fast network-aware clustering 18 2000
7,296,089 Method for improving web performance by adapting servers based on client cluster characterization 28 2002
* 2003/0046,343 Method for improving web performance by adapting servers based on client cluster characterization 15 2002
* 2002/0198,961 Method for improving web performance by client characterization-driven server adaptation 23 2002
7,191,168 Fast prefix matching of bounded strings 12 2002
* Cited By Examiner