Approximate join processing over data streams
作者： Abhinandan Das , Johannes Gehrke , Mirek Riedewald
关键词:
摘要: We consider the problem of approximating sliding window joins over data streams in a stream processing system with limited resources. In our model, we deal resource constraints by shedding load form dropping tuples from streams. first discuss alternate architectural models for join processing, and survey suitable measures quality an approximation set-valued query result. then number generated result as measure, give optimal offline fast online algorithms it. thorough experimental study synthetic real show efficacy solutions. For applications demand exact results introduce new Archive-metric which captures amount work needed to complete case are archived later processing.
usc.edu
core.ac.uk
acm.org
neu.edu 
sci-hub.se 参考文章(28)
Flip Korn, S. Muthukrishnan, Divesh Srivastava, Reverse nearest neighbor aggregates over data streams very large data bases. pp. 814- 825 ,(2002) , 10.1016/B978-155860869-6/50077-9
Philippe Bonnet, Johannes Gehrke, Praveen Seshadri, Towards Sensor Database Systems mobile data management. pp. 3- 14 ,(2001) , 10.1007/3-540-44498-X_1
Amol Deshpande, Joseph M. Hellerstein, Vijayshankar Raman, Samuel Madden, Mehul A. Shah, Sirish Chandrasekaran, Michael J. Franklin, Kris Hildrum, Adaptive Query Processing: Technology in Evolution. IEEE Data(base) Engineering Bulletin. ,vol. 23, pp. 7- 18 ,(2000)
Yannis E. Ioannidis, Viswanath Poosala, Histogram-Based Approximation of Set-Valued Query-Answers very large data bases. pp. 174- 185 ,(1999)
Andrew V Goldberg, An Efficient Implementation of a Scaling Minimum-Cost Flow Algorithm Journal of Algorithms. ,vol. 22, pp. 1- 29 ,(1997) , 10.1006/JAGM.1995.0805
Surajit Chaudhuri, Rajeev Motwani, Vivek Narasayya, On random sampling over joins ACM SIGMOD Record. ,vol. 28, pp. 263- 274 ,(1999) , 10.1145/304181.304206
Brian Babcock, Shivnath Babu, Mayur Datar, Rajeev Motwani, Jennifer Widom, Models and issues in data stream systems symposium on principles of database systems. pp. 1- 16 ,(2002) , 10.1145/543613.543615
Mayur Datar, Aristides Gionis, Piotr Indyk, Rajeev Motwani, Maintaining Stream Statistics over Sliding Windows SIAM Journal on Computing. ,vol. 31, pp. 1794- 1813 ,(2002) , 10.1137/S0097539701398363
Piotr Indyk, Aristides Gionis, Rajeev Motwani, Mayur Datar, Maintaining stream statistics over sliding windows: (extended abstract) symposium on discrete algorithms. pp. 635- 644 ,(2002) , 10.5555/545381.545466
Nitin Thaper, Sudipto Guha, Piotr Indyk, Nick Koudas, Dynamic multidimensional histograms Proceedings of the 2002 ACM SIGMOD international conference on Management of data - SIGMOD '02. pp. 428- 439 ,(2002) , 10.1145/564691.564741