{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T09:03:00Z","timestamp":1775638980225,"version":"3.50.1"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2006,6,29]],"date-time":"2006-06-29T00:00:00Z","timestamp":1151539200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2007,10]]},"DOI":"10.1007\/s00778-005-0178-0","type":"journal-article","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T23:02:26Z","timestamp":1151535746000},"page":"483-505","source":"Crossref","is-referenced-by-count":74,"title":["The Omni-family of all-purpose access methods: a simple and effective way to make similarity search more efficient"],"prefix":"10.1007","volume":"16","author":[{"suffix":"Jr.","given":"Caetano","family":"Traina","sequence":"first","affiliation":[]},{"given":"Roberto F. Santos","family":"Filho","sequence":"additional","affiliation":[]},{"given":"Agma J. M.","family":"Traina","sequence":"additional","affiliation":[]},{"given":"Marcos R.","family":"Vieira","sequence":"additional","affiliation":[]},{"given":"Christos","family":"Faloutsos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,6,29]]},"reference":[{"key":"178_CR1","unstructured":"Aggarwal, C.C., Hinneburg, A., Keim, D.A.: On the surprising behavior of distance metrics in high dimensional spaces. In: Proceedings of the 8th International Conference on Database Theory (ICDT). Lecture Notes in Computer Science, vol. 1973, pp. 420\u2013434. Springer (2001)."},{"key":"178_CR2","doi-asserted-by":"crossref","unstructured":"Annamalai, M., Chopra, R., De Fazio, S.: Indexing images inoracle8i. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, pp. 539\u2013547. ACM Press (2000)","DOI":"10.1145\/335191.335463"},{"key":"178_CR3","unstructured":"Arantes, A.S., Vieira, M.R., Traina, A.J.M., Traina, C. Jr.: The fractal dimension making similarity queries more efficient. In: Proceedings of the II ACM SIGKDD Workshop on Fractals, Power Laws and Other Next Generation Data Mining Tools, pp. 12\u201317. Washington, USA (2003)"},{"key":"178_CR4","doi-asserted-by":"crossref","unstructured":"Baeza-Yates, R.A., Cunto, W., Manber, U., Wu, S.: Proximity matching using fixed-queries trees. In: Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching (CPM). Lecture Notes in Computer Science, vol. 807, pp. 198\u2013212. Springer (1994)","DOI":"10.1007\/3-540-58094-8_18"},{"key":"178_CR5","doi-asserted-by":"crossref","unstructured":"Beckmann, N.: Kriegel, H.-P., Schneider, R., Seeger, B.: The R*-Tree: an efficient and robust access method for points and rectangles. In: Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, pp. 322\u2013331. ACM Press (1990)","DOI":"10.1145\/93605.98741"},{"key":"178_CR6","unstructured":"Belussi, A., Faloutsos, C.: Estimating the selectivity of spatial queries using the \u2018correlation\u2019 fractal dimension. In: Proceedings of 21th International Conference on Very Large Data Bases (VLDB), pp. 299\u2013310. Morgan Kaufmann (1995)"},{"key":"178_CR7","doi-asserted-by":"crossref","unstructured":"Berman, A., Shapiro, L.G.: Selecting good keys fortriangle-inequality-based pruning algorithms. In: Proceedings of the International Workshop on Content-Based Access of Image and Video Databases (CAIVD), pp. 12\u201319. IEEE Computer Society (1998)","DOI":"10.1109\/CAIVD.1998.646029"},{"key":"178_CR8","doi-asserted-by":"crossref","unstructured":"Beyer, K.S., Goldstein, J., Ramakrishnan, R., Shaft, U.: When is \u201cnearest neighbor\u201d meaningful? In: Proceedings of the 7th International Conference on Database Theory (ICDT). Lecture Notes in Computer Science. vol. 1540, pp. 217\u2013235. Springer (1999)","DOI":"10.1007\/3-540-49257-7_15"},{"key":"178_CR9","doi-asserted-by":"crossref","unstructured":"Bozkaya, T., \u00d3zsoyoglu, Z. Meral.: Distance-based indexing for high-dimensional metric spaces. In: Proceedings of the 1997ACM SIGMOD International Conference on Management of Data, pp. 357\u2013368. ACM Press (1997)","DOI":"10.1145\/253262.253345"},{"issue":"3","key":"178_CR10","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1145\/328939.328959","volume":"24","author":"T. Bozkaya","year":"1999","unstructured":"Bozkaya, T., \u00d3zsoyoglu, Z. Meral.: Indexing large metric spaces for similarity search queries. ACM Trans. Database Syst. (TODS) 24(3), 361\u2013404 (1999)","journal-title":"ACM Trans. Database Syst. (TODS)"},{"key":"178_CR11","unstructured":"Brin, S.: Near neighbor search in large metric spaces. In: Proceedings of 21th International Conference on Very Large DataBases (VLDB), pp. 574\u2013584. Morgan Kaufmann (1995)"},{"issue":"4","key":"178_CR12","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1145\/362003.362025","volume":"16","author":"W.A. Burkhard","year":"1973","unstructured":"Burkhard, W.A., Keller, R.M.: Some approaches to best-match filesearching. Commun. ACM (CACM) 16(4),230\u2013236 (1973)","journal-title":"Commun. ACM (CACM)"},{"issue":"1","key":"178_CR13","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1023\/A:1011326007550","volume":"14","author":"F. Camastra","year":"2001","unstructured":"Camastra, F., Vinciarelli, A.: Intrinsic dimension estimation of data: an approach based on Grassberger-Procaccia's algorithm. Neural. Process. Lett. 14(1), 27\u201334 (2001)","journal-title":"Neural. Process. Lett."},{"key":"178_CR14","doi-asserted-by":"crossref","unstructured":"Ch\u00e1vez, E., Marroqu\u00edn, J.L., Baeza-Yates, R.A.: Spaghettis: An array based algorithm for similarity queries inmetric spaces. In: Proceeding of the String Processing and Information Retrieval Symposium & International Workshop on Groupware (SPIRE\/CRIWG), pp. 38\u201346. IEEE Computer Society (1999)","DOI":"10.1109\/SPIRE.1999.796576"},{"issue":"3","key":"178_CR15","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1145\/502807.502808","volume":"33","author":"E. Ch\u00e1vez","year":"2001","unstructured":"Ch\u00e1vez, E., Navarro, G., Baeza-Yates, R.A., Marroqu\u00edn, J.L.: Searching in metric spaces. ACM Comput. Surveys 33(3), 273\u2013321 (2001)","journal-title":"ACM Comput. Surveys"},{"key":"178_CR16","unstructured":"Ciaccia, P., Patella, M., Zezula, P.: M-Tree: An efficient access method for similarity search in metric spaces. In: Proceedings of 23rd International Conference on Very Large Data Bases (VLDB), Athens, Greece, pp. 426\u2013435. Morgan Kaufmann Publishers (1997)"},{"key":"178_CR17","unstructured":"de Sousa, E.P.M., Traina, C. Jr., Traina, A.J.M., Faloutsos, C.: How to use fractal dimension to find correlations between attributes. In: Proceeding of the First Workshop on Fractals and Self-Similarity in Data Mining: Issues and Approaches (in conjunction with 8th ACMSIGKDD International Conference on Knowledge Discovery & DataMining), Edmonton, Alberta, Canada, pp. 26\u201330. ACM Press (2002)"},{"key":"178_CR18","doi-asserted-by":"crossref","unstructured":"Faloutsos, C., Seeger, B., Traina, A.J.M., Traina, C. Jr.: Spatialjoin selectivity using power laws. In: Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, pp. 177\u2013188, Dallas, USA. ACM Press (2000)","DOI":"10.1145\/335191.335412"},{"issue":"9","key":"178_CR19","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1109\/34.232083","volume":"15","author":"A. Farag\u00f3","year":"1993","unstructured":"Farag\u00f3, A., Linder, T., Lugosi, G.: Fast nearest-neighbor search in dissimilarity spaces. IEEE Trans. Pattern Anal. Mach. Intell.(TPAMI) 15(9), 957\u2013962(1993)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell.(TPAMI)"},{"issue":"2","key":"178_CR20","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/PL00010672","volume":"9","author":"Ada Wai-Chee Fu","year":"2000","unstructured":"Fu, Ada Wai-Chee, Chan, Polly Mei Shuen, Cheung, Yin-Ling, Moon, Yiu Sang.: Dynamic vp-Tree indexing for n-nearest neighbor search given pair-wise distances. VLDB J. 9(2), 154\u2013173 (2000)","journal-title":"VLDB J."},{"issue":"2","key":"178_CR21","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1145\/280277.280279","volume":"30","author":"V. Gaede","year":"1998","unstructured":"Gaede, V., G\u00fcnther, O.: Multi dimensional access methods. ACM Comput. Surveys 30(2), 170\u2013231 (1998)","journal-title":"ACM Comput. Surveys"},{"key":"178_CR22","unstructured":"Gennaro, C., Savino, P., Zezula, P.: A hashed schema forsimilarity search in metric spaces. In: Proceeding of the 1st DELOS Network of Excellence Workshop on Information Seeking, Searching and Querying in Digital Libraries, pp. 83\u201388. Zurich, Switzerland (2000)"},{"key":"178_CR23","doi-asserted-by":"crossref","unstructured":"Guttman, A.: R-Tree : A dynamic index structure for spatial searching. In: Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data, Boston, USA, pp. 47\u201357. ACM Press (1984)","DOI":"10.1145\/602259.602266"},{"issue":"4","key":"178_CR24","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1145\/958942.958948","volume":"28","author":"G.R. Hjaltason","year":"2003","unstructured":"Hjaltason, G.R., Samet, H.: Index-driven similarity search inmetric spaces. ACM Trans. Database Syst. (TODS) 28(4), 517\u2013580 (2003)","journal-title":"ACM Trans. Database Syst. (TODS)"},{"key":"178_CR25","doi-asserted-by":"crossref","unstructured":"Ishikawa, M., Chen, H., Furuse, K., Yu, Jeffrey Xu, Ohbo, N.: Mb+tree: A dynamically updatable metric index for similarity searches. In: Proceedings of the First International Conference Web-Age Information Management (WAIM). Lecture Notes in Computer Science, vol. 1846, pp. 356\u2013373. Springer (2000)","DOI":"10.1007\/3-540-45151-X_34"},{"key":"178_CR26","doi-asserted-by":"crossref","unstructured":"Jin, Hui, Ooi, Beng Chin, Shen, Heng Tao, Yu, Cui, Zhou, Aoying.: An adaptive and efficient dimensionality reduction algorithm for high-dimensional indexing. In: Proceedings of the 19th International Conference on Data Engineering (ICDE), pp. 87\u201398. IEEE Computer Society (2003)","DOI":"10.1109\/ICDE.2003.1260784"},{"key":"178_CR27","doi-asserted-by":"crossref","unstructured":"Katayama, N., Satoh, S.: The SR-Tree: An index structure for high-dimensional nearest neighbor queries. In: Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data, pp. 369\u2013380. ACM Press (1997)","DOI":"10.1145\/253262.253347"},{"issue":"1","key":"178_CR28","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1109\/69.908983","volume":"13","author":"F. Korn","year":"2001","unstructured":"Korn, F., Pagel, Bernd-Uwe, Faloutsos, C.: On the \u2018dimensionality curse\u2019 and the \u2018self-similarity blessing\u2019. IEEE Trans. Knowledge Data Eng. (TKDE) 13(1), 96\u2013111 (2001)","journal-title":"IEEE Trans. Knowledge Data Eng. (TKDE)"},{"key":"178_CR29","doi-asserted-by":"crossref","unstructured":"Koudas, N., Ooi, Beng Chin, Shen, Heng Tao, Tung, A.K.H.: Ldc: enabling search by partial distance in a hyper-dimensional space. In: Proceedings of the 20th International Conference on Data Engineering (ICDE), pp. 6\u201317. IEEE Computer Society (2004)","DOI":"10.1109\/ICDE.2004.1319980"},{"issue":"8","key":"178_CR30","first-page":"707","volume":"10","author":"V.I. Levenshtein","year":"1966","unstructured":"Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Cybernet. Control Theory 10(8), 707\u2013710 (1966)","journal-title":"Cybernet. Control Theory"},{"issue":"4","key":"178_CR31","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/BF01231606","volume":"3","author":"K.-I. Lin","year":"1994","unstructured":"Lin, K.-I., Jagadish, H.V., Faloutsos, C.: The tv-tree: an index structure for high-dimensional data. VLDB J. 3(4), 517\u2013542 (1994)","journal-title":"VLDB J."},{"issue":"1","key":"178_CR32","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/0167-8655(94)90095-7","volume":"15","author":"L. Mic\u00f3","year":"1994","unstructured":"Mic\u00f3, L., Oncina, J., Vidal, E.: A new version of the nearest-neighbour approximating and eliminating search algorithm (aesa) with linear preprocessing time and memory requirements. Pattern Recog. Lett. 15(1), 9\u201317 (1994)","journal-title":"Pattern Recog. Lett."},{"key":"178_CR33","doi-asserted-by":"crossref","unstructured":"Moreno-Seco, F., Mic\u00f3, L., Oncina, J.: Extending laesa fastnearest neighbour algorithm to find the k nearest neighbours. In: Proceedings of the International Workshop of Structural, Syntactic, and Statistical Pattern Recognition (SSPR), Lecture Notes in Computer Science, vol. 2396, pp. 718\u2013724. Springer(2002)","DOI":"10.1007\/3-540-70659-3_75"},{"key":"178_CR34","doi-asserted-by":"crossref","unstructured":"Pagel, B.-U., Korn, F., Faloutsos, C.: Deflating the dimensionality curse using multiple fractal dimensions. In: Proceedings of the 16th International Conference on Data Engineering (ICDE), pp. 589\u2013598. IEEE Computer Society (2000)","DOI":"10.1109\/ICDE.2000.839457"},{"key":"178_CR35","doi-asserted-by":"crossref","unstructured":"Santos Filho, R.F., Traina, A.J.M., Traina, C. Jr., Faloutsos, C.: Similarity search without tears: the OMNI family of all-purpose access methods. In: Proceedings of the 17th International Conference on Data Engineering (ICDE), Heidelberg, Germany, pp. 623\u2013630. IEEE Computer Society (2001)","DOI":"10.1109\/ICDE.2001.914877"},{"key":"178_CR36","volume-title":"Fractals, Chaos, Power Laws.","author":"M. Schroeder","year":"1991","unstructured":"Schroeder, M.: Fractals, Chaos, Power Laws. W.H. Freeman &Company, New York, USA (1991)"},{"key":"178_CR37","unstructured":"Sellis, T.K.: Nick Roussopoulos, and Christos Faloutsos. The R+-Tree: A dynamic index for multi-dimensional objects. In: Proceedings of 13th International Conference on Very Large Databases (VLDB), Brighton, England, pp. 507\u2013518. Morgan Kaufmann Publishers (1987)"},{"issue":"10","key":"178_CR38","doi-asserted-by":"publisher","first-page":"1165","DOI":"10.1109\/34.954606","volume":"23","author":"A. Senior","year":"2001","unstructured":"Senior, A.: A combination fingerprint classifier. IEEE Trans. Pattern Anal. Mach. Intell. (TPAMI) 23(10), 1165\u20131175 (2001)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell. (TPAMI)"},{"key":"178_CR39","doi-asserted-by":"crossref","unstructured":"Traina, C., Agma, J.M. Jr., Faloutsos, C.: Distance exponent: a new concept for selectivity estimation in metric trees. In: Proceedings of the 16th International Conference on Data Engineering (ICDE), San Diego - CA, pp. 195. IEEE Computer Society (2000)","DOI":"10.21236\/ADA363780"},{"key":"178_CR40","doi-asserted-by":"crossref","unstructured":"Traina, A.J.M., Traina, C. Jr., Bueno, Josiane M., de Azevedo Marques, P.M.: The metric histogram: a new and effiretrieval. In: Proceedings of the Sixth IFIP Working Conference on Visual Database Systems (VDB), Brisbane, Australia, pp. 297\u2013311. Kluwer Academic Publishers (2002)","DOI":"10.1007\/978-0-387-35592-4_21"},{"issue":"2","key":"178_CR41","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1109\/69.991715","volume":"14","author":"C. Traina Jr.","year":"2002","unstructured":"Traina, C. Jr., Traina, A.J.M., Faloutsos, C., Seeger, B.: Fast indexing and visualization of metric datasets using slim-Trees. IEEE Trans. Knowledge Data Eng. (TKDE) 14(2), 244\u2013260 (2002)","journal-title":"IEEE Trans. Knowledge Data Eng. (TKDE)"},{"key":"178_CR42","doi-asserted-by":"crossref","unstructured":"Traina, C. Jr., Traina, A.J.M., Faloutsos, C.: Distance exponent:a new concept for selectivity estimation in metric trees. Research Paper CMU-CS-99-110, Carnegie Mellon University - School of Computer Science, Pittsburgh-PA USA, March 1999","DOI":"10.21236\/ADA363780"},{"key":"178_CR43","doi-asserted-by":"crossref","unstructured":"Traina, C. Jr., Traina, A.J.M., Seeger, B., Faloutsos, C.: Slim-Trees: High performance metric trees minimizing overlap between nodes. In: Proceedings of the International Conference on Extending Database Technology (EDBT). Lecture Notes in Computer Science, vol. 1777, pp. 51\u201365, Konstanz, Germany. Springer (2000)","DOI":"10.1007\/3-540-46439-5_4"},{"key":"178_CR44","unstructured":"Traina, C. Jr., Traina, A.J.M., Wu, L., Faloutsos, C.: Fast feature selection using fractal dimension. In: XV Brazilian Database Symposium (SBBD), Jo\u00e3o Pessoa, Brazil, pp. 158\u2013171 (2000)"},{"issue":"4","key":"178_CR45","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0020-0190(91)90074-R","volume":"40","author":"J.K. Uhlmann","year":"1991","unstructured":"Uhlmann, J.K.: Satisfying general proximity\/similarity querieswith metric trees. Inform. Process. Lett. 40(4), 175\u2013179 (1991)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"178_CR46","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1109\/2.745722","volume":"32","author":"H.D. Wactlar","year":"1999","unstructured":"Wactlar, H.D., Christel, M.G., Gong, Y., Hauptmann, A.G.: Lessons learned from building a terabyte digital video library. IEEE Comput. 32(2), 66\u201373 (1999)","journal-title":"IEEE Comput."},{"key":"178_CR47","unstructured":"Weber R., Schek, H.-J., Blott, S.: A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In: Proceedings of 24rd International Conference on Very Large Data Bases (VLDB), pp. 194\u2013205 (1998)"},{"key":"178_CR48","doi-asserted-by":"crossref","unstructured":"White, D.A., Jain, R.: Similarity indexing with the SS-Tree. In: Proceedings of the 12th International Conference on Data Engineering (ICDE), New Orleans, USA, pp. 516\u2013523. IEEE Computer Society (1996)","DOI":"10.1109\/ICDE.1996.492202"},{"key":"178_CR49","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1613\/jair.346","volume":"6","author":"D.R. Wilson","year":"1997","unstructured":"Wilson, D.R., Martinez, T.R.: Improved heterogeneous distance functions. J. Artif. Intell. Res. 6, 1\u201334 (1997)","journal-title":"J. Artif. Intell. Res."},{"key":"178_CR50","unstructured":"Yianilos, P.N.: Data structures and algorithms for nearestneighbor search in general metric spaces. In: Proceedings of the 4th Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms (SODA), Austin, USA, pp. 311\u2013321 (1993)"},{"key":"178_CR51","unstructured":"Yianilos, P.N.: Excluded middle vantage point forests for nearest neighbor search. Research paper, NEC Research Institute, Princeton, NJ, USA, Princeton, USA (1998)"},{"key":"178_CR52","unstructured":"Yu, Cui, Ooi, Beng Chin, Tan, Kian-Lee, Jagadish, H.V.: Indexing the distance: an efficient method to knn processing. In: Proceedings of 27th International Conference on Very Large Data Bases (VLDB), pp. 421\u2013430. Morgan Kaufmann (2001)"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-005-0178-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-005-0178-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-005-0178-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-005-0178-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T16:27:55Z","timestamp":1736440075000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-005-0178-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,6,29]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,10]]}},"alternative-id":["178"],"URL":"https:\/\/doi.org\/10.1007\/s00778-005-0178-0","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,6,29]]}}}