Browse Prior Art Database

Method for a distributed n-nary tree structure and search algorithm for data in a known range

IP.com Disclosure Number: IPCOM000146560D
Publication Date: 2007-Feb-16
Document File: 8 page(s) / 92K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for a distributed n-nary tree structure and search algorithm for data in a known range. Benefits include improved functionality and improved performance.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 38% of the total text.

Method for a distributed n-nary tree structure and search algorithm for data in a known range

Disclosed is a method for a distributed n-nary tree structure and search algorithm for data in a  known range. Benefits include improved functionality and improved performance.

Background

      A conventional n-nary tree contains a stem and branches. For example, a binary tree can have a data range of 0 – 999. Data entries include the following values (see Figure 1):

300, 20, 100, 500, 250, 10, 30, 800, 600, 330, 550, 60, 900, 80, 850

      The depth of the tree is 6. Reaching a node requires the following number of steps:

•     Node 10 takes 2 steps

•     Node 80 takes 5 steps

•     Node 550 takes 4 steps

•     Node 850 takes 4 steps

      Adding two new nodes, 15 and 700, requires 3 steps and 4 steps, respectively.

       A balanced tree has a total number of number of nodes represented by the following equation:
m = rangemax - rangemin +1

      The original depth of a conventional tree is represented by the following equation:                            

dorg = logn (m+1)

      For a binary tree, the value of n is 2.

      For a balanced tree with a data range from 1 to 15, the total nodes is (see Figure 2):

m = 15 – 1 + 1 = 15

      As a result, the depth is:

dorg = log2 (15 + 1) = 4

      For a left/right biased tree with a data range of 1 to 15, the total nodes is (see Figure 3):

m = 15 – 1 + 1 = 15

      The original depth is:

dorg =  m = 15

General description

      The disclosed method is a distributed n-nary tree structure and search algorithm for data in known ranges. The method is a generic concept that can be applied for any related field/product regardless of the software or hardware implementation. The method speeds up the data manipulation process and enables some degree of parallel processing. The method can be applied to functions such as database management, simulation, and routing path calculation.

Advantages

      The disclosed method provides advantages, including:

•     Improved functionality due to enabling parallel processing if data search/insertion/deletion are processed on data in different subtrees

•     Improved performance due to improving search and node manipulation process time by reducing the number of steps required to reach a node

Detailed description

      The disclosed method is a distributed n-nary tree structure and search algorithm for data in known ranges. The method reduces the tree depth, which ranges from (logn x – 1) to (m – m/x), depending on the incoming data sequence. As a result, tree searching and manipulation, such as add, delete, and find, are performed faster.

      With the disclosed method, a slot is a subtree. For e...