350 руб
Журнал «Информационно-измерительные и управляющие системы» №12 за 2016 г.
Статья в номере:
Приближенная обработка запросов к большим многомерным хранилищам данных с прогнозируемой погрешностью
Ключевые слова: OLAP сжатие данных вейвлет-преобразование Хаара
Авторы:
Ю.А. Григорьев - д.т.н., профессор, кафедра «Системы обработки информации и управления», Московский государственный технический университет им. Н.Э. Баумана E-mail: grigorev@bmstu.ru А.О. Ухаров - к.т.н., PH Informatics Corp. (Москва) E-mail: oukharov@gmail.com
Аннотация:
Проанализированы существующие методы сжатия данных: выборки, гистограмм и вейвлет-преобразования. Показано, что метод вейвлет-преобразования обладает преимуществом, так как позволяет восстанавливать значения отдельных ячеек исходного хранилища. Предложен метод приближенной обработки запросов на основе вейвлет-преобразования, позволяющий оценить погрешность выполнения запросов к сжатому хранилищу, а также решить обратную задачу: для заданной погрешности выполнения запросов оценить требуемую степень сжатия хранилища данных. Показана приемлемая точность реализации запросов на примере поиска единичных значений и сумм, а также выигрыш по времени выполнения запросов к сжатому хранилищу в зависимости от степени сжатия и размерности обрабатываемых данных.
Страницы: 79-89
Список источников

 

  1. Chaudhuri S., Das G., Datar M. Overcoming Limitations of Sampling for Aggregation Queries // Proceedings of the 17th International Conference on Data Engineering. Washington. 2001. P. 534-542.
  2. Ganti V., Lee M., Ramakrishnan R. ICICLES: Self-Tuning Samples for Approximate Query Answering. Proceedings of International Conference on Very Large Databases // Proceedings of the 26th International Conference on Very Large Data Bases. San Francisco, 2000. P. 176-187.
  3. Gibbons P.B., Matias Y. New Sampling-Based Summary Statistics for Improving Approximate Query Answers // Proceedings of the 1998 ACM SIGMOD international conference on Management of data. New York. 1998. P. 331-342.
  4. Poosala V., Ioannidis Y. Selectivity Estimation Without the Attribute Value Independence Assumption // Proceedings of the 23rd International Conference on Very Large Data Bases. San Francisco. 1997. P. 486-495.
  5. Ioannidis Y. The History of Histograms // Proceedings of the 29th international conference on Very large data bases. Berlin. 2003. V. 27 (1). P. 19-30.
  6. Chakrabarti K., Garofalakis M., Rastogi R. Approximate query processing using wavelets // The VLDB Journal - The International Journal on Very Large Data Bases. 2001. V. 10(2). P. 199-223.
  7. Garofalakis M., Gibbons P.B. Probabilistic Wavelet Synopses // ACM Transactions on Database Systems (TODS). 2004. V. 29(1). P. 43-90.
  8. Garofalakis M., Kumar A. Deterministic Wavelet Thresholding for Maximum Error Metrics // Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. New York. 2004. P. 166-176.
  9. Vitter J.S., Wang M. Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets // Proceedings of the 1999 ACM SIGMOD international conference on Management of data. New York, 1999. P. 193-204.
  10. Vitter J.F., Wang M., Iyer B. Data Cube Approximation and Histograms via Wavelets // Proceedings of the seventh international conference on Information and knowledge management. Bethesda. 1998. P. 96-104.
  11. Stollnitz E.J., DeRose T.D., Salesin D.H. Wavelets for Computer Graphics: Theory and Applications. Morgan Kaufmann Publishers. Inc., San Francisco. California. 1996.
  12. Welstead S. Fractal and Wavelet Image Compression Techniques. SpiePress. 1999.
  13. Burdakov A., Grigorev U., Ploutenko A., Ukharov A. Approximate Query Processing Using Wavelets in OLAP with Arbitrarily Sized Data and Bounded Errors // 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing PDP 2016, Heraklion, Greece, February 2016.
  14. Central limit theorem: http://en.wikipedia.org/wiki/Central_limit_theorem#Lyapunov_CLT.