{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T09:19:32Z","timestamp":1773825572546,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>\n            This paper proposes a general framework for matching similar subsequences in both time series and string databases. The matching results are pairs of query subsequences and database subsequences. The framework finds all possible pairs of similar subsequences if the distance measure satisfies the \"consistency\" property, which is a property introduced in this paper. We show that most popular distance functions, such as the Euclidean distance, DTW, ERP, the Frech\u00e9t distance for time series, and the Hamming distance and Levenshtein distance for strings, are all \"consistent\". We also propose a generic index structure for metric spaces named \"reference net\". The reference net occupies\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) space, where\n            <jats:italic>n<\/jats:italic>\n            is the size of the dataset and is optimized to work well with our framework. The experiments demonstrate the ability of our method to improve retrieval performance when combined with diverse distance measures. The experiments also illustrate that the reference net scales well in terms of space overhead and query time.\n          <\/jats:p>","DOI":"10.14778\/2350229.2350271","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1579-1590","source":"Crossref","is-referenced-by-count":9,"title":["A generic framework for efficient and effective subsequence retrieval"],"prefix":"10.14778","volume":"5","author":[{"given":"Haohan","family":"Zhu","sequence":"first","affiliation":[{"name":"Boston University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George","family":"Kollios","sequence":"additional","affiliation":[{"name":"Boston University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vassilis","family":"Athitsos","sequence":"additional","affiliation":[{"name":"University of Texas at Arlington"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Basic local alignment search tool. Journal of molecular biology, 215(3):403--410","author":"Altschul S.","year":"1990","unstructured":"S. Altschul , W. Gish , W. Miller , E. W. Myers , and D. J. Lipman . Basic local alignment search tool. Journal of molecular biology, 215(3):403--410 , 1990 . S. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman. Basic local alignment search tool. Journal of molecular biology, 215(3):403--410, 1990."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687721"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376656"},{"key":"e_1_2_1_4_1","first-page":"359","volume-title":"KDD Workshop","author":"Berndt D. J.","year":"1994","unstructured":"D. J. Berndt and J. Clifford . Using dynamic time warping to find patterns in time series . In KDD Workshop , pages 359 -- 370 , 1994 . D. J. Berndt and J. Clifford. Using dynamic time warping to find patterns in time series. In KDD Workshop, pages 359--370, 1994."},{"key":"e_1_2_1_5_1","first-page":"591","volume-title":"ISMIR","author":"Bertin-Mahieux T.","year":"2011","unstructured":"T. Bertin-Mahieux , D. P. W. Ellis , B. Whitman , and P. Lamere . The million song dataset . In ISMIR , pages 591 -- 596 , 2011 . T. Bertin-Mahieux, D. P. W. Ellis, B. Whitman, and P. Lamere. The million song dataset. In ISMIR, pages 591--596, 2011."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/328939.328959"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316758"},{"key":"e_1_2_1_9_1","first-page":"426","volume-title":"VLDB","author":"Ciaccia P.","year":"1997","unstructured":"P. Ciaccia , M. Patella , and P. Zezula . M-tree: An efficient access method for similarity search in metric spaces . In VLDB , pages 426 -- 435 , 1997 . P. Ciaccia, M. Patella, and P. Zezula. M-tree: An efficient access method for similarity search in metric spaces. In VLDB, pages 426--435, 1997."},{"key":"e_1_2_1_10_1","first-page":"15","volume-title":"Nearest-neighbor searching and metric space dimensions","author":"Clarkson K. L.","year":"2006","unstructured":"K. L. Clarkson . Nearest-neighbor searching and metric space dimensions . In G. Shakhnarovich, T. Darrell, and P. Indyk, editors, Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, pages 15 -- 59 . MIT Press , 2006 . K. L. Clarkson. Nearest-neighbor searching and metric space dimensions. In G. Shakhnarovich, T. Darrell, and P. Indyk, editors, Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, pages 15--59. MIT Press, 2006."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191925"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2010.0005"},{"key":"e_1_2_1_14_1","first-page":"423","volume-title":"VLDB","author":"Han W.-S.","year":"2007","unstructured":"W.-S. Han , J. Lee , Y.-S. Moon , and H. Jiang . Ranked subsequence matching in time-series databases . In VLDB , pages 423 -- 434 , 2007 . W.-S. Han, J. Lee, Y.-S. Moon, and H. Jiang. Ranked subsequence matching in time-series databases. In VLDB, pages 423--434, 2007."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989371"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287405"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/347090.347153"},{"key":"e_1_2_1_18_1","first-page":"325","volume-title":"VLDB","author":"Kim M.-S.","year":"2005","unstructured":"M.-S. Kim , K.-Y. Whang , J.-G. Lee , and M.-J. Lee . n-gram\/2l : A space and time efficient two-level n-gram inverted index structure . In VLDB , pages 325 -- 336 , 2005 . M.-S. Kim, K.-Y. Whang, J.-G. Lee, and M.-J. Lee. n-gram\/2l: A space and time efficient two-level n-gram inverted index structure. In VLDB, pages 325--336, 2005."},{"key":"e_1_2_1_19_1","first-page":"798","volume-title":"SODA","author":"Krauthgamer R.","year":"2004","unstructured":"R. Krauthgamer and J. R. Lee . Navigating nets: simple algorithms for proximity search . In SODA , pages 798 -- 807 , 2004 . R. Krauthgamer and J. R. Lee. Navigating nets: simple algorithms for proximity search. In SODA, pages 798--807, 2004."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn032"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1186\/gb-2009-10-3-r25"},{"issue":"8","key":"e_1_2_1_22_1","first-page":"707","article-title":"Binary codes capable of correcting deletions, insertions, and reversals","volume":"10","author":"Levenshtein V. I.","year":"1966","unstructured":"V. I. Levenshtein . Binary codes capable of correcting deletions, insertions, and reversals . Soviet Physics , 10 ( 8 ): 707 -- 710 , 1966 . V. I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics, 10(8):707--710, 1966.","journal-title":"Soviet Physics"},{"key":"e_1_2_1_23_1","first-page":"303","volume-title":"VLDB","author":"Li C.","year":"2007","unstructured":"C. Li , B. Wang , and X. Yang . Vgram: Improving performance of approximate queries on string collections using variable-length grams . In VLDB , pages 303 -- 314 , 2007 . C. Li, B. Wang, and X. Yang. Vgram: Improving performance of approximate queries on string collections using variable-length grams. In VLDB, pages 303--314, 2007."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp324"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989370"},{"key":"e_1_2_1_26_1","first-page":"207","volume-title":"VLDB","author":"Litwin W.","year":"2007","unstructured":"W. Litwin , R. Mokadem , P. Rigaux , and T. J. E. Schwarz . Fast ngram-based string search over data encoded using algebraic signatures . In VLDB , pages 207 -- 218 , 2007 . W. Litwin, R. Mokadem, P. Rigaux, and T. J. E. Schwarz. Fast ngram-based string search over data encoded using algebraic signatures. In VLDB, pages 207--218, 2007."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564735"},{"key":"e_1_2_1_28_1","first-page":"263","volume-title":"ICDE","author":"Moon Y.-S.","year":"2001","unstructured":"Y.-S. Moon , K.-Y. Whang , and W.-K. Loh . Duality-based subsequence matching in time-series databases . In ICDE , pages 263 -- 272 , 2001 . Y.-S. Moon, K.-Y. Whang, and W.-K. Loh. Duality-based subsequence matching in time-series databases. In ICDE, pages 263--272, 2001."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687651"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339576"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.368963"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.21"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(81)90087-5"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0062-1"},{"key":"e_1_2_1_36_1","first-page":"906","volume-title":"VLDB","author":"Venkateswaran J.","year":"2006","unstructured":"J. Venkateswaran , D. Lachwani , T. Kahveci , and C. M. Jermaine . Reference-based indexing of sequence databases . In VLDB , pages 906 -- 917 , 2006 . J. Venkateswaran, D. Lachwani, T. Kahveci, and C. M. Jermaine. Reference-based indexing of sequence databases. In VLDB, pages 906--917, 2006."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-011-0459-6"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376655"},{"key":"e_1_2_1_39_1","first-page":"311","volume-title":"SODA","author":"Yianilos P. N.","year":"1993","unstructured":"P. N. Yianilos . Data structures and algorithms for nearest neighbor search in general metric spaces . In SODA , pages 311 -- 321 , 1993 . P. N. Yianilos. Data structures and algorithms for nearest neighbor search in general metric spaces. In SODA, pages 311--321, 1993."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2350229.2350271","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:30:32Z","timestamp":1672227032000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2350229.2350271"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":38,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.14778\/2350229.2350271"],"URL":"https:\/\/doi.org\/10.14778\/2350229.2350271","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}