Hisashi KOGA (古賀 久志)

Offer Organization: 日本学術振興会, System Name: 科学研究費助成事業 基盤研究(C), Category: 基盤研究(C), Fund Type: -, Overall Grant Amount: - (direct: 2700000, indirect: 810000)
本研究課題はデータストリームを対象とする類似検索を取り扱う。その具体的な応用としては、嗜好性が似たユーザの発見が挙げられる。例えば、閲覧したウェブニュース記事の集合が互いに似た2ユーザは、興味がある事柄が似ており、嗜好性が似ていると言える。このようにして、類似ユーザ検索を集合間類似検索に帰着できる。
要素が固定した通常の集合に対しては、Min Hashというハッシュ関数を利用して集合の要約(スケッチ）を事前生成し、スケッチ間で軽量に類似度計算することで、類似検索を高速化できる。しかし、ストリーム環境では新しい要素の追加と古い要素の消滅が起きるため、スケッチを高速更新する必要がある。そこで本研究では、ストリーム環境で集合の要素が入れ替わる状況で、Min Hashを高速計算するアルゴリズムの開発に取り組んだ。
そして2021年度は、多重集合を取り扱えなかったDatarらの既存手法を、多重集合が取り扱えるよう拡張することに成功した。ここで、多重集合とは同じラベルの要素を複数持てる集合のことである。Min Hashは集合の各要素に確率的に値を割り当て、その最小値をハッシュ値とする。既存手法では将来的に最小値になりえない要素を削除して、ハッシュ値再計算のオーバーヘッドを削減している。しかし、多重集合の場合、要素への割り当て値が多重度に依存して動的に変わるため将来的に最小値になりえるかの判定が困難になる。我々の提案手法は、この厳しい条件下で、将来的に最小値にならない要素を判別する。さらに同一ラベルの要素を、提案手法が高々１つだけ保持すればよいことも示せた。集合の要素数をWとすると、提案手法の計算時間は実験的にlog Wに比例し、O(W)かかるベースライン手法より圧倒的に高速に動作することを確認できた。

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 2100000, indirect: 630000)
This research studied similarity search for data streams. In particular, we regard the latest data in a data stream as an evolving set whose elements can change dynamically. Then, we realized the similarity search for data streams by reducing the problem to the set similarity search. In particular, we developed several fast similarity search algorithms that measure the similarity between two data just enough to determine the search results, avoiding unnecessary similarity computations. It is also our research contribution that we formulated two similarity search problems for data streams.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 2100000, indirect: 630000)
Compression based pattern recognition is an unsupervised data analysis technique which realizes data analysis without prior knowledge about the data to be analyzed. Its primary point is to measure the similarity between two data based on the compression rate. In particular, in order to exploit the standard pattern recognition algorithms such as SVM and k-means, this research deals with compression-based feature spaces in which an object is represented as a compression vector consisting of multiple compression ratios and studies their effective construction. As the main result, by exchanging the words among the compression dictionaries each of which is responsible for one dimension so that they may be more independent one another, we succeeded in improving the pattern recognition accuracy by 7 to 8% as compared with the previous method in literatures.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 2400000, indirect: 720000)
This project studied the similarity search for structural data such as graphs. Because structural data are complex, the overhead to compute the similarity between two data tends to be enormous. Therefore, we generate a small data structure called "digest" for an individual graph and measure the similarity between two data in a short time by comparing their digests. Here, the search accuracy depends on how to summarize the structural information of a graph onto its digest. By embedding the similarity information regarding substructures into the digests, we succeeded in realizing the similarity search with a high retrieval accuracy.


We also studied the structure-based image processing which is a promising application of similarity search for structural data.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 3200000, indirect: 960000)
Traditional object recognition schemes have been the statistical one wherein target objects’ statistical models are prepared manually and applied to unknown task data. Due to the heavy human intervention, this approach becomes weak for multi-media data with variety of target objects. In this research, a new autonomous object model acquisition scheme is investigated. For this, we investigate the possibility of data’s compressibility vector as a general feature, the possibility of co-occurrence-based object discovery and the possibility of highly autonomous recognition scheme based oh them. Promising experimental results are reported.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 1900000, indirect: 570000)
We studied the two problems which arise in the environment where multiple computers interact with one another and designed effective algorithms for the problems. First, we constructed an algorithm which alleviates the throughput unfairness among different TCP connections. To deploy our algorithm, we have only to replace the operating systems in the end-hosts without modifying the routers. Next, we dealt with the similarity search in the distributed database composed by multiple computers and devised an algorithm which makes the query response shorter by 10% than the known simple method.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 3300000, indirect: 990000)
インターネットや携帯電話の発展の中で文章、音声、画像などのマルチメディアデータが爆発的に増大している。本研究では、人手介入なしに、計算機によってこれらを分類あるいは検索する方式を検討した。我々が過去検討してきた、圧縮率によるテキストの特徴表現方式を原理としつつ、より高性能な圧縮性特徴空間の構成可能性の検討、文書や画像分類への適用などを試みた。文法知識を事前準備せずに、文章や画像に適用できること、従来方式をしのぐ性能も発揮できることなどを確認できた。なお、EUでの衛星画像利用地球環境管理国際プロジェクト(GEOSS)関係機関より招待され、衛星画像処理への応用可能性について講演も実施した。

Offer Organization: 日本学術振興会, System Name: 科学研究費助成事業 若手研究(B), Category: 若手研究(B), Fund Type: -, Overall Grant Amount: - (direct: 2500000, indirect: -)
本年度は、まずTCPのack回数と通信品質(遅延)との関係を昨年度に提案したスライディングウィンドウ機構を考慮した理論モデル上でより厳密に解析を行い、受信者が送信者側の輻輳ウィンドウサイズを知ることができればack頻度を増やさずに遅延の増大を抑えられることを示した。現状のTCPでは輻輳ウィンドウサイズを受信者が知らないので、この点を改良することで性能向上が期待できる。
本結果は国際会議lnternational Workshop on Algorithm and Data Structuresにおいて採択された。また、海外雑誌への論文投稿も完了し、査読中である。
次に、高速トランスポート層プロトコルの公平性に関する研究を実施した。高速トランスポートプロトコルは長距離広帯域ネットワークを効率的に使う目的で開発されたが、異なる種類の高速トランスポート層プロトコルが競合する環境を想定して設計されていない。この結果、aggressiveな高速プロトコルがmoderateな高速プロトコルと競合すると、後者は高速プロトコルであるにもかかわらず低いスループットしか出せないという問題があ。本研究では一番aggressiveな高速プロトコルとして知られているUDTに着目し、UDTをmoderateに改良したmUDTというプロトコルを提案した。mUDTの特徴は、RTTの増加により他のコネクションと競合しているかを検知し、競合発生時のみ送信レート増加を遅くする点である。これにより空き帯域を短時間で埋めるというUDTの長所を残しつつ、他のプロトコルとの公平性を増加させることに成功した。本成果を電子情報通信学会情報ネットワーク研究会で発表した。
また、モバイルアドホックネットワークにおける通信の省電力化に着目し、特に端末に指向性アンテナが装備された環境で、指向性・非指向性の切り替えと送信パワーコントロールをどうスケジューリングすれば、通信性能を劣化させずに省電力化を実現できるかいう研究に取り組んだ。評価にqualnetを使用したが、外部発表できるだけのまとまった成果は得られていない。