High performance FPGA and GPU complex pattern matching over spatio-temporal streams

详细信息    查看全文

• 作者：Roger Moussalli (1)
  Ildar Absalyamov (2)
  Marcos R. Vieira (3)
  Walid Najjar (2)
  Vassilis J. Tsotras (2)
  
  1. IBM T.J. Watson Research Center ; 1101 Kitchawan Rd. ; Yorktown Heights ; NY ; USA
  2. Department of Computer Science and Engineering ; University of California ; Riverside ; 900 University Ave. ; Riverside ; CA ; USA
  3. IBM Research - Brazil ; Av. Pasteur 138 ; 146 ; Rio de Janeiro ; RJ ; Brazil
  
• 关键词：Spatio ; temporal ; Spatial ; Temporal ; Database ; FPGA ; GPU ; Acceleration ; Pattern ; Matching
• 刊名：GeoInformatica
• 出版年：2015
• 出版时间：April 2015
• 年：2015
• 卷：19
• 期：2
• 页码：405-434
• 全文大小：3,026 KB
• 参考文献：1. Absalyamov I, Moussalli R, Tsotras VJ, Najjar WA (2013) High-performance XML twig filtering using GPUs. In: Proceedings of the ADMS, pp 13鈥?4
  2. Aggarwal C, Agrawal D (2003) On nearest neighbor indexing of nonlinear trajectories. In: Proceedings of the ACM PODS, pp 252鈥?59
  3. Bakkum P, Skadron K (2010) Accelerating SQL database operations on a GPU with CUDA. In: Proceedings of the GPGPU, pp 94鈥?03. ACM
  4. Beier F, Kilias T, Sattler KU (2012) GiST scan acceleration using coprocessors. In: Proceedings of the DaMoN, pp 63鈥?9
  5. Cascarano, N, Rolando, P, Risso, F, Sisto, R (2010) iNFAnt: NFA pattern matching on GPGPU devices. SIGCOMM Comput Commun Rev 40: pp. 20-26 CrossRef
  6. Cazalas, J, Guha, RK (2012) Performance Modeling of Spatio-Temporal Algorithms Over GEDS Framework. IJGHPC 4: pp. 63-84
  7. (2013) Chorochronos: http://www.chorochronos.org
  8. Erwig, M, Schneider, M (2002) Spatio-Temporal Predicates. IEEE Trans Knowl Data Eng 14: pp. 881-901 CrossRef
  9. Fender J, Rose J (2003) A High-Speed Ray Tracing Engine Built on a Field-Programmable System. In: Proceedings of the IEEE FPT, pp 188鈥?95
  10. Hadjieleftheriou M, Kollios G, Bakalov P, Tsotras VJ (2005) Complex Spatio-temporal Pattern Queries. In: Proceedings of the VLDB, pp 877鈥?88
  11. Hadjieleftheriou, M, Kollios, G, Tsotras, VJ, Gunopulos, D (2006) Indexing Spatiotemporal Archives. VLDB J 15: pp. 143-164 CrossRef
  12. He B, Yang K, Fang R, Lu M, Govindaraju N, Luo Q, Sander P (2008) Relational joins on graphics processors. In: Proceedings of the ACM SIGMOD, pp 511鈥?24. ACM
  13. Heckbert PS (1994) Graphics Gems IV, vol 4. Morgan Kaufmann
  14. Kim C, et al. (2010) FAST: fast architecture sensitive tree search on modern CPUs and GPUs. In: Proceedings of the ACM SIGMOD, pp 339鈥?50. ACM
  15. Kim SS, Nam SW, Lee IH (2007) Fast Ray-Triangle Intersection Computation Using Reconfigurable Hardware. In: Computer Vision/Computer Graphics Collaboration Techniques, LNCS, vol 4418, pp 70鈥?1. Springer
  16. Knuth, D, Morris, J, Pratt, V (1977) Fast Pattern Matching in Strings. SIAM. J Comput 6: pp. 323-350
  17. Kumar S, et al (2006) Algorithms to Accelerate Multiple Regular Expressions Matching for Deep Packet Inspection. In: Proceedings of the ACM SIGCOMM, pp 339鈥?50
  18. Mitra A, Najjar W, Bhuyan L (2007) Compiling PCRE to FPGA for Accelerating SNORT IDS. In: Proceedings of the ACM/IEEE ANCS, pp 127鈥?36
  19. Mokhtar H, Su J, Ibarra O (2002) On Moving Object Queries. In: Proceedings of the ACM PODS, pp 188鈥?98
  20. Moussalli R, Halstead R, Salloum M, Najjar W, Tsotras VJ (2011) Efficient XML path filtering using GPUs. In: Proceedings of the ADMS
  21. Moussalli R, Najjar W, Luo X, Khan A (2013) A High Throughput No-Stall Golomb-Rice Hardware Decoder. In: Proceedings of the IEEE FCCM, pp 65鈥?2
  22. Moussalli R, Salloum M, Najjar W, Tsotras VJ (2010) Accelerating XML Query Matching Through Custom Stack Generation on FPGAs. In: HiPEAC, pp 141鈥?55
  23. Moussalli R, Salloum M, Najjar W, Tsotras VJ (2011) Massively Parallel XML Twig Filtering Using Dynamic Programming on FPGAs. In: Proceedings of the IEEE ICDE
  24. Moussalli R, Vieira MR, Najjar WA, Tsotras VJ (2013) Stream-mode fpga acceleration of complex pattern trajectory querying. In: Proceedings of the SSTD, pp 201鈥?22
  25. Mouza, C, Rigaux, P (2005) Mobility Patterns. Geoinformatica 9: pp. 297-319 CrossRef
  26. du Mouza C, Rigaux P, Scholl M (2005) Efficient evaluation of parameterized pattern queries. In: Proceedings of the ACM CIKM, pp 728鈥?35
  27. Nvidia (2014) Nvidia GPU Programming Guide. http://docs.nvidia.com/cuda/
  28. Pfoser D, Jensen C, Theodoridis Y (2000) Novel Approaches in Query Processing for Moving Object Trajectories. In: Proceedings of the VLDB, pp 395鈥?06
  29. Pico Computing M-Series Modules (2012). http://picocomputing.com/m-series/m-501
  30. Piorkowski M, Sarafijanovoc-Djukic N, Grossglauser M (2009) A Parsimonious Model of Mobile Partitioned Networks with Clustering. In: Proceedings of the COMSNETS
  31. Sadoghi, M (2010) Efficient Event Processing Through Reconfigurable Hardware for Algorithmic Trading. Proc. of the VLDB Endow 3: pp. 1525-1528 CrossRef
  32. Sakr MA, G眉ting RH (2009) Spatiotemporal Pattern Queries in Secondo. In: Proceedings of the SSTD, pp 422鈥?26
  33. Schmittler J, Woop S, Wagner D, Paul WJ, Slusallek P (2004) Realtime Ray Tracing of Dynamic Scenes on an FPGA Chip. In: Proceedings of the ACM HWWS, pp 95鈥?06
  34. Sidhu R, Prasanna VK (2001) Fast Regular Expression Matching Using FPGAs. In: Proceedings of the IEEE FCCM, pp 227鈥?38
  35. Tao Y, Papadias D (2001) MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries. In: Proceedings of the VLDB, pp 431鈥?40
  36. Tao Y, Papadias D, Shen Q (2002) Continuous Nearest Neighbor Search. In: Proceedings of the VLDB, pp 287鈥?98
  37. Teubner J, M眉ller R, Alonso G (2010) FPGA Acceleration for the Frequent Item Problem. In: Proceedings of the IEEE ICDE, pp 669鈥?80
  38. Vieira MR, Bakalov P, Tsotras VJ (2010) Querying Trajectories Using Flexible Patterns. In: Proceedings of the EDBT, pp 406鈥?17
  39. Vieira MR, Bakalov P, Tsotras VJ (2011) FlexTrack: a System for Querying Flexible Patterns in Trajectory Databases. In: Proceedings of the SSTD, pp 475鈥?80
  40. Woods, L, Teubner, J, Alonso, G (2010) Complex Event Detection at Wire Speed with FPGAs. Proc. of the VLDB Endow 3: pp. 660-669 CrossRef
  41. Zheng, Y, Xie, X, Ma, WY (2010) GeoLife: A Collaborative Social Networking Service Among User, Location and Trajectory. IEEE Data Eng Bull 33: pp. 32-40
  
• 刊物类别：Earth and Environmental Science
• 刊物主题：Geography
  Geographical Information Systems and Cartography
  Data Structures, Cryptology and Information Theory
  Computer Science, general
  Information Storage and Retrieval
  Multimedia Information Systems
  
• 出版者：Springer Netherlands
• ISSN：1573-7624

文摘

The wide and increasing availability of collected data in the form of trajectories has led to research advances in behavioral aspects of the monitored subjects (e.g., wild animals, people, and vehicles). Using trajectory data harvested by devices, such as GPS, RFID and mobile devices, complex pattern queries can be posed to select trajectories based on specific events of interest. In this paper, we present a study on FPGA- and GPU-based architectures processing complex patterns on streams of spatio-temporal data. Complex patterns are described as regular expressions over a spatial alphabet that can be implicitly or explicitly anchored to the time domain. More importantly, variables can be used to substantially enhance the flexibility and expressive power of pattern queries. Here we explore the challenges in handling several constructs of the assumed pattern query language, with a study on the trade-offs between expressiveness, scalability and matching accuracy. We show an extensive performance evaluation where FPGA and GPU setups outperform the current state-of-the-art (single-threaded) CPU-based approaches, by over three orders of magnitude for FPGAs (for expressive queries) and up to two orders of magnitude for certain datasets on GPUs (and in some cases slowdown). Unlike software-based approaches, the performance of the proposed FPGA and GPU solutions is only minimally affected by the increased pattern complexity.