دوره 14، شماره 3 - ( 9-1396 )
جلد 14 شماره 3 صفحات 22-3 |
برگشت به فهرست نسخه ها
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Safaei A. Providing a Dynamic Technique for Answering Ad-hoc Continuous Aggregate. JSDP 2017; 14 (3) :3-22
URL: http://jsdp.rcisp.ac.ir/article-1-486-fa.html
URL: http://jsdp.rcisp.ac.ir/article-1-486-fa.html
مسافری مهدی، صفائی علی‌اصغر. ارائه روشی پویا جهت پاسخ به پرس‌وجوهای
پیوسته تجمّعی اقتضایی
. پردازش علائم و داده‌ها. 1396; 14 (3) :3-22
دانشگاه تربیت مدرس
چکیده: (4929 مشاهده)
جریان‌های داده دنباله‌های نامتناهی، سریع، متغیر با زمان و با نرخ ورود انفجاری از نشان‌های داده هستند که به‌طورمعمول نیاز دارند به‌صورت برخط و به‌طورتقریبی بی‌درنگ پردازش شوند. بر این اساس، الگوریتم‌های پردازش جریان‌های داده و اجرای پرس‌وجوها روی جریان داده‌ها بیش‌تر تک‌گذره هستند. اجرای این الگوریتم‌های تک‌گذره با محدودیت‌ها و چالش‌هایی از قبیل محدودیت در حافظه، زمان‌بندی، و دقت پاسخ‌ها مواجه است. این چالش‌ها به‌ویژه در شرایطی که پرس‌وجوی مورد نظر از قبل تعیین و مشخص نشده باشد و به‌صورت اقتضایی، پس از ارسال جریان داده ارائه شود، به‌مراتب جد‌ی‌تر و حل آن‌ها دشوارتر خواهد بود. در این مقاله، برای پردازش پرس‌وجوهای تجمعی که به‌طور پیوسته روی جریان‌های داده اجرا خواهند شد و البته به‌طور اقتضایی ارائه می‌شوند، راه حلی مبتنی بر ساختار درختواره و نگهداشت نتایج تجمعی معرفی شده است. نکته مهم در این روش، برقراری برخط بودن در تمام مراحل ساخت، نگهداری و بهره‌برداری از درخت است. برای تأمین برخط بودن فرایند پاسخ به پرس‌وجو، کافی است تمامی پاسخ‌های محتمل را نگهداری کنیم؛ اما برای حفظ برخط‌بودن فرایند ساخت و نگهداری درخت، با توجه به ویژگی‌های ذاتی جریان داده ناچاریم برخی پاسخ‌ها را نگهداری کنیم. بدین ترتیب، هدف و مسئله اساسی آن است که دست‌کم پاسخ‌های انتخابی برای ذخیره در قالب درختواره را به مجموعه پاسخ‌های مورد نیاز برای پرس‌وجوهای اقتضایی رسیده نزدیک‌تر کنیم. ساختار درخت تجمعی پیشوندی پیشنهادی که به‌صورت پویا ایجاد، نگهداری، مدیریت و در پردازش پرس‌وجوها استفاده می‌شود، تشریح و صحت عملکرد آن به‌صورت عملی مورد ارزیابی قرار گرفته که نتایج حاکی از کارآمد‌بودن آن برای به‌کارگیری در پردازش برخط پرس‌وجوهای پیوسته تجمعی اقتضایی روی جریان‌های داده است.
نوع مطالعه: پژوهشي |
موضوع مقاله:
مقالات پردازش داده‌های رقمی
دریافت: 1394/11/20 | پذیرش: 1395/8/8 | انتشار: 1396/11/9 | انتشار الکترونیک: 1396/11/9
دریافت: 1394/11/20 | پذیرش: 1395/8/8 | انتشار: 1396/11/9 | انتشار الکترونیک: 1396/11/9
فهرست منابع
1. [1] M. Chen, S. Mao and Y. Liu, "Big Data: A Survey," Mobile Networks and Applications, vol. 19, no. 2, pp. 171-209, April 2014. [DOI:10.1007/s11036-013-0489-0]
2. [2] C. L. Philip Chen and C. Y. Zhang, "Data-intensive applications, challenges, techniques and technologies: A survey on Big Data," Elsevier, vol. 275, pp. 314-347, January 2014.
3. [3] R. Motwani, J. Widom, A. Arasu, B. Babcock, S. Babu, M. Datar, G. Manku, C. Olston, J. Rosenstein and R. Varma, "Query Processing, Resource Management, and Approximation in a Data Stream Management System," in Proceedings of the 2003 CIDR Conference, Asilomar, 2003.
4. [4] صباغ‌گل ریحانه، دانشپور نگین. بهبود الگوریتم انتخاب دید در پایگاه داده تحلیلی با استفاده از یافتن پرس‌جوهای پرتکرار. پردازش علائم و داده‌ها. 1396؛ 14 (1): 29-40.
5. [4] R. Sabbagh Go and N. Daneshpour, "An Improved View Selection Algorithm in Data Warehouses by Finding Frequent Queries," JSDP, vol. 14, no. 1, pp. 29-40, 2017. [DOI:10.18869/acadpub.jsdp.14.1.29]
6. [5] M. Cho, J. Pei and K. Wang, "Answering ad hoc aggregate queries from data streams using prefix aggregate trees," Knowledge and Information Systems, vol. 12, no. 3, pp. 301 - 329, August 2007. [DOI:10.1007/s10115-006-0024-8]
7. [6] C. J. Hahn, S. G. Warren and R. Eastman, "Extended Edited Synoptic Cloud Reports from Ships and Land Stations Over the Globe," 1952-2009. [Online]. Available: http://cdiac.ornl.gov/epubs/ndp/ndp026c/ndp026c.html.
8. [7] K. Beyer and R. Ramakrishnan, "Bottom-up computation of sparse and Iceberg CUBE," in SIGMOD '99 Proceedings of the 1999 ACM SIGMOD international conference on Management of data, New York, 1999. [DOI:10.1145/304182.304214]
9. [8] K. A. Ross and D. Srivastava, "Fast Computation of Sparse Datacubes," in VLDB '97 Proceedings of the 23rd International Conference on Very Large Data Bases, San Francisco, 1997.
10. [9] Y. Sismanis, A. Deligiannakis, N. Roussopoulos and Y. Kotidis, "Dwarf: Shrinking the PetaCube," in SIGMOD '02 Proceedings of the 2002 ACM SIGMOD international conference on Management of data, New York, 2002. [DOI:10.1145/564691.564745]
11. [10] W. Wang, J. Feng, H. Lu and J. Yu, "Condensed cube: an effective approach to reducing data cube size," in 18th International Conference on Data Engineering, San Fransisco,CA, 2002. [DOI:10.1109/ICDE.2002.994705]
12. [11] J. Li, D. Maier, K. Tufte, V. Papadimos and P. A. Tucker, "Semantics and evaluation techniques for window aggregates in data streams," in International Conference on Management of Data, New York, 2005. [DOI:10.1145/1066157.1066193]
13. [12] S. Madden, M. J. Franklin, J. M. Hellerstein and W. Hong, "TAG: a Tiny AGgregation Service for Ad- Hoc Sensor Networks," ACM SIGOPS Operating Systems Review - OSDI '02: Proceedings of the 5th symposium on Operating systems design and implementation, vol. 36, no. SI, pp. 131-146, 2002. [DOI:10.1145/1060289.1060303]
14. [13] J. Considine, F. Li, G. Kollios and J. Byers, "Approximate aggregation techniques for sensor databases," in ICDE '04 Proceedings of the 20th International Conference on Data Engineering, Washington, DC, USA, 2004. [DOI:10.1109/ICDE.2004.1320018]
15. [14] C. Intanagonwiwat, R. Govindan and D. Estrin, "Directed diffusion: a scalable and robust communication paradigm for sensor networks," in MobiCom '00 Proceedings of the 6th annual international conference on Mobile computing and networking, New York, NY, USA, 2000. [DOI:10.1145/345910.345920]
16. [15] Y. Yao and J. Gehrke, "The cougar approach to in-network query processing in sensor networks," ACM SIGMOD Record, vol. 31, no. 3, pp. 9-18, September 2002. [DOI:10.1145/601858.601861]
17. [16] Y. Yao and J. Gehrke, "Query Processing for Sensor Networks," Asilomar, 2003.
18. [17] J. Zhao, R. Govindan and D. Estrin, "Computing Aggregates for Monitoring Wireless Sensor Networks," in SNPA, 2003.
19. [18] S. Madden, M. J. Franklin, J. M. Hellerstein and W. Hong, "The Design of an Acquisitional Query Processor for Sensor Networks," in International Conference on Management of Data, New York, NY, USA, 2003. [DOI:10.1145/872757.872817]
20. [19] A. A. Safaei, M. Haghjoo and F. Abdi, "Semantic Cache Schema for Query Processing in Mobile Databases," in IEEE ICDIM'08, London, UK, 2008. [DOI:10.1109/ICDIM.2008.4746755]
21. [20] A. A. Safaei, K. Mehran, M. Haghjoo and K. Izadi, "Caching Intermediate Results for Multiple-Query Optimization," in 5th ACS/IEEE International Conference on Computer Systems and Applications (AICCSA-2007), Jordan, 2007. [DOI:10.1109/AICCSA.2007.370914]
22. [21] P. Flajolet and G. N. Martin, "Probabilistic counting algorithms for data base applications," Journal of Computer and System Sciences, vol. 31, no. 2, pp. 182 - 209, 1985. [DOI:10.1016/0022-0000(85)90041-8]
23. [22] N. Alon, Y. Matias and M. Szegedy, "The space complexity of approximating the frequency moments," JOURNAL OF COMPUTER AND SYSTEM SCIENCES, vol. 58, no. 1, pp. 137-147, February 1999. [DOI:10.1006/jcss.1997.1545]
24. [23] Z. Bar-yossef, T. S. Jayram, R. Kumar, D. Sivakumar and L. Trevisan, "Counting Distinct Elements in a Data Stream," in Randomization and Approximation Techniques in Computer Science, Springer-Verlag, 2002, pp. 1-10. [DOI:10.1007/3-540-45726-7_1]
25. [24] G. Cormode, M. Datar, P. Indyk and S. Muthukrishnan, "Comparing data streams using hamming norms (how to zero in)," IEEE Transactions on Knowledge and Data Engineering, vol. 15, no. 3, pp. 529-540, March 2003. [DOI:10.1109/TKDE.2003.1198388]
26. [25] P. Flajolet, "On Adaptive Sampling," Computing, vol. 43, no. 4, pp. 391 - 400, February 1990. [DOI:10.1007/BF02241657]
27. [26] S. Ganguly, M. Garofalakis and R. Rastogi, "Processing set expressions over continuous update streams," in MOD International Conference on Management of Data, New York, NY, USA, 2003. [DOI:10.1145/872757.872790]
28. [27] P. B. Gibbons and S. Tirthapura, "Estimating simple functions on the ::union:: of data streams," in SPAA '01 Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, New York, NY, USA, 2001. [DOI:10.1145/378580.378687]
29. [28] F. Dehne, Q. Kong, A. Rau-Chaplin, H. Zaboli and R. Zhou, "Scalable real-time OLAP on cloud architectures," Parallel and Distributed Computing, Vols. 79-80, pp. 31-41, May 2015. [DOI:10.1016/j.jpdc.2014.08.006]
30. [29] A. A. Safaei, "Real-time Processing of Streaming Big Data," Journal of Real-Time Systems, August 2016.
31. [30] B. Babcock, S. Babu, M. Datar, R. Motwani and J. Widom, "Models and issues in data stream systems," in twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database, New York, 2002. [DOI:10.1145/543613.543615]
32. [31] A. Arasu, B. Babcock, S. Babu, J. Cieslewicz, K. Ito, R. Motwani, U. Srivastava and J. Widom, "Stream: The stanford data stream management system," Stanford InfoLab, 2004.
33. [32] D. J. DeWitt and J. Gray, "Parallel Database Systems: The Future of High Performance Database Processing," Communications of the ACM, vol. 36, no. 6, pp. 85-98, June 1992. [DOI:10.1145/129888.129894]
34. [33] A. A. Safaei and M. Haghjoo, "Dispatching of Stream Operators in Parallel Execution of Continuous Queries," Supercomputing, vol. 61, pp. 619-641, 2012. [DOI:10.1007/s11227-011-0621-5]
35. [34] A. A. Safaei and M. Haghjoo, "Parallel processing of continuous queries over data streams," Distributed and Parallel Databases, vol. 28, no. 2, pp. 93-118, 2010. [DOI:10.1007/s10619-010-7066-3]
36. [35]ع. ا. صفایی و م. حق جو, "پردازش موازی جریان داده ها," نشریه علمی پژوهشی انجمن کامپیوتر ایران, جلد 11, شماره 1 (الف), pp. 11-29, 1392.
37. [35] Safaei, A. A., and M. S. Haghjoo. "Parallel processing of data streams." J Comput Sci Eng 11.2 (2014): 11-29
ارسال پیام به نویسنده مسئول
| بازنشر اطلاعات | |
 |
این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است. |
