{"created":"2021-03-01T06:30:33.825360+00:00","id":22770,"links":{},"metadata":{"_buckets":{"deposit":"34533de8-0518-4c0a-8bf7-73dc2c63b52d"},"_deposit":{"id":"22770","owners":[],"pid":{"revision_id":0,"type":"depid","value":"22770"},"status":"published"},"_oai":{"id":"oai:nagoya.repo.nii.ac.jp:00022770","sets":["312:313:314"]},"author_link":["67041","67042","67043","67044","67045","67046"],"item_10_biblio_info_6":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2016-04","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"1","bibliographicPageEnd":"5","bibliographicPageStart":"5","bibliographicVolumeNumber":"41","bibliographic_titles":[{"bibliographic_title":"ACM Transactions on Database Systems (TODS)","bibliographic_titleLang":"en"}]}]},"item_10_description_4":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_language":"en","subitem_description_type":"Abstract"}]},"item_10_description_5":{"attribute_name":"内容記述","attribute_value_mlt":[{"subitem_description":"- Invited Paper from ICDT 2015, SIGMOD 2014, EDBT 2014 and Regular Papers","subitem_description_language":"en","subitem_description_type":"Other"}]},"item_10_identifier_60":{"attribute_name":"URI","attribute_value_mlt":[{"subitem_identifier_type":"URI","subitem_identifier_uri":"http://doi．org/10.1145/2877201"},{"subitem_identifier_type":"HDL","subitem_identifier_uri":"http://hdl.handle.net/2237/24929"}]},"item_10_publisher_32":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Association for Computing Machinery","subitem_publisher_language":"en"}]},"item_10_relation_11":{"attribute_name":"DOI","attribute_value_mlt":[{"subitem_relation_type":"isVersionOf","subitem_relation_type_id":{"subitem_relation_type_id_text":"https://doi.org/10.1145/2877201","subitem_relation_type_select":"DOI"}}]},"item_10_rights_12":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"© 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","subitem_rights_language":"en"}]},"item_10_select_15":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_select_item":"author"}]},"item_10_source_id_7":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"0362-5915","subitem_source_identifier_type":"PISSN"}]},"item_1615787544753":{"attribute_name":"出版タイプ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_ab4af688f83e57aa","subitem_version_type":"AM"}]},"item_access_right":{"attribute_name":"アクセス権","attribute_value_mlt":[{"subitem_access_right":"open access","subitem_access_right_uri":"http://purl.org/coar/access_right/c_abf2"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Zhou, Xiaoling","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"67041","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Qin, Jianbin","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"67042","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Xiao, Chuan","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"67043","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Wang, Wei","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"67044","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Lin, Xuemin","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"67045","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Ishikawa, Yoshiharu","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"67046","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2018-02-22"}],"displaytype":"detail","filename":"tods-beva-final.pdf","filesize":[{"value":"1.8 MB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"tods-beva-final.pdf","objectType":"fulltext","url":"https://nagoya.repo.nii.ac.jp/record/22770/files/tods-beva-final.pdf"},"version_id":"df26ba76-71d7-4610-8fad-db62b9775846"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"BEVA: An Efficient Query Processing Algorithm for Error-Tolerant Autocompletion","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"BEVA: An Efficient Query Processing Algorithm for Error-Tolerant Autocompletion","subitem_title_language":"en"}]},"item_type_id":"10","owner":"1","path":["314"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2016-09-30"},"publish_date":"2016-09-30","publish_status":"0","recid":"22770","relation_version_is_last":true,"title":["BEVA: An Efficient Query Processing Algorithm for Error-Tolerant Autocompletion"],"weko_creator_id":"1","weko_shared_id":-1},"updated":"2023-01-16T04:12:18.102115+00:00"}