WEKO3
アイテム
BEVA: An Efficient Query Processing Algorithm for Error-Tolerant Autocompletion
http://hdl.handle.net/2237/24929
http://hdl.handle.net/2237/249291b756205-2d8f-4a37-bce7-2a0d9257ad39
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
tods-beva-final.pdf (1.8 MB)
|
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2016-09-30 | |||||
| タイトル | ||||||
| タイトル | BEVA: An Efficient Query Processing Algorithm for Error-Tolerant Autocompletion | |||||
| 言語 | en | |||||
| 著者 |
Zhou, Xiaoling
× Zhou, Xiaoling× Qin, Jianbin× Xiao, Chuan× Wang, Wei× Lin, Xuemin× Ishikawa, Yoshiharu |
|||||
| アクセス権 | ||||||
| アクセス権 | open access | |||||
| アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||
| 権利 | ||||||
| 言語 | en | |||||
| 権利情報 | © ACM 2016. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM Transactions on Database Systems (TODS). v.41, n.1, 2016, p.5, http://dx.doi.org/10.1145/2877201 | |||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | Query autocompletion has become a standard feature in many search applications, especially for search engines. A recent trend is to support the error-tolerant autocompletion, which increases the usability significantly by matching prefixes of database strings and allowing a small number of errors. In this article, we systematically study the query processing problem for error-tolerant autocompletion with a given edit distance threshold. We propose a general framework that encompasses existing methods and characterizes different classes of algorithms and the minimum amount of information they need to maintain under different constraints. We then propose a novel evaluation strategy that achieves the minimum active node size by eliminating ancestor-descendant relationships among active nodes entirely. In addition, we characterize the essence of edit distance computation by a novel data structure named edit vector automaton (EVA). It enables us to compute new active nodes and their associated states efficiently by table lookups. In order to support large distance thresholds, we devise a partitioning scheme to reduce the size and construction cost of the automaton, which results in the universal partitioned EVA (UPEVA) to handle arbitrarily large thresholds. Our extensive evaluation demonstrates that our proposed method outperforms existing approaches in both space and time efficiencies. | |||||
| 言語 | en | |||||
| 内容記述 | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | - Invited Paper from ICDT 2015, SIGMOD 2014, EDBT 2014 and Regular Papers | |||||
| 言語 | en | |||||
| 出版者 | ||||||
| 出版者 | Association for Computing Machinery | |||||
| 言語 | en | |||||
| 言語 | ||||||
| 言語 | eng | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
| 資源タイプ | journal article | |||||
| 出版タイプ | ||||||
| 出版タイプ | AM | |||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||
| DOI | ||||||
| 関連タイプ | isVersionOf | |||||
| 識別子タイプ | DOI | |||||
| 関連識別子 | https://doi.org/10.1145/2877201 | |||||
| ISSN | ||||||
| 収録物識別子タイプ | PISSN | |||||
| 収録物識別子 | 0362-5915 | |||||
| 書誌情報 |
en : ACM Transactions on Database Systems (TODS) 巻 41, 号 1, p. 5-5, 発行日 2016-04 |
|||||
| 著者版フラグ | ||||||
| 値 | author | |||||
| URI | ||||||
| 識別子 | http://doi．org/10.1145/2877201 | |||||
| 識別子タイプ | URI | |||||
| URI | ||||||
| 識別子 | http://hdl.handle.net/2237/24929 | |||||
| 識別子タイプ | HDL | |||||
