wiki:bibliography

Bibliography

M-tree structure and extensions

Original M-tree paper:

[Ciaccia et al., 1997b] Ciaccia, P., Patella, M., and Zezula, P. (1997b). M-tree: An efficient access method for similarity search in metric spaces. In Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB 1997), Athens, Greece, August 25-29, 1997, pages 426–435. Morgan Kaufmann.

Slim-tree is an extension of M-tree which defines a different split policy:

[Traina, Jr. et al., 2000b] Traina, Jr., C., Traina, A. J. M., Seeger, B., and Faloutsos, C. (2000b). Slim-Trees: High performance metric trees minimizing overlap between nodes. In Zaniolo, C., Lockemann, P. C., Scholl, M. H., and Grust, T., editors, Proceedings of the 7th International Conference on Extending Database Technology (EDBT 2000), Konstanz, Germany, March 27-31, 2000, volume 1777 of Lecture Notes in Computer Science, pages 51–65. Springer.

DBM-tree is an unbalanced M-tree useful for data with dense regions:

[VTCT04] Vieira,M. R., Traina, Jr., C., Chino, F. J. T., and Traina, A. J.M. (2004). DBM-Tree: a dynamic metric access method sensitive to local density data. In Proceedings of the 19th Brazilian Symposium on Databases (SBBD 2004), Bras´ılia, Distrito Federal, Brasil, October 18-20, 2004, pages 163–177. University of Bras´ılia.

PM-tree is an extension of M-tree and applies additional pivot-filtering:

[Skopal, 2004] Skopal, T. (2004). Pivoting M-tree: A metric access method for efficient similarity search. In Proceedings of the Annual International Workshop on DAtabases, TExts, Specifications and Objects (DATESO 2004), Desna, Czech Republic, April 14-16, 2004, volume 98 of CEUR Workshop Proceedings. Technical University of Aachen (RWTH).

DF-Tree (Distance Field Tree) uses additional pivot-filtering as well:

[TTFF02] Traina, Jr., C., Traina, A. J. M., Filho, R. F. S., and Faloutsos, C. (2002). How to improve the pruning ability of dynamic metric access methods. In Proceedings of the 2002 ACM CIKM International Conference on Information and Knowledge Management (CIKM 2002), McLean?, VA, USA, November 4-9, 2002, pages 219–226. ACM.

M+-tree is restricted to vector datasets and defines a key dimension:

[Zhou et al., 2003] Zhou, X., Wang, G., Yu, J. X., and Yu, G. (2003). M+-tree: A new dynamical multidimensional index for metric spaces. In Schewe, K.-D. and Zhou, X., editors, Proceedings of the 14th Australasian Database Conference on Database Technologies (ADC 2003), Adelaide, South Australia, February 4-7, 2003, volume 17 of CRPIT, pages 161–168. Australian Computer Society.

Two key dimensions are exploited in BM+-tree:

[Zhou et al., 2005] Zhou, X.,Wang, G., Zhou, X., andYu,G. (2005). BM+-Tree:Ahyperplanebased index method for high-dimensional metric spaces. In Proceedings of the 10th International Conference on Database Systems for Advanced Applications (DASFAA 2005), Beijing, China, April 17-20, 2005, volume 3453 of Lecture Notes in Computer Science, pages 398–409. Springer.

M2-tree allows queries with multiple predicates:

[Ciaccia and Patella, 2000a] Ciaccia, P. and Patella, M. (2000a). TheM2-tree: Processing complex multi-feature queries with just one index. In Proceedings of the First DELOS Network of Excellence Workshop on Information Seeking, Searching and Querying in Digital Libraries, Zurich, Switzerland, December 11-12, 2000.

Improvements of M-tree algorithms

Bulk-Loading Algorithm of M-tree is a procedure which constructs an M-tree efficiently for large datasets:

Top-down bulk-loading:

[Ciaccia and Patella, 1998] Ciaccia, P. and Patella, M. (1998). Bulk loading the M-tree. In Proceedings of the 9th Australasian Database Conference (ADC 1998), Perth, Australia, February 2-3, 1998, volume 20(2) of Australian Computer Science Communications, pages 15–26. Springer.

Bottom-up bulk-loading:

[MXSM03] Mao, R., Xu, W., Singh, N., and Miranker, D. P. (2003). An assessment of a metric space database index to support sequence homology. In Proceedings of the 3rd IEEE International Symposium on BioInformatics? and BioEngineering? (BIBE 2003), Bethesda, MD, USA, March 10-12, 2003, pages 375–382. IEEE Computer Society.

Complex similarity queries

[Ciaccia et al., 1998b] Ciaccia, P., Patella, M., and Zezula, P. (1998b). Processing complex similarity queries with distance-based access methods. In Schek, H.-J., Saltor, F., Ramos, I., and Alonso, G., editors, Proceedings of the 6th International Conference on Extending Database Technology (EDBT 1998), Valencia, Spain, March 23-27, 1998, volume 1377 of Lecture Notes in Computer Science, pages 9–23. Springer.

Slim-down algorithm optimizes the leaf-node occupation:

[Traina, Jr. et al., 2000b] Traina, Jr., C., Traina, A. J. M., Seeger, B., and Faloutsos, C. (2000b). Slim-Trees: High performance metric trees minimizing overlap between nodes. In Zaniolo, C., Lockemann, P. C., Scholl, M. H., and Grust, T., editors, Proceedings of the 7th International Conference on Extending Database Technology (EDBT 2000), Konstanz, Germany, March 27-31, 2000, volume 1777 of Lecture Notes in Computer Science, pages 51–65. Springer.

[Traina, Jr. et al., 2002] Traina, Jr., C., Traina, A. J. M., Faloutsos, C., and Seeger, B. (2002). Fast indexing and visualization of metric data sets using Slim-Trees. IEEE Transactions on Knowledge and Data Engineering (TKDE 2002), 14(2):244–260. IEEE Computer Society.

Improved M-tree building algorithms. Mainly the generalized slim-down algorithm and mutli-way insertion algorithm:

[Skopal et al., 2003] Skopal, T., Pokorn´y, J., Kr´atk´y, M., and Sn´aˇsel, V. (2003). Revisiting MTree building principles. In Proceedings of the 7th East European Conference on Advances in Databases and Information Systems (ADBIS 2003), Dresden, Germany, September 3-6, 2003, volume 2798 of Lecture Notes in Computer Science. Springer.

Nearest neighbor search using PM-tree:

[Skopal et al., 2005] Skopal, T., Pokorn´y, J., and Sn´aˇsel, V. (2005). Nearest neighbours search using the PM-Tree. In Proceedings of the 10th International Conference on Database Systems for Advanced Applications (DASFAA 2005), Beijing, China, April 17-20, 2005, volume 3453 of Lecture Notes in Computer Science, pages 803–815. Springer.

Additional Sources

M-tree C++ Implementation based on GiST:

[Ciaccia et al., 1997a] Ciaccia, P., Patella, M., Rabitti, F., and Zezula, P. (1997a). The M-tree Project. Available at http://www-db.deis.unibo.it/Mtree/.

Last modified 10 years ago Last modified on May 31, 2007, 1:32:23 PM