{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:45:14Z","timestamp":1750308314317,"version":"3.41.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2007,6,1]],"date-time":"2007-06-01T00:00:00Z","timestamp":1180656000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2007,6]]},"abstract":"<jats:p>\n            A common problem in many types of databases is retrieving the most similar matches to a query object. Finding these matches in a large database can be too slow to be practical, especially in domains where objects are compared using computationally expensive similarity (or distance) measures. Embedding methods can significantly speed-up retrieval by mapping objects into a vector space, where distances can be measured rapidly using a Minkowski metric. In this article we present a novel way to improve embedding quality. In particular, we propose to construct embeddings that use a\n            <jats:italic>query-sensitive<\/jats:italic>\n            distance measure for the target space of the embedding. This distance measure is used to compare those vectors that the query and database objects are mapped to. The term \u201cquery-sensitive\u201d means that the distance measure changes, depending on the current query object. We demonstrate theoretically that using a query-sensitive distance measure increases the modeling power of embeddings and allows them to capture more of the structure of the original space. We also demonstrate experimentally that query-sensitive embeddings can significantly improve retrieval performance. In experiments with an image database of handwritten digits and a time-series database, the proposed method outperforms existing state-of-the-art non-Euclidean indexing methods, meaning that it provides significantly better tradeoffs between efficiency and retrieval accuracy.\n          <\/jats:p>","DOI":"10.1145\/1242524.1242525","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"8","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Query-sensitive embeddings"],"prefix":"10.1145","volume":"32","author":[{"given":"Vassilis","family":"Athitsos","sequence":"first","affiliation":[{"name":"Boston University, Boston, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marios","family":"Hadjieleftheriou","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs-Research, Florham Park, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George","family":"Kollios","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stan","family":"Sclaroff","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/373626.373638"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2005.141"},{"volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 268--275","author":"Athitsos V.","key":"e_1_2_1_4_1","unstructured":"Athitsos , V. , Alon , J. , Sclaroff , S. , and Kollios , G . 2004. BoostMap: A method for efficient approximate similarity rankings . In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 268--275 . Athitsos, V., Alon, J., Sclaroff, S., and Kollios, G. 2004. BoostMap: A method for efficient approximate similarity rankings. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 268--275."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066238"},{"volume-title":"Proceedings of the Gesture Workshop.","author":"Athitsos V.","key":"e_1_2_1_6_1","unstructured":"Athitsos , V. and Sclaroff , S . 2003. Database indexing methods for 3D hand pose estimation . In Proceedings of the Gesture Workshop. ( Heidelberg, Germany) Springer Verlag. 288--299. Athitsos, V. and Sclaroff, S. 2003. Database indexing methods for 3D hand pose estimation. In Proceedings of the Gesture Workshop. (Heidelberg, Germany) Springer Verlag. 288--299."},{"volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence. 659--663","author":"Barrow H.","key":"e_1_2_1_7_1","unstructured":"Barrow , H. , Tenenbaum , J. , Bolles , R. , and Wolf , H . 1977. Parametric correspondence and Chamfer matching: Two new techniques for image matching . In Proceedings of the International Joint Conference on Artificial Intelligence. 659--663 . Barrow, H., Tenenbaum, J., Bolles, R., and Wolf, H. 1977. Parametric correspondence and Chamfer matching: Two new techniques for image matching. In Proceedings of the International Joint Conference on Artificial Intelligence. 659--663."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.993558"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502809"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02776078"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/328939.328959"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases. 89--100","author":"Chakrabarti K.","key":"e_1_2_1_12_1","unstructured":"Chakrabarti , K. and Mehrotra , S . 2000. Local dimensionality reduction: A new approach to indexing high dimensional spaces . In Proceedings of the International Conference on Very Large Data Bases. 89--100 . Chakrabarti, K. and Mehrotra, S. 2000. Local dimensionality reduction: A new approach to indexing high dimensional spaces. In Proceedings of the International Conference on Very Large Data Bases. 89--100."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2002.1033219"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/354756.354822"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223812"},{"volume-title":"Proceedings of the International Conference on Very Large Databases. 518--529","author":"Gionis A.","key":"e_1_2_1_16_1","unstructured":"Gionis , A. , Indyk , P. , and Motwani , R . 1999. Similarity search in high dimensions via hashing . In Proceedings of the International Conference on Very Large Databases. 518--529 . Gionis, A., Indyk, P., and Motwani, R. 1999. Similarity search in high dimensions via hashing. In Proceedings of the International Conference on Very Large Databases. 518--529."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.506411"},{"key":"e_1_2_1_18_1","unstructured":"Hinneburg A. Aggarwal C. C. and Keim D. A. 2000. What is the nearest neighbor in high dimensional spaces&quest; In Proceedings of the International Conference on Very Large Data Bases. 506--515.   Hinneburg A. Aggarwal C. C. and Keim D. A. 2000. What is the nearest neighbor in high dimensional spaces&quest; In Proceedings of the International Conference on Very Large Data Bases. 506--515."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2003.1195989"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/958942.958948"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.232073"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.862197"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276320"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287405"},{"volume-title":"Proceedings of the IEEE International Conference on Data Engineering. 6--17","author":"Koudas N.","key":"e_1_2_1_26_1","unstructured":"Koudas , N. , Ooi , B. C. , Shen , H. T. , and Tung , A. K. H. 2004. LDC: Enabling search by partial distance in a hyper-dimensional space . In Proceedings of the IEEE International Conference on Data Engineering. 6--17 . Koudas, N., Ooi, B. C., Shen, H. T., and Tung, A. K. H. 2004. LDC: Enabling search by partial distance in a hyper-dimensional space. In Proceedings of the IEEE International Conference on Data Engineering. 6--17."},{"key":"e_1_2_1_27_1","unstructured":"Kruskall J. B. and Liberman M. 1983. The symmetric time warping algorithm: From continuous to discrete. In Time Warps. Addison-Wesley.  Kruskall J. B. and Liberman M. 1983. The symmetric time warping algorithm: From continuous to discrete. In Time Warps. Addison-Wesley."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.726791"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2002.1019214"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(00)00064-7"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.290.5500.2323"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2003.1260787"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases. 516--526","author":"Sakurai Y.","key":"e_1_2_1_33_1","unstructured":"Sakurai , Y. , Yoshikawa , M. , Uemura , S. , and Kojima , H . 2000. The A-tree: An index structure for high-dimensional spaces using relative approximation . In Proceedings of the International Conference on Very Large Data Bases. 516--526 . Sakurai, Y., Yoshikawa, M., Uemura, S., and Kojima, H. 2000. The A-tree: An index structure for high-dimensional spaces using relative approximation. In Proceedings of the International Conference on Very Large Data Bases. 516--526."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007614523901"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.290.5500.2319"},{"volume-title":"Proceedings of the 7th International Conference on Extending Database Technology (EDBT). 51--65","author":"Traina Jr., C.","key":"e_1_2_1_36_1","unstructured":"Traina , Jr., C. , Traina , A. , Seeger , B. , and Faloutsos , C . 2000. Slim-Trees: High performance metric trees minimizing overlap between nodes . In Proceedings of the 7th International Conference on Extending Database Technology (EDBT). 51--65 . Traina, Jr., C., Traina, A., Seeger, B., and Faloutsos, C. 2000. Slim-Trees: High performance metric trees minimizing overlap between nodes. In Proceedings of the 7th International Conference on Extending Database Technology (EDBT). 51--65."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956777"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s101150050009"},{"volume-title":"Proceedings of the International Conference on Extending Database Technology. 21--35","author":"Weber R.","key":"e_1_2_1_39_1","unstructured":"Weber , R. and B\u00f6hm , K . 2000. Trading quality for time with nearest-neighbor search . In Proceedings of the International Conference on Extending Database Technology. 21--35 . Weber, R. and B\u00f6hm, K. 2000. Trading quality for time with nearest-neighbor search. In Proceedings of the International Conference on Extending Database Technology. 21--35."},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases. 194--205","author":"Weber R.","key":"e_1_2_1_40_1","unstructured":"Weber , R. , Schek , H.-J. , and Blott , S . 1998. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces . In Proceedings of the International Conference on Very Large Data Bases. 194--205 . Weber, R., Schek, H.-J., and Blott, S. 1998. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In Proceedings of the International Conference on Very Large Data Bases. 194--205."},{"volume-title":"Proceedings of the SPIE Storage and Retrieval for Image and Video Databases. 62--73","author":"White D. A.","key":"e_1_2_1_41_1","unstructured":"White , D. A. and Jain , R . 1996. Similarity indexing: Algorithms and performance . In Proceedings of the SPIE Storage and Retrieval for Image and Video Databases. 62--73 . White, D. A. and Jain, R. 1996. Similarity indexing: Algorithms and performance. In Proceedings of the SPIE Storage and Retrieval for Image and Video Databases. 62--73."},{"volume-title":"Proceedings of the IEEE International Conference on Data Engineering. 201--208","author":"Yi B.-K.","key":"e_1_2_1_42_1","unstructured":"Yi , B.-K. , Jagadish , H. V. , and Faloutsos , C . 1998. Efficient retrieval of similar time sequences under time warping . In Proceedings of the IEEE International Conference on Data Engineering. 201--208 . Yi, B.-K., Jagadish, H. V., and Faloutsos, C. 1998. Efficient retrieval of similar time sequences under time warping. In Proceedings of the IEEE International Conference on Data Engineering. 201--208."},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 311--321","author":"Yianilos P.","year":"1993","unstructured":"Yianilos , P. 1993 . Data structures and algorithms for nearest neighbor search in general metric spaces . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 311--321 . Yianilos, P. 1993. Data structures and algorithms for nearest neighbor search in general metric spaces. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 311--321."},{"key":"e_1_2_1_44_1","volume-title":"Multidimensional Scaling: History, Theory and Applications","author":"Young F.","year":"1987","unstructured":"Young , F. and Hamer , R . 1987 . Multidimensional Scaling: History, Theory and Applications . Lawrence Erlbaum , Hillsdale, NJ . Young, F. and Hamer, R. 1987. Multidimensional Scaling: History, Theory and Applications. Lawrence Erlbaum, Hillsdale, NJ."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050069"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1242524.1242525","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1242524.1242525","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:38:56Z","timestamp":1750268336000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1242524.1242525"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,6]]}},"alternative-id":["10.1145\/1242524.1242525"],"URL":"https:\/\/doi.org\/10.1145\/1242524.1242525","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2007,6]]},"assertion":[{"value":"2007-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}