Browse Prior Art Database

Dynamic Bin Database Algorithm

IP.com Disclosure Number: IPCOM000111056D
Original Publication Date: 1994-Feb-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 4 page(s) / 103K

Publishing Venue

IBM

Related People

Smith, GL: AUTHOR

Abstract

The dynamic bin database in an O[N] algorithm that uses bin sorting and preallocated linked lists of index numbers to efficiently sort and retrieve data from a large dynamic linear array of fixed size data records kept in main memory. The database procedure was developed to efficiently organize and retrieve dynamic two dimensional data from a scanning surveillance system. The database requires approximately 2N index integers of additional storage. So storage requirements are O[N]. This is a small fraction of the storage required to store N complete data records in main memory.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Dynamic Bin Database Algorithm

      The dynamic bin database in an O[N]  algorithm that uses bin
sorting and preallocated linked lists of index numbers to efficiently
sort and retrieve data from a large dynamic linear array of fixed
size data records kept in main memory.  The database procedure was
developed to efficiently organize and retrieve dynamic two
dimensional data from a scanning surveillance system.  The database
requires approximately 2N index integers of additional storage.  So
storage requirements are O[N].  This is a small fraction of the
storage required to store N complete data records in main memory.

      As can be seen in Fig. 1, data is organized main computer
memory as a large linear array of Data Records DR(P).  Each data
record is associated with one data point.  A data record contains
information such as scan number, X, Y coordinates, brightness, sensor
type, adjacency, etc.  Integer index numbers are used like pointer to
select data records.  Data records are loaded into the linear array
of data records, a scan at a time, as a batch process.  When the
linear arrays fills up, records are written over old ones by simply
wrapping around the index numbers.  Before any records of the oldest
scan are written over, the oldest scan number is removed from a list
of valid scan numbers.

      Linked lists associated with each bin of the bin matrix are
formed in a second array LL(pi) of integer numbers.  This array has
the same number of integers as the number of records in DR.  It does
not require initialization.

      A fixed bin matrix BM(xi,yi) of integer number is defined for
each scan of data.  It is a table of head index numbers that identify
the first record in the linked list associated with each bin.  The
bin matrix assigned to a new scan is initialized with zeros.  A do
loop with index pi selects each of the new records DR(pi).  X and Y
coordinates found in the data record are converted into integer index
numbers xi and yi.  To convert a real number to an index, simply
multiply the real number by a scale constant (for example, 625).  The
result is truncated to form an integer number.  Finally an integer
constant (for example, 100) is added to eliminate the sign.  Index
numbers derived from the coordinat...