Faculty Profiles - ISHIKAWA, Yoshiharu

Papers - ISHIKAWA, Yoshiharu

Division display 81 - 100 of about 320 ／ All the affair displays >>

Scalable Top-k Keyword Search in Relational Databases Reviewed

Yanwei Xu, Jihong Guan, Yoshiharu Ishikawa

Proceedings of 17th International Conference on Database Systems for Advanced Applications (DASFAA 2012) Vol. 2 page： 65-80 2012.4

Language：English

Keyword search in relational databases has been widely studied in recent years because it does not require users neither to master a certain structured query language nor to know the complex underlying database schemas. There would be a huge number of valid results for a keyword query in a large database. However, only the top 10 or 20 most relevant matches for the keyword query - according to some definition of 'Relevance' - are generally of interest. In this paper, we propose an efficient method for answering top-k keyword queries over relational databases. The proposed method is built on an existing scheme of keyword search on relational data streams, but incorporates the ranking mechanisms into the query processing methods and makes two improvements to support top-k keyword search in relational databases. Experimental results validate the effectiveness and efficiency of the proposed method.

DOI： 10.1007/978-3-642-29035-0_5

Hadoop環境における空間分割による並列全k近傍問合せ処理 Reviewed

横山拓也, 石川佳治, 鈴木優

日本データベース学会論文誌 Vol. 11 ( 1 ) page： 25-30 2012.6

Language：Japanese Publishing type：Research paper (scientific journal)

指定された点に対して最も近い$k$個の点を求める$k$最近傍問合せは，空間データベースでは基本的な問合せの1つである．これに関連して，データ集合中の各点について，それぞれの$k$最近傍を一度に求める問合せを全$k$最近傍問合せという．本研究では，この全k最近傍問合せをMapReduceフレームワーク上で行う手法を提案する．空間をセルに分割し，全$k$最近傍問合せの処理をMapReduceの並列分散処理方式に合った形で実行する．分割により生じる問題にMapReduceフレームワークに適した形で対応するための，対象データの分布情報を考慮した改善策についても提案を行う．

Processing All k-Nearest Neighbor Queries in Hadoop Reviewed

Takuya Yokoyama, Yoshiharu Ishikawa, Yu Suzuki

Proceedings of the 13th International Conference on Web-Age Information Management (WAIM 2012) page： 346-351 2012.8

Language：English

A k-nearest neighbor (k-NN) query, which retrieves nearest k points from a database is one of the fundamental query types in spatial databases. An all k-nearest neighbor query (AkNN query), a variation of a k-NN query, determines the k-nearest neighbors for each point in the dataset in a query process. In this paper, we propose a method for processing AkNN queries in Hadoop. We decompose the given space into cells and execute a query using the MapReduce framework in a distributed and parallel manner. Using the distribution statistics of the target data points, our method can process given queries efficiently.

DOI： 10.1007/978-3-642-32281-5_34

Privacy Preservation for Location-Based Services Based on Attribute Visibility Reviewed

Masanori Mano, Xi Guo, Tingting Dong, Yoshiharu Ishikawa

Proceedings of the International Workshop on Information Management in Mobile Applications (IMMoA 2012) page： 33-41 2012.8

Language：English

To provide a high-quality mobile service in a safe way, many techniques for \emph{location anonymity} have been proposed in recent years.
Advanced location-based services such as mobile advertisement services may use not only users' locations but also users' attributes.
However, the existing location anonymization methods do not consider attribute information and may result in low-quality privacy protection.
In this paper, we propose the notion of \emph{visibility}, which describes the degree that an adversary can infer the identity of the user by an observation. Then we present an anonymization method which considers not only location information but also users' attributes. We show several strategies for the anonymization process and evaluate them based on the experiments.

Combination Skyline Queries Reviewed

Xi Guo, Chuan Xiao, Yoshiharu Ishikawa

Transactions on Large-Scale Data- and Knwoledge-Centered Systems Vol. 6 page： 1-30 2012.9

Language：English Publishing type：Research paper (scientific journal)

Given a collection of data objects, the skyline problem is to select the objects which are not dominated by any others. In this paper, we propose a new variation of the skyline problem, called the combination skyline problem. The goal is to find the fixed-size combinations of objects which are skyline among all possible combinations. Our problem is technically challenging as traditional skyline approaches are inapplicable to handle a huge number of possible combinations. By indexing objects with an R-tree, our solution is based on object-selecting patterns that indicate the number of objects to be selected for each MBR. We develop two major pruning conditions to avoid unnecessary expansions and enumerations, as well as a technique to reduce space consumption on storing the skyline for each rule in the object-selecting pattern. The efficiency of the proposed algorithm is demonstrated by extensive experiments on both real and synthetic datasets.

