{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:40:33Z","timestamp":1750308033368,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"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. Inf. Syst."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>\n            There is an increasing demand for similarity searches in a multidimensional non-ordered discrete data space (NDDS) from application areas such as bioinformatics and data mining. The non-ordered and discrete nature of an NDDS raises new challenges for developing efficient indexing methods for similarity searches. In this article, we propose a new indexing technique, called the\n            <jats:italic>NSP-tree<\/jats:italic>\n            , to support efficient similarity searches in an NDDS. As we know, overlap causes a performance degradation for indexing methods (e.g., the R-tree) for a continuous data space. In an NDDS, this problem is even worse due to the limited number of elements available on each dimension of an NDDS. The key idea of the NSP-tree is to use a novel discrete space-partitioning (SP) scheme to ensure no overlap at each level in the tree. A number of heuristics and strategies are incorporated into the tree construction algorithms to deal with the challenges for developing an SP-based index tree for an NDDS. Our experiments demonstrate that the NSP-tree is quite promising in supporting efficient similarity searches in NDDSs. We have compared the NSP-tree with the ND-tree, a data-partitioning-based indexing technique for NDDSs that was proposed recently, and the linear scan using different NDDSs. It was found that the search performance of the NSP-tree was better than those of both methods.\n          <\/jats:p>","DOI":"10.1145\/1125857.1125860","type":"journal-article","created":{"date-parts":[[2006,5,8]],"date-time":"2006-05-08T16:09:20Z","timestamp":1147104560000},"page":"79-110","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["A space-partitioning-based indexing method for multidimensional non-ordered discrete data spaces"],"prefix":"10.1145","volume":"24","author":[{"given":"Gang","family":"Qian","sequence":"first","affiliation":[{"name":"University of Central Oklahoma, Edmond, OK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qiang","family":"Zhu","sequence":"additional","affiliation":[{"name":"The University of Michigan---Dearborn, Dearborn, MI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qiang","family":"Xue","sequence":"additional","affiliation":[{"name":"Michigan State University, East Lansing, MI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sakti","family":"Pramanik","sequence":"additional","affiliation":[{"name":"Michigan State University, East Lansing, MI"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/320521.320530"},{"volume-title":"Proceedings of the Workshop on Computational Geometry. 13--25","author":"Becker S.","key":"e_1_2_1_2_1","unstructured":"Becker , S. , Franciosa , P. G. , Gschwind , S. , Ohler , T. , Thiemt , G. , and Widmayer , P . 1991. An optimal algorithm for approximating a set of rectangles by two minimum area rectangles . In Proceedings of the Workshop on Computational Geometry. 13--25 . Becker, S., Franciosa, P. G., Gschwind, S., Ohler, T., Thiemt, G., and Widmayer, P. 1991. An optimal algorithm for approximating a set of rectangles by two minimum area rectangles. In Proceedings of the Workshop on Computational Geometry. 13--25."},{"volume-title":"Proceedings of the SIGMOD. 322--331","author":"Beckmann N.","key":"e_1_2_1_3_1","unstructured":"Beckmann , N. , Kriegel , H. , Schneider , R. , and Seeger , B . 1990. The R&ast;-tree: An efficient and robust access method for points and rectangles . In Proceedings of the SIGMOD. 322--331 . 10.1145\/93597.98741 Beckmann, N., Kriegel, H., Schneider, R., and Seeger, B. 1990. The R&ast;-tree: An efficient and robust access method for points and rectangles. In Proceedings of the SIGMOD. 322--331. 10.1145\/93597.98741"},{"key":"e_1_2_1_4_1","volume-title":"-P","author":"Berchtold S.","year":"1996","unstructured":"Berchtold , S. , Keim , D. A. , and Kriegel , H . -P . 1996 . The X-tree : An index structure for high-dimensional data. In Proceedings of VLDB. 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 VLDB. 28--39."},{"volume-title":"Proceedings of SIGMOD. 357--368","author":"Bozkaya T.","key":"e_1_2_1_5_1","unstructured":"Bozkaya , T. and Ozsoyoglu , M . 1997. Distance-based indexing for high-dimensional metric spaces . In Proceedings of SIGMOD. 357--368 . 10.1145\/253260.253345 Bozkaya, T. and Ozsoyoglu, M. 1997. Distance-based indexing for high-dimensional metric spaces. In Proceedings of SIGMOD. 357--368. 10.1145\/253260.253345"},{"volume-title":"Proceedings of ICDE. 440--447","author":"Chakrabarti K.","key":"e_1_2_1_6_1","unstructured":"Chakrabarti , K. and Mehrotra , S . 1999. The hybrid tree: An index structure for high dimensional feature spaces . In Proceedings of ICDE. 440--447 . Chakrabarti, K. and Mehrotra, S. 1999. The hybrid tree: An index structure for high dimensional feature spaces. In Proceedings of ICDE. 440--447."},{"volume-title":"Proceedings of VLDB. 426--435","author":"Ciaccia P.","key":"e_1_2_1_7_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 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 VLDB. 426--435."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Clement J. Flajolet P. and Vallee B. 2001. Dynamic sources in information theory: A general analysis of trie structures. Algorithm 29 1\/2 307--369.  Clement J. Flajolet P. and Vallee B. 2001. Dynamic sources in information theory: A general analysis of trie structures. Algorithm 29 1\/2 307--369.","DOI":"10.1007\/BF02679623"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/301970.301973"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of SIGMOD. 47--57","author":"Guttman A.","year":"1984","unstructured":"Guttman , A. 1984 . R-trees: A dynamic index structure for spatial searching . In Proceedings of SIGMOD. 47--57 . 10.1145\/602259.602266 Guttman, A. 1984. R-trees: A dynamic index structure for spatial searching. In Proceedings of SIGMOD. 47--57. 10.1145\/602259.602266"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of ICDE. 68--75","author":"Henrich A.","year":"1996","unstructured":"Henrich , A. 1996 . Improving the performance of multi-dimensional access structures based on K-D-trees . In Proceedings of ICDE. 68--75 . Henrich, A. 1996. Improving the performance of multi-dimensional access structures based on K-D-trees. In Proceedings of ICDE. 68--75."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of ICDE. 362--369","author":"Henrich A.","year":"1998","unstructured":"Henrich , A. 1998 . The LSDh-tree: An access structure for feature vectors . In Proceedings of ICDE. 362--369 . Henrich, A. 1998. The LSDh-tree: An access structure for feature vectors. In Proceedings of ICDE. 362--369."},{"volume-title":"Proceedings of SIGMOD. 369--380","author":"Katayama N.","key":"e_1_2_1_13_1","unstructured":"Katayama , N. and Satoh , S . 1997. The SR-tree: An index structure for high-dimensional nearest neighbor queries . In Proceedings of SIGMOD. 369--380 . 10.1145\/253260.253347 Katayama, N. and Satoh, S. 1997. The SR-tree: An index structure for high-dimensional nearest neighbor queries. In Proceedings of SIGMOD. 369--380. 10.1145\/253260.253347"},{"key":"e_1_2_1_14_1","first-page":"656","article-title":"BLAT---the BLAST-like aligment tool","volume":"12","author":"Kent W. J.","year":"2002","unstructured":"Kent , W. J. 2002 . BLAT---the BLAST-like aligment tool . Genome Res. 12 , 656 -- 664 . Kent, W. J. 2002. BLAT---the BLAST-like aligment tool. Genome Res. 12, 656--664.","journal-title":"Genome Res."},{"volume-title":"The Art of Computer Programming","author":"Knuth D. E.","key":"e_1_2_1_15_1","unstructured":"Knuth , D. E. 1973. The Art of Computer Programming , Vol. 3 . Addison-Wesley , Reading, MA . Knuth, D. E. 1973. The Art of Computer Programming, Vol. 3. Addison-Wesley, Reading, MA."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/99935.99949"},{"volume-title":"Proceedings of VLDB. 620--631","author":"Qian G.","key":"e_1_2_1_18_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 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 VLDB. 620--631."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1138394.1138395"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of SIGMOD. 10--18","author":"Robinson J. T.","year":"1981","unstructured":"Robinson , J. T. 1981 . The K-D-B-tree: A search structure for large multidimensional dynamic indexes . In Proceedings of SIGMOD. 10--18 . 10.1145\/582318.582321 Robinson, J. T. 1981. The K-D-B-tree: A search structure for large multidimensional dynamic indexes. In Proceedings of SIGMOD. 10--18. 10.1145\/582318.582321"},{"volume-title":"Proceedings of Dateso 2004 Annual International Workshop on DAtabases, TExts, Specifications and Objects (DATESO'04)","author":"Skopal T.","key":"e_1_2_1_21_1","unstructured":"Skopal , T. , Pokorny , J. , and Snasel , V . 2004. PM-tree: Pivoting metric tree for similarity search in multimedia databases . In Proceedings of Dateso 2004 Annual International Workshop on DAtabases, TExts, Specifications and Objects (DATESO'04) . 27--37. Skopal, T., Pokorny, J., and Snasel, V. 2004. PM-tree: Pivoting metric tree for similarity search in multimedia databases. In Proceedings of Dateso 2004 Annual International Workshop on DAtabases, TExts, Specifications and Objects (DATESO'04). 27--37."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.991715"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0020-0190(91)90074-R","article-title":"Satisfying general proximity\/similarity queries with metric trees","volume":"40","author":"Uhlmann J. K.","year":"1991","unstructured":"Uhlmann , J. K. 1991 . Satisfying general proximity\/similarity queries with metric trees . Inf. Proc. Lett. 40 , 4, 175 -- 179 . Uhlmann, J. K. 1991. Satisfying general proximity\/similarity queries with metric trees. Inf. Proc. Lett. 40, 4, 175--179.","journal-title":"Inf. Proc. Lett."},{"volume-title":"Proceedings of VLDB. 357--367","author":"Weber R.","key":"e_1_2_1_24_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 VLDB. 357--367 . 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 VLDB. 357--367."},{"volume-title":"Proceedings of ICDE. 516--523","author":"White D.","key":"e_1_2_1_25_1","unstructured":"White , D. and Jain , R . 1996. Similarity indexing with the SS-tree . In Proceedings of ICDE. 516--523 . White, D. and Jain, R. 1996. Similarity indexing with the SS-tree. In Proceedings of ICDE. 516--523."},{"volume-title":"Proceedings of the 14th Australasian Database Conference. 161--168","author":"Zhou X.","key":"e_1_2_1_26_1","unstructured":"Zhou , X. , Wang , G. , Yu , J. X. , and Yu , G . 2003. M&plus;-tree: A new dynamical multidimensional index for metric spaces . In Proceedings of the 14th Australasian Database Conference. 161--168 . Zhou, X., Wang, G., Yu, J. X., and Yu, G. 2003. M&plus;-tree: A new dynamical multidimensional index for metric spaces. In Proceedings of the 14th Australasian Database Conference. 161--168."},{"volume-title":"Human Behavior and the Principle of Least Effort","author":"Zipf G. K.","key":"e_1_2_1_27_1","unstructured":"Zipf , G. K. 1949. Human Behavior and the Principle of Least Effort . Addison-Wesley , Reading, MA . Zipf, G. K. 1949. Human Behavior and the Principle of Least Effort. Addison-Wesley, Reading, MA."}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1125857.1125860","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1125857.1125860","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:14:10Z","timestamp":1750259650000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1125857.1125860"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1145\/1125857.1125860"],"URL":"https:\/\/doi.org\/10.1145\/1125857.1125860","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"type":"print","value":"1046-8188"},{"type":"electronic","value":"1558-2868"}],"subject":[],"published":{"date-parts":[[2006,1]]},"assertion":[{"value":"2006-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}