ログイン
言語:

WEKO3

  • トップ
  • ランキング
To
lat lon distance
To

Field does not validate



インデックスリンク

インデックスツリー

メールアドレスを入力してください。

WEKO

One fine body…

WEKO

One fine body…

アイテム

  1. A500 情報学部/情報学研究科・情報文化学部・情報科学研究科
  2. A500a 雑誌掲載論文
  3. 学術雑誌

BEVA: An Efficient Query Processing Algorithm for Error-Tolerant Autocompletion

http://hdl.handle.net/2237/24929
http://hdl.handle.net/2237/24929
1b756205-2d8f-4a37-bce7-2a0d9257ad39
名前 / ファイル ライセンス アクション
tods-beva-final.pdf 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

WEKO 67041

en Zhou, Xiaoling

Search repository
Qin, Jianbin

× Qin, Jianbin

WEKO 67042

en Qin, Jianbin

Search repository
Xiao, Chuan

× Xiao, Chuan

WEKO 67043

en Xiao, Chuan

Search repository
Wang, Wei

× Wang, Wei

WEKO 67044

en Wang, Wei

Search repository
Lin, Xuemin

× Lin, Xuemin

WEKO 67045

en Lin, Xuemin

Search repository
Ishikawa, Yoshiharu

× Ishikawa, Yoshiharu

WEKO 67046

en Ishikawa, Yoshiharu

Search repository
アクセス権
アクセス権 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
資源タイプ
資源タイプresource 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
戻る
0
views
See details
Views

Versions

Ver.1 2021-03-01 14:50:22.041494
Show All versions

Share

Mendeley Twitter Facebook Print Addthis

Cite as

エクスポート

OAI-PMH
  • OAI-PMH JPCOAR 2.0
  • OAI-PMH JPCOAR 1.0
  • OAI-PMH DublinCore
  • OAI-PMH DDI
Other Formats
  • JSON
  • BIBTEX

Confirm


Powered by WEKO3


Powered by WEKO3