Not logged in.

Contribution Details

Type Conference or Workshop Paper
Scope Discipline-based scholarship
Published in Proceedings Yes
Title Single Point Incremental Fourier Transform on 2D Data Streams
Organization Unit
  • Michael Hanspeter Böhlen
  • Abraham Bernstein
  • Daniele Dell' Aglio
  • Muhammad Saad
Presentation Type paper
Item Subtype Original Work
Refereed Yes
Status Published in final form
  • English
ISBN 978-1-7281-9185-0
ISSN 2375-026X
Event Title 37th IEEE International Conference on Data Engineering
Event Type conference
Event Location Chania, Greece
Event Start Date April 19 - 2021
Event End Date April 22 - 2021
Place of Publication Chania, Greece
Publisher IEEE
Abstract Text 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.
Official URL
Digital Object Identifier 10.1109/ICDE51399.2021.00079
Export BibTeX