Dimitris Palyvos-Giannas
Skip Abstract Section
Abstract
Data streaming enables online monitoring of large and continuous event streams in Cyber-Physical Systems (CPSs). In such scenarios, fine-grained backward provenance tools can connect streaming query results to the source data producing them, allowing analysts to study the dependency/causality of CPS events. While CPS monitoring commonly produces many events, backward provenance does not help prioritize event inspection since it does not specify if an event's provenance could still contribute to future results.
To cover this gap, we introduce Ananke, a framework to extend any fine-grained backward provenance tool and deliver a live bipartite graph of fine-grained forward provenance. With Ananke, analysts can prioritize the analysis of provenance data based on whether such data is still potentially being processed by the monitoring queries. We prove our solution is correct, discuss multiple implementations, including one leveraging streaming APIs for parallel analysis, and show Ananke results in small overheads, close to those of existing tools for fine-grained backward provenance.
- Tyler Akidau, Alex Balikov, Kaya Bekiroğlu, Slava Chernyak, Josh Haberman, Reuven Lax, Sam McVeety, Daniel Mills, Paul Nordstrom, and Sam Whittle. 2013. MillWheel: fault-tolerant stream processing at internet scale. Proceedings of the VLDB Endowment 6, 11 (2013), 1033--1044. Google Scholar
Digital Library
- Tyler Akidau, Robert Bradshaw, Craig Chambers, Slava Chernyak, Rafael J Fer Andez-Moctezuma, Reuven Lax, Sam Mcveety, Daniel Mills, Frances Perry, Eric Schmidt, and Sam Whittle Google. 2015. The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing. VLDB 8, 12 (2015), 1792--1803. Google ScholarDigital Library
- Apache. 2020. Beam. Retrieved November 12, 2020 from https://beam.apache.org/Google Scholar
- Apache. 2020. Heron. Retrieved November 12, 2020 from https://heron.incubator.apache.org/Google Scholar
- Apache. 2020. Storm. Retrieved November 12, 2020 from http://storm.apache.org/Google Scholar
- Arvind Arasu, Mitch Cherniack, Eduardo Galvez, David Maier, Anurag S. Maskey, Esther Ryvkina, Michael Stonebraker, and Richard Tibbetts. 2004. Linear Road: A Stream Data Management Benchmark. In Proceedings of the Thirtieth International Conference on Very Large Data Bases - Volume 30 (Toronto, Canada) (VLDB '04). VLDB Endowment, Toronto, Canada, 480--491. http://dl.acm.org/citation.cfm?id=1316689.1316732 Google ScholarDigital Library
- Leilani Battle, Danyel Fisher, Robert DeLine, Mike Barnett, Badrish Chandramouli, and Jonathan Goldstein. 2016. Making Sense of Temporal Queries with Interactive Visualization. In Proceedings of the 2016 CHI Conference on Human Factors in Computing Systems - CHI '16. ACM Press, Santa Clara, California, USA, 5433--5443. Google ScholarDigital Library
- Paris Carbone, Asterios Katsifodimos, Stephan Ewen, Volker Markl, Seif Haridi, and Kostas Tzoumas. 2015. Apache Flink: Stream and batch processing in a single engine. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering 36, 4 (2015), 28--38.Google Scholar
- Badrish Chandramouli, Jonathan Goldstein, Mike Barnett, Robert Deline, Danyel Fisher, John C Platt, James F Terwilliger, and John Wernsing. 2015. Trill : A High-Performance Incremental Query Processor for Diverse Analytics. VLDB - Very Large Data Bases 8, 4 (2015), 401--412. Google ScholarDigital Library
- Ming-Fang Chang, John Lambert, Patsorn Sangkloy, Jagjeet Singh, Slawomir Bak, Andrew Hartnett, De Wang, Peter Carr, Simon Lucey, Deva Ramanan, et al. 2019. Argoverse: 3D Tracking and Forecasting With Rich Maps. In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). 8740--8749.Google ScholarCross Ref
- James Cheney, Laura Chiticariu, and Wang-Chiew Tan. 2007. Provenance in Databases: Why, How, and Where. Foundations and Trends in Databases 1, 4 (2007), 379--474. Google ScholarDigital Library
- Daniel Crawl, Jianwu Wang, and Ilkay Altintas. 2011. Provenance for MapReduce-Based Data-Intensive Workflows. In Proceedings of the 6th Workshop on Workflows in Support of Large-Scale Science (Seattle, Washington, USA) (WORKS '11). Association for Computing Machinery, New York, NY, USA, 21--30. Google ScholarDigital Library
- Yingwei Cui, Jennifer Widom, and Janet L. Wiener. 2000. Tracing the Lineage of View Data in a Warehousing Environment. ACM Transactions on Database Systems 25, 2 (June 2000), 179--227. Google ScholarDigital Library
- Wim De Pauw, Mihai Leţia, Buğra Gedik, Henrique Andrade, Andy Frenkiel, Michael Pfeifer, and Daby Sow. 2010. Visual Debugging for Stream Processing Applications. In Runtime Verification, Howard Barringer, Ylies Falcone, Bernd Finkbeiner, Klaus Havelund, Insup Lee, Gordon Pace, Grigore Roşu, Oleg Sokolsky, and Nikolai Tillmann (Eds.). Vol. 6418. Springer Berlin Heidelberg, Berlin, Heidelberg, 18--35. Google ScholarDigital Library
- Katarina Nielsen Dominiak and Anders Ringgaard Kristensen. 2017. Prioritizing alarms from sensor-based detection models in livestock production - A review on model performance and alarm reducing methods. Computers and Electronics in Agriculture 133 (2017), 46 -- 67. Google ScholarDigital Library
- Romaric Duvignau, Vincenzo Gulisano, Marina Papatriantafilou, and Vladimir Savic. 2019. Streaming Piecewise Linear Approximation for Efficient Data Management in Edge Computing. In Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing - SAC '19. ACM Press, Limassol, Cyprus, 593--596. Google ScholarDigital Library
- Bugra Gedik, Henrique Andrade, Kun-Lung Wu, Philip S. Yu, and Myungcheol Doo. 2008. SPADE: The Systems Declarative Stream Processing Engine. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data (SIGMOD '08). Association for Computing Machinery, New York, NY, USA, 1123--1134. Google ScholarDigital Library
- GitHub. 2020. Ananke Implementation. Retrieved November 12, 2020 from https://github.com/dmpalyvos/anankeGoogle Scholar
- Boris Glavic, Kyumars Sheykh Esmaili, Peter M. Fischer, and Nesime Tatbul. 2014. Efficient Stream Provenance via Operator Instrumentation. ACM Trans. Internet Technol. 14, 1, Article 7 (Aug. 2014), 26 pages. Google ScholarDigital Library
- Boris Glavic, Kyumars Sheykh Esmaili, Peter Michael Fischer, and Nesime Tatbul. 2013. Ariadne: Managing Fine-Grained Provenance on Data Streams. In Proceedings of the 7th ACM International Conference on Distributed Event-Based Systems (Arlington, Texas, USA) (DEBS '13). Association for Computing Machinery, New York, NY, USA, 39--50. Google ScholarDigital Library
- HardKernel. 2020. Odroid-XU4. Retrieved November 12, 2020 from http://www.hardkernel.comGoogle Scholar
- Bastian Havers, Romaric Duvignau, Hannaneh Najdataei, Vincenzo Gulisano, Marina Papatriantafilou, and Ashok Chaitanya Koppisetty. 2020. DRIVEN: A framework for efficient Data Retrieval and clustering in Vehicular Networks. Future Generation Computer Systems 107 (2020), 1--17.Google ScholarDigital Library
- Melanie Herschel, Ralf Diestelkämper, and Houssem Ben Lahmar. 2017. A Survey on Provenance: What for? What Form? What From? VLDB Journal 26, 6 (2017), 881--906. Google ScholarDigital Library
- Mohammad Rezwanul Huq, Andreas Wombacher, and Peter M.G. Apers. 2011. Adaptive Inference of Fine-grained Data Provenance to Achieve High Accuracy at Lower Storage Costs. IEEE Computer Society, USA, 202--209. Google ScholarDigital Library
- Jeong-Hyon Hwang, Ugur Cetintemel, and Stan Zdonik. 2007. Fast and Reliable Stream Processing over Wide Area Networks. In 2007 IEEE 23rd International Conference on Data Engineering Workshop. 604--613. Google ScholarDigital Library
- Jin Li, Kristin Tufte, Vladislav Shkapenyuk, Vassilis Papadimos, Theodore Johnson, and David Maier. 2008. Out-of-order processing: a new architecture for high-performance stream systems. Proceedings of the VLDB Endowment 1, 1 (2008), 274--288. Google ScholarDigital Library
- MongoDB. 2020. MongoDB. Retrieved November 12, 2020 from https://www.mongodb.comGoogle Scholar
- Hannaneh Najdataei, Yiannis Nikolakopoulos, Vincenzo Gulisano, and Marina Papatriantafilou. 2018. Continuous and Parallel LiDAR Point-Cloud Clustering. In 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS). IEEE Computer Society, Vienna, Austria, 671--684. Google ScholarCross Ref
- Neo4j. 2020. Neo4j. Retrieved November 12, 2020 from https://neo4j.com/Google Scholar
- Dimitris Palyvos-Giannas, Vincenzo Gulisano, and Marina Papatriantafilou. 2019. GeneaLog: Fine-grained data streaming provenance in cyber-physical systems. Parallel Comput. 89 (2019), 102552.Google ScholarDigital Library
- Dimitris Palyvos-Giannas, Vincenzo Gulisano, and Marina Papatriantafilou. 2019. Haren: A Framework for Ad-Hoc Thread Scheduling Policies for Data Streaming Applications. In Proceedings of the 13th ACM International Conference on Distributed and Event-Based Systems (DEBS '19). ACM, Darmstadt, Germany, 19--30. Google ScholarDigital Library
- Fabio Pasqualetti, Florian Dörfler, and Francesco Bullo. 2013. Attack Detection and Identification in Cyber-Physical Systems. IEEE Trans. Automat. Control 58, 11 (2013), 2715--2729.Google ScholarCross Ref
- PostgreSQL. 2020. PostgreSQL. Retrieved November 12, 2020 from https://www.postgresql.orgGoogle Scholar
- Saeed Salah, Gabriel Maciá-Fernández, and Jesús E. Díaz-Verdejo. 2013. A model-based survey of alert correlation techniques. Computer Networks 57, 5 (2013), 1289 -- 1317. Google ScholarDigital Library
- SQLite. 2020. SQLite. Retrieved November 12, 2020 from https://www.sqlite.org/Google Scholar
- Michael Stonebraker, Uǧur Çetintemel, and Stan Zdonik. 2005. The 8 requirements of real-time stream processing. ACM Sigmod Record 34, 4 (2005), 42--47. Google ScholarDigital Library
- Joris van Rooij, Vincenzo Gulisano, and Marina Papatriantafilou. 2018. LoCo-Volt: Distributed Detection of Broken Meters in Smart Grids through Stream Processing. In Proceedings of the 12th ACM International Conference on Distributed and Event-Based Systems (Hamilton, New Zealand) (DEBS '18). Association for Computing Machinery, New York, NY, USA, 171--182. Google ScholarDigital Library
- Chad Vicknair, Michael Macias, Zhendong Zhao, Xiaofei Nan, Yixin Chen, and Dawn Wilkins. 2010. A Comparison of a Graph Database and a Relational Database: A Data Provenance Perspective. In Proceedings of the 48th Annual Southeast Regional Conference (Oxford, Mississippi) (ACM SE '10). Association for Computing Machinery, New York, NY, USA, Article 42, 6 pages. Google ScholarDigital Library
- Nithya N. Vijayakumar and Beth Plale. 2006. Towards Low Overhead Provenance Tracking in Near Real-Time Stream Filtering. In Provenance and Annotation of Data, Luc Moreau and Ian Foster (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 46--54. Google ScholarDigital Library
- Min Wang, Marion Blount, John Davis, Archan Misra, and Daby Sow. 2007. A Time-and-value Centric Provenance Model and Architecture for Medical Event Streams. In Proceedings of the 1st ACM SIGMOBILE International Workshop on Systems and Networking Support for Healthcare and Assisted Living Environments (San Juan, Puerto Rico) (HealthNet '07). ACM, New York, NY, USA, 95--100. Google ScholarDigital Library
- Yu Zheng, Xing Xie, and Wei-Ying Ma. 2010. Geolife: A collaborative social networking service among user, location and trajectory. IEEE Data Eng. Bull. 33, 2 (2010), 32--39.Google Scholar
Index Terms
- Ananke: a streaming framework for live forward provenance
Index terms have been assigned to the content through auto-classification.
Recommendations
OPQL: A First OPM-Level Query Language for Scientific Workflow Provenance
SCC '11: Proceedings of the 2011 IEEE International Conference on Services ComputingProvenance, which is one kind of metadata that captures the derivation history of a data product, including its original data sources, intermediate products, and the steps that were applied to produce it, has become increasingly important in services ...
Editorial: OPQL: Querying scientific workflow provenance at the graph level
Provenance has become increasingly important in scientific workflows to understand, verify, and reproduce the result of scientific data analysis. Most existing systems store provenance data in provenance stores with proprietary provenance data models ...
Comments