Practical Algorithms for Tracking Database Join Sizes
作者： Sumit Ganguly , Deepanjan Kesh , Chandan Saha
DOI: 10.1007/11590156_24
关键词:
摘要: We present novel algorithms for estimating the size of natural join two data streams that have efficient update processing times and provide excellent quality estimates.
springer.com
springerlink.com
acm.org 参考文章(18)
Moses Charikar, Kevin Chen, Martin Farach-Colton, Finding Frequent Items in Data Streams international colloquium on automata languages and programming. ,vol. 312, pp. 693- 703 ,(2002) , 10.1016/S0304-3975(03)00400-6
Arvind Arasu, Brian Babcock, Shivnath Babu, John Cieslewicz, Mayur Datar, Keith Ito, Rajeev Motwani, Utkarsh Srivastava, Jennifer Widom, STREAM: The Stanford Data Stream Management System Data-Centric Systems and Applications. pp. 317- 336 ,(2016) , 10.1007/978-3-540-28608-0_16
Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider, Practical selectivity estimation through adaptive sampling international conference on management of data. ,vol. 19, pp. 1- 11 ,(1990) , 10.1145/93597.93611
Wen-Chi Hou, Gultekin Ozsoyoglu, Baldeo K. Taneja, Statistical estimators for relational algebra expressions symposium on principles of database systems. pp. 276- 287 ,(1988) , 10.1145/308386.308455
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
Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy, Tracking join and self-join sizes in limited storage symposium on principles of database systems. pp. 10- 20 ,(1999) , 10.1145/303976.303978
Mikkel Thorup, Yin Zhang, Tabulation based 4-universal hashing with applications to second moment estimation symposium on discrete algorithms. pp. 615- 624 ,(2004) , 10.5555/982792.982884
Graham Cormode, S. Muthukrishnan, An improved data stream summary: the count-min sketch and its applications Journal of Algorithms. ,vol. 55, pp. 58- 75 ,(2005) , 10.1016/J.JALGOR.2003.12.001
Noga Alon, Yossi Matias, Mario Szegedy, The Space Complexity of Approximating the Frequency Moments Journal of Computer and System Sciences. ,vol. 58, pp. 137- 147 ,(1999) , 10.1006/JCSS.1997.1545
Sumit Ganguly, Phillip B Gibbons, Yossi Matias, Avi Silberschatz, None, Bifocal sampling for skew-resistant join size estimation international conference on management of data. ,vol. 25, pp. 271- 281 ,(1996) , 10.1145/233269.233340