Affordable Access

Publisher Website

Optimal merging of sorted data under the mean absolute error criterion

Authors
Journal
Computers & Electrical Engineering
0045-7906
Publisher
Elsevier
Publication Date
Volume
18
Issue
2
Identifiers
DOI: 10.1016/0045-7906(92)90007-z
Disciplines
  • Computer Science

Abstract

Abstract In this paper we consider the problem of optimally merging two sets of ordered data such that the mean absolute distance (discrete l 1 norm) that a merged element must move in order to properly order the combined set is minimized. The final sorting algorithm then only needs to move the merged elements a short distance. Such a problem is important in the implementation of multidimensional order statistics and related filters and database applications. A powerful result obtained under the assumption that the elements of both sets are independent and identically distributed (iid) and are derived from the same continuous parent distribution is that the optimal merging (using any l p norm) is independent of the parent distribution. The exact solution to the minimization problem for the l 0+, l 2 and l ∞ cases are given and used as a basis for choosing a good approximation solution for the positions which minimize the l 1 norm. The performance for typical 2-D and 3-D filtering and database applications are also given.

There are no comments yet on this publication. Be the first to share your thoughts.