DOI： 10.1007/978-3-642-34179-3_1

Efficient Error-tolerant Query Autocompletion Reviewed

Chuan Xiao, Jianbin Qin, Wei Wang, Yoshiharu Ishikawa, Koji Tsuda, Kunihiko Sadakane

Proceedings of the VLDB Endowment (PVLDB) Vol. 6 ( 6 ) page： 373-384 2013.4

Language：English Publishing type：Research paper (scientific journal)

Query autocompletion is an important feature saving users many keystrokes from typing the entire query. In this paper we study the problem of query autocompletion that tolerates errors in users' input using edit distance constraints. Previous approaches index data strings in a trie, and continuously maintain all the prefixes of data strings whose edit distance from the query are within the threshold. The major inherent problem is that the number of such prefixes is huge for the first few characters of the query and is exponential in the alphabet size. This results in slow query response even if the entire query approximately matches only few prefixes.
In this paper, we propose a novel neighborhood generation-based algorithm, IncNGTrie, which can achieve up to two orders of magnitude speedup over existing methods for the error-tolerant query autocompletion problem. Our proposed algorithm only maintains a small set of active nodes, thus saving both space and time to process the query. We also study efficient duplicate removal which is a core problem in fetching query answers. In addition, we propose optimization techniques to reduce our index size, as well as discus- sions on several extensions to our method. The efficiency of our method is demonstrated against existing methods through extensive experiments on real datasets.

Pattern Discovery in Data Streams under the Time Warping Distance Reviewed

Machiko Toyoda, Yasushi Sakurai, Yoshiharu Ishikawa

The VLDB Journal Vol. 6 ( 6 ) page： 295-318 2013.6

Language：English Publishing type：Research paper (scientific journal)

Subsequence matching is a basic problem in the field of data stream mining. In recent years, there has been significant research effort spent on efficiently finding subsequences similar to a query sequence. Another challenging issue in relation to subsequence matching is how we identify common local patterns when both sequences are evolving. This problem arises in trend detection, clustering, and outlier detection. Dynamic time warping (DTW) is often used for subsequence matching and is a powerful similarity measure. However, the straightforward method using DTW incurs a high computation cost for this problem. In this paper, we propose a one-pass algorithm, CrossMatch, that achieves the above goal. CrossMatch addresses two important challenges: (1) how can we identify common local patterns efficiently without any omission? (2) how can we find common local patterns in data stream processing? To tackle these challenges, CrossMatch incorporates three ideas: (1) a scoring function, which computes the DTW distance indirectly to reduce the computation cost, (2) a position matrix, which stores starting positions to keep track of common local patterns in a streaming fashion, and (3) a streaming algorithm, which identifies common local patterns efficiently and outputs them on the fly. We provide a theoretical analysis and prove that our algorithm does not sacrifice accuracy. Our experimental evaluation and case studies show that CrossMatch can incrementally discover common local patterns in data streams within constant time (per update) and space.

DOI： 10.1007/s00778-012-0289-3

Event Pattern Queries on Probabilistic Event Streams Reviewed

Sho Kato, Yoshiharu Ishikawa

DBSJ Journal Vol. 12 ( 1 ) page： 55-60 2013.6

Language：Japanese Publishing type：Research paper (scientific journal)

Complex event processing (CEP) is a task to detect high-level events from a large volume of stream data. In this paper, we focus on CEP for probabilistic event streams in which each event is assigned its occurrence probability. We propose two types of pattern query semantics to get a group of matches for a given regular expression pattern. A group of matches represents a semantic unit for considering high-level events.

Query Processing in Moving Robot Databases

Kento Sugiura, Arata Hayashi, Yoshiharu Ishikawa

Technical Report of IEICE Vol. 113 ( 150 ) page： 145-150 2013.7

Similarity Queries on Gaussian Distributions

Tingting Dong, Chuan Xiao, Yoshiharu Ishikawa

IPSJ SIG Technical Report Vol. 2013-DBS-157 ( 32 ) page： 1-6 2013.7

Processing Probabilistic Range Queries over Gaussian-based Uncertain Data Reviewed

Tingting Dong, Chuan Xiao, Xi Guo, Yoshiharu Ishikawa

Processing Probabilistic Range Queries over Gaussian-based Uncertain Data page： 410-428 2013.8

