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 OwnerAddress
ERICSSON INCP O BOX 13969 7001 DEVELOPMENT DRIVE RESEARCH TRIANGLE PARK NC 27709

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

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

Cited Art Landscape

Load Citation

Patent Citation Ranking

Forward Cite Landscape

Load Citation