{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T19:09:14Z","timestamp":1674241754734},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2005,10,1]],"date-time":"2005-10-01T00:00:00Z","timestamp":1128124800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"},{"start":{"date-parts":[[2005,10,1]],"date-time":"2005-10-01T00:00:00Z","timestamp":1128124800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Braz Comp Soc"],"published-print":{"date-parts":[[2005,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Metric Access Methods (MAM) are employed to accelerate the processing of similarity queries, such as the range and the k-nearest neighbor queries. Current methods, such as the Slim-tree and the M-tree, improve the query performance minimizing the number of disk accesses, keeping a constant height of the structures stored on disks (height-balanced trees). However, the overlapping between their nodes has a very high influence on their performance. This paper presents a new dynamic MAM called the<jats:italic>DBM<\/jats:italic>-tree (Density-Based Metric tree), which can minimize the overlap between high-density nodes by relaxing the height-balancing of the structure. Thus, the height of the tree is larger in denser regions, in order to keep a tradeoff between breadth-searching and depth-searching. An underpinning for cost estimation on tree structures is their height, so we show a non-height dependable cost model that can be applied for DBM-tree. Moreover, an optimization algorithm called<jats:italic>Shrink<\/jats:italic> is also presented, which improves the performance of an already built<jats:italic>DBM<\/jats:italic>-tree by reorganizing the elements among their nodes. Experiments performed over both synthetic and real world datasets showed that the<jats:italic>DBM<\/jats:italic>-tree is, in average, 50% faster than traditional MAM and reduces the number of distance calculations by up to 72% and disk accesses by up to 66%. After performing the Shrink algorithm, the performance improves up to 40% regarding the number of disk accesses for range and<jats:italic>k<\/jats:italic>-nearest neighbor queries. In addition, the<jats:italic>DBM<\/jats:italic>-tree scales up well, exhibiting linear performance with growing number of elements in the database.<\/jats:p>","DOI":"10.1007\/bf03192381","type":"journal-article","created":{"date-parts":[[2010,11,11]],"date-time":"2010-11-11T15:17:14Z","timestamp":1289488634000},"page":"37-51","source":"Crossref","is-referenced-by-count":3,"title":["DBM-Tree: Trading height-balancing for performance in metric access methods"],"prefix":"10.1007","volume":"11","author":[{"given":"Marcos R.","family":"Vieira","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Caetano","family":"Traina","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabio J. T.","family":"Chino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Agma J. M.","family":"Traina","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF03192381_CR1","doi-asserted-by":"crossref","unstructured":"Ricardo A. Baeza-Yates, Walter Cunto, Udi Manber, and Sun Wu. Proximity matching using fixedqueries trees. In5th Annual Symposium on Combinatorial Pattern Matching (CPM), volume 807 of LNCS, pages 198\u2013212, Asilomar, USA, 1994. Springer Verlag.","DOI":"10.1007\/3-540-58094-8_18"},{"key":"BF03192381_CR2","doi-asserted-by":"crossref","unstructured":"Tolga Bozkaya and Meral zsoyoglu. Distance-based indexing for high-dimensional metric spaces. InProceedings of the ACM International Conference on Management of Data (SIGMOD), pages 357\u2013368, 1997.","DOI":"10.1145\/253262.253345"},{"issue":"3","key":"BF03192381_CR3","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1145\/328939.328959","volume":"24","author":"Tolga Bozkaya","year":"1999","unstructured":"Tolga Bozkaya and Meral zsoyoglu. Indexing large metric spaces for similarity search queries.ACM Transactions on Database Systems (TODS), 24(3):361\u2013404, sep 1999.","journal-title":"ACM Transactions on Database Systems (TODS)"},{"key":"BF03192381_CR4","unstructured":"Sergey Brin. Near neighbor search in large metric spaces. InProceedings of the International Conference on Very Large Data Bases (VLDB), pages 574-584, Zurich, Switzerland, 1995. Morgan Kaufmann."},{"issue":"4","key":"BF03192381_CR5","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1145\/362003.362025","volume":"16","author":"W. A. Burkhard","year":"1973","unstructured":"W. A. Burkhard and R. M. Keller. Some approaches to best-match file searching.Communications of the ACM, 16(4):230\u2013236, apr 1973.","journal-title":"Communications of the ACM"},{"key":"BF03192381_CR6","unstructured":"Fabio J. T. Chino, Marcos R. Vieira, Agma J. M. Traina, and Caetano Traina Jr. Mamview: A visual tool for exploring and understanding metric access methods. InProceedings of the 20th Annual ACM Symposium on Applied Computing (SAC), page 6p, Santa Fe, New Mexico, USA, 2005. ACM Press."},{"issue":"3","key":"BF03192381_CR7","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1145\/502807.502808","volume":"33","author":"Edgar Chvez","year":"2001","unstructured":"Edgar Chvez, Gonzalo Navarro, Ricardo Baeza-Yates, and Jos Luis Marroqun. Searching in metric spaces.ACM Computing Surveys (CSUR), 33(3):273\u2013321, sep 2001.","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"BF03192381_CR8","doi-asserted-by":"crossref","unstructured":"P. Ciaccia, M. Patella, and P. Zezula. A cost model for similarity queries in metric spaces. InACM Symposium on Principles of Database Systems (PODS), pages 59\u201368, 1998.","DOI":"10.1145\/275487.275495"},{"key":"BF03192381_CR9","unstructured":"Paolo Ciaccia, Marco Patella, and Pavel Zezula. M-tree: An efficient access method for similarity search in metric spaces. InProceedings of International Conference on Very Large Data Bases (VLDB), pages 426\u2013435, Athens, Greece, 1997. Morgan Kaufmann."},{"key":"BF03192381_CR10","unstructured":"Roberto F. Santos Filho, Agma J. M. Traina, Caetano Traina Jr., and Christos Faloutsos. Similarity search without tears: The OMNI family of allpurpose access methods. InIEEE International Conference on Data Engineering (ICDE), pages 623\u2013630, Heidelberg, Germany, 2001."},{"issue":"2","key":"BF03192381_CR11","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1145\/280277.280279","volume":"30","author":"Volker Gaede","year":"1998","unstructured":"Volker Gaede and Oliver Gnther. Multidimensional access methods.ACM Computing Surveys (CSUR), 30(2):170\u2013231, 1998.","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"BF03192381_CR12","doi-asserted-by":"crossref","unstructured":"A. Guttman. R-tree : A dynamic index structure for spatial searching. InACM International Conference on Data Management (SIGMOD), pages 47\u201357, Boston, USA, 1984.","DOI":"10.1145\/971697.602266"},{"issue":"4","key":"BF03192381_CR13","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1145\/958942.958948","volume":"28","author":"Gisli R. Hjaltason","year":"2003","unstructured":"Gisli R. Hjaltason and Hanan Samet. Index-driven similarity search in metric spaces.ACM Transactions on Database Systems (TODS), 28(4):517\u2013580, dec 2003.","journal-title":"ACM Transactions on Database Systems (TODS)"},{"issue":"2","key":"BF03192381_CR14","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1109\/69.991715","volume":"14","author":"Caetano Traina","year":"2002","unstructured":"Caetano Traina Jr., Agma J. M. Traina, Christos Faloutsos, and Bernhard Seeger. Fast indexing and visualization of metric datasets using slim-trees.IEEE Transactions on Knowledge and Data Engineering (TKDE), 14(2):244\u2013260, 2002.","journal-title":"IEEE Transactions on Knowledge and Data Engineering (TKDE)"},{"key":"BF03192381_CR15","doi-asserted-by":"crossref","unstructured":"Caetano Traina Jr., Agma J. M. Traina, Bernhard Seeger, and Christos Faloutsos. Slim-trees: High performance metric trees minimizing overlap between nodes. InInternational Conference on Extending Database Technology (EDBT), volume 1777 ofLNCS, pages 51\u201365, Konstanz, Germany, 2000. Springer.","DOI":"10.1007\/3-540-46439-5_4"},{"key":"BF03192381_CR16","unstructured":"K. A. Ross, I. Sitzmann, and P. J. Stuckey. Costbased unbalanced R-trees. InIEEE International Conference on Scientific and Statistical Database Management (SSDBM), pages 203\u2013212, 2001."},{"issue":"1","key":"BF03192381_CR17","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1109\/69.842247","volume":"12","author":"Y. Theodoridis","year":"2000","unstructured":"Y. Theodoridis, E. Stefanakis, and T. K. Sellis. Efficient cost models for spatial queries using R-trees.IEEE Transactions on Knowledge and Data Engineering (TKDE), 12(1):19\u201332, 2000.","journal-title":"IEEE Transactions on Knowledge and Data Engineering (TKDE)"},{"key":"BF03192381_CR18","doi-asserted-by":"crossref","unstructured":"Agma J. M. Traina, Caetano Traina Jr., Josiane M. Bueno, and Paulo M. de A. Marques. The metric histogram: A new and efficient approach for content-based image retrieval. InSixth IFIP Working Conference on Visual Database Systems (VDB), Brisbane, Australia, 2002.","DOI":"10.1007\/978-0-387-35592-4_21"},{"issue":"4","key":"BF03192381_CR19","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0020-0190(91)90074-R","volume":"40","author":"Jeffrey K. Uhlmann","year":"1991","unstructured":"Jeffrey K. Uhlmann. Satisfying general proximity\/ similarity queries with metric trees.Information Processing Letters, 40(4):175\u2013179, 1991.","journal-title":"Information Processing Letters"},{"key":"BF03192381_CR20","unstructured":"Marcos R. Vieira, Caetano Traina Jr., Fabio J. T. Chino, and Agma J. M. Traina. DBM-tree: A dynamic metric access method sensitive to local density data. InXIX Brazilian Symposium on Databases (SBBD), pages 163\u2013177, Bras\u00edlia, Brazil, 2004."},{"key":"BF03192381_CR21","unstructured":"Peter N. Yianilos. Data structures and algorithms for nearest neighbor search in general metric spaces. InProceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 311\u2013321, Austin, USA, 1993."}],"container-title":["Journal of the Brazilian Computer Society"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF03192381.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/BF03192381\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BF03192381","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF03192381.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T04:04:59Z","timestamp":1630469099000},"score":1,"resource":{"primary":{"URL":"https:\/\/journal-bcs.springeropen.com\/articles\/10.1007\/BF03192381"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,10]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,10]]}},"alternative-id":["BF03192381"],"URL":"https:\/\/doi.org\/10.1007\/bf03192381","relation":{},"ISSN":["0104-6500","1678-4804"],"issn-type":[{"value":"0104-6500","type":"print"},{"value":"1678-4804","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,10]]}}}