Header

UZH-Logo

Maintenance Infos

Single Point Incremental Fourier Transform on 2D Data Streams


Saad, Muhammad; Bernstein, Abraham; Böhlen, Michael Hanspeter; Dell'Aglio, Daniele (2021). Single Point Incremental Fourier Transform on 2D Data Streams. In: IEEE. 2021 IEEE 37th International Conference on Data Engineering (ICDE). New York: IEEE Xplore, 852-863.

Abstract

In radio astronomy, antennas monitor portions of the sky to collect radio signals. The antennas produce data streams that are of high volume and velocity (2.5 GB/s) and the inverse Fourier transform is used to convert the collected signals into sky images that astrophysicists use to conduct their research. Applying the inverse Fourier transform in a streaming setting, however, is not ideal since its computational complexity
is quadratic in the size of the image.

In this article, we propose the Single Point Incremental Fourier Transform (SPIFT), a novel incremental algorithm to produce sequences of sky images. SPIFT computes the Fourier transform for a new signal in a linear number of complex multiplications by exploiting twiddle factors, multiplicative constant coefficients. We prove that twiddle factors are periodic and show how circular shifts can be exploited to reuse multiplication results. The cost of the additive operations can be curbed by exploiting the embarrassingly parallel nature of the additions, which modern big data streaming frameworks can leverage to compute slices of the image in parallel. Our experiments suggest that SPIFT can efficiently generate sequences of sky images: it computes the complex multiplications 4 to 12x faster than the Discrete Fourier Transform, and its parallelisation of the additive operations shows linear speedup.

Abstract

In radio astronomy, antennas monitor portions of the sky to collect radio signals. The antennas produce data streams that are of high volume and velocity (2.5 GB/s) and the inverse Fourier transform is used to convert the collected signals into sky images that astrophysicists use to conduct their research. Applying the inverse Fourier transform in a streaming setting, however, is not ideal since its computational complexity
is quadratic in the size of the image.

In this article, we propose the Single Point Incremental Fourier Transform (SPIFT), a novel incremental algorithm to produce sequences of sky images. SPIFT computes the Fourier transform for a new signal in a linear number of complex multiplications by exploiting twiddle factors, multiplicative constant coefficients. We prove that twiddle factors are periodic and show how circular shifts can be exploited to reuse multiplication results. The cost of the additive operations can be curbed by exploiting the embarrassingly parallel nature of the additions, which modern big data streaming frameworks can leverage to compute slices of the image in parallel. Our experiments suggest that SPIFT can efficiently generate sequences of sky images: it computes the complex multiplications 4 to 12x faster than the Discrete Fourier Transform, and its parallelisation of the additive operations shows linear speedup.

Statistics

Citations

Altmetrics

Additional indexing

Item Type:Book Section, refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Informatics
08 Research Priority Programs > Digital Society Initiative
Dewey Decimal Classification:000 Computer science, knowledge & systems
Scopus Subject Areas:Physical Sciences > Software
Physical Sciences > Signal Processing
Physical Sciences > Information Systems
Language:English
Date:2021
Deposited On:04 Jan 2022 08:24
Last Modified:26 Feb 2024 02:40
Publisher:IEEE Xplore
ISBN:978-1-7281-9184-3
Additional Information:Conference Location: Chania, Greece
OA Status:Closed
Publisher DOI:https://doi.org/10.1109/ICDE51399.2021.00079
Official URL:https://ieeexplore.ieee.org/document/9458728
Other Identification Number:merlin-id:20875
Full text not available from this repository.