On a partitioning problem

ABSTRACT

This paper investigates the problem of locating a set of “boundary points” of a large number of records. Conceptually, the boundary points partition the records into subsets of roughly the same number of elements, such that the key values of the records in one subset are all smaller or all larger than those of the records in another subset. We guess the locations of the boundary points by linear interpolation and check their accuracy by reading the key values of the records on one pass. This process is repeated until all boundary points are determined. Clearly, this problem can also be solved by performing an external tape sort. Both analytical and empirical results indicate that the number of passes required is small in comparison with that in an external tape sort. This kind of record partitioning may be of interest in setting up a statistical database system.

REFERENCES

• 1: FELLER, W. An Introduction to Probability Theory and Its Applications, Vol. I. Wiley, New York, 1968.
• 2: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 3: C. T. Yu , F. Y. Chin, A study on the protection of statistical data bases, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada [doi>10.1145/509404.509432]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Region growing, partitioning

General Terms:
Design

Keywords:
external sort, key value, partition, passes, tape probability