Work Files Saved Searches
   My Account                                                  Search:   Quick/Number   Boolean   Advanced       Help   

 The Delphion Integrated View

  Buy Now:   Buy PDF- 8pp  PDF  |   File History  |   Other choices   
  Tools:  Citation Link  |  Add to Work File:    
  View:  Expand Details   |  INPADOC   |  Jump to: 
 Email this to a friend  Email this to a friend 
Title: US5530957: Storing trees in navigable form
[ Derwent Title ]

Country: US United States of America

View Images High


8 pages

Inventor: Koenig, Andrew R.; Gillette, NJ

Assignee: AT&T Corp., Murray Hill, NJ
other patents from AT&T CORP. (706518) (approx. 16,328)
 News, Profiles, Stocks and More about this company

Published / Filed: 1996-06-25 / 1992-08-07

Application Number: US1992000927087

IPC Code: Advanced: G06F 9/45; G06F 12/00; G06F 17/30;
IPC-7: G06F 17/30;

ECLA Code: G06F17/30Z1T;

U.S. Class: Current: 001/001; 707/999.1; 707/E17.012;
Original: 395/600; 364/251.6; 364/960.5; 364/DIG.1; 395/700;

Field of Search: 395/600,200,700,400,425,159,160,2 364/DIG. 1,251.6,960.5 341/051,65,67,79,87

Priority Number:
1992-08-07  US1992000927087

Abstract:     A compact representation of a tree data structure and techniques for navigating the compact representation. The compact representation is a list. Each element of the list represents a node of the tree and the list is organized according to a preorder traversal of the tree. Each list element contains only the index of a data dictionary entry for the kind of item represented by the node corresponding to the list element. The navigation techniques permit the location of the list element for the sibling of the node corresponding to the given list element, the location of the list element for that node's parent, and in the case of a parent node, the location of the list element for any child of the parent. The navigation techniques work by finding the list elements for subtrees. The subtrees are found by techniques based on the fact that the number of children of all of the nodes in a subtree minus the number of nodes in the subtree always equals -1. The number of children of a given node is determined by a valence function which takes the index of the data dictionary entry as its argument.

Attorney, Agent or Firm: Nelson, Gordon E. ;

Primary / Asst. Examiners: Black, Thomas G.; Alam, Hosain T.

Maintenance Status: E3 Expired  Check current status

INPADOC Legal Status: Show legal status actions          Buy Now: Family Legal Status Report

Designated Country: DE ES FR GB IT 

Family: Show 8 known family members

First Claim:
Show all 11 claims
What is claimed is:     1. Apparatus for storing a tree data structure in a memory system, the tree structure being made up of one or more nodes, each of which represents one of a plurality of items, the apparatus comprising:
  • a data dictionary in the memory system which includes one data dictionary entry for each of the items;
  • valence function means for determining the number of children which a node representing an item has; and
  • a list in the memory system which has one or more list entries, the list entries being ordered according to a traversal of the tree structure and each list entry representing a single one of the nodes and including a value which is used both to locate the entry in the data dictionary for the item represented by the node and with the valence function means to determine the number of children of the node represented by the entry.

Background / Summary: Show background / summary

Drawing Descriptions: Show drawing descriptions

Description: Show description

Forward References: Show 36 U.S. patent(s) that reference this one

U.S. References: Go to Result Set: All U.S. references   |  Forward references (36)   |   Backward references (12)   |   Citation Link

Patent  Pub.Date  Inventor Assignee   Title
Get PDF - 31pp US4868743  1989-09 Nishio  Hitachi, Ltd. Traversal method of processing tree structure information and apparatus using the same
Get PDF - 13pp US4945475  1990-07 Bruffey et al.  Apple Computer, Inc. Hierarchical file system to provide cataloging and retrieval of data
Get PDF - 31pp US5153591  1992-10 Clark  British Telecommunications public limited company Method and apparatus for encoding, decoding and transmitting data in compressed form
Get PDF - 14pp US5202986  1993-04 Nickel  Bull HN Information Systems Inc. Prefix search tree partial key branching
Get PDF - 9pp US5253325  1993-10 Clark  British Telecommunications public limited company Data compression with dynamically compiled dictionary
Get PDF - 16pp US5257365  1993-10 Powers et al.   Database system with multi-dimensional summary search tree nodes for reducing the necessity to access records
Get PDF - 18pp US5263160  1993-11 Porter et al.  Digital Equipment Corporation Augmented doubly-linked list search and management method for a system having data stored in a list of data elements in memory
Get PDF - 14pp US5276874  1994-01 Thomson  Digital Equipment Corporation Method for creating a directory tree in main memory using an index file in secondary memory
Get PDF - 16pp US5295261  1990-07 Simonetti  Pacific Bell Corporation Hybrid database structure linking navigational fields having a hierarchial database structure to informational fields having a relational database structure
Get PDF - 32pp US5297284  1991-04 Jones et al.  Microsoft Corporation Method and system for implementing virtual functions and virtual base classes and setting a this pointer for an object-oriented programming language
Get PDF - 34pp US5303367  1990-12 Leenstra, Sr. et al.  Applied Technical Systems, Inc. Computer driven systems and methods for managing data which use two generic data elements and a single ordered file
Get PDF - 10pp US5307486  1994-04 Nakamigawa  Kabushiki Kaisha Toshiba Method for updating an index tree structure of data based on node sizes
Foreign References: None

Other Abstract Info: DERABS G94-076377

Other References:
  • Practical Dictionary Management for Hardware Data Compression, Bunton et al., Communications of the ACM, V35, n1, p. 95(11), Jan., 1992.

  • Inquire Regarding Licensing

    Powered by Verity

    Plaques from Patent Awards      Gallery of Obscure PatentsNominate this for the Gallery...

    Thomson Reuters Copyright © 1997-2014 Thomson Reuters 
    Subscriptions  |  Web Seminars  |  Privacy  |  Terms & Conditions  |  Site Map  |  Contact Us  |  Help