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

Number of patents in Portfolio can not be more than 2000

United States of America Patent

APP PUB NO 20030236793A1
SERIAL NO

10175249

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

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

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

Cited Art Landscape

Patent Info (Count) # Cites Year
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (2)
* 5655129 Character-string retrieval system and method 59 1995
* 5774081 Approximated multi-symbol arithmetic coding method and apparatus 17 1995
 
LONGSAND LIMITED (1)
* 5983180 Recognition of sequential data using finite state sequence models organized in a tree structure 48 1998
 
BULL HN INFORMATION SYSTEMS INC. (1)
* 5202986 Prefix search tree partial key branching 89 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)
* 6266706 Fast routing lookup system using complete prefix tree, bit vector, and pointers in a routing table for determining where to route IP datagrams 84 1998
 
CANON KABUSHIKI KAISHA (1)
* 2003/0208,473 Browsing electronically-accessible resources 34 2000
* Cited By Examiner

Patent Citation Ranking

Forward Cite Landscape

Patent Info (Count) # Cites Year
 
QUALCOMM INCORPORATED (2)
* 8004431 Fast parsing of variable-to-fixed-length codes 24 2009
* 2010/0141,489 FAST PARSING OF VARIABLE-TO-FIXED-LENGTH CODES 17 2009
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (3)
* 9264396 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
* 9276899 Workload balancing between nodes in a cluster as required by allocations of IP addresses within a cluster 0 2013
 
SAP SE (3)
* 7403495 Method and system for compressing a tree 1 2004
8203972 Method and system for compressing a tree 9 2008
* 2009/0043,796 METHOD AND SYSTEM FOR COMPRESSING A TREE 1 2008
 
BLACKBERRY LIMITED (1)
* 2014/0245,178 COMMUNICATION DEVICE AND METHOD FOR PROFILING AND PRESENTATION OF MESSAGE THREADS 2 2013
 
IM2, Inc. (1)
* 7672958 Method and system to identify records that relate to a pre-defined context in a data set 2 2005
 
FACEBOOK, INC. (1)
* 2006/0161,569 Method and system to identify records that relate to a pre-defined context in a data set 2 2005
 
FUJITSU LIMITED (2)
* 8122064 Computer program, method, and apparatus for data sorting 1 2007
* 2008/0114,765 Computer program, method, and apparatus for data sorting 3 2007
 
HUAWEI TECHNOLOGIES CO., LTD. (2)
8711014 Methods and devices for creating, compressing and searching binary tree 0 2012
9521082 Methods and devices for creating, compressing and searching binary tree 0 2014
 
AVAGO TECHNOLOGIES GENERAL IP (SINGAPORE) PTE. LTD. (4)
8886677 Integrated search engine devices that support LPM search operations using span prefix masks that encode key prefix length 0 2007
7831626 Integrated search engine devices having a plurality of multi-way trees of search keys therein that share a common root node 7 2007
* 7987205 Integrated search engine devices having pipelined node maintenance sub-engines therein that support database flush operations 2 2007
8086641 Integrated search engine devices that utilize SPM-linked bit maps to reduce handle memory duplication and methods of operating same 5 2008
 
AT&T CORP. (6)
* 6928485 Method for network-aware clustering of clients in a network 110 2000
7219160 Method for fast network-aware clustering 19 2000
7296089 Method for improving web performance by adapting servers based on client cluster characterization 29 2002
* 2003/0046,343 Method for improving web performance by adapting servers based on client cluster characterization 36 2002
* 2002/0198,961 Method for improving web performance by client characterization-driven server adaptation 24 2002
7191168 Fast prefix matching of bounded strings 15 2002
* Cited By Examiner