Adaptive Data Partition for Sorting using Probability Distribution
  
  
Xipeng Shen and Chen Ding
  
  
                            ABSTRACT 
  
  
  Many computing problems benefit from dynamic partition of data into
  smaller chunks with better parallelism and locality.  However, it is
  difficult to partition all types of inputs with the same high
  efficiency.  This paper presents a new partition method in sorting
  scenario based on probability distribution, an idea first studied by
  Janus and Lamagna in early 1980's on a mainframe computer.  The new
  technique makes three improvements.  The first is a rigorous
  sampling technique that ensures accurate estimate of the probability
  distribution.  The second is an efficient implementation on modern,
  cache-based machines.  The last is the use of probability
  distribution in parallel sorting.  Experiments show 10-30%
  improvement in partition balance and 20-70% reduction in partition
  overhead, compared to two commonly used techniques.  The new method
  reduces the parallel sorting time by 33-50% and outperforms the
  previous fastest sequential sorting technique by up to 30%.
  
  Download the paper in  pdf format.
  
   Copyright notice