Elsevier Science Home
Computer Physics Communications Program Library
Full text online from Science Direct
Programs in Physics & Physical Chemistry
CPC Home

[Licence| Download | New Version Template] actz_v1_0.gz(21 Kbytes)
Manuscript Title: Numerical database system based on a weighted search tree.
Authors: S.C. Park, J.P. Draayer, S.-Q. Zheng, C. Bahri
Program title: WSTREE
Catalogue identifier: ACTZ_v1_0
Distribution format: gz
Journal reference: Comput. Phys. Commun. 82(1994)247
Programming language: Fortran.
Computer: IBM 3090/600J.
Operating system: MVS/XA (Version 3 Release 13).
RAM: 20K words
Word size: 32
Keywords: Heap, Binary tree, Avl tree, Weighted search tree, Linked list, Multi-list Representation, Dynamic storage, Priority strategy, Database numerical, On-line database, File directory system, General purpose, Utility.
Classification: 4.14, 9.

Nature of problem:
Scientific computing applications frequently involve redundant calculations. This occurs either because the number of numbers that need to be calculated is too large to be stored in memory or they occur in unknown combinations so pregeneration, which would allow them to be ordered separately and efficiently so a simple binary look up could be used, is impracticable or impossible. The wst numerical database system introduced here [1-3] can be used to circumvent this problem as it enables one to perform the on-line search of an existing data structure for a particular element and use it if it is found, but if it is not found, it allows generated results to be added to the list so they can be reused as necessary at a later stage in the calculation. Typically this modus operandi yields a two fold gain, namely, needed results are calculated only once and unneeded results are never generated. When the database is full, which occurs when either the tree or associated storage arrays have reached their maximum capacity, one or perhaps even several elements, depending on the size of the incoming data set, have to be deleted before new information can be added to the database. In the sample program the delete option is exercised when the incoming element has a higher priority than the lowest priority element in the database. The deletion process checks to see if the free space generated by deleting the lowest priority node suffices to accommodatete the incoming data, and if it does not additional nodes are deleted, provided of course that their priorities are less than that of the incoming node, until sufficient free space is obtained. Whenever the delete option is invoked, it is the lowest priority node that is removed from the database.

Solution method:
A wst system solves the problem described above with a series of routines that have optimal time and space complexities. Within the wst, search, insert and delete operations on dynamically generated lists of length n execute in times that goes as O[log(n)]. In addition, the wst saves space by using a multi-list representation for the height balanced tree that is the backbone structure of the database system. A full discussion of the theory behind the wst structure can be found in Ref. [3].

Restrictions:
The maximum number of nodes in a wst is set by user. If the pointers are n bit integer words, the theoretical limit on the maximum number is 2**n-1. In actual practice, however, the number will usually be much less than this.

Unusual features:
Intrinsic logical AND and SHIFT functions for integers, which are called IAND and ISHFT in the wst routines [4], are used for bit operations to encode and decode the priority and balance factor that are stored as a single integer word.

Running time:
0.14 ms/item on an IBM 3090/600J

References:
[1] C.J. Date, "An Introduction to Database Systems," Fourth Ed. (Addison-Wesley, Reading, MA, 1986).
[2] S.C. Park and J.P. Draayer, Comput. Phys. Commun. 55, 189, 1989.
[3] S.C. Park, J.P. Draayer, and S.-Q. Zheng, "Time-Space Optimal Numerical Database for Large-Scale Scientific Applications," in Proceedings of the International Computer Symposium, December 17-19, 1990, Hsinchu, Taiwan, R.O.C.
[4] IBM, "VS FORTRAN Version 2: Language and Library Reference," Release 3 IBM, San Jose, CA, 1987.