跳到主要內容

臺灣博碩士論文加值系統

(18.204.48.64) 您好!臺灣時間:2021/08/04 18:50
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:黃宥勝
研究生(外文):You-Sheng Huang
論文名稱:可有效回覆字串相似度搜尋之演算法
論文名稱(外文):A Query-Efficient Algorithm for String-Similarity Search
指導教授:趙坤茂
指導教授(外文):Kun-Mao Chao
口試委員:王弘倫黃耀廷
口試委員(外文):Hung-Lung WangYao-Ting Huang
口試日期:2015-06-08
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:英文
論文頁數:24
中文關鍵詞:編輯距離字串相似度搜尋範圍查詢前k個查詢
外文關鍵詞:edit distancestring similarity searchrange querytop-k query
相關次數:
  • 被引用被引用:0
  • 點閱點閱:503
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
編輯距離(edit distance) 是一個廣泛地被用於測量字串之間相似程度
的度量,而字串相似度搜尋(string similarity search) 則要找出在特定的字串集合中和給予的查詢字串(query string) 相似的字串。以編輯距離為測量依據的字串相似度搜尋,被大量地應用在如數據清理(database
cleaning) 、錯誤檢查更正(Error detection and correction) 與資料擷取(data retrieval) 等領域。目前此類問題的解決方法大多先將可排除的字串過濾掉後,再對剩下的字串進行檢驗。然而,這些方法在排除字串的過程中,幾乎全部都採用相同的過濾規則,使得效率隨著字串集合的改變而下降。為了克服這個問題,我們提出一個整合不同過濾方法
的資料結構(data structure) 讓字串的過濾維持穩定的效率。我們並提出對應的演算法解決兩個主要的字串相似度搜尋問題:範圍查詢(range
query) 與前k 個查詢(top-k query) 。實驗結果顯示當門檻值小於一定的程度時,我們的方法在範圍查詢上具有優異的性能表現。

Edit distance, a measure determining the similarity between two strings, is a criterion that has been used widely. String similarity search finds strings in a dataset that are similar to a given query string. Edit-distance based string similarity search is exploited in many fields, e.g., database cleaning, error detection and correction and data retrieval. Most approaches toward string similarity search resort to filtering out as many strings in datasets as possible and verifying the remaining strings. However, these approaches use only one
filtering method throughout the whole procedure, which makes the power of the method fluctuates during the whole procedure. To overcome this problem, we propose a data structure integrating different filtering methods and
adopting a more efficient one on each phase. We also give corresponding algorithms for two important queries of string similarity search, range query and top-k query. Experimental results show that our approach is competitive for range query when thresholds are small enough.

1 Introduction 1
1.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Verifying Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.3 Pruning Technique . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Our Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Preliminaries 6
2.1 Preliminary Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.1 Edit Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.2 Computations of Edit Distance . . . . . . . . . . . . . . . . . . . 7
2.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
iv
2.2.1 Range Query . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.2 Top-k Query . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Complex-Tree Based Solution 9
3.1 Filtering Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.1.1 String Length . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.1.2 Letter Count . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.1.3 Reference String . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Index Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2.1 String Length . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2.2 Letter Count . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2.3 Reference String . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3 Query Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3.1 Range Query . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3.2 Top-k Query . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4 Experimental Evaluation 18
4.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.2 Space Consumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.3 Comparison with Other Approaches . . . . . . . . . . . . . . . . . . . . 19
4.3.1 Range Query . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.3.2 Top-k Query . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5 Conclusions and Future Work 22
5.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

[1] A. Chandel, O. Hassanzadeh, N. Koudas, M. Sadoghi, and D. Srivastava. Benchmarking declarative approximate selection predicates. In SIGMOD, pp. 353-364, 2007.
[2] S. Chaudhuri, B.-C. Chen, V. Ganti, and R. Kaushik. Exampledriven design of efficient record matching queries, In VLDB, pp. 327-338, 2007.
[3] L. Gravano, P. G. Ipeirotis, H. V. Jagadish, N. Koudas, S. Muthukrishnan, and D. Srivastava. Approximate string joins in a database (almost) for free. In VLDB, pp. 491-500, 2001.
[4] C. Li, B. Wang, and X. Yang. Vgram: Improving performance of approximate queries on string collections using variable-length grams. In VLDB, pp. 303-314, 2007.
[5] C. Li, J. Lu, and Y. Lu. Efficient merging and filtering algorithms for approximate string searches. In ICDE, pp. 257-266, 2008.
[6] R. Vernicaand and C. Li. Efficient top-k algorithms for fuzzy search in string collections. In KEYS ’09: Proceedings of the First International Workshop on Keyword Search on Structured Data, pp. 9-14, 2009.
[7] J. Qin, W. Wang, Y. Lu, C. Xiao, and X. Lin. Efficient exact edit similarity query processing with the asymmetric signature scheme. In SIGMOD Conference, pp. 1033-1044, 2011.
[8] J. Wang, G. Li, and J. Feng. Can we beat the prefix filtering?: an adaptive framework for similarity join and search. In SIGMOD Conference, pp. 85-96, 2012.23
[9] A. Behm, S. Ji, C. Li, and J. Lu. Space-constrained gram-based indexing for efficient approximate string search. In ICDE, pp. 604-615, 2009.
[10] A. Behm, C. Li, and M. J. Carey. Answering approximate string queries on large data sets using external memory. In ICDE, pp. 888-899, 2011.
[11] S. Chaudhuri, V. Ganti, and R. Kaushik. A primitive operator for similarity joins in data cleaning. In ICDE, pp. 5, 2006.
[12] A. Arasu, V. Ganti, and R. Kaushik. Efficient exact set-similarity joins. In VLDB,
pp. 918-929, 2006.
[13] G. Li, D. Deng, J. Wang, and J. Feng. Pass-join: A partition-based method for similarity joins. In PVLDB, vol. 5, no. 3, pp. 253-264, 2011.
[14] Z. Zhang, M. Hadjieleftheriou, B. C. Ooi, and D. Srivastava. Bedtree: an all-purpose index structure for string similarity search based on edit distance. In SIGMOD, pp. 915-926, 2010.
[15] W. Lu, X. Du, M. Hadjieleftheriou, and B. C. Ooi. Efficiently supporting edit distance based string similarity search using B+-trees. In IEEE Transactions on Knowledge and Data Engineering, vol.26, no.12, pp.2983-2996, 2014.
[16] W. J. Masek and M. Paterson. A faster algorithm computing string edit distances. In Journal of Computer and System Sciences, 20(1):18-31, 1980.
[17] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. In MIT Press and McGraw-Hill, 2001.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top