{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,20]],"date-time":"2025-10-20T10:31:03Z","timestamp":1760956263966,"version":"3.40.4"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319099668"},{"type":"electronic","value":"9783319099675"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-09967-5_15","type":"book-chapter","created":{"date-parts":[[2014,9,30]],"date-time":"2014-09-30T15:10:04Z","timestamp":1412089804000},"page":"252-271","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Input-Adaptive Algorithm for High Performance Sparse Fast Fourier Transform"],"prefix":"10.1007","author":[{"given":"Shuo","family":"Chen","sequence":"first","affiliation":[]},{"given":"Xiaoming","family":"Li","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,10,1]]},"reference":[{"key":"15_CR1","unstructured":"Akavia, A.: Deterministic sparse fourier approximation via fooling arithmetic progressions. In: The 23rd Conference on Learning Theory, pp. 381\u2013393 (2010)"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Akavia, A., Goldwasser, S., Safra, S.: Proving hard-core predicates using list decoding. In: The 44th Symposium on Foundations of Computer Science, pp. 146\u2013157. IEEE (2003)","DOI":"10.1109\/SFCS.2003.1238189"},{"issue":"4","key":"15_CR3","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1109\/TAU.1970.1162132","volume":"18","author":"L Bluestein","year":"1970","unstructured":"Bluestein, L.: A linear filtering approach to the computation of discrete Fourier transform. IEEE Trans. Audio Electroacoust. 18(4), 451\u2013455 (1970)","journal-title":"IEEE Trans. Audio Electroacoust."},{"issue":"19","key":"15_CR4","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0165-1684(90)90158-U","volume":"4","author":"P Duhamel","year":"1990","unstructured":"Duhamel, P., Vetterli, M.: Fast fourier transforms: a tutorial review and a state of the art. Signal Process. 4(19), 259\u2013299 (1990)","journal-title":"Signal Process."},{"issue":"2","key":"15_CR5","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1109\/JPROC.2004.840301","volume":"93","author":"M Frigo","year":"2005","unstructured":"Frigo, M., Johnson, S.G.: The design and implementation of fftw3. Proc. IEEE 93(2), 216\u2013231 (2005)","journal-title":"Proc. IEEE"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Gilbert, A., Guha, S., Indyk, P., Muthukrishnan, M., Strauss, M.: Near-optimal sparse fourier representations via sampling. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 152\u2013161. ACM (2002)","DOI":"10.1145\/509907.509933"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"Gilbert, A., Muthukrishnan, M., Strauss, M.: Improved time bounds for near-optimal space fourier representations. In: Proceedings of SPIE Wavelets XI (2005)","DOI":"10.1117\/12.615931"},{"issue":"2","key":"15_CR8","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1111\/j.2517-6161.1958.tb00300.x","volume":"20","author":"I Good","year":"1958","unstructured":"Good, I.: The interaction algorithm and practical Fourier analysis. J. R. Stat. Soc. Ser. B (Methodological) 20(2), 361\u2013372 (1958)","journal-title":"J. R. Stat. Soc. Ser. B (Methodological)"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Hassanieh, H., Indyk, P., Katabi, D., Price, E.: Simple and practical algorithm for sparse fourier transform. In: Proceedings of the 23th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1183\u20131194. ACM (2012)","DOI":"10.1137\/1.9781611973099.93"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Hassanieh, H., Indyk, P., Katabi, D., Price, E.: Nearly optimal sparse fourier transform. In: Proceedings of the 44th Symposium on Theory of Computing, pp. 563\u2013578. ACM (2012)","DOI":"10.1145\/2213977.2214029"},{"key":"15_CR11","unstructured":"Iwen, M.: AAFFT (Ann Arbor Fast Fourier Transform) (2008). http:\/\/sourceforge.net\/projects\/aafftannarborfa\/"},{"issue":"3","key":"15_CR12","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s10208-009-9057-1","volume":"10","author":"M Iwen","year":"2010","unstructured":"Iwen, M.: Combinatorial sublinear-time fourier algorithms. Found. Comput. Math. 10(3), 303\u2013338 (2010)","journal-title":"Found. Comput. Math."},{"issue":"2","key":"15_CR13","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D Knuth","year":"1977","unstructured":"Knuth, D., Morris, J., Pratt, V.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Li, L., Huang, W., Gu, I., Tian, Q.: Foreground object detection from videos containing complex background. In: Proceedings of the 11th ACM International Conference on Multimedia, pp. 2\u201310. ACM (2003)","DOI":"10.1145\/957013.957017"},{"key":"15_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/3-540-55719-9_79","volume-title":"Automata, Languages and Programming","author":"Y Mansour","year":"1992","unstructured":"Mansour, Y.: Randomized interpolation and approximation of sparse polynomials. In: Kuich, Werner (ed.) ICALP 1992. LNCS, vol. 623, pp. 261\u2013272. Springer, Heidelberg (1992)"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"Nukada, A., Matsuoka, S.: Learning decision trees using the fourier spectrum. In: Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis, pp. 455\u2013464. ACM (1991)","DOI":"10.1145\/103418.103466"},{"issue":"6","key":"15_CR17","doi-asserted-by":"publisher","first-page":"1107","DOI":"10.1109\/PROC.1968.6477","volume":"56","author":"C Rader","year":"1968","unstructured":"Rader, C.: Discrete Fourier transforms when the number of data samples is prime. Proc. IEEE 56(6), 1107\u20131108 (1968)","journal-title":"Proc. IEEE"}],"container-title":["Lecture Notes in Computer Science","Languages and Compilers for Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-09967-5_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T22:57:01Z","timestamp":1746399421000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-09967-5_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319099668","9783319099675"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-09967-5_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"1 October 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}