{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T16:59:11Z","timestamp":1759683551466,"version":"3.41.0"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,5,24]],"date-time":"2017-05-24T00:00:00Z","timestamp":1495584000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2017,8]]},"DOI":"10.1007\/s00778-017-0465-6","type":"journal-article","created":{"date-parts":[[2017,5,24]],"date-time":"2017-05-24T10:48:52Z","timestamp":1495622932000},"page":"585-610","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Indexing metric uncertain data for range queries and range joins"],"prefix":"10.1007","volume":"26","author":[{"given":"Lu","family":"Chen","sequence":"first","affiliation":[]},{"given":"Yunjun","family":"Gao","sequence":"additional","affiliation":[]},{"given":"Aoxiao","family":"Zhong","sequence":"additional","affiliation":[]},{"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[]},{"given":"Gang","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Baihua","family":"Zheng","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,24]]},"reference":[{"key":"465_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Cheng, S.W., Tao, Y., Yi, K.: Indexing uncertain data. In: PODS, pp. 137\u2013146 (2009)","DOI":"10.1007\/978-0-387-09690-2"},{"key":"465_CR2","doi-asserted-by":"crossref","unstructured":"Aggarwal, C., Yu, P.: On high dimensional indexing of uncertain data. In: ICDE, pp. 1460\u20131461 (2008)","DOI":"10.1109\/ICDE.2008.4497589"},{"issue":"9","key":"465_CR3","doi-asserted-by":"crossref","first-page":"1640","DOI":"10.1109\/TKDE.2011.93","volume":"24","author":"F Angiulli","year":"2012","unstructured":"Angiulli, F., Fassetti, F.: Indexing uncertain data in general metric space. IEEE Trans. Knowl. Data Eng. 24(9), 1640\u20131657 (2012)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"465_CR4","doi-asserted-by":"crossref","unstructured":"Bohm, C., Kunath, P., Schubert, M.: The Gauss-tree: efficient object identification of probabilistic feature vectors. In: ICDE, article 9 (2006)","DOI":"10.1109\/ICDE.2006.159"},{"issue":"14","key":"465_CR5","doi-asserted-by":"crossref","first-page":"2357","DOI":"10.1016\/S0167-8655(03)00065-5","volume":"24","author":"B Bustos","year":"2003","unstructured":"Bustos, B., Navarro, G., Chavez, E.: Pivot selection techniques for proximity searching in metric spaces. Pattern Recognit. Lett. 24(14), 2357\u20132366 (2003)","journal-title":"Pattern Recognit. Lett."},{"key":"465_CR6","doi-asserted-by":"crossref","unstructured":"Chen, J., Cheng, R.: Efficient evaluation of imprecise location-dependent queries. In: ICDE, pp. 586\u2013595 (2007)","DOI":"10.1109\/ICDE.2007.367904"},{"key":"465_CR7","doi-asserted-by":"crossref","unstructured":"Chen, L., Gao, Y., Li, X., Jensen, C.S., Chen, G.: Efficient metric indexing for similarity search. In: ICDE, pp. 591\u2013602 (2015)","DOI":"10.1109\/ICDE.2015.7113317"},{"key":"465_CR8","doi-asserted-by":"crossref","unstructured":"Chen, L., Gao, Y., Li, X., Jensen, C.S., Chen, G., Zheng, B.: Indexing metric uncertain data for range queries. In: SIGMOD, pp. 951\u2013965 (2015)","DOI":"10.1145\/2723372.2723728"},{"key":"465_CR9","doi-asserted-by":"crossref","unstructured":"Cheng, R., Singh, S., Prabhakar, S., Shah, R., Vitter, J.S., Xia, Y.: Efficient join processing over uncertain data. In: CIKM, pp. 738\u2013747 (2006)","DOI":"10.1145\/1183614.1183719"},{"key":"465_CR10","doi-asserted-by":"crossref","unstructured":"Cheng, R., Xia, Y., Prabhakar, S., Shah, R., Vitter, J.S.: Efficient indexing methods for probabilistic threshold queries over uncertain data. In: VLDB, pp. 876\u2013887 (2004)","DOI":"10.1016\/B978-012088469-8.50077-2"},{"key":"465_CR11","doi-asserted-by":"crossref","unstructured":"Chung, C.W., Pan, C.H., Liu, C.M.: An effective index for uncertain data. In: IS3C, pp. 482\u2013485 (2014)","DOI":"10.1109\/IS3C.2014.132"},{"key":"465_CR12","doi-asserted-by":"crossref","unstructured":"Ciaccia, P., Patella, M., Zezula, P.: M-tree: an efficient access method for similarity search in metric spaces. In: VLDB, pp. 426\u2013435 (1997)","DOI":"10.1145\/275487.275495"},{"key":"465_CR13","doi-asserted-by":"crossref","unstructured":"Dai, D., Xie, J., Zhang, H., Dong, J.: Efficient range queries over uncertain strings. In: SSDBM, pp. 75\u201395 (2012)","DOI":"10.1007\/978-3-642-31235-9_5"},{"issue":"1","key":"465_CR14","first-page":"13","volume":"8","author":"M Dallachiesa","year":"2014","unstructured":"Dallachiesa, M., Palpanas, T., Ilyas, I.F.: Top- $$k$$ k nearest neighbor search in uncertain data series. PVLDB 8(1), 13\u201324 (2014)","journal-title":"PVLDB"},{"key":"465_CR15","doi-asserted-by":"crossref","unstructured":"Fredriksson, K., Braithwaite, B.: Quicker similarity joins in metric spaces. In: SISAP, pp. 127\u2013140 (2013)","DOI":"10.1007\/978-3-642-41062-8_13"},{"issue":"3","key":"465_CR16","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1109\/TKDE.2008.164","volume":"21","author":"E Frentzos","year":"2008","unstructured":"Frentzos, E., Gratsias, K., Theodoridis, Y.: On the effect of location uncertainty in spatial querying. IEEE Trans. Knowl. Data Eng. 21(3), 366\u2013383 (2008)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"465_CR17","doi-asserted-by":"crossref","unstructured":"Gao, M., Jin, C., Wang, W., Lin, X., Zhou, A.: Similarity query processing for probabilistic sets. In: ICDE, pp. 913\u2013924 (2013)","DOI":"10.1109\/ICDE.2013.6544885"},{"key":"465_CR18","doi-asserted-by":"crossref","unstructured":"Ge, T., Li, Z.: Approximate substring matching over uncertain strings. In: PVLDB vol. 4(11), pp. 772\u2013782 (2011)","DOI":"10.14778\/3402707.3402717"},{"issue":"301","key":"465_CR19","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13\u201330 (1963)","journal-title":"J. Am. Stat. Assoc."},{"key":"465_CR20","doi-asserted-by":"crossref","unstructured":"Jacox, E.H., Samet, H.: Metric space similarity joins. ACM Trans. Database Syst. 33(2), 7:1\u20137:38 (2008)","DOI":"10.1145\/1366102.1366104"},{"key":"465_CR21","doi-asserted-by":"crossref","unstructured":"Jestes, J., Li, F., Yan, Z., Yi, K.: Probabilistic string similarity joins. In: SIGMOD, pp. 327\u2013338 (2010)","DOI":"10.1145\/1807167.1807204"},{"key":"465_CR22","doi-asserted-by":"crossref","unstructured":"Jin, R., Liu, L., Ding, B., Wang, H.: Distance constraint reachability computation in uncertain graphs. In: PVLDB vol. 4(9), pp. 511\u2013562 (2011)","DOI":"10.14778\/2002938.2002941"},{"key":"465_CR23","doi-asserted-by":"crossref","unstructured":"Kimura, H., Madden, S., Zdonik, S.B.: UPI: a primary index for uncertain databases. In: PVLDB vol. 3(1), pp. 630\u2013637 (2010)","DOI":"10.14778\/1920841.1920922"},{"key":"465_CR24","doi-asserted-by":"crossref","unstructured":"Knight, A., Yu, Q., Rege, M.: Efficient range query processing on complicated uncertain data. In: Ozyer, T., Kianmehr, K., Tan, M., Zeng, J. (eds.) Information Reuse and Integration in Academia and Industry, pp.\u00a051\u201372. Springer, Vienna (2013)","DOI":"10.1007\/978-3-7091-1538-1_3"},{"key":"465_CR25","doi-asserted-by":"crossref","unstructured":"Kriegel, H.P., Bernecker, T., Renz, M., Zuefle, A.: Probabilistic join queries in uncertain databases. In: Aggarwal, C. C. (ed.) Managing and Mining Uncertain Data, pp.\u00a0257\u2013298. Springer, New York (2009)","DOI":"10.1145\/1557019.1557039"},{"key":"465_CR26","doi-asserted-by":"crossref","unstructured":"Kriegel, H.P., Kunath, P., Pfeifle, M., Renz, M.: Probabilistic similarity join on uncertain data. In: DASFAA, pp. 295\u2013309 (2006)","DOI":"10.1007\/11733836_22"},{"key":"465_CR27","doi-asserted-by":"crossref","unstructured":"Lian, X., Chen, L.: A generic framework for handling uncertain data with local correlations. In: PVLDB, vol. 4(1), pp. 12\u201321 (2010)","DOI":"10.14778\/1880172.1880174"},{"key":"465_CR28","doi-asserted-by":"crossref","unstructured":"Lian, X., Chen, L.: Set similarity join on probabilistic data. In: PVLDB, vol. 3(1), pp. 650\u2013659 (2010)","DOI":"10.14778\/1920841.1920924"},{"key":"465_CR29","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.jda.2011.10.004","volume":"13","author":"R Mao","year":"2012","unstructured":"Mao, R., Mirankerb, W.L., Mirankerc, D.P.: Pivot selection: dimension reduction for distance-based indexing. J. Discrete Algorithms 13, 32\u201346 (2012)","journal-title":"J. Discrete Algorithms"},{"issue":"4","key":"465_CR30","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1016\/j.is.2010.10.002","volume":"36","author":"D Novak","year":"2011","unstructured":"Novak, D., Batko, M., Zezula, P.: Metric index: an efficient and scalable solution for precise and approximate similarity search. Inf. Syst. 36(4), 721\u2013723 (2011)","journal-title":"Inf. Syst."},{"issue":"1","key":"465_CR31","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/j.jda.2008.09.012","volume":"7","author":"R Paredes","year":"2009","unstructured":"Paredes, R., Reyes, N.: Solving similarity joins and range queries in metric spaces with the list of twin clusters. J. Discrete Algorithms 7(1), 18\u201335 (2009)","journal-title":"J. Discrete Algorithms"},{"key":"465_CR32","doi-asserted-by":"crossref","unstructured":"Pearson, S.S., Silva, Y.N.: Index-based R-S similarity joins. In: SISAP, pp. 106\u2013112 (2014)","DOI":"10.1007\/978-3-319-11988-5_10"},{"key":"465_CR33","doi-asserted-by":"crossref","unstructured":"Sarma, A.D., He, Y., Chaudhuri, S.: Clusterjoin: a similarity joins framework using map-reduce. In: PVLDB, vol. 7(12), pp. 1059\u20131070 (2014)","DOI":"10.14778\/2732977.2732981"},{"key":"465_CR34","doi-asserted-by":"crossref","unstructured":"Silva, Y.N., Aref, W.G., Ali, M.H.: The similarity join database operator. In: ICDE, pp. 892\u2013903 (2010)","DOI":"10.1109\/ICDE.2010.5447873"},{"key":"465_CR35","doi-asserted-by":"crossref","unstructured":"Silva, Y.N., Pearson, S.: Exploiting database similarity joins for metric spaces. In: PVLDB, vol. 5(12), pp. 1922\u20131925 (2012)","DOI":"10.14778\/2367502.2367538"},{"key":"465_CR36","doi-asserted-by":"crossref","unstructured":"Singh, S., Mayfield, C., Prabhakar, S., Shah, R., Hambrusch, S.E.: Indexing uncertain categorical data. In: ICDE, pp. 616\u2013625 (2007)","DOI":"10.1109\/ICDE.2007.367907"},{"key":"465_CR37","doi-asserted-by":"crossref","unstructured":"Skopal, T., Pokorny, J., Snasel, V.: PM-tree: pivoting metric tree for similarity search in multimedia databases. In: ADBIS, pp. 803\u2013815 (2004)","DOI":"10.1007\/11408079_73"},{"key":"465_CR38","doi-asserted-by":"crossref","unstructured":"Tao, Y., Xiao, X., Cheng, R.: Range search on multidimensional uncertain data. ACM Trans. Database Syst. 32(3), 15:1\u201315:54 (2007)","DOI":"10.1145\/1272743.1272745"},{"key":"465_CR39","doi-asserted-by":"crossref","unstructured":"Traina Jr, C., Traina, A.J.M., Seeger, B., Faloutsos, C.: Slim-trees: high performance metric trees minimizing overlap between nodes. In: ICDE, pp. 51\u201365 (2000)","DOI":"10.1007\/3-540-46439-5_4"},{"key":"465_CR40","doi-asserted-by":"crossref","unstructured":"Traina Jr, C., Filho, R.F.S., Traina, A.J.M., Vieira, M.R., Faloutsos, C.: The omni-family of all-purpose access methods: a simple and effective way to make similarity search more efficient. VLDB J. 16(4), 483\u2013505 (2007)","DOI":"10.1007\/s00778-005-0178-0"},{"issue":"3","key":"465_CR41","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0167-8655(86)90013-9","volume":"4","author":"E Vidal","year":"1986","unstructured":"Vidal, E.: An algorithm for finding nearest neighbors in (approximately) constant average time. Pattern Recognit. Lett. 4(3), 145\u2013157 (1986)","journal-title":"Pattern Recognit. Lett."},{"key":"465_CR42","doi-asserted-by":"crossref","unstructured":"Wang, Y., Metwally, A., Parthasarathy, S.: Scalable all-pairs similarity search in metric spaces. In: KDD, pp. 829\u2013837 (2013)","DOI":"10.1145\/2487575.2487625"},{"issue":"9","key":"465_CR43","doi-asserted-by":"crossref","first-page":"1247","DOI":"10.1109\/TKDE.2010.77","volume":"22","author":"Y Zhang","year":"2010","unstructured":"Zhang, Y., Lin, X., Zhang, W., Wang, J., Lin, Q.: Effectively indexing the uncertain space. IEEE Trans. Knowl. Data Eng. 22(9), 1247\u20131261 (2010)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"465_CR44","doi-asserted-by":"crossref","unstructured":"Zhang, Y., Zhang, W., Lin, Q., Lin, X.: Effectively indexing the multi-dimensional uncertain objects for range searching. In: EDBT, pp. 504\u2013515 (2012)","DOI":"10.1145\/2247596.2247655"},{"key":"465_CR45","doi-asserted-by":"crossref","unstructured":"Zhu, R., Wang, B., Wang, G.: Indexing uncertain data for supporting range queries. In: WAIM, pp. 72\u201383 (2014)","DOI":"10.1007\/978-3-319-08010-9_10"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-017-0465-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-017-0465-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-017-0465-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:43:37Z","timestamp":1750275817000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-017-0465-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,24]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["465"],"URL":"https:\/\/doi.org\/10.1007\/s00778-017-0465-6","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"type":"print","value":"1066-8888"},{"type":"electronic","value":"0949-877X"}],"subject":[],"published":{"date-parts":[[2017,5,24]]}}}