The median problem transforms a set of $N$ numbers in such a way that none of the first $\frac{N}{2}$ numbers exceeds any of the last $\frac{N}{2}$ numbers. A comparator network that solves the median problem on a set of $r$ numbers is commonly called an $r$-{\em classifier}. This paper shows how the well-known Leighton's Columnsort algorithm can be modified to solve the median problem of $N=rs$ numbers, with $1 \le s \le r$,using an $r$-classifier instead of an $r$-sorting network. Overall the $r$-classifier is used $O(s)$ times, namely the same number of times that Columnsort applies an $r$-sorter. A hardware implementation is proposed that runs in optimal $O(s + \log r)$ time and uses an $O(r\log r(s + \log r))$ work. The implementation shows that when $N= r\log r$ there is a classifier network solving the median problem on $N$ numbers in the same $O(\log r)$ time and using the same $O(r\log r)$ comparators as an $r$-classifier, thus saving a $\log r$ factor in the number of comparators over an $(r\log r)$-classifier.

Selection on Matrices Classifying Rows and Columns / Bertossi, Alan Albert; Olariu, Stephan; Zheng, S. -Q.; Pinotti, Maria Cristina. - ELETTRONICO. - (2002), pp. 1-23.

Selection on Matrices Classifying Rows and Columns

Bertossi, Alan Albert;Pinotti, Maria Cristina
2002-01-01

Abstract

The median problem transforms a set of $N$ numbers in such a way that none of the first $\frac{N}{2}$ numbers exceeds any of the last $\frac{N}{2}$ numbers. A comparator network that solves the median problem on a set of $r$ numbers is commonly called an $r$-{\em classifier}. This paper shows how the well-known Leighton's Columnsort algorithm can be modified to solve the median problem of $N=rs$ numbers, with $1 \le s \le r$,using an $r$-classifier instead of an $r$-sorting network. Overall the $r$-classifier is used $O(s)$ times, namely the same number of times that Columnsort applies an $r$-sorter. A hardware implementation is proposed that runs in optimal $O(s + \log r)$ time and uses an $O(r\log r(s + \log r))$ work. The implementation shows that when $N= r\log r$ there is a classifier network solving the median problem on $N$ numbers in the same $O(\log r)$ time and using the same $O(r\log r)$ comparators as an $r$-classifier, thus saving a $\log r$ factor in the number of comparators over an $(r\log r)$-classifier.
2002
Trento, Italia
Università degli Studi di Trento. DEPARTMENT OF INFORMATION AND COMMUNICATION TECHNOLOGY
Selection on Matrices Classifying Rows and Columns / Bertossi, Alan Albert; Olariu, Stephan; Zheng, S. -Q.; Pinotti, Maria Cristina. - ELETTRONICO. - (2002), pp. 1-23.
Bertossi, Alan Albert; Olariu, Stephan; Zheng, S. -Q.; Pinotti, Maria Cristina
File in questo prodotto:
File Dimensione Formato  
73.pdf

accesso aperto

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 618.97 kB
Formato Adobe PDF
618.97 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/358593
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
  • OpenAlex ND
social impact