{"created":"2021-03-01T05:52:57.577279+00:00","id":1245,"links":{},"metadata":{"_buckets":{"deposit":"cd4bf6cb-c1eb-4a36-9491-6bc5be7fca32"},"_deposit":{"id":"1245","owners":[],"pid":{"revision_id":0,"type":"depid","value":"1245"},"status":"published"},"_oai":{"id":"oai:repository.nii.ac.jp:00001245","sets":["136"]},"author_link":[],"control_number":"1245","item_5_biblio_info_30":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2008-08-18","bibliographicIssueDateType":"Issued"},"bibliographicPageStart":"none","bibliographic_titles":[{"bibliographic_title":"NIIテクニカル・レポート","bibliographic_titleLang":"ja"},{"bibliographic_title":"NII Technical Report","bibliographic_titleLang":"en"}]}]},"item_5_description_28":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"We propose an approximation method to answer shortest path queries in graphs, based on hierarchical random sampling and Voronoi duals. The lowest level of the hierarchy stores the initial graph. At each higher level, we compute a simplification of the graph on the level below, by selecting a constant fraction of nodes. Edges are generated as the Voronoi dual within the lower level, using the selected nodes as Voronoi sites. This hierarchy allows for fast computation of approximate shortest paths for general graphs. The time-quality tradeoff decision can be made at query time. We provide bounds on the approximation ratio of the path lengths.","subitem_description_language":"en","subitem_description_type":"Abstract"}]},"item_5_identifier_registration":{"attribute_name":"ID登録","attribute_value_mlt":[{"subitem_identifier_reg_text":"10.20736/0000001245","subitem_identifier_reg_type":"JaLC"}]},"item_5_publisher_31":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"国立情報学研究所","subitem_publisher_language":"ja"}]},"item_5_source_id_32":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1346-5597","subitem_source_identifier_type":"ISSN"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Sommer, Christian","creatorNameLang":"en"}]},{"creatorNames":[{"creatorName":"Houle, Michael E.","creatorNameLang":"en"}]},{"creatorNames":[{"creatorName":"Wolff, Martin","creatorNameLang":"en"}]},{"creatorNames":[{"creatorName":"本位田, 真一","creatorNameLang":"ja"},{"creatorName":"Honiden, Shinichi","creatorNameLang":"en"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2019-03-12"}],"displaytype":"detail","filename":"08-007E.pdf","filesize":[{"value":"306.0 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"NII Technical Report (NII-2008-007E)：Approximate Shortest Path Queries in Graphs Using Voronoi Duals","url":"https://repository.nii.ac.jp/record/1245/files/08-007E.pdf"},"version_id":"242939cc-d842-498e-acbc-c081dfb3fd89"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"テクニカルレポート","subitem_subject_language":"ja","subitem_subject_scheme":"Other"},{"subitem_subject":"Technical Report","subitem_subject_language":"en","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"departmental bulletin paper","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"NII Technical Report (NII-2008-007E)：Approximate Shortest Path Queries in Graphs Using Voronoi Duals","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"NII Technical Report (NII-2008-007E)：Approximate Shortest Path Queries in Graphs Using Voronoi Duals","subitem_title_language":"en"}]},"item_type_id":"5","owner":"1","path":["136"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2019-03-12"},"publish_date":"2019-03-12","publish_status":"0","recid":"1245","relation_version_is_last":true,"title":["NII Technical Report (NII-2008-007E)：Approximate Shortest Path Queries in Graphs Using Voronoi Duals"],"weko_creator_id":"1","weko_shared_id":-1},"updated":"2023-01-05T06:25:08.176064+00:00"}