Not logged in.
Quick Search - Contribution
Contribution Details
| Type | Book Chapter |
| Scope | Discipline-based scholarship |
| Title | Single Point Incremental Fourier Transform on 2D Data Streams |
| Organization Unit | |
| Authors |
|
| Editors |
|
| Item Subtype | Original Work |
| Refereed | Yes |
| Status | Published in final form |
| Language |
|
| Booktitle | 2021 IEEE 37th International Conference on Data Engineering (ICDE) |
| ISBN | 978-1-7281-9184-3 |
| ISSN | 2375-026X |
| Place of Publication | New York |
| Publisher | IEEE Xplore |
| Page Range | 852 - 863 |
| Date | 2021 |
| 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 | https://ieeexplore.ieee.org/document/9458728 |
| Digital Object Identifier | 10.1109/ICDE51399.2021.00079 |
| Other Identification Number | merlin-id:20875 |
| Export |
BibTeX
EP3 XML (ZORA)
|
| Additional Information | Conference Location: Chania, Greece |