{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T07:54:25Z","timestamp":1649058865723},"reference-count":35,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. & Syst."],"published-print":{"date-parts":[[2019,4,1]]},"DOI":"10.1587\/transinf.2018dap0005","type":"journal-article","created":{"date-parts":[[2019,3,31]],"date-time":"2019-03-31T22:10:59Z","timestamp":1554070259000},"page":"745-758","source":"Crossref","is-referenced-by-count":0,"title":["The BINDS-Tree: A Space-Partitioning Based Indexing Scheme for Box Queries in Non-Ordered Discrete Data Spaces"],"prefix":"10.1587","volume":"E102.D","author":[{"given":"A. K. M. Tauhidul","family":"ISLAM","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Michigan State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sakti","family":"PRAMANIK","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Michigan State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qiang","family":"ZHU","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science, University of Michigan - Dearborn"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"publisher","unstructured":"[1] M.L. Metzker, \u201cSequencing technologies \u2014 the next generation,\u201d Nat. Rev. Genet., vo.11, pp.31-46, 2010. 10.1038\/nrg2626","DOI":"10.1038\/nrg2626"},{"key":"2","doi-asserted-by":"publisher","unstructured":"[2] T.J. Treangen and S.L. Salzberg, \u201cRepetitive DNA and next-generation sequencing: computational challenges and solutions,\u201d Nature Reviews Genetics, vol.13, no.1, pp.36-46, 2012. 10.1038\/nrg3117","DOI":"10.1038\/nrg3117"},{"key":"3","doi-asserted-by":"crossref","unstructured":"[3] S.F. Altschul, T.L. Madden, A.A. Sch\u00e4ffer, J. Zhang, Z. Zhang, W. Miller, and D.J. Lipman, \u201cGapped BLAST and PSI-BLAST: a new generation of protein database search programs,\u201d Nucleic Acids Research, vol.25, no.17, pp.3389-3402, 1997. 10.1093\/nar\/25.17.3389","DOI":"10.1093\/nar\/25.17.3389"},{"key":"4","doi-asserted-by":"publisher","unstructured":"[4] W.J. Kent, \u201cBLAT \u2014 The BLAST-like alignment tool,\u201d Genome Research, vol.12, no.4, pp.656-664, 2002. 10.1101\/gr.229202","DOI":"10.1101\/gr.229202"},{"key":"5","doi-asserted-by":"crossref","unstructured":"[5] A.K.M.T. Islam, S. Pramanik, X. Ji, J.R. Cole, and Q. Zhu, \u201cBack Translated Peptide k-mer Search and Local Alignment in Large DNA Sequence Databases Using BoND-SD-tree Indexing,\u201d Proc. BIBE'15, pp.1-6, 2015. 10.1109\/bibe.2015.7367638","DOI":"10.1109\/BIBE.2015.7367638"},{"key":"6","unstructured":"[6] Y. Gu, Q. Zhu, X. Liu, Y. Dong, C.T. Brown, and S. Pramanik, \u201cUsing Disk Based Index and Box Queries for Genome Sequencing Error Correction,\u201d Proc. BICoB'16, pp.69-76, 2016."},{"key":"7","doi-asserted-by":"crossref","unstructured":"[7] Y. Gu, X. Liu, Q. Zhu, Y. Dong, C.T. Brown, and S. Pramanik, \u201cA new method for DNA sequencing error verification and correction via an on-disk index tree,\u201d Proc. ACM BCB'15, pp.503-504, 2015. 10.1145\/2808719.2811429","DOI":"10.1145\/2808719.2811429"},{"key":"8","doi-asserted-by":"publisher","unstructured":"[8] D.R. Kelley, M.C. Schatz, and S.L. Salzberg, \u201cQuake: quality-aware detection and correction of sequencing errors,\u201d Genome Biol., vol.11, no.11, R116, 2010. 10.1186\/gb-2010-11-11-r116","DOI":"10.1186\/gb-2010-11-11-r116"},{"key":"9","doi-asserted-by":"publisher","unstructured":"[9] C. Chen, A. Watve, S. Pramanik, and Q. Zhu, \u201cThe BoND-tree: an efficient indexing method for box queries in nonordered discrete data spaces,\u201d IEEE Trans. Knowl. Data Eng., vol.25, no.11, pp.2629-2643, 2013. 10.1109\/tkde.2012.132","DOI":"10.1109\/TKDE.2012.132"},{"key":"10","doi-asserted-by":"publisher","unstructured":"[10] G. Qian, Q. Zhu, Q. Xue, and S. Pramanik, \u201cA space-partitioning-based indexing method for multidimensional non-ordered discrete data spaces,\u201d ACM Trans. Info. Syst., vol.23, no.1, pp.79-110, 2006. 10.1145\/1125857.1125860","DOI":"10.1145\/1125857.1125860"},{"key":"11","doi-asserted-by":"crossref","unstructured":"[11] A. Guttman, \u201cR-tree: a Dynamic Index Structure for Spatial Searching,\u201d Proc. SIGMOD'84, pp.47-57, 1984. 10.1145\/602259.602266","DOI":"10.1145\/602264.602266"},{"key":"12","doi-asserted-by":"publisher","unstructured":"[12] N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. \u201cThe R*-tree: an efficient and robust access method for points and rectangles,\u201d Proc. SIGMOD'90, pp.322-331, 1990. 10.1145\/93605.98741","DOI":"10.1145\/93605.98741"},{"key":"13","doi-asserted-by":"crossref","unstructured":"[13] J.T. Robinson, \u201cThe KDB-tree: a search structure for large multidimensional dynamic indexes,\u201d Proceedings of the 1981 ACM SIGMOD international conference on Management of data, pp.10-18. ACM, 1981. 10.1145\/582319.582321","DOI":"10.1145\/582318.582321"},{"key":"14","doi-asserted-by":"publisher","unstructured":"[14] T. Bozkaya and M. Ozsoyoglu, \u201cIndexing large metric spaces for similarity search queries,\u201d ACM Transactions on Database Systems (TODS), vol.24, no.3, pp.361-404, 1999. 10.1145\/328939.328959","DOI":"10.1145\/328939.328959"},{"key":"15","doi-asserted-by":"publisher","unstructured":"[15] G.R. Hjaltason and H. Samet, \u201cIndex-driven similarity search in metric spaces (survey article),\u201d ACM Transactions on Database Systems (TODS), vol.28, no.4, pp.517-580, 2003. 10.1145\/958942.958948","DOI":"10.1145\/958942.958948"},{"key":"16","unstructured":"[16] P.N. Yianilos, \u201cData structures and algorithms for nearest neighbor search in general metric spaces,\u201d SODA, vol.93, no.194, pp.311-21, 1993."},{"key":"17","unstructured":"[17] P. Ciaccia, M. Patella, and P. Zezula. \u201cM-tree: An E cient Access Method for Similarity Search in Metric Spaces,\u201d Proceedings of the 23rd VLDB conference, Athens, Greece, pp.426-435, 1997."},{"key":"18","unstructured":"[18] M. Farach, \u201cOptimal suffix tree construction with large alphabets,\u201d Proceedings 38th Annual Symposium on Foundations of Computer Science, pp.137-143, IEEE, 1997. 10.1109\/sfcs.1997.646102"},{"key":"19","doi-asserted-by":"crossref","unstructured":"[19] B. Phoophakdee and M.J. Zaki, \u201cGenome-scale disk-based suffix tree indexing,\u201d Proceedings of the 2007 ACM SIGMOD international conference on Management of data, pp.833-844. ACM, 2007. 10.1145\/1247480.1247572","DOI":"10.1145\/1247480.1247572"},{"key":"20","doi-asserted-by":"publisher","unstructured":"[20] E. Hunt, M.P. Atkinson, and R.W. Irving, \u201cDatabase indexing for large DNA and protein sequence collections,\u201d The VLDB Journal-The International Journal on Very Large Data Bases, vol.11, no.3, pp.256-271, 2002. 10.1007\/s007780200064","DOI":"10.1007\/s007780200064"},{"key":"21","doi-asserted-by":"crossref","unstructured":"[21] M. Barsky, U. Stege, A. Thomo, and C. Upton, \u201cA new method for indexing genomes using on-disk suffix trees,\u201d Proceedings of the 17th ACM conference on Information and knowledge management, pp.649-658. ACM, 2008. 10.1145\/1458082.1458170","DOI":"10.1145\/1458082.1458170"},{"key":"22","doi-asserted-by":"publisher","unstructured":"[22] H. Li and N. Homer, \u201cA survey of sequence alignment algorithms for next-generation sequencing,\u201d Briefings in Bioinformatics vol.11, no.5, pp.473-483, 2010. 10.1093\/bib\/bbq015","DOI":"10.1093\/bib\/bbq015"},{"key":"23","doi-asserted-by":"crossref","unstructured":"[23] S. Burkhardt, A. Crauser, P. Ferragina, H.-P. Lenhof, E. Rivals, and M. Vingron, \u201cq-gram based database searching using a suffix array (QUASAR),\u201d Proceedings of the third annual international conference on Computational molecular biology, pp.77-83, ACM, 1999. 10.1145\/299432.299460","DOI":"10.1145\/299432.299460"},{"key":"24","doi-asserted-by":"publisher","unstructured":"[24] M.I. Abouelhoda, S. Kurtz, and E. Ohlebusch, \u201cReplacing suffix trees with enhanced suffix arrays,\u201d Journal of Discrete Algorithms, vol.2, no.1, pp.53-86, 2004. 10.1016\/s1570-8667(03)00065-0","DOI":"10.1016\/S1570-8667(03)00065-0"},{"key":"25","doi-asserted-by":"publisher","unstructured":"[25] R. Bayer and K. Unterauer, \u201cPrefix B-Trees,\u201d ACM Trans. Database Systems, vol.2, no.1, pp.11-26, 1977. 10.1145\/320521.320530","DOI":"10.1145\/320521.320530"},{"key":"26","doi-asserted-by":"publisher","unstructured":"[26] P. Ferragina and R. Grossi, \u201cThe String B-Tree: A New Data Structure for String Search in External Memory and its Applications,\u201d J. ACM, vol.46, no.2, pp.236-280, 1998. 10.1145\/301970.301973","DOI":"10.1145\/301970.301973"},{"key":"27","doi-asserted-by":"crossref","unstructured":"[27] G. Qian, Q. Zhu, Q. Xue, and S. Pramanik, \u201cThe ND-tree: A dynamic indexing technique for multidimensional non-ordered discrete data spaces,\u201d Proc. VLDB'03, pp.620-631, 2003. 10.1016\/b978-012722442-8\/50061-6","DOI":"10.1016\/B978-012722442-8\/50061-6"},{"key":"28","doi-asserted-by":"crossref","unstructured":"[29] Z. Zhou, X. Liu, Y. Wang, and Q. Zhu, \u201cFast Construction of an Index Tree for Large Non-ordered Discrete Datasets Using Multi-way Top-Down Split and MapReduce,\u201d 2016 International Conference on Advanced Cloud and Big Data (CBD), pp.49-55, IEEE, 2016. 10.1109\/cbd.2016.019","DOI":"10.1109\/CBD.2016.019"},{"key":"29","doi-asserted-by":"crossref","unstructured":"[30] R. Cherniak, Q. Zhu, Y. Gu, and S. Pramanik, \u201cExploring Deletion Strategies for the BoND-Tree in Multidimensional Non-ordered Discrete Data Spaces,\u201d Proceedings of the 21st International Database Engineering & Applications Symposium, pp.153-160, ACM, 2017. 10.1145\/3105831.3105840","DOI":"10.1145\/3105831.3105840"},{"key":"30","unstructured":"[31] D.-Y. Choi, A.K.M.T. Islam, S. Pramanik, and Q. Zhu, \u201cA Bulk-Loading Algorithm for the BoND-Tree Index Scheme for Non-ordered Discrete Data Spaces,\u201d 25th International Conference on Software Engineering and Data Engineering (SEDE 2016), pp.123-128, 2016."},{"key":"31","doi-asserted-by":"publisher","unstructured":"[32] G. Qian, Q. Zhu, Q. Xue, and S. Pramanik, \u201cDynamic indexing for multidimensional non-ordered discrete data spaces using a data-partitioning approach,\u201d ACM Trans. Database Syst., vol.31, no.2, pp.439-484, 2006. 10.1145\/1138394.1138395","DOI":"10.1145\/1138394.1138395"},{"key":"32","unstructured":"[33] Institute for Cyber-Enabled Research, Michigan State University. https:\/\/hpcc.msu.edu\/"},{"key":"33","unstructured":"[34] G.K. Zipf, Human Behavior and the Principle of Least Effort, pp.147-149, Addison-Wesley, 1949."},{"key":"34","unstructured":"[35] M. Girdea, L. No\u00e9, and G. Kucherov, \u201cBack-translation for discovering distant protein homologies in the presence of frameshift mutations,\u201d Algorithms for Molecular Biology, vol.5, no.1, 6, 2010. 10.1186\/1748-7188-5-6"},{"key":"35","doi-asserted-by":"crossref","unstructured":"[36] J.R. Cole, Q. Wang, E. Cardenas, J, Fish, B. Chai, R.J. Farris, A.S. Kulam-Syed-Mohideen, D.M. McGarrell, T. Marsh, G.M. Garrity, and J.M. Tiedje, \u201cThe Ribosomal Database Project: improved alignments and new tools for rRNA analysis,\u201d Nucleic Acids Research, vol.37, no.2, pp.D141-D145, 2008. 10.1093\/nar\/gkn879","DOI":"10.1093\/nar\/gkn879"}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E102.D\/4\/E102.D_2018DAP0005\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T03:47:49Z","timestamp":1559360869000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E102.D\/4\/E102.D_2018DAP0005\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,1]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2018dap0005","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"value":"0916-8532","type":"print"},{"value":"1745-1361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,1]]}}}