オープンネットワーク環境における位置依存サービスのための高性能牽引構造

开放网络环境中位置相关服务的高性能牵引结构

基本信息

批准号：
06F06368
负责人：
北川博之
金额：
$ 1.54万
依托单位：
University of Tsukuba
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2006
资助国家：
日本
起止时间：
2006 至 2008
项目状态：
已结题

项目摘要

ストリームデータの中には,移動体の位置情報等,多次元データが存在する.多次元データでは,空間的検索を支援する必要がある.例えば,距離検索や近傍検索等である.多次元データに対する索引機構としては,R木等の空間索引が従来用いられてきたが,従来の空間索引は静的なデータを対象としており,オブジェクトの現在値が頻繁に変化する動的な環境下では,極めて性能が劣化することが知られている.本研究では,R木を元に,主記憶と二次記憶を有機的に利用することで,この問題に対応するための新たな索引機構R^{sb}木(R-tree with Semi-Bulkloading)を開発した.頻繁なデータの更新がある状況でのR木の性能劣化は,主に,処理時間のかかるディスクアクセスが頻繁に発生することに起因する,そこで,現在値の多くを主記憶上のバッファ領域で管理し,空間的に近いオブジェクトの更新情報をバッチ的にまとめてディスク中のR木に反映することで,ディスクアクセス数を大幅に削減する方式を考案した.ディスクアクセス時には,該当ページに新たな現在値を追加すると共に同一ページ中にある古い値を削除する.また,移動オブジェクト情報の生成器によって生成された実験データを用いて,さまざまなパラメタ値のもとで,更新性能,問合せ処理性能,索引サイズ等を測定した.また,同様の実験を既存の関連研究で提案されている手法に対しても実施した.この結果,提案手法は既存の関連手法に比べて様々な側面において優位性があることを確認した.

流数据包括多维数据，例如移动物体的位置信息。多维数据需要支持空间搜索，例如距离搜索、邻域搜索。多维数据传统上，使用R树等空间索引作为索引机制众所周知，在对象当前值频繁变化的动态环境中，性能会极度下降。一种新的索引机制R^{sb}树（R-tree）。和我们开发了一种称为半批量加载（Semi-Bulkloading）的方法。在数据频繁更新的情况下，R-tree 的性能恶化主要是由于频繁的磁盘访问占用了处理时间。我们设计了一种方法来显着减少次数。通过管理主存缓冲区中空间上接近的对象的更新信息，并将其批量反映到磁盘上的R树上，来进行磁盘访问。向该页面添加新的当前值并删除同一页面上的旧值。此外，使用移动对象信息生成器生成的实验数据，我们测量了各种参数值下的性能、查询处理性能、我们也对现有相关研究中提出的方法进行了类似的实验，证实在这些方面都存在优势。