{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:32:47Z","timestamp":1750307567199,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,5,1]],"date-time":"2010-05-01T00:00:00Z","timestamp":1272672000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["#IIS-0414576#IIS-04145940"],"award-info":[{"award-number":["#IIS-0414576#IIS-04145940"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2010,5]]},"abstract":"<jats:p>\n            Numerous techniques have been proposed in the past for supporting efficient\n            <jats:italic>k<\/jats:italic>\n            -nearest neighbor (\n            <jats:italic>k<\/jats:italic>\n            -NN) queries in continuous data spaces. Limited work has been reported in the literature for\n            <jats:italic>k<\/jats:italic>\n            -NN queries in a nonordered discrete data space (NDDS). Performing\n            <jats:italic>k<\/jats:italic>\n            -NN queries in an NDDS raises new challenges. The Hamming distance is usually used to measure the distance between two vectors (objects) in an NDDS. Due to the coarse granularity of the Hamming distance, a\n            <jats:italic>k<\/jats:italic>\n            -NN query in an NDDS may lead to a high degree of nondeterminism for the query result. We propose a new distance measure, called Granularity-Enhanced Hamming (GEH) distance, which effectively reduces the number of candidate solutions for a query. We have also implemented\n            <jats:italic>k<\/jats:italic>\n            -NN queries using multidimensional database indexing in NDDSs. Further, we use the properties of our multidimensional NDDS index to derive the probability of encountering valid neighbors within specific regions of the index. This probability is used to develop a new search ordering heuristic. Our experiments on synthetic and genomic data sets demonstrate that our index-based\n            <jats:italic>k<\/jats:italic>\n            -NN algorithm is efficient in finding\n            <jats:italic>k<\/jats:italic>\n            -NNs in both uniform and nonuniform data sets in NDDSs and that our heuristics are effective in improving the performance of such queries.\n          <\/jats:p>","DOI":"10.1145\/1740592.1740595","type":"journal-article","created":{"date-parts":[[2010,6,8]],"date-time":"2010-06-08T12:37:24Z","timestamp":1276000644000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Efficient k-nearest neighbor searching in nonordered discrete data spaces"],"prefix":"10.1145","volume":"28","author":[{"given":"Dashiell","family":"Kolbe","sequence":"first","affiliation":[{"name":"Michigan State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qiang","family":"Zhu","sequence":"additional","affiliation":[{"name":"University of Michigan\u2014Dearborn"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sakti","family":"Pramanik","sequence":"additional","affiliation":[{"name":"Michigan State University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,6,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0263-7855(92)80069-P"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"volume-title":"Proceedings of the 22nd International Conference on Very Large Databases. 28--39","author":"Berchtold S.","key":"e_1_2_1_3_1","unstructured":"Berchtold , S. , Keim , D. A. , and Kriegel , H . -P. 1996. The X-tree: An index structure for high-dimensional data . In Proceedings of the 22nd International Conference on Very Large Databases. 28--39 . Berchtold, S., Keim, D. A., and Kriegel, H.-P. 1996. The X-tree: An index structure for high-dimensional data. In Proceedings of the 22nd International Conference on Very Large Databases. 28--39."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1020499411651"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502808"},{"volume-title":"Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB). 426--435","author":"Ciaccia P.","key":"e_1_2_1_6_1","unstructured":"Ciaccia , P. , Patella , M. , and Zezula , P . 1997. M-tree: An efficient access method for similarity search in metric spaces . In Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB). 426--435 . Ciaccia, P., Patella, M., and Zezula, P. 1997. M-tree: An efficient access method for similarity search in metric spaces. In Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB). 426--435."},{"key":"e_1_2_1_7_1","volume-title":"R-trees: A Dynamic Index Structure for Spatial Searching","author":"Guttman A.","year":"1988","unstructured":"Guttman , A. 1988 . R-trees: A Dynamic Index Structure for Spatial Searching . Morgan Kaufmann Publishers Inc ., San Francisco, CA. Guttman, A. 1988. R-trees: A Dynamic Index Structure for Spatial Searching. Morgan Kaufmann Publishers Inc., San Francisco, CA."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1950.tb00463.x"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/645483.656224"},{"key":"e_1_2_1_10_1","volume-title":"Tech. Rep. TR-4199, Computer-Science Department","author":"Hjaltason G.","year":"2000","unstructured":"Hjaltason , G. and Samet , H . 2000 . Incremental similarity search in multimedia databases. Tech. Rep. TR-4199, Computer-Science Department , University of Maryland. Hjaltason, G. and Samet, H. 2000. Incremental similarity search in multimedia databases. Tech. Rep. TR-4199, Computer-Science Department, University of Maryland."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.229202"},{"volume-title":"Proceedings of the 13th international Conference on Very Large Data Bases (VLDB). 840--851","author":"Kolahdouzan M.","key":"e_1_2_1_12_1","unstructured":"Kolahdouzan , M. and Shahabi , C . 2004. Voronoi-based k nearest neighbor search for spatial network databases . In Proceedings of the 13th international Conference on Very Large Data Bases (VLDB). 840--851 . Kolahdouzan, M. and Shahabi, C. 2004. Voronoi-based k nearest neighbor search for spatial network databases. In Proceedings of the 13th international Conference on Very Large Data Bases (VLDB). 840--851."},{"volume-title":"Proceedings of the 23rd International Conference on Data Engineering (ICDE). 426--435","author":"Kolbe D.","key":"e_1_2_1_13_1","unstructured":"Kolbe , D. , Zhu , Q. , and Pramanik , S . 2007. On k-nearest neighbor searching in nonordered discrete data spaces . In Proceedings of the 23rd International Conference on Data Engineering (ICDE). 426--435 . Kolbe, D., Zhu, Q., and Pramanik, S. 2007. On k-nearest neighbor searching in nonordered discrete data spaces. In Proceedings of the 23rd International Conference on Data Engineering (ICDE). 426--435."},{"volume-title":"Proceedings of the 22th International Conference on Very Large Data Bases (VLDB). 215--226","author":"Korn F.","key":"e_1_2_1_14_1","unstructured":"Korn , F. , Sidiropoulos , N. , Faloutsos , C. , Siegel , E. , and Protopapas , Z . 1996. Fast nearest neighbor search in medical image databases . In Proceedings of the 22th International Conference on Very Large Data Bases (VLDB). 215--226 . Korn, F., Sidiropoulos, N., Faloutsos, C., Siegel, E., and Protopapas, Z. 1996. Fast nearest neighbor search in medical image databases. In Proceedings of the 22th International Conference on Very Large Data Bases (VLDB). 215--226."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pmed.0050050"},{"volume-title":"Proceedings of the 29th International Conference on Very Large Data Bases (VLDB). 620--631","author":"Qian G.","key":"e_1_2_1_17_1","unstructured":"Qian , G. , Zhu , Q. , Xue , Q. , and Pramanik , S . 2003. The ND-tree: A dynamic indexing technique for multidimensional non-ordered discrete data spaces . In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB). 620--631 . Qian, G., Zhu, Q., Xue, Q., and Pramanik, S. 2003. The ND-tree: A dynamic indexing technique for multidimensional non-ordered discrete data spaces. In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB). 620--631."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1138394.1138395"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1125857.1125860"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/582318.582321"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223794"},{"volume-title":"Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB). 506--515","author":"Seidl T.","key":"e_1_2_1_22_1","unstructured":"Seidl , T. and Kriegel , H . -P. 1997. Efficient user-adaptable similarity search in large multimedia databases . In Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB). 506--515 . Seidl, T. and Kriegel, H.-P. 1997. Efficient user-adaptable similarity search in large multimedia databases. In Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB). 506--515."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/276305.276319"}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1740592.1740595","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1740592.1740595","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:40:55Z","timestamp":1750250455000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1740592.1740595"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,5]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,5]]}},"alternative-id":["10.1145\/1740592.1740595"],"URL":"https:\/\/doi.org\/10.1145\/1740592.1740595","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"type":"print","value":"1046-8188"},{"type":"electronic","value":"1558-2868"}],"subject":[],"published":{"date-parts":[[2010,5]]},"assertion":[{"value":"2008-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}