Parallel bottom-up construction of radix trees

Details Parallel bottom-up construction of radix trees Parallel bottom-up construction of radix trees

1996-03-22

1998-10-20

Black, Thomas G.

Data processing: database and file management or data structures

Database design

Data structure types

707 2, 711 1, 370408, G06F 1730

Patent

active

058262628

ABSTRACT:
A method for partitioning keys onto radix tree logical pages and a parallel index page build algorithm in order to provide radix tree build speedup proportional to the number of processors on the system and controlled efficient page utilization. Also, since keys are intelligently partitioned so that a complete set of keys is inserted into a logical page, there is no page overflow during the tree construction and thus page splitting is eliminated. Since radix index trees are really groups of logical pages in which each logical page contains a small tree, the tree is built (with respect to the logical pages) from the bottom up, while within each individual logical page the tree is constructed from the top down. The space required for a logical page is pre-allocated to allow construction of limbs to begin without waiting for the build of their underlying pages to complete.

REFERENCES:
patent: 3916387 (1975-10-01), Woodrum
patent: 4774657 (1988-09-01), Anderson et al.
patent: 4819156 (1989-04-01), DeLorme et al.
patent: 5058002 (1991-10-01), Nakamura et al.
patent: 5179699 (1993-01-01), Iyer et al.
patent: 5202986 (1993-04-01), Nickel
patent: 5241648 (1993-08-01), Cheng et al.
patent: 5345585 (1994-09-01), Iyer et al.
patent: 5355473 (1994-10-01), Au
patent: 5446887 (1995-08-01), Berkowitz
patent: 5490258 (1996-02-01), Fenner
patent: 5546390 (1996-08-01), Stone
patent: 5659728 (1997-08-01), Bhargava et al.
Varman et al. "An Efficient Multiprocessor Merge Algorithm", PARABASE '90, p. 276283, 1990.
Wolf et al. "Optimal Buffer Partitioning for the Nested Block Join Algorithm", Digital Engineering, 1991 7th Int'l Conf., pp. 510-519, 1991.
Cheng et al. "An Efficient Hybrid Join Algorithm: A DB2 Prototype", Data Engineering, 1991 7th Int'l Conf., pp. 171-180, 1991.
Ciciani et al. "A Hybrid distribution Centralized System Structure for Transaction Processing", IEEE Transactions on Software Eng., vol. 16, No. 8, pp. 791-806, 1990.
Howard et al. "System/38 Machine Data Indexing Support", IBM System/38 Technical Developments, pp. 67-79, 1978.
Law et al. "Multicast and Self-Routing in ATM Radix Trees and Banyan Networks", Infocom '95, vol. 3, pp. 951-959, 1995.
IBM Technical Disclosure Bulletin, Vol. 19, No. 4, p. 1360, Sep. 1976, "Search Argument Checking", C. H. Wolff and L. J. Woodrum, P0875-0359.
IBM System/38 Technical Developments, 1978, "System/38 Machine Data Base Support", C. T. Watson and G. F. Aberle, pp. 59-62, System/38 Machine Indexing Support, P. H. Howard and K. W. Borgendale, pp. 67-69, and System/38 Data Base Concepts, C. T. Watson, F. E. Benson and P. T. Taylor, pp. 78-80.
Chandrasekharan et al, "Ray Tracing and Binary Trees Computations Using PVM"; Proceeding of the Twenty-Sixth Hawaii International Conference on System Sciences; Jan. 1993; pp. 104-105.

Affiliated with

Also associated with

Rating

Parallel bottom-up construction of radix trees does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Parallel bottom-up construction of radix trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel bottom-up construction of radix trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-260056