智能计算机与应用
智能計算機與應用
지능계산궤여응용
Computer Study
2012年
5期
31-34,38
,共5页
字符串相似连接%编辑距离%外存算法%数据划分
字符串相似連接%編輯距離%外存算法%數據劃分
자부천상사련접%편집거리%외존산법%수거화분
字符串相似连接操作具有广泛应用,因而将着重研究基于编辑距离的字符串相似连接.而现有的字符串相似连接算法大多为内存算法.实际应用中的数据集越来越大,有必要针对超大规模数据集研制字符串相似性连接外存算法.利用组合频率向量划分数据集,并提出了基于编辑距离的字符串相似性连接外存算法框架,证明了磁盘调度问题的难度并提出了不同的启发式磁盘调度方法.此外,还提出了基于该外存算法框架实现字符串相似性连接增量式计算的方法.实验结果表明,数据划分方法可以有效地过滤不相关的数据子集;磁盘调度算法能够有效减少磁盘IO次数;外存算法是高效的;增量式计算方法能够高效地处理数据更新.
字符串相似連接操作具有廣汎應用,因而將著重研究基于編輯距離的字符串相似連接.而現有的字符串相似連接算法大多為內存算法.實際應用中的數據集越來越大,有必要針對超大規模數據集研製字符串相似性連接外存算法.利用組閤頻率嚮量劃分數據集,併提齣瞭基于編輯距離的字符串相似性連接外存算法框架,證明瞭磁盤調度問題的難度併提齣瞭不同的啟髮式磁盤調度方法.此外,還提齣瞭基于該外存算法框架實現字符串相似性連接增量式計算的方法.實驗結果錶明,數據劃分方法可以有效地過濾不相關的數據子集;磁盤調度算法能夠有效減少磁盤IO次數;外存算法是高效的;增量式計算方法能夠高效地處理數據更新.
자부천상사련접조작구유엄범응용,인이장착중연구기우편집거리적자부천상사련접.이현유적자부천상사련접산법대다위내존산법.실제응용중적수거집월래월대,유필요침대초대규모수거집연제자부천상사성련접외존산법.이용조합빈솔향량화분수거집,병제출료기우편집거리적자부천상사성련접외존산법광가,증명료자반조도문제적난도병제출료불동적계발식자반조도방법.차외,환제출료기우해외존산법광가실현자부천상사성련접증량식계산적방법.실험결과표명,수거화분방법가이유효지과려불상관적수거자집;자반조도산법능구유효감소자반IO차수;외존산법시고효적;증량식계산방법능구고효지처리수거경신.