{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T16:58:10Z","timestamp":1759683490672,"version":"3.41.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p>\n            Metric space searching is an emerging technique to address the problem of efficient similarity searching in many applications, including multimedia databases and other repositories handling complex objects. Although promising, the metric space approach is still immature in several aspects that are well established in traditional databases. In particular, most indexing schemes are static, that is, few of them tolerate insertion or deletion of elements at reasonable cost over an existing index. The spatial approximation tree (\n            <jats:italic>sa--tree<\/jats:italic>\n            ) has been experimentally shown to provide a good tradeoff between construction cost, search cost, and space requirement. However, the\n            <jats:italic>sa--tree<\/jats:italic>\n            is static, which renders it unsuitable for many database applications. In this paper, we study different methods to handle insertions and deletions on the\n            <jats:italic>sa--tree<\/jats:italic>\n            at low cost. In many cases, the dynamic construction (by successive insertions) is even faster than the previous static construction, and both are similar elsewhere. In addition, the dynamic version significantly improves the search performance of\n            <jats:italic>sa--trees<\/jats:italic>\n            in virtually all cases. The result is a much more practical data structure that can be useful in a wide range of database applications.\n          <\/jats:p>","DOI":"10.1145\/1227161.1322337","type":"journal-article","created":{"date-parts":[[2008,10,8]],"date-time":"2008-10-08T13:57:58Z","timestamp":1223474278000},"page":"1-68","source":"Crossref","is-referenced-by-count":26,"title":["Dynamic spatial approximation trees"],"prefix":"10.1145","volume":"12","author":[{"given":"Gonzalo","family":"Navarro","sequence":"first","affiliation":[{"name":"University of Chile, Santiago, Chile"}]},{"given":"Nora","family":"Reyes","sequence":"additional","affiliation":[{"name":"Universidad Nacional de San Luis, San Luis, Argentina"}]}],"member":"320","published-online":{"date-parts":[[2008,6,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","unstructured":"Apers P. Blanken H. and Houtsma M. 1997. Multimedia Databases in Perspective. Springer New York.","DOI":"10.5555\/549518"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/553876"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/647814.738307"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502809"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253345"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/645921.673006"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/362003.362025"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/646491.694974"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.53"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/646679.702317"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2004.11.014"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/519452.830765"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011343115154"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502808"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/645923.671005"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009449"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4379(87)90041-X"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30192-9_13"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025026030880"},{"key":"e_1_2_1_21_1","unstructured":"Duda R. and Hart P. 1973. Pattern Classification and Scene Analysis. Wiley New York."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/280277.280279"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/313559.313676"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/262228"},{"key":"e_1_2_1_25_1","volume-title":"Tech. Rep. CS-TR-4199","author":"Hjaltason G.","year":"2000","unstructured":"Hjaltason, G. and Samet, H. 2000. Incremental similarity search in multimedia databases. Tech. Rep. CS-TR-4199, University of Maryland, Computer Science Department."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(03)00122-3"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/958942.958948"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510013"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","unstructured":"Krauthgamer R. and Lee J. 2004. Navigating nets: simple algorithms for proximity search. In SODA. 798--807.","DOI":"10.5555\/982792.982913"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/146370.146380"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(94)90095-7"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(96)00032-3"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/519452.830772"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780200060"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/646491.694958"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/646491.694958"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/950790.951316"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/950790.951316"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.615448"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","unstructured":"Noltemeier H. Verbarg K. and Zirkelbach C. 1992. Monotonous Bisector&ast; Trees---a tool for efficient partitioning of complex schenes of geometric objects. In Data Structures and Efficient Algorithms. LNCS 594. Springer-Verlag New York. 186--203.","DOI":"10.5555\/647823.736538"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/576628"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/1076819"},{"key":"e_1_2_1_43_1","volume-title":"Eds","author":"Sankoff D.","year":"1983","unstructured":"Sankoff, D. and Kruskal, J., Eds. 1983. Time Warps, String Edits, and Macromolecules: the Theory and Practice of Sequence Comparison. Addison-Wesley, Reading, MA."},{"volume-title":"ADBIS (Local Proceedings).","author":"Skopal T.","key":"e_1_2_1_44_1","unstructured":"Skopal, T., Pokorn\u00fd, J., and Sn\u00e1sel, V. 2004. PM-tree: Pivoting metric tree for similarity search in multimedia databases. In ADBIS (Local Proceedings)."},{"key":"e_1_2_1_45_1","volume-title":"Proc. Command and Control Symposium","author":"Uhlmann J.","year":"1991","unstructured":"Uhlmann, J. 1991a. Implementing metric trees to satisfy general proximity\/similarity queries. In Proc. Command and Control Symposium. Washington, DC. Also published as Code 5570 NRL Memo Report (1991) at the Naval Research Laboratory."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90074-R"},{"key":"e_1_2_1_47_1","unstructured":"Uribe R. and Navarro G. 2003. Una estructura din\u00e1mica para b\u00fasqueda en espacios m\u00e9tricos. In Actas del XI Encuentro Chileno de Computaci\u00f3n Jornadas Chilenas de Computaci\u00f3n. Chill\u00e1n Chile. In Spanish. In CD-ROM."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7091-7584-2_22"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(86)90013-9"},{"volume-title":"Introduction to Computational Biology: Maps, Sequences and Genomes","author":"Waterman M.","key":"e_1_2_1_50_1","unstructured":"Waterman, M. 1995. Introduction to Computational Biology: Maps, Sequences and Genomes. Chapman and Hall\/CRC, Boca Raton, FL."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/313559.313789"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/338219.338273"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.755617"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/1121569"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1322337","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1227161.1322337","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:37Z","timestamp":1750278157000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1322337"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":54,"alternative-id":["10.1145\/1227161.1322337"],"URL":"https:\/\/doi.org\/10.1145\/1227161.1322337","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}