Abstract
Bitmap join indexes are designed to prejoin the facts and dimension tables in data warehouses modeled by a star schema. They are defined on the fact table using attributes which belong to one or many dimension tables. The index selection process has become an important issue regarding the complexity of the search space to explore. Thus, the indexes can be defined on several attributes from several dimension tables (that may contain hundreds of attributes). However, only a few selection algorithms were proposed. In this article, we present a bitmap join indexes selection approach based on artificial immune algorithm. An experimental study was conducted on the dataset generated from APB-1 benchmark in order to compare the artificial immune algorithm with other algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Kimball, R., Strehlo, K.: Why decision support fails and how to fix it. SIGMOD Record 24(3), 92–97 (1995)
Comer, D.: The ubiquitous b-tree. ACM Comput. Surv. 11(2), 121–137 (1979)
Valduriez, P.: Join indices. ACM Transactions on Database Systems 12(2), 218–246 (1987)
Bellatreche, L., Boukhalfa, K., Mohania, M.: Pruning Search Space of Physical Database Design. In: Wagner, R., Revell, N., Pernul, G. (eds.) DEXA 2007. LNCS, vol. 4653, pp. 479–488. Springer, Heidelberg (2007)
Chan, C.Y., Ioannidis, Y.E.: Bitmap index design and evaluation. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 355–366 (June 1998)
Red Brick Systems Inc., Star schema processing for complex queries. White Paper (1997)
O’Neil, P., Graefe, G.: Multi-table joins through bitmapped join indices. SIGMOD Record 24(3), 8–11 (1995)
Aouiche, K., Boussaid, O., Bentayeb, F.: Automatic Selection of Bitmap Join Indexes in Data Warehouses, pp. 64–73 (2005)
Boukhalfa, K., Bellatreche, L., Ziani, B.: Index de jointure binaires: Stratgies de slection et etude de performances. In: Journe Francophone sur les Entrepts de donnes et l’Analyse en ligne (EDA 2010). Revue des Nouvelles Technologies (2010)
Bellatreche, L., Boukhalfa, K.: Yet Another Algorithms for Selecting Bitmap Join Indexes. In: Bach Pedersen, T., Mohania, M.K., Tjoa, A.M. (eds.) DAWAK 2010. LNCS, vol. 6263, pp. 105–116. Springer, Heidelberg (2010)
Bellatreche, L., Missaoui, R., Necir, H., Drias, H.: A data mining approach for selecting bitmap join indices. Journal of Computing Science and Engineering 2(1), 206–223 (2008)
Stöhr, T., Martens, H., Rahm, E.: Multidimensional database allocation for parallel data warehouses. In: International Conference on Very Large Databases, pp. 273–284 (2000)
Bouchakri, R., Bellatreche, L., Boukhalfa, K.: Slection statique et incrmentale des index de jointure binaires multiples. In: Journe Francophones sur les Entrepts de donnes et l’Analyse en ligne (EDA 2011). Revue des Nouvelles Technologies RNTI, France (2011)
Farmer, J., Packard, N., Perelson, A.: The immune system, adaptation and machine learning. Physica 22D, 187–204 (1986)
Ishida, Y.: Immunity-Based-Systems: A Design Perspective. Springer (2004)
Forrest, S., Perelson, A.S., Allen, L., Cherukuri, R.: Self-nonself discrimination in a computer. In: IEEE Symposium on Research in Security and Privacy (1994)
De Castro, L., Von Zuben, F.: Learning and optimization using the clonal selection principle. IEEE Transactions on Evolutionary Computation, Special Issue on Artificial Intelligence Systems, 239–251 (2002)
Timmis, J., Neal, M., Hunt, J.: An artificial immune system for data analysis. Knowledge Based Systems 14(3-4), 121–130 (2000)
Dasgupta, D., Forrest, S.: Novelty detection in time series data using ideas from immunology. In: 5th International Conference on Intelligent Systems (1996)
Ishida, Y.: An Immune Network Model and its Applications to Process Diagnosis Systems and Computers (1993)
Hunt, J., Cooke, D., Holstein, H.: Case memory and retrieval based on the immune system. In: International Conference on Case Based Reasoning (1995)
Bersini, H.: Immune network and adaptative control. In: First European Conference on Artificial Life (1991)
Nasaroui, O., Dasgupta, D., Gonzlez, F.: A novel artificial immune system approach to robust datamining. In: Genetic and Evolutionary Computation Conference (2002)
Council, O.: Apb-1 olap benchmark, release ii (1998), http://www.olapcouncil.org/research/bmarkly.htm
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gacem, A., Boukhalfa, K. (2012). Immune Algorithm for Bitmap Join Indexes. In: Huang, T., Zeng, Z., Li, C., Leung, C.S. (eds) Neural Information Processing. ICONIP 2012. Lecture Notes in Computer Science, vol 7665. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34487-9_68
Download citation
DOI: https://doi.org/10.1007/978-3-642-34487-9_68
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34486-2
Online ISBN: 978-3-642-34487-9
eBook Packages: Computer ScienceComputer Science (R0)