WEKO3
アイテム
{"_buckets": {"deposit": "15e0b9b6-906d-4b7a-a231-d8781d500943"}, "_deposit": {"created_by": 3, "id": "8532", "owners": [3], "pid": {"revision_id": 0, "type": "depid", "value": "8532"}, "status": "published"}, "_oai": {"id": "oai:uec.repo.nii.ac.jp:00008532", "sets": ["10"]}, "author_link": ["23300"], "control_number": "8532", "item_10006_alternative_title_1": {"attribute_name": "その他(別言語等)のタイトル", "attribute_value_mlt": [{"subitem_alternative_title": "空間Webデータにおけるm-最近接キーワード検索問題のトップダウン解法に関する研究", "subitem_alternative_title_language": "ja"}]}, "item_10006_date_granted_11": {"attribute_name": "学位授与年月日", "attribute_value_mlt": [{"subitem_dategranted": "2017-03-24"}]}, "item_10006_degree_grantor_9": {"attribute_name": "学位授与機関", "attribute_value_mlt": [{"subitem_degreegrantor": [{"subitem_degreegrantor_name": "電気通信大学"}], "subitem_degreegrantor_identifier": [{"subitem_degreegrantor_identifier_name": "12612", "subitem_degreegrantor_identifier_scheme": "kakenhi"}]}]}, "item_10006_degree_name_8": {"attribute_name": "学位名", "attribute_value_mlt": [{"subitem_degreename": "博士(工学)"}]}, "item_10006_description_10": {"attribute_name": "学位授与年度", "attribute_value_mlt": [{"subitem_description": "2016", "subitem_description_type": "Other"}]}, "item_10006_description_7": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "This thesis addresses the problem of m-closest keywords queries (mCK queries) over spatial web objects that contain descriptive texts and spatial information. The mCK query is a problem to find the optimal set of records in the sense that they are the spatially-closest records that satisfy m user-given keywords in their texts. The mCK query can be widely used in various applications to find the place of user’s interest.\n Generally, top-down search techniques using tree-style data structures are appropriate for finding optimal results of queries over spatial datasets. Thus in order to solve the mCK query problem, a previous study of NUS group assumed a specialized R*-tree (called bR*-tree) to store all records and proposed a top-down approach which uses an Apriori-based node-set enumeration in top-down process. However this assumption of prepared bR*-tree is not applicable to practical spatial web datasets, and the pruning ability of Apriori-based enumeration is highly dependent on the data distribution.\n In this thesis, we do not expect any prepared data-partitioning, but assume that we create a grid partitioning from necessary data only when an mCK query is given. Under this assumption, we propose a new search strategy termed Diameter Candidate Check (DCC), which can find a smaller node-set at an earlier stage of search so that it can reduce search space more efficiently. According to DCC search strategy, we firstly employ an implementation of DCC strategy in a nested loop search algorithm (called DCC-NL). Next, we improve the DCC-NL in a recursive way (called RDCC). RDCC can afford a more reasonable priority order of node-set enumeration. We also uses a tight lower bound to improve pruning ability in RDCC.\n RDCC performs well in a wide variey of data distributions, but it has still deficiency when one data-point has many query keywords and numerous node-sets are generated. Hence in order to avoid the generation of node-sets which is an unstable factor of search efficiency, we propose another different top-down search approach called Pairwise Expansion. Finally, we discuss some optimization techniques to enhance Pairwise Expansion approach. We first discuss the index structure in the Pairwise Expansion approach, and try to use an on-the-fly kd-tree to reduce building cost in the query process. Also a new lower bound and an upper bound are employed for more powerful pruning in Pairwise Expansion.\n We evaluate these approaches by using both real datasets and synthetic datasets for different data distributions, including 1.6 million of Flickr photo data. The result shows that DCC strategy can provide more stable search performance than the Apriori-based approach. And the Pairwise Expansion approach enhanced with lower/upper bounds, has more advantages over those algorithms having node-set generation, and is applicable for real spatial web data.", "subitem_description_type": "Abstract"}]}, "item_10006_dissertation_number_12": {"attribute_name": "学位授与番号", "attribute_value_mlt": [{"subitem_dissertationnumber": "甲第904号"}]}, "item_10006_text_22": {"attribute_name": "専攻", "attribute_value_mlt": [{"subitem_text_value": "情報システム学研究科"}, {"subitem_text_value": "情報システム基盤学専攻"}]}, "item_10006_text_23": {"attribute_name": "学術成果タイプ", "attribute_value_mlt": [{"subitem_text_value": "博士学位論文"}]}, "item_10006_version_type_18": {"attribute_name": "著者版フラグ", "attribute_value_mlt": [{"subitem_version_resource": "http://purl.org/coar/version/c_970fb48d4fbd8a85", "subitem_version_type": "VoR"}]}, "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": "邱, 原", "creatorNameLang": "ja"}, {"creatorName": "キュウ, ゲン", "creatorNameLang": "ja-Kana"}, {"creatorName": "Qiu, Yuan", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "23300", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2017-04-24"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "1363003.pdf", "filesize": [{"value": "18.2 MB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 18200000.0, "url": {"label": "1363003.pdf", "url": "https://uec.repo.nii.ac.jp/record/8532/files/1363003.pdf"}, "version_id": "43401685-f7a8-4e09-b418-820ed6b5bd50"}]}, "item_language": {"attribute_name": "言語", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"resourcetype": "doctoral thesis", "resourceuri": "http://purl.org/coar/resource_type/c_db06"}]}, "item_title": "A Study on Top-down Search Algorithms for m-Closest Keywords Queries Problem over Spatial Web", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "A Study on Top-down Search Algorithms for m-Closest Keywords Queries Problem over Spatial Web", "subitem_title_language": "en"}]}, "item_type_id": "10006", "owner": "3", "path": ["10"], "permalink_uri": "https://uec.repo.nii.ac.jp/records/8532", "pubdate": {"attribute_name": "PubDate", "attribute_value": "2017-08-01"}, "publish_date": "2017-08-01", "publish_status": "0", "recid": "8532", "relation": {}, "relation_version_is_last": true, "title": ["A Study on Top-down Search Algorithms for m-Closest Keywords Queries Problem over Spatial Web"], "weko_shared_id": -1}
A Study on Top-down Search Algorithms for m-Closest Keywords Queries Problem over Spatial Web
https://uec.repo.nii.ac.jp/records/8532
https://uec.repo.nii.ac.jp/records/853209e7be6d-a700-41af-9c94-322d60bbdfb1
名前 / ファイル | ライセンス | アクション |
---|---|---|
1363003.pdf (18.2 MB)
|
|
Item type | 学位論文 / Thesis or Dissertation(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2017-08-01 | |||||
タイトル | ||||||
言語 | en | |||||
タイトル | A Study on Top-down Search Algorithms for m-Closest Keywords Queries Problem over Spatial Web | |||||
言語 | ||||||
言語 | eng | |||||
資源タイプ | ||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_db06 | |||||
資源タイプ | doctoral thesis | |||||
アクセス権 | ||||||
アクセス権 | open access | |||||
アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||
その他(別言語等)のタイトル | ||||||
その他のタイトル | 空間Webデータにおけるm-最近接キーワード検索問題のトップダウン解法に関する研究 | |||||
言語 | ja | |||||
著者 |
邱, 原
× 邱, 原 |
|||||
抄録 | ||||||
内容記述タイプ | Abstract | |||||
内容記述 | This thesis addresses the problem of m-closest keywords queries (mCK queries) over spatial web objects that contain descriptive texts and spatial information. The mCK query is a problem to find the optimal set of records in the sense that they are the spatially-closest records that satisfy m user-given keywords in their texts. The mCK query can be widely used in various applications to find the place of user’s interest. Generally, top-down search techniques using tree-style data structures are appropriate for finding optimal results of queries over spatial datasets. Thus in order to solve the mCK query problem, a previous study of NUS group assumed a specialized R*-tree (called bR*-tree) to store all records and proposed a top-down approach which uses an Apriori-based node-set enumeration in top-down process. However this assumption of prepared bR*-tree is not applicable to practical spatial web datasets, and the pruning ability of Apriori-based enumeration is highly dependent on the data distribution. In this thesis, we do not expect any prepared data-partitioning, but assume that we create a grid partitioning from necessary data only when an mCK query is given. Under this assumption, we propose a new search strategy termed Diameter Candidate Check (DCC), which can find a smaller node-set at an earlier stage of search so that it can reduce search space more efficiently. According to DCC search strategy, we firstly employ an implementation of DCC strategy in a nested loop search algorithm (called DCC-NL). Next, we improve the DCC-NL in a recursive way (called RDCC). RDCC can afford a more reasonable priority order of node-set enumeration. We also uses a tight lower bound to improve pruning ability in RDCC. RDCC performs well in a wide variey of data distributions, but it has still deficiency when one data-point has many query keywords and numerous node-sets are generated. Hence in order to avoid the generation of node-sets which is an unstable factor of search efficiency, we propose another different top-down search approach called Pairwise Expansion. Finally, we discuss some optimization techniques to enhance Pairwise Expansion approach. We first discuss the index structure in the Pairwise Expansion approach, and try to use an on-the-fly kd-tree to reduce building cost in the query process. Also a new lower bound and an upper bound are employed for more powerful pruning in Pairwise Expansion. We evaluate these approaches by using both real datasets and synthetic datasets for different data distributions, including 1.6 million of Flickr photo data. The result shows that DCC strategy can provide more stable search performance than the Apriori-based approach. And the Pairwise Expansion approach enhanced with lower/upper bounds, has more advantages over those algorithms having node-set generation, and is applicable for real spatial web data. |
|||||
学位名 | ||||||
学位名 | 博士(工学) | |||||
学位授与機関 | ||||||
学位授与機関識別子Scheme | kakenhi | |||||
学位授与機関識別子 | 12612 | |||||
学位授与機関名 | 電気通信大学 | |||||
学位授与年度 | ||||||
内容記述タイプ | Other | |||||
内容記述 | 2016 | |||||
学位授与年月日 | ||||||
学位授与年月日 | 2017-03-24 | |||||
学位授与番号 | ||||||
学位授与番号 | 甲第904号 | |||||
著者版フラグ | ||||||
出版タイプ | VoR | |||||
出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||
専攻 | ||||||
情報システム学研究科 | ||||||
専攻 | ||||||
情報システム基盤学専攻 | ||||||
学術成果タイプ | ||||||
博士学位論文 |