Ocena efektywności hierarchicznego indeksu bitmapowego wspierającego wykonywanie zapytań w bazach danych z atrybutami zawierającymi zbiory

• Autorzy: Andrzejewski, W. , Królikowski, Z. , Morzy, M. , Morzy, T.

Warianty tytułu

EN

Performance Evaluation of Hierarchical Bitmap Index Supporting Processing of Queries on Set Values Attributes

• Języki publikacji: PL

Abstrakty

PL

W niniejszej pracy przedstawiono ocenę efektywności hierarchicznego indeksu bitmapowego, wspierającego wykonywanie zapytań eksploracyjnych. W ramach badań wykonano zakrojony na szeroką skalę zestaw eksperymentów, obejmujących przetwarzanie zapytań eksploracyjnych wszystkich klas do baz danych z atrybutami zawierającymi zbiory. Zapytania były realizowane z wykorzystaniem "naiwnego" algorytmu wykonującego pełny przegląd bazy danych, pliku odwróconego, RD drzewa, S drzewa oraz dwóch odmian hierarchicznego indeksu bitmapowego. Bazy danych wykorzystywane w trakcie eksperymentów różniły się liczbą przechowywanych zbiorów oraz średnimi rozmiarami zbiorów. Wyniki pomiarów wykazały, że w porównaniu z innymi technikami stosowanymi do tej pory, hierarchiczny indeks bitmapowy charakteryzuje się najwyższą efektywnością przetwarzania dla zapytań o podzbiory, zapytań równościowych, oraz zapytań przybliżonych. Dla zapytań o nadzbiory efektywność hierarchicznego indeksu bitmapowego jest niższa jedynie od plików odwróconych.

EN

In this paper we paper we present performance evaluation of the hierarchical bitmap index supporting processing of data mining queries. Performance evaluation includes the results of several experiments on processing of various data mining queries against databases with set valued attributes. Data mining queries were processed using the following strategies: a "naive" approach consisting in full database scan, inverted files, RD trees, S trees, and two types of the hierarchical bitmap index. Databases used through-out the experiments differed in the number of sets and the average sizes of sets stored in the database. The results of the conducted experiments show that the hierarchical bitmap index outperforms other indexing techniques with respect to the processing of equality, superset, and similarity queries. For subset queries the hierarchical bitmap index was surpassed only by the inverted file index.

• Czasopismo: Archiwum Informatyki Teoretycznej i Stosowanej
• Rocznik: 2005
• Tom: T. 17, z. 4
• Strony: 273-288
• Opis fizyczny: Bibliogr. 11 poz., rys.

Twórcy

autor

Andrzejewski, W.

• Politechnika Poznańska Instytut Informatyki ul. Piotrowo 3a, 60-965 Poznań, Poland

autor

Królikowski, Z.

• Politechnika Poznańska Instytut Informatyki ul. Piotrowo 3a, 60-965 Poznań, Poland

autor

Morzy, M.

• Politechnika Poznańska Instytut Informatyki ul. Piotrowo 3a, 60-965 Poznań, Poland

autor

Morzy, T.

• Politechnika Poznańska Instytut Informatyki ul. Piotrowo 3a, 60-965 Poznań, Poland

Bibliografia

• [1]Andrzejewski W., Królikowski Z. i M. Morzy M., Hierarchiczny indeks bitmapowy wspierający wykonywanie zapytań w bazach danych z atrybutami zawierającymi zbiory, Archiwum Informatyki Teoretycznej i Stosowanej, 2005, Tom 17, z.3/2005, str.213 - 228.
• [2] Araujo M.D., Navarro G., N. Ziviani N., Large text searching allowing errors, Proc. of the 4th South American Workshop on String Processing, 1997, Valparaiso Chile, str. 2 20.
• [3] Deppisch U., S-Tree: A Dynamic Balanced Signature Index for Office Retrieval, Proceedings of the ACM Conference on Research and Development in Information Retrieval, 1986, str. 77-87.
• [4] Faloutsos Ch., Christodoulakis S., Signature Files: An Access Method for Documents and Its Analitical Performance Evaluation, ACM Trans, on Office Information Systems (TOOIS), 1984, str. 267-288.
• [5] Hellerstein J.M., Pfeffer A., The RD tree: An index structure for sets, Technical Report 1252, 1994 University of Wisconsin at Madison.
• [6] Jeong B-S., Omiecinski E., Inverted file partitioning schemes in multiple disk systems, IEEE Transactions on Parallel and Distributed Systems, t. 6 nr. zeszytu 2, 1995, str. 142-153.
• [7] Morzy M., Morzy T., Manolopoulos Y., Nanopoulos A., Hierarchical Bitmap Index: an Efficient and Scalable Indexing Technique for Set-valued Attributes, Proc. of the 7th East-European Conf. on Advances in Databases and Information Systems ADBIS'2003, Springer Verlag, str. 236-252.
• [8] Navarro G., Moura E., Neubert M., Ziviani N., Baeza-Yates R., Adding compression to block addressing inverted indexes, Kluwer Information Retrieval Journal, t. 3 nr 1, 2000, str. 49-77.
• [9] Quest Synthetic Data Generation Code, wersja z dnia 3 czerwca 1995 r., http://www.almaden.ibm.com/software/quest/Resources/datasets/syndata.html
• [10] Ribeiro-Neto B., Kitajima J.P., Navarro G., Santana C, N. Ziviani N., Parallel generation of inverted files for distributed text collections. Proc. of Int. Conf. of the Chilean Society of Com¬puter Science, (SCCC'98), 1998 Antofagasta, Chile, str. 149-150.
• [11] Zobel J., Moffat A., Ramamohanarao K., Inverted files versus signature files for text indexing. ACM Transactions on Database Systems, t. 23 nr zeszytu 4, 1998, str. 453-490.