SLIPstream: scalable low-latency interactive perception on streaming data

ABSTRACT

A critical problem in implementing interactive perception applications is the considerable computational cost of current computer vision and machine learning algorithms, which typically run one to two orders of magnitude too slowly to be used interactively. Fortunately, many of these algorithms exhibit coarse-grained task and data parallelism that can be exploited across machines. The SLIPstream project focuses on building a highly-parallel runtime system called Sprout that can harness the computing power of a cluster to execute perception applications with low latency. This paper makes the case for using clusters for perception applications, describes the architecture of the Sprout runtime, and presents two compute-intensive yet interactive applications.

REFERENCES

• 1: Visual Object Instance Recognition. http://people.csail.mit.edu/rahimi/projects/objrec/.
• 2: D. J. Abadi, Y. Ahmad, M. Balazinska, U. Çetintemel, M. Cherniack, J. Hwang, W. Lindner, A. S. Maskey, A. Rasin, E. Ryvkina, N. Tatbul, Y. Xing, and S. Zdonik. The Design of the Borealis Stream Processing Engine. In Proc. Innovative Data Systems Research, 2005.
• 3: J. Allard, V. Gouranton, L. Lecointre, S. Limet, E. Melin, B. Raffin, and S. Robert. FlowVR: a middleware for large scale virtual reality applications. In Proc. Euro-Par, 2004.
• 4: Lisa Amini , Henrique Andrade , Ranjita Bhagwan , Frank Eskesen , Richard King , Philippe Selo , Yoonho Park , Chitra Venkatramani, SPC: a distributed, scalable platform for data mining, Proceedings of the 4th international workshop on Data mining standards, services and platforms, p.27-37, August 20-20, 2006, Philadelphia, Pennsylvania [doi>10.1145/1289612.1289615]
• 5: Aaron F. Bobick , James W. Davis, The Recognition of Human Movement Using Temporal Templates, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.3, p.257-267, March 2001 [doi>10.1109/34.910878]
• 6: Ian Buck , Tim Foley , Daniel Horn , Jeremy Sugerman , Kayvon Fatahalian , Mike Houston , Pat Hanrahan, Brook for GPUs: stream computing on graphics hardware, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 7: S. Chandrasekaran, O. Cooper, A. Deshpande, M. J. Franklin, J. M. Hellerstein, W. Hong, S. Krishnamurthy, S. Madden, V. Raman, F. Reiss, and M. Shah. TelegraphCQ: Continuous Dataflow Processing for an Uncertain World. In Proceedings of the Conference on Innovative Data Systems Research, 2003.
• 8: M. Cherniack, H. Balakrishnan, M. Balazinska, D. Carney, U. Cetintemel, Y. Xing, and S. Zdonik. Scalable Distributed Stream Processing. In Proceedings of the Conference on Innovative Data Systems Research, 2003.
• 9: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Communications of the ACM, v.51 n.1, January 2008 [doi>10.1145/1327452.1327492]
• 10: P. Dollar, V. Rabaud, G. Cottrell, and S. Belongie. Behavior recognition via sparse spatio-temporal features. In IEEE Workshop on PETS, 2005.
• 11: Lewis Girod , Yuan Mei , Ryan Newton , Stanislav Rost , Arvind Thiagarajan , Hari Balakrishnan , Samuel Madden, XStream: a Signal-Oriented Data Stream Management System, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.1180-1189, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497527]
• 12: Michael I. Gordon , William Thies , Saman Amarasinghe, Exploiting coarse-grained task, data, and pipeline parallelism in stream programs, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 13: Jayanth Gummaraju , Joel Coburn , Yoshio Turner , Mendel Rosenblum, Streamware: programming general-purpose multicore processors using streams, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA
• 14: J. Hartigan and M. Wang. A k-means clustering algorithm. Applied Statistics, 28:100--108, 1979.
• 15: Michael Isard , Mihai Budiu , Yuan Yu , Andrew Birrell , Dennis Fetterly, Dryad: distributed data-parallel programs from sequential building blocks, Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, March 21-23, 2007, Lisbon, Portugal
• 16: Theodore Johnson , Muthu S. Muthukrishnan , Vladislav Shkapenyuk , Oliver Spatscheck, Query-aware partitioning for monitoring massive network data streams, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376730]
• 17: Ujval J. Kapasi , Scott Rixner , William J. Dally , Brucek Khailany , Jung Ho Ahn , Peter Mattson , John D. Owens, Programmable Stream Processors, Computer, v.36 n.8, p.54-62, August 2003 [doi>10.1109/MC.2003.1220582]
• 18: Yan Ke , Rahul Sukthankar , Martial Hebert, Efficient Visual Event Detection Using Volumetric Features, Proceedings of the Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1, p.166-173, October 17-20, 2005 [doi>10.1109/ICCV.2005.85]
• 19: Y. Ke, R. Sukthankar, and M. Hebert. Event detection in crowded videos. In Proceedings of International Conference on Computer Vision, 2007.
• 20: Kathleen Knobe , James M. Rehg , Arun Chauhan , Rishiyur S. Nikhil , Umakishore Ramachandran, Scheduling constrained dynamic applications on clusters, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.46-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331578]
• 21: Ivan Laptev , Tony Lindeberg, Space-time Interest Points, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.432, October 13-16, 2003
• 22: J.-D. Lesage and B. Raffin. A Hierarchical Component Model for Large Parallel Interactive Applications. The Journal of Supercomputing, July 2008.
• 23: David G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, International Journal of Computer Vision, v.60 n.2, p.91-110, November 2004 [doi>10.1023/B:VISI.0000029664.99615.94]
• 24: U. Ramachandran, R. Nikhil, J. M. Rehg, Y. Angelov, A. Paul, S. Adhikari, K. Mackenzie, N. Harel, and K. Knobe. Stampede: a cluster programming middleware for interactive stream-oriented applications. IEEE Trans. Parallel and Distributed Systems, 14(11), 2003.
• 25: Christian Schuldt , Ivan Laptev , Barbara Caputo, Recognizing Human Actions: A Local SVM Approach, Proceedings of the Pattern Recognition, 17th International Conference on (ICPR'04) Volume 3, p.32-36, August 23-26, 2004 [doi>10.1109/ICPR.2004.747]
• 26: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 27: P. Viola and M. Jones. Rapid object detection using a boosted cascade of simple features. In Proc. Computer Vision and Pattern Recognition, 2001.
• 28: Joel Wolf , Nikhil Bansal , Kirsten Hildrum , Sujay Parekh , Deepak Rajan , Rohit Wagle , Kun-Lung Wu , Lisa Fleischer, SODA: an optimizing scheduler for large-scale stream-based distributed computer systems, Proceedings of the 9th ACM/IFIP/USENIX International Conference on Middleware, December 01-05, 2008, Leuven, Belgium
• 29: C. Wren, F. Sparacino, A. Azarbayejani, T. Darrell, T. Starner, A. Kotani, C. Chao, M. Hlavac, K. Russell, and A. Pentland. Perceptive spaces for performance and entertainment: Untethered interaction using computer vision and audition. Applied AI, 11(4), 1996.
• 30: D. Zhang, Z.-Z. Li, H. Song, and L. Liu. A Programming Model for an Embedded Media Processing Architecture. In Embedded Computer Systems: Architectures, Modeling, and Simulation, 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.0 General

General Terms:
Algorithms, Design, Performance

Keywords:
cluster applications, computational perception, multimedia, parallel computing, sensing, stream processing