The week's pick
Random Articles
Reseach Article
A Density based Priority Queue Strategy to Evaluate Iceberg Queries Efficiently using Compressed Bitmap Indices
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 67 - Number 21 |
| Year of Publication: 2013 |
| Authors: Vuppu Shankar, C. V. Guru Rao |
10.5120/11523-7426
|
Vuppu Shankar, C. V. Guru Rao . A Density based Priority Queue Strategy to Evaluate Iceberg Queries Efficiently using Compressed Bitmap Indices. International Journal of Computer Applications. 67, 21 ( April 2013), 39-44. DOI=10.5120/11523-7426
Abstract
In particular, iceberg query is a special class of aggregation query that computes aggregated values upon user interested threshold (T). The bitmap index is a common data structure for fast retrieval of matching tuples from data base table. These resultant tuples are useful to compute aggregations such as SUM, COUNT, AVG, MIN, MAX, and RANK. In this paper, we propose a density based bitmap pruning strategy to evaluate iceberg queries efficiently using compressed bitmap indices. The strategy prioritizes the vectors to be enter in to priority queue by allowing high density of 1's count that achieve optimal pruning effect. Extensive experimentation demonstrates our proposed approach is much more efficient than existing strategy.
References
- Bin He, Hui-I Hsiao, Ziyang Liu, Yu Huang and Yi Chen, "Efficient Iceberg Query Evaluation Using Compressed Bitmap Index", IEEE Transactions On Knowledge and Data Engineering, vol 24, issue 9, sept 2011, pp. 1570-1589
- D. E. Knuth, "The Art of Computer Programming : A Foundation for computer mathematics" Addison-Wesley Professional, second edition, ISBN NO: 0-201-89684-2, January 10, 1973.
- G. Antoshenkov, "Byte-aligned Bitmap Compression", Proceedings of the Conference on Data Compression, IEEE Computer Society, Washington, DC, USA, Mar28-30,1995, pp. 476
- Hsiao H, Liu Z, Huang Y, Chen Y, "Efficient Iceberg Query Evaluation using Compressed Bitmap Index", in Knowledge and Data Engineering, IEEE, Issue: 99, 2011, pp:1.
- Jinuk Bae,Sukho Lee, "Partitioning Algorithms for the Computation of Average Iceberg Queries", Springer-Verlag, ISBN:3-540-67980-4, 2000, pp: 276 – 286.
- J. Baeand, S. Lee, "Partitioning Algorithms for the Computation of Average Iceberg Queries", in DaWaK, 2000.
- K. P. Leela, P. M. Tolani, and J. R. Haritsa. "On Incorporating Iceberg Queries in Query Processors", in DASFAA, 2004, pages 431–442.
- K. Stockinger, J. Cieslewicz, K. Wu, D. Rotem and A. Shoshani. "Using Bitmap Index for Joint Queries on Structured and Text Data", Annals of Information Systems, 2009, pp: 1–23.
- K. Wu,E. J. Otoo and A. Shoshani. "Optimizing Bitmap Indices with Ef?cient Compression", ACM Transactions on Database System, 31(1):1–38, 2006.
- K. Wu,EJ. Otoo,and A. Shoshani, "On the Performance of Bitmap Indices for High Cardinality Attributes", VLDB, 2004, pp: 24–35.
- K. -Y. Whang, B. T. V. Zanden and H. M. Taylor. "A Linear-Time Probabilistic Counting Algorithm for Database Applications". ACMTrans. Database Syst. , 15(2):208–229, 1990.
- M. Fang, N. Shivakumar, H. Garcia- Molina, R. Motwani and J. D. Ullman. "Computing Iceberg Queries Ef?ciently". In VLDB, pages 299–310, 1998.
- M. Jrgens "Tree Based Indexes vs. Bitmap Indexes: A Performance Study" In DMDW, 1999.
- M. Stonebraker, D. J. Abadi, A. Batkin, X. Chen, M. Cherniack, M. Ferreira, E. Lau,A. Lin, S. Madden, E. J. O'Neil, P. E. O'Neil, A. Rasin, N. Tran and S. B. Zdonik. C-Store: "A Column-oriented DBMS". In VLDB, pages 553–564, 2005.
- P. E. O'Neil. "Model204 Architecture and Performance". In HPTS Pages 40–59, 1987.
- P. E. O'Neiland D. Quass. "Improved Query Performance with Variant Indexes". In SIGMOD Conference, pages 38–49, 1997.
- P. E. O'Neil and G. Graefe. "Multi-Table Joins Through Bitmapped Join Indices". SIGMOD Record, 24(3):8–11, 1995.
- R. Agarwal,T. Imilinski,andA. Swami. "MiningA ssociation Rules between Sets of Items in Large databases". In SIGMOD Conference, pages 207-216, 1993.
- Spiegler I; Maayan R "Storage and retrieval considerations of binary databases". Information processing and management: an international journal 21 (3): pages 233-54, 1985
- Dr. C. V. Guru Rao and V. Shankar,"Efficient iceberg query evaluation using compressed bitmap indices by deferring bitwise-XOR operations" 3rd IEEE,on Advanced Computing Conference, 22nd &23 rd Feb 2013,New Delhi, India,pp. 1374-79.
Index Terms
Keywords