Language：English Publishing type：Research paper (scientific journal)

Probabilistic range query is an important type of query in the area of uncertain data management. A probabilistic range query returns all the objects within a specific range from the query object with a probability no less than a given threshold. In this paper we assume that each uncertain object stored in the databases is associated with a multi-dimensional Gaussian distribution, which describes the probability distribution that the object appears in the multi-dimensional space. A query object is either a certain object or an uncertain object modeled by a Gaussian distribution. We propose several filtering techniques and an R-tree-based index to efficiently support probabilistic range queries over Gaussian objects. Extensive experiments on real data demonstrate the efficiency of our proposed approach.

DOI： 10.1007/978-3-642-40235-7_24

曖昧な移動軌跡に対する範囲問合せ

早矢仕新, 杉浦健人, 董ていてい, 石川佳治

第12回情報科学技術フォーラム（FIT 2013）講演論文集 page： D-013 2013.9

オントロジーに基づくLBSN上でのイベント検出

稲葉鉄平, 高橋正和, 簗井美咲, 石川佳治

第12回情報科学技術フォーラム（FIT 2013）講演論文集 page： D-030 2013.9

Collocation Extraction Using a PMI-Based Association Measure for Dependency Tree Pattern Reviewed

Hiroki Takayama, Yoshihide Kato, Tomohiro Ohno, Shigeki Matsubara, Yoshiharu Ishikawa

Proceedings of the 10th International Symposium on Natural Language Processing (SNLP 2013) page： 136-141 2013.10

Language：English Publishing type：Research paper (scientific journal)

In this paper, we propose a method of automatically extracting collocations from a dependency treebank. This method obtains sequences of words connected with dependency relations by extracting tree patterns from a dependency treebank. For the tree patterns, the method applies an association measure which is based on pointwise mutual information(PMI) and selects tree patterns corresponding to collocations. Our method can obtain discontinuous collocations which are made up of three or more words. We conducted an experiment using ACL Anthology Corpus. The experimental result shows that this method is effective for extracting discontinuous collocations which consist of three or more words.

Clustering Editors of Wikipedia by Editor's Biases Reviewed

Akira Nakamura, Yu Suzuki, Yoshiharu Ishikawa

Proceedings of the 2013 IEEE/WIC/ACM International Conference on Web Intelligence (WI 2013) page： 351-358 2013.11

Language：English Publishing type：Research paper (scientific journal)

Wikipedia is an Internet encyclopedia where any user can edit articles. Because editors act on their own judgments, editors' biases are reflected in edit actions. When editors' biases are reflected in articles, the articles have low credibility. However, it is difficult for users to judge which parts in articles have biases. In this paper, we propose a method of clustering editors by editors' biases for the purpose that we distinct texts' biases by using editors' biases and aid users to judge the credibility of each description. If each text is distinguished such as by colors, users can utilize it for the judgments of the text credibility. Our system makes use of the relationships between editors: agreement and disagreement. We assume that editors leave texts written by editors that they agree with, and delete texts written by editors that they disagree with. In addition, we can consider that editors who agree with each other have similar biases, and editors who disagree with each other have different biases. Hence, the relationships between editors enable to classify editors by biases. In experimental evaluation, we verify that our proposed method is useful in clustering editors by biases. Additionally, we validate that considering the dependency between editors improves the clustering performance.

オントロジーを利用したLBSN基盤フレームワークの設計

稲葉鉄平, 簗井美咲, 高橋正和, 石川佳治

第6回データ工学と情報マネジメントに関するフォーラム（DEIM 2014） page： E4-5 2014.3

パーティクル表現を用いた曖昧位置情報に対する空間問合せ処理

早矢仕新, 杉浦健人, 董ていてい, 石川佳治

第6回データ工学と情報マネジメントに関するフォーラム（DEIM 2014） page： E4-6 2014.3

人気経路の推薦のための大規模移動軌跡データ処理

姜仁河, 杉山武至, 石川佳治

情報処理学会第76回全国大会講演論文集 page： 1N-3 2014.3

確率的ストリームにおけるグループを用いたパターン問合せ

杉浦健人, 早矢仕新, 石川佳治

情報処理学会第76回全国大会講演論文集 page： 3N-5 2014.3

Wikipedia のノートページにおける編集者の重要度算出手法

近藤弘隆, 鈴木優, 石川佳治

情報処理学会第76回全国大会講演論文集 page： 4M-9 2014.3

　 PREV - NEXT 　

<ISHIKAWA, Yoshiharu>

Papers - ISHIKAWA, Yoshiharu