Award type：Honored in official journal of a scientific society, scientific journal  Country：Japan

Award type：Honored in official journal of a scientific society, scientific journal  Country：Japan

Award type：Award from Japanese society, conference, symposium, etc.  Country：Japan

Award type：Award from Japanese society, conference, symposium, etc.  Country：Japan

Award type：Award from Japanese society, conference, symposium, etc.  Country：Japan

Language：English  

Signature files are known as promising facilities to speed up access to large information repositories in database and information retrieval systems. This paper presents a new signature file organization method, named Partitioned Frame-Sliced Signature File (P-FSSF), and studies its performance. P-FSSF incorporates both vertical and horizontal decomposition schemes to reduce page accesses required to look up signatures. In addition, P-FSSF is flexible enough to have its concrete organization tuned to real application environments. We develop formulas to estimate the retrieval cost of P-FSSF in the context of the general set-valued object retrieval. Also, formulas to tell the update and storage costs are derived. Then, the processing cost of P-FSSF is shown to be lower than the other existing signature file organizations in general. We also show that Partitioned Bit-Sliced Signature File (P-BSSF), which is a special case of P-FSSF, is appropriate organization in most probable cases through the study of the optimal parameter values for P-FSSF.

Language：English  

To integrate distributed heterogeneous information sources in networked environments, we need efficient facilities to access such information. In this paper, we propose a method called SignatureCache to enable clients to access distributed sources in an efficient manner. The method is based on signature files, a popular indexing method in text retrieval. In our framework, a mediator extracts textual information from each source and generates a signatur---a compact representation of the extracted information. Generated signatures are collected by the mediator and accumulated into a signature file. Each client of the mediator replicates a part of signatures in the signature file during query execution time. The cached signatures can be considered as a special kind of signature file, thus we can utilize them for efficient index lookup at later time. In query processing, we can make use of subsumption relationship between queries and the semantic descriptions for cached signatures to determine whether the required signature entries are locally available or not.

Authorship：Lead author   Language：English  

With the growth of digital libraries and electronic publishing, many structured document sources are appearing and their effective mediation is an important research topic. In this paper, we propose a wrapping architecture for externally maintained structured document sources. Our wrapping target is information retrieval systems (IRSs) that provide access to structured documents. We describe a wrapper construction method for such IRSs with limited functionality. The constructed wrapper enhances retrieval facilities of the underlying IRS and provides an object database view to the mediator. We focus on determining whether the underlying IRS can support a given query. Then we discuss some research issues related to our wrapping architecture.

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

Modern database systems have to support complex data objects, which appear in advanced data models such as object-oriented data models and nested relational data models. Set-valued objects are basic constructs to build complex structures in those models. Therefore, efficient processing of set-valued object retrieval (simply, set retrieval) is an important feature required of advanced database systems. Our previous work proposed a basic scheme to apply superimposed coded signature files to set retrieval and showed its potential advantages over the B-tree index based approach using a performance analysis model. Retrieval with signature files is always accompanied by mismatches called false drops, and proper control of the false drops is indispensable in the signature file design. This study intensively analyzes the false drops in set retrieval with signature files. First, schemes to use signature files are presented to process set retrieval involving "has-subset," "is-subset," "has-intersection," and "is-equal" predicates, and generic formulas estimating the false drops are derived. Then, three sets of concrete formulas are derived in three ways to estimate the false drops in the four types of set retrieval. Finally, their estimates are validated with computer simulations, and advantages and disadvantages of each set of the false drop estimation formulas are discussed. The analysis shows that proper choice of estimation formulas gives quite accurate estimates of the false drops in set retrieval with signature files.

Authorship：Lead author   Language：English  

Users often can not easily express their queries. For example, in a multimedia/image by content setting, the user might want photographs with sunsets; in current systems, like QBIC, the user has to give a sample query, andto specify the relative importance of color, shape and texture. Even worse, the user might want correlations between attributes, like, for example, in a traditional, medical record database, a medical researcher might wantto find "mildly overweight patients", where the implied query would be "weight/height ~ 4 lb/inch".

Our goal is to provide a user-friendly, but theoretically solid method, tohandle such queries. We allow the user to give several examples, and, optionally, their 'goodness' scores, and we propose a novel method to "guess" which attributes are important, which correlations are important, and withwhat weight.

Our contributions are twofold: (a) we formalize the problem as a minimization problem and show how to solve for the optimal solution, completely avoiding the ad-hoc heuristics of the past. (b) Moreover, we are the first that can handle 'diagonal' queries (like the 'overweight' query above). Experiments on synthetic and real datasets show that our method estimates quickly and accurately the 'hidden' distance function in the user's mind.

Authorship：Lead author   Language：English  

Because performance is a crucial issue in database systems, data caching techniques have been studied in database research field, especially in client-server databases and distributed databases. Recently, the idea of semantic caching has been proposed. The approach uses semantic information to describe cached data items so that it tries to exploit not only temporal locality but also semantic locality to improve query response time. In this paper, we propose linear constraint-based semantic caching as a new approach, we describe the semantic information about the cached relational tuples as compact constraint tuples. The focus in this paper is the representation method of cache information and the cache examination algorithm.

Language：English  

Integration of heterogeneous information sources has been one of important research issues in recent advanced application environments. Today, various types of information sources are available. Dissemination-based information delivery services that autonomously deliver information from the server sites to users are among the useful and promising information sources. In this paper, we present incorporation of dissemination-based information delivery into information integration environments. The integration here has two goals: (1) Users can utilize dissemination-based information services as other information sources such as databases and the Web. Namely, they can be sources of information integration. (2) Users can obtain integrated information through dissemination-based delivery. We explain this requirement can be met by a combination of an information integration engine and event-driven rule processing scheme. We also explain prototype system development.

Language：English  

With the recent and rapid advance of the Internet, management of structured documents such as XML documents and their databases has become more and more important. A number of query languages for XML documents have been proposed up to the present. Some of them enable tag-based powerful document structure manipulation. However, their contents processing capability is very limited. Here, the contents processing implies the similarity-based selection, ranking, summary generation, topic extraction, and so on, as well as simple string-based pattern matching. In this paper, we propose an extensible XML query language X2QL, which features inclusion of user-defined foreign functions to process document contents in the context of XML-QL-based document structure manipulation. This feature makes it possible to integrate application-oriented high-level contents processing facilities into querying documents. We also describe an implementation of an X2QL query processing systemon top of XSLT processors.

Authorship：Lead author   Language：English  

Recent progress of digital cartography and Internet technologies
enabled new types of services on the network such
as search engines that provide information within some specific
geographic areas and retrieval services which allow
map-oriented query interfaces. We call such services spatial
information sources. In this paper, we propose a framework
to integrate heterogeneous spatial information sources
to provide an integrated view to users. Our main focus is
heterogeneity of spatial information sources―since existing
spatial information sources differ in their contents and
query capabilities, integration of such sources requires an
appropriate framework to describe their contents and query
capabilities. In this paper, we show such a description
framework and illustrate query processing strategies that
utilize source descriptions of spatial information sources.

Language：English  

Integration of heterogeneous information sources has
been one of important data engineering research issues.
Various types of information sources are available today.
They include dissemination-based information sources,
which actively and autonomously deliver information
from server sites to users. We have been developing a
mediator/wrapper-based information integration system, in
which we employ ECA rules to enable users to define new
information delivery services integrating multiple existing
dissemination-based information sources. However, it is
not easy for users to directly specify ECA rules and to verify
them. In this paper, we propose a scheme to specify new
information delivery services using the framework of the
relational algebra. We discuss some important properties
of the specification, and show how we can derive ECA rules
to implement the delivery services.

Language：English  

XML has attracted a great deal of attention as standard data exchange format, and XML representing geographic information such as G-XML has been developed. In near future, geographic data written in XML will be exchanged through the Internet. Therefore, it will become a very important issue to efficiently query geographic data in XML. To query geographic data in XML, spatial operations such as distance calculation and spatial containment test need be provided in query languages. However, in general, XML query languages do not support such spatial operations. This paper illustrates G-XML data can be queried via eXtensible XML Query Language X2QL, which has been developed by our research group. X2QL features inclusion of user-defined foreign functions to introduce application-oriented processing capability. Thus, we can utilize various spatial operations in X²QL as appropriate foreign functions. This paper also describes the development of a prototpye X2QL query processing system.

Authorship：Lead author   Language：English  

With the rapid development of on-line information services, information technologies for on-line information processing have been receiving much attention recently. Clustering plays important roles in various on-line applications such as extraction of useful information from news feeding services and selection of relevant documents from the incoming scientific articles in digital libraries. In on-line environments, users generally have interests on newer documents than older ones and have no interests on obsolete old documents. Based on this observation, we propose an on-line document clustering method F2ICM ( Forgetting-Factor-based Incremental Clustering Method) that incorporates the notion of a forgetting factor to calculate document similarities. The idea is that every document gradually losses its weight (or memory) as time passes according to this factor. Since F2ICM generates clusters using a document similarity measure based on the forgetting factor, newer documents have much effects on the resulting cluster structure than older ones. In this paper, we present the fundamental idea of the F2ICM method and describe its details such as the similarity measure and the clustering algorithm. Also, we show an efficient incremental statistics maintenance method of F2ICM which is indispensable for on-line dynamic environments. Keywords: clustering, on-line information processing, incremental algorithms, forgetting factors

Authorship：Lead author   Language：English  

Rapid development of information technology such as mobile terminals and GPS systems enabled information services that provide location-oriented information based on users' positions. In this paper, we propose an approach for the modeling of information integration applications that incorporate spatial information sources in addition to conventional information sources to provide appropriate location-oriented information to users. First, we present our approach to the modeling of spatial information sources based on the source description framework. It provides a way to represent the content and the query capability of a spatial information source in a descriptive manner. Then we show a query processing scheme that finds a combination of information sources to respond to given queries and to evaluate them efficiently.

Language：English  

The integration of heterogeneous information sources is an important data engineering research issue. Various types of information sources are available today. They include dissemination-based information sources, which actively and autonomously deliver information from servers to users. We are developing a mediator/wrapper-based information integration system in which we employ ECA rules to define new information delivery channels, integrating multiple existing dissemination-based information sources. ECA rules in this system are derived from integration requirement specifications based on relational algebra provided by users. Dissemination-based information sources usually have data arrival properties, such as an information delivery schedule. Using the data arrival properties of underlying information sources, the system can derive more appropriate ECA rules and check the consistency of requirements more accurately. This paper proposes an extended scheme to process information integration requirements using source data arrival properties of dissemination-based information sources.

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

Integration of heterogeneous information sources has been one of important research in recent advanced network environments. In these days, various types of information sources are available. Dissemination-baesd information sources that actively deliver information from server sites to users are important information sources. In our research group, a dissemination-based information integration system that uses ECA rules to process dissemination-based information sources has been built to incorporate delivered information in a flexible manner. However, the users of the system have to specify and verify ECA rules by themselves. In this paper, we present a framework to specify dissemination services declaratively, and to derive ECA rules automatically.

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

XML views over RDBs and to allow users to access data with XML query languages such as XQuery.The query processing is done effciently by making the best of the querying power of RDBMSs.Namely,XML queries are translated into SQL queries and tagging operations, which are processed by the RDBMSs and, middleware,respectively.In some XML query languages including XQuery,use of user-de ?ned foreign functions is enabled or planned as an extension feature to cope with domain dependent semantics.Foreign functions are de ?ned for XML fragments,and their implementations are often given by codes in a general programming language.The existing query processing schemes on XML views do not consider cases where foreign functions are included in XML queries.In this paper,we propose extended schemes to process XML queries in such cases.In the proposed schemes,the middleware takes care of processing foreign functions as well as tagging operations.Therefore,the proposed schemes are applicable to XML views on commonly available RDBMSs.Three types of query processing schemes are proposed,and their performance is studied with experiments.

Authorship：Lead author   Language：English  

Based on the recent progress of digital cartography, global positioning systems (GPSs), and hand-held devices, there are growing needs of technology that provides neighborhood information to moving objects according to their locations and trajectories. In this paper, we propose spatial query generation models that take account of the current position and the past/future trajectories of a moving object to provide appropriate neighborhood information to it. For this purpose, we introduce an influence model of trajectory points and derive neighborhood query generation models using adaptive ellipsoid distances. We describe query processing strategies for these query generation models and show incremental query update procedures to support continual query facilities with low processing cost. Finally, we present experimental results to show the effectiveness of our approach.

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

Authorship：Lead author   Language：English  

The widespreading of XML as a content-description language
on the Web requires advanced processing and
management techniques for huge XML databases. XPath
is a standard language for extracting the specified elements
from XML documents, and its efficient support
is one of the key issues in the current XML database
technology. In this paper, we propose an XPath query
transformation method for the efficient query processing.
It transforms top-down, navigation-based XPath queries
into equivalent bottom-up query plans by using schema
information. Based on this technique, we can achieve efficient
set-oriented processing of XPath queries with the
support of index mechanisms.

Language：English  

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

Authorship：Lead author   Language：English  

With the increased popularity of XML, XML publishing of RDBs has been attracting a lot of research interests. One of typical approaches is to use a middleware system to render XML views over RDBs and to allow users to access data with XML query languages such as XQuery. The query processing is done efficiently by making the best of the querying power of RDBMSs. Namely, XML queries are translated into SQL queries and tagging operations, which are processed by the RDBMSs and middleware, respectively. In some XML query languages including XQuery, use of user-defined foreign functions is enabled or planned as an extension feature to cope with domain dependent semantics. Foreign functions are defined for XML fragments, and their implementations are often given by codes in a general programming language. The existing query processing schemes on XML views do not consider cases where foreign functions are included in XML queries. In this paper, we propose extended schemes to process XML queries in such cases. In the proposed schemes, the middleware takes care of processing foreign functions as well as tagging operations. Therefore, the proposed schemes are applicable to XML views on commonly available RDBMSs. Three types of query processing schemes are proposed, and their performance is studied with experiments.

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

Peer-to-peer (P2P) technology has attracted a lot of attention in recent years. Efficient object retrieval is an important research issue in P2P environments, especially in those without centralized global indices. Although a number of hash-based basic object retrieval schemes are known to alleviate the problem, they cannot provide flexible feature-based object search. In this paper, we propose a novel object retrieval method using distributed frame sliced signatures, and evaluate its effectiveness with simulation experiments.

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

With the recent progress of spatial information technologies
and mobile computing technologies, spatio-temporal databases
which store information on moving objects including vehicles
and mobile users have gained a lot of research interests. In this
paper, we propose an algorithm to extract mobility statistics
from indexed spatio-temporal datasets for the interactive
analysis of huge collections of moving object trajectories. We
focus on a mobility statistics value called the Markov transition
probability, which is based on a cell-based organization of a
target space and the Markov chain model. The proposed
algorithm efficiently computes the specified Markov transition probabilities with the help of a spatial index R-tree. We reduce
the statistics computation task to a kind of constraint
satisfaction problem that uses a spatial index, and utilize
internal representation of R-tree in an efficient manner.

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

With the recent progress of spatial information technologies and mobile computing technologies, spatio-temporal databases which store information on moving objects including vehicles and mobile users have gained a lot of research interests. Here we focus on a mobility statistics value called the Markov transition probability, which is based on a cell-based organization of a target space and the Markov chain model. We have proposed an algorithm to extract mobility statistics from indexed spatio-temporal datasets for the interactive analysis of huge collections of moving object trajectories. The proposed algorithm efficiently computes the specified Markov transition probabilities with the help of a spatial index R-tree. In this paper, we evaluate the effectiveness of proposed method based on an experiment.

Authorship：Lead author   Language：Japanese   Publishing type：Research paper (scientific journal)  

Clustering plays important roles in various on-line
applications such as extraction of useful information from
news feeding services and selection of relevant documents
from incoming scientific articles in digital libraries. In
on-line environments, users generally have interests on
newer documents than older ones and have no interests
on obsolete old documents.
Based on this observation, we have proposed an on-line
document clustering method that incorporates the notion
of a forgetting factor to calculate document similarities.
The idea is that every document gradually losses its
weight (or memory) as time passes according to this factor.
Since our method generates clusters using a document
similarity measure based on the forgetting factor, newer
documents have much effect on the resulting cluster
structure than older ones. In this paper, we extend our
clustering method by using the K-means clustering
algorithm as its basis. The new algorithm has clear
semantics and supports incremental updates of cluster
structures.

Authorship：Lead author   Language：English  

Rapid development and ongoing research activities on
mobile devices, digital cartography, and global positioning
systems (GPSs) have brought us a new type of software
service―location-based services for moving objects (such
as people with mobile devices and vehicles with car navigation
systems). Realization of location-based services requires
new technologies to provide appropriate neighborhood
information to moving objects. A general approach
to providing neighborhood information to moving objects
is to retrieve objects in the neighborhood of a moving object
with a spatial query that uses the traditional Euclidean
distance. However, if we know the destination and the estimated
route of a moving object, we would be able to provide
more appropriate information to the object. Based on
this idea, we have developed adaptive spatial query generation
models that take the trajectory of a moving object into
consideration to retrieve desired information. In this paper,
we describe the design and implementation of the neighborhood
information retrieval system based on the models and
evaluate its effectiveness with experiments.

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

The recent development of network technology has enabled us to access various information sources easily, and their integration has been studied intensively by the data engineering research community. Although technological advancement has made it possible to integrate existing heterogeneous information sources, we still have to deal with information sources of a new kind--dissemination-based information sources. They actively and autonomously deliver information from server sites to users. Integration of dissemination-based information sources is one of the popular research topics. We have been developing an information integration system in which we employ ECA rules to enable users to define new information delivery services integrating multiple existing dissemination-based information sources. However, it is not easy for users to directly specify ECA rules and to verify them. In this paper, we propose a scheme to specify new dissemination-based information delivery services using the framework of relational algebra. We discuss some important properties of the specification, and show how we can derive ECA rules to implement the services.

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

Language：English  

Peer-to-Peer (P2P) technology has attracted a lot of attention in recent years. Efficient object search is an important research issue in P2P environments, especially in those without centralized global indexes. Although a number of hash-based basic object search schemes are known to alleviate the problem, they cannot provide flexible feature-based object searches. This paper proposes a novel object search method using distributed frame sliced signatures, and looks at an appropriate choice of parameters to adapt the configuration to the object search and registration workload. It shows object search and registration schemes that take into account the number of messages and response times. Effectiveness of these schemes is evaluated through simulation experiments.

Authorship：Lead author   Language：English  

With the recent progress of spatial information
technologies and mobile computing technologies,
spatio-temporal databases that store information of
moving objects have gained a lot of research interests.
In this paper, we propose an algorithm
to extract mobility statistics from indexed spatiotemporal
datasets for interactive analysis of huge
collections of moving object trajectories. We focus
on mobility statistics called the Markov transition
probability, which is based on a cell-based organization
of a target space and the Markov chain model.
The algorithm computes the specified Markov transition
probabilities efficiently with the help of an Rtree
spatial index. It reduces the statistics computation
task to a kind of constraint satisfaction problem
and uses internal structure of an R-tree in an efficient
manner.

Authorship：Lead author   Language：Japanese   Publishing type：Research paper (scientific journal)  

In information systems which provide XML documents,
RDBs are often used for data storage and XML
generation. XML documents in these systems can be
seen as database views. In this paper, we assume
an environment such that a client can define XML
views using XSLT over a remote relational database
and XML views are materialized on the client. We
propose an efficient method for updating materialized
XML views in an incremental manner. In our
approach, the view management system analyzes a
database schema and XSLT view definitions, and generates
update scripts. When a new update occurs, the
scripts are executed for XML view updates.

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

Recently web mining that tries to find relevant information
from the vast amount of web pages has attracted
a lot of research interests. Besides, it is becoming
an important task to provide information related
to a user-specified geographic area. In this paper,
we propose a method to extract spatial information
hub pages. A spatial information hub is a webpage
which is related to a specified geographic area
and has much local information or many hyperlinks
to local web pages. We employ geographic information
to create spatial nodes and spatial links, and then conduct
link analysis based on the extended link structure.

Language：English  

Recently, web mining that tries to find useful knowledge from the vast amount of web pages has attracted a lot of research interests. Besides, it is becoming an essential task to provide web pages related to a user-specified geographic area. In this paper, we propose an approach to extract spatial information hubs from the web. A spatial information hub is a web page which is related to a specified geographic area and has much local information and/or many hyperlinks to local web pages. In the traditional approach of web link analysis, the importance and quality of pages are judged only by their contents and hyperlink structures. However, we take their geographic localities into consideration. In our approach, we first extract geographic information from web pages to create spatial nodes and spatial links, then conduct a link analysis based on the extended link structures. We also show our approach works well based on the experiments.

Language：English  

In this paper, we propose a method called LocalRank to rank web pages by integrating the web and a user database containing information on a specific geographical area. LocalRank is a rank value for a web page to assess its relevance degree to database entries considering geographical locality and its popularity on a local web space. In our method, we first construct a linked graph structure using entries contained in the database. The nodes of this graph consist of database entries and their related web pages. The edges in the graph are composed of semantic links including geographical links between these nodes, in addition to conventional hyperlinks. Then a link analysis is performed to compute a LocalRank value for each node. LocalRank can represent user's interest since this graph effectively integrates the web and the user database. Our experimental results for a local restaurant database shows that local web pages related to the database entries are highly ranked based on our method.

Language：English  

Document clustering has been used as a core technique in managing vast amount of data and providing needed information. In on-line environments, generally new information gains more interests than old one. Traditional clustering focuses on grouping similar documents into clusters by treating each document with equal weight. We proposed a novelty-based incremental clustering method for on-line documents that has biases on recent documents. In the clustering method, the notion of `novelty' is incorporated into a similarity function and a clustering method, a variant of the K-means method, is proposed. We examine the efficiency and behaviors of the method by experiments.

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

For the accumulation and analysis of a large collection
of moving object trajectories, our group focuses
on the research on a mobility histogram to summarize
moving object trajectories. The histogram is based on
a mobility statistics model called the Markov chain
model. We provide a mobility histogram datacubelike
logical representation and support an OLAP-style
analysis. As its physical structure, we introduce a tree
structure that efficiently works in a limited memory
space. We describe the details of the method and evaluate
its performance based on experiments.

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

Clustering has been widely used as a fundamental
method in many areas such as characterization
and classification. Various clustering researches have
been conducted since decades ago. In previous papers,
we presented a novelty-based incremental document
clustering method which considers novelty of
on-line documents in its similarity measure and performs
clustering based on an extended algorithm of
the K-means method. This paper further examines the
performance of the incremental and non-incremental
processing of the clustering method and effect of parameter
values on the method by showing the experimental
results.

Authorship：Lead author   Language：English  

With the recent progress of spatial information technologies and communication technologies, it has become easier to track positions of a large number of moving objects in real-time. Mobility statistics plays an important role in the interactive analysis of a large collection of moving objects trajectories and its use of movement pattern prediction. The development of an effective mobility statistics measure and its efficient computation method are critical issues. Thus, we propose an approach for constructing a mobility histogram to summarize a number of moving object trajectories. The histogram is based on a mobility statistics model called the Markov chain model. To facilitate an interactive analysis performed by a user, we provide a mobility histogram data cube-like logical representation and support an OLAP-style analysis. Since trajectory data is often received continuously as a trajectory stream, we have to support dynamic histogram construction and maintenance. We introduce a tree structure as the physical representation of a histogram and present histogram construction and maintenance methods that work efficiently within the given upperbound size. We evaluate the performance and the precision of the proposed method by means of experiments.

Authorship：Lead author   Language：Japanese   Publishing type：Research paper (scientific journal)  

Due to the progress of GPS and communication technologies, it has become easier to track positions of moving objects. By monitoring and aggregating the movements of a large number of objects in real-time, we can analyze and estimate their behaviors effectively. For this purpose, we propose an approach to constructing a mobility histogram for the summarization of a large volume of moving object trajectories. The histogram is based on a mobility statistics model called the Markov chain model. We provide a mobility histogram data cube-like logical representation and support an OLAP-style analysis. We introduce a tree structure as its physical representation and present approximated histogram construction methods for the reduction of the storage size. Since trajectory data is often received continuously as a trajectory stream, we enable efficient histogram construction for the real-time processing. We evaluate the performance and the precision of the proposed methods based on the experiments.

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

On the Internet, delivery of a large amount of documents such as news articles is continually performed everyday. In this paper, we describe an information visualization system T-Scroll to show the transition of topics contaned in such documents to the user and to provide an overview of their trends. The system is built on a clustering system for time-sereis of documents and presents relationships between clusters like a scroll. This paper describes the idea, the functions, and the implementation of the system.

Language：English  

In recent years, the research of record extraction from large document data is becoming popular. However there still exist some problems in record extraction. 1) when large document data is used for the target of information extraction, the process usually becomes very expensive. 2) it is also likely that extracted records may not pertain to the user's interest on the aspect of the topic. To address these problems, in this paper we propose a method to efficiently extract those records whose topics agree with the user's interest. To improve the efficiency of the information extraction system, our method identifies documents from which useful records are probably extracted. We make use of user feedback on extraction results to find topic-related documents and records. Our experiments show that our system achieves high extraction accuracy across different extraction targets.

Authorship：Lead author   Language：English  

On the Internet, a large number of documents such as news articles and online journals are delivered everyday. We often have to review major topics and topic transitions from a large time-series of documents, but it requires much time and effort to browse and analyze the target documents. We have therefore developed an information visualization system called T-Scroll (Trend/Topic-Scroll) to visualize the transition of topics extracted from those documents. The system takes periodical outputs of the underlying clustering system for a time-series of documents then visualizes the relationships between clusters as a scroll. Using its interaction facility, users can grasp the topic transitions and the details of topics for the target time period. This paper describes the idea, the functions, the implementation, and the evaluation of the T-Scroll system.

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

In recent years, the research on record extraction from a large number of text documents is becoming popular. However, there still exist some problems in record extraction. 1) When a large number of documents are used for the target of information extraction, the process usually becomes very time-consuming. 2) It is also likely that extracted records may not pertain to the user's interest on the aspect of the topic. To address these problems, in this paper we propose a method for efficiently extracting those records whose topics are relevant to the user's interest. To improve the efficiency of the information extraction system, our method identifies documents from which useful records are probably extracted. Those selected documents are first processed in order to reduce processing cost. Moreover, from these documents user-desired records are apt to be extracted so that high extraction accuracy is obtained. Our experiments show that our system reduces the processing cost with achieving high extraction accuracy.

Authorship：Lead author   Language：Japanese   Publishing type：Research paper (scientific journal)  

In sensor environments and mobile robot applications, we often find the situation in which the location of an object is imprecise due to measurement errors and/or object movements. In this paper, we present an approach for processing spatial queries when the location of a query object is specified by a probabilistic density function based on the Gaussian distribution.

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

On the Internet, a large number of documents such as news articles and online journals are delivered everyday. Documents continually delivered with timestamps such as issue dates are called a time-series of documents. We often need to review major topics and trends from a large time-series of documents, but it requires much time and effort to browse and analyze the target documents. We have therefore developed an information visualization system called T-Scroll (Trend/Topic-Scroll) to display the overall trends extracted from those documents. The system takes periodical outputs of the underlying clustering system for a time-series of documents then visualizes the relationships between clusters as a scroll. Using its interaction facility, users can grasp the trends and the details of the topics contained in the documents. This paper describes the idea, the functions, the implementation, and the evaluation of the T-Scroll system.

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

In this paper, we describe a document clustering method called novelty-based document clustering. This method clusters documents based on similarity and novelty. The method assigns higher weights to recent documents than old ones and generates clusters with the focus on recent topics. The similarity function is derived probabilistically, extending the conventional cosine measure of the vector space model by incorporating a document forgetting model to produce novelty-based clusters. The clustering procedure is a variation of the K-means method. An additional feature of our clustering method is an incremental update facility, which is applied when new documents are incorporated into a document repository. Performance of the clustering method is examined through experiments. Experimental results show the efficiency and effectiveness of our method.

Language：English  

Information exchanges in P2P networks have become very popular in recent years. However, tracing how data circulates between peers and how data modifications are performed during the circulation before reaching the destination are not easy because data replications and modifications are performed independently by peers. This creates a lack of reliability among the records exchanged. To provide reliable and flexible information exchange facilities in P2P networks, we propose a framework for a record exchange system based on database technologies. The system consists of three layers: a user layer, a logical layer and a physical layer. Its tracing operations are executed as distributed recursive queries among cooperating peers in a P2P network. This paper describes the concept and overviews the framework.

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

In recent years, there is an increasing need to monitor k nearest neighbor (k-NN) in a road network. There are existing solutions on either monitoring k-NN objects from a single query point over a road network, or computing the snapshot k-NN objects over a road network to minimize an aggregate distance function with respect to multiple query points. In this paper, we study a new problem that is to monitor k-NN objects over a road network from multiple query points to minimize an aggregate distance function with respect to the multiple query points. We call it a continuous aggregate k-NN (CANN) query. We propose a new approach that can significantly reduce the cost of computing network distances when monitoring aggregate k-NN objects on road networks. We conducted extensive experimental studies and confirmed the fficiency of our algorithms.

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

In recent years, peer-to-peer (P2P) technologies are used for flexible and scalable information exchange in the Internet, but there exist problems to be solved for reliable information exchange. It is important to trace how data circulates between peers and how data modifications are performed during the circulation before reaching the destination for enhancing the reliability of exchanged information. However, such lineage tracing is not easy in current P2P networks, since data replications and modifications are performed independently by autonomous peers---this creates a lack of reliability among the records exchanged. In this paper, we propose a framework for traceable record exchange in a P2P network. By managing historical information in distributed peers, we make the modification and exchange histories of records traceable. One of the features of our work is that the database technologies are utilized for realizing the framework. Histories are maintained in a relational database in each peer, and tracing queries are written in the datalog query language and executed in a P2P network by cooperating peers. This paper describes the concept of the framework and overviews the approach to query processing.

Language：English  

Document clustering methods for time-series documents produce a sequence of snapshots of clustering over time. Analyzing the contents (topics) and trends in a long sequence of clustering snapshots is hard and requires efforts since there are too many number of clusters; a user may need to access every cluster or read every document contained in each cluster. In this paper, we propose a framework to find clusters of user interest and change patterns called transition patterns involving the clusters. A cluster in a clustering result may persist in another cluster, branch into more than one cluster, merge with other clusters to form one cluster, or disappear in the adjacent clustering result. This research aims at providing users facilities to retrieve specific transition patterns in the clustering results. For this purpose, we propose a query language for time-series document clustering results and an approach to query processing. The first experimental results on TDT2 corpus clustering results are presented.

Authorship：Lead author   Language：English  

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

A document clusteringmethod for time series documents produces a sequence of clustering results over time. Analyzing the contents and trends in a long sequence of clustering results is a hard and tedious task since there are too many number of clusters. In this paper, we propose a framework to find clusters of users' topics of interest and evolution patterns called transition patterns involving
the topics. A cluster in a clustering result may continue to appear in or move to another cluster, branch into more than one cluster, merge with other clusters to form one cluster, or disappear in the adjacent clustering result. This research aims at providing users facilities to retrieve specific transition patterns in the clustering results. For this purpose, we propose a query language for time series document clustering results and an approach to query processing. The first experimental results on TDT2 corpus clustering results are presented.

Authorship：Lead author   Language：English  

In sensor environments and moving robot applications, the position of an object is often known imprecisely because of measurement error and/or movement of the object. In this paper, we present query processing methods for spatial databases in which the position of the query object is imprecisely specified by a probability density function based on a Gaussian distribution. We define the notion of a {\em probabilistic range query\/} by extending the traditional notion of a spatial range query, then present three strategies for query processing. Since the qualification probability evaluation of target objects requires numerical integration by a method such as the Monte Carlo method, reduction of the number of candidate objects that should be evaluated has a large impact on query performance. We compare three strategies and their combinations in terms of the experiments and evaluate their effectiveness.

Language：English  

In recent years, data provenance or lineage tracing has become an acute issue in the database research. Our target is the data provenance issue in peer-to-peer (P2P) networks where duplicates and modifications of data occur independently in autonomous peers. To ensure reliability among the exchanged data in P2P networks, we have proposed a reliable record exchange framework with tracing facilities based on database technologies in [5,6]. The framework is based on the "pay-as-you-go" approach in which the system maintains the minimum amount of information for tracing with low maintenance cost and a user pays the cost when he or she issues a tracing query to the system. This paper focuses on its two alternative query processing strategies and compare their characteristics according to the performance.

Language：English  

A nearest neighbor query is an important notion in spatial databases and moving object databases. In the emerging application fields of moving object technologies, such as mobile sensors and mobile robotics, the location of an object is often imprecise due to noise and estimation errors. We propose techniques for processing a nearest neighbor query when the location of the query object is specified by an imprecise Gaussian distribution. First, we consider two query processing strategies for pruning candidate objects, which can reduce the number of objects that require numerical integration for computing the qualification probabilities. In addition, we consider a hybrid approach that combines the two strategies. The performance of the proposed methods is evaluated using test data.

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

To assure the reliability of exchanged data in peer-to-peer (P2P) networks, we are developing PIREX system, a P2P record exchange system that supports trace facilities. In this paper, we present the feature of its event-driven queries. Using event-driven queries, we can monitor updates and exchanges of information without heavy network load. We discuss the outline of the feature and implementation ideas.

Language：English  

Keyword search in relational databases has recently emerged
as a new research topic. As a search result is often assembled from multiple relational tables, existing IR-style ranking strategies can not be applied directly. In this paper, we propose a novel IR ranking strategy considering query semantics for eective keyword search. The experimental results on a large-scale real database emonstrate that our method results in signicant improvement in terms of retrieval eectiveness as compared to previous ranking strategies.

Language：English  

Due to the recent development of mobile computing and communication network technologies, information services for mobile phone users and car navigation systems have becomeof
some importance. Since these mobile devices have limited display sizes, we often need to select carefully the appropriate information to be presented to the user. However,
it is not easy to select the "appropriate" information because users have different contexts and preferences.
In this paper, we present an approach to recommending items such as restaurants to a mobile user taking into account his current location and preferences. In our framework,
a user initially provides a profile, which records preferences as relative orders within predefined categories such as food types and prices. We then select items to be recommended
from the database based on the user's profile as well as the current location. To select good items, we extend the notion of spatial skyline queries to incorporate not
only distance information but also categorical preference information.
Based on the proposed approach, a prototype system has been implemented in a small mobile PC containing a small embedded RDBMS. The facilities of the RDBMS, such as
spatial indexes, were used to process our skyline queries effectively.

Authorship：Lead author   Language：Japanese  

Language：English  

Keyword search in relational databases has been widely studied in recent years. Most of the previous studies focus on how to answer an instant keyword query. In this paper, we focus on how to find the top-k answers in relational databases for continuous keyword queries efficiently. As answering a keyword query involves a large number of join operations between relations, reevaluating the keyword query when the database is updated is rather expensive. We propose a method to compute a range for the future relevance score of query answers. For each keyword query, our method computes a state of the query evaluation process, which only contains a small amount of data and can be used to maintain top-k answers when the database is continually growing. The experimental results show that our method can be used to solve the problem of responding to continuous keyword searches for a relational database that is updated frequently.

Language：English  

Materialized views which are derived from base relations and stored in the database are often used to speed up query processing. In this paper, we leverage them in a traceable peer-to-peer (P2P) record exchange framework which was proposed to ensure reliability among the exchanged data in P2P networks where duplicates and modifications of data occur independently in autonomous peers. In our proposed framework, the provenance/lineage of the exchanged data can be available by issuing tracing queries. Processing for tracing queries was based on the "pay-as-you-go" approach. The framework can achieve low maintenance cost since each peer only maintains minimum amount of information for tracing. However, the user must pay relatively high query processing cost when he or she issues a query. We consider that the use of materialized views allows more efficient query execution plans. In this paper, we focus on how to incorporate query processing based on materialized views in our framework.

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

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

A nearest neighbor query is an important notion in location-based applications such as mobile robotics and mobile sensor networks. In these application fields, query processing methods considering impreciseness are required because obtained location information of the query object is usually imprecise due to such as control noise and measurement errors. In this paper, we propose techniques for processing a nearest neighbor query when the location of the query object is specified by an imprecise Gaussian distribution. Moreover, we compare the performance of the proposed methods by experiments.

Language：English  

Traditional location-based services recommend nearest objects to the user by considering their spatial proximity. However, an object not only has its distance but also has its direction which originates from the user to it. In this paper, we study direction-based spatial skyline queries (DSS queries) which retrieve nearest objects around the user from different directions. The closer object is better than or dominates the further object if they are in the same direction. The objects that cannot be dominated by any other object are included in the direction-based spatial skyline (DSS). We propose algorithms to answer snapshot queries which find objects on the DSS according to the user's current position. We also develop algorithms to support continuous queries which retrieve objects on the DSS while the user is moving linearly. Extensive experiments verify the performance of our proposed algorithms using both real and synthetic datasets.

Language：English  

Materialized views which are derived from base relations and stored in the database are often used to speed up query processing. In this paper, we leverage them in a traceable peer-to-peer (P2P) record exchange framework which was proposed to ensure reliability among the exchanged data in P2P networks where duplicates and modifications of data occur independently in autonomous peers. In our proposed framework, the provenance/lineage of the exchanged data can be available by issuing tracing queries. Processing for tracing queries was based on the "pay-as-you-go" approach. The framework can achieve low maintenance cost since each peer only maintains minimum amount of information for tracing. However, the user must pay relatively high query processing cost when he or she issues a query. We consider that the use of materialized views allows more efficient query execution plans. In this paper, we focus on how to incorporate query processing based on materialized views in our framework.

DOI： 10.1007/978-3-642-16720-1_25

Language：English  

Keyword search in relational databases has been widely studied in recent years. Most of the previous studies focus on how to answer an instant keyword query. In this paper, we focus on how to find the top-k answers in relational databases for continuous keyword queries efficiently. As answering a keyword query involves a large number of join operations between relations, reevaluating the keyword query when the database is updated is rather expensive. We propose a method to compute a range for the future relevance score of query answers. For each keyword query, our method computes a state of the query evaluation process, which only contains a small amount of data and can be used to maintain top-k answers when the database is continually growing. The experimental results show that our method can be used to solve the problem of responding to continuous keyword searches for a relational database that is updated frequently.

DOI： 10.1007/978-3-642-14246-8_71

Language：English  

Due to the growing use of mobile devices, location-based services have become popular. A location service often requires the user's exact location to provide appropriate services and this brings the risk of threats to privacy. In this paper, we propose an anonymization method for users of location-based services in mobile environments.

The anonymization approach is based on the well-known k-anonymity concept, but has additional features. We consider the situation that a mobile service (e.g., mobile advertisement) utilizes mobile users' profiles for its service. Since a profile contains privacy information such as the age and address of the user, the use of profile information brings another kind of privacy threat.

The anonymization method proposed in this paper considers not only location information but also privacy-related attributes in the user's profile. The location anonymizer, a trusted third-party placed between users and mobile application services, anonymizes the location and profile attributes based on the request. We define a similarity measure between mobile users for anonymization purposes. The similarity is used for related users in terms of their locations and profile attributes. We present the concept behind our method and the anonymization algorithm, and then show some experimental results.

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

P2P technologies are drawing increasing attention nowadays, and have been widely deployed on the Internet for various purposes. Unlike the traditional client-server architecture, a P2P network allows all computers to communicate and share resources as equals and does not depend on a central server for control. In such an environment, tracing how data is copied between peers and how data modifications are performed are not easy because data replications and modifications are performed independently by autonomous peers. This creates inconsistencies in exchanged information and results in a lack of trustworthiness. To provide reliable and flexible information exchange facility in P2P networks, we have proposed a framework for enabling traceable record exchange. In this framework, a computer can exchange structured records with a predefined schema with other peers. The framework supports a tracing facility to query the lineage of the records obtained. A tracing query is described in Datalog and executed as a recursive query among cooperating peers in a P2P network. In the query execution process, the exchange and modification histories of the queried records are collected dynamically from relevant peers.
In this paper, we focus on how to enhance the traceable P2P record exchange framework using materialized views. First, we discuss how to construct materialized views in our framework. Then we present methods for reducing query processing cost and providing fault tolerance using the materialized views.

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

We define and solve the problem of 'cross-similarity' in data streams. Given multiple data streams, our goal is to find partial similarity between them. To achieve the above goal, we exploit the well-known Dynamic Time Warping (DTW) distance. We present a one-pass algorithm. Our algorithm is strictly based on DTW and continuously works in a streaming fashion. Instead of straightforwardly using DTW, our algorithm achieves a great resource reduction in terms of time and space. We provide a theoretical analysis and prove that our algorithm does not sacrifice accuracy. Our experimental evaluation shows that CrossMatch can incrementally capture cross-similarity, efficiently and effectively.

Language：English  

Multi-objective optimization problem finds out optimal objects w.r.t. several objectives rather than a single objective. We propose a new problem called a multi-objective optimal combination problem (MOC problem) which finds out object combinations w.r.t. multiple objectives. A combination dominates another combination if it is not worse than anther one in all attributes and better than another one in one attribute at least. The combinations, which cannot be dominated by any other combinations, are optimal. We propose an efficient algorithm to find out optimal combinations by reducing the search space with a lower bound reduction method and an upper bound reduction method based on the R-tree index. We implemented the proposed algorithm and conducted experiments on synthetic data sets.

DOI： 10.1007/978-3-642-23088-2_4

Language：English  

In the research area of spatial databases, query processing based on uncertain location information has become an important research topic. In this paper, we propose an index structure for the case that the locations of a query object and target objects are imprecise and specified by Gaussian distributions with different parameters. The index structure efficiently supports probabilistic spatial range queries, which is an enhanced version of traditional spatial range queries, by considering the properties of Gaussian distributions. We implement the proposed index structure using GiST, a generalized index structure, and we evaluate its performance based on the experiments.

Language：English  

P2P technologies are getting more and more attention lately. However, unlike the traditional client-server architecture, a P2P network allows all computers to communicate and share resources as equals without central server control. This causes inconsistency in exchanged information and results in lack of trustworthiness. To provide trustful and flexible information exchange facility in P2P networks, we proposed a traceable P2P record exchange framework. In this framework, a peer can exchange structured records with a predefined schema among other peers. The framework supports a tracing facility to query the lineage of the obtained records based on database technologies. A tracing query is described in Datalog and executed as a recursive query among cooperating peers in a P2P network. In this paper, we focus on analyzing and verifying the traceable P2P record exchange framework based on simulation experiments in three different example P2P networks.

DOI： 10.1007/978-3-642-22947-3_5

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

Location-based recommendation services recommend objects to the user based on the user's preferences. In general, the nearest objects are good choices considering their spatial proximity to the user. However, not only the distance of an object to the user but also their directional relationship are important. Motivated by these, we propose a new spatial query, namely a direction-based surrounder (DBS) query, which retrieves the nearest objects around the user from different directions. We define the DBS query not only in a two-dimensional Euclidean space E but also in a road network R. In the Euclidean space E, we consider two objects a and b are directional close w.r.t. a query point q iff the included angle aqb is bounded by a threshold specified by the user at the query time. In a road network R, we consider two objects a and b are directional close iff their shortest paths to q overlap. We say object a dominates object b iff they are directional close and meanwhile a is closer to q than b. All the objects that are not dominated by others based on the above dominance relationship constitute direction-based surrounders (DBSs). In this paper, we formalize the DBS query, study it in both the snapshot and continuous settings, and conduct extensive experiments with both real and synthetic datasets to evaluate our proposed algorithms. The experimental results demonstrate that the proposed algorithms can answer DBS queries efficiently.

DOI： 10.1007/s00778-011-0241-y

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

Keyword search in relational databases has been widely studied in recent years because it requires users neither to master a certain structured query language nor to know the complex underlying database schemas. Most existing methods focus on answering snapshot keyword queries in static databases. In practice, however, databases are updated frequently, and users may have long-term interests on specific topics. To deal with such situations, it is necessary to build effective and efficient facilities in a database system to support continual keyword queries. In this paper, we propose an efficient method for answering continual keyword queries over relational databases. The proposed method consists of two core algorithms. The first one computes a set of potential top-k results by evaluating the range of the future relevance score for every query result and creates a light-weight state for each keyword query. The second one uses these states to maintain the top-k results of keyword queries while the database is continually being updated. Experimental results validate the effectiveness and efficiency of the proposed method.

DOI： 10.2197/ipsjjip.20.114

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

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

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

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

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.

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

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.

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

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.

Language：Japanese  

Language：Japanese  

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

Language：Japanese  

Language：Japanese  

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.

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.

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

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

DOI： 10.1007/s00778-013-0306-1

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 data 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 database 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.1587/transinf.E97.D.694

Authorship：Lead author   Language：Japanese   Publishing type：Research paper (scientific journal)  

Facing the age of big data, data analytics, in which sophisticated analysis is performed on large amouts of data, is the focus on attention. In this paper, we survey the current trend of research and development of data analytics and describe the future prospects. First, we classify various approaches for data analytics and then explain how DBMSs are extended for data analytics. Moreover, we describe how machine learning facilities are incoporated in DBMSs and how DBMSs are used as simulation engines. Then, we compare parallel DBMSs and MapReduce from the viewpoint of data analytics and mention system architecture issues. Finally, we present some interesting extentions of MapReduce for data analytics and then present the outlook for the future.

Language：English  

DOI： 10.1007/978-3-662-43984-5_20

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

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

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

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

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

Presentation slide composition is an important job for knowledge workers. Instead of starting from scratch, users tend to make new presentation slides by reusing existing ones. A primary challenge in slide reuse is to select desired materials from a collection of existing slides. The state-of-the-art solution utilizes texts and images in slides as well as file names to help users to retrieve the materials they want. However, it only allows users to choose an entire slide as a query but does not support the search for a single element such as a few keywords, a sentence, an image, or a diagram. In this paper, we investigate content-based search for a variety of elements in presentation slides. Users may freely choose a slide element as a query. We propose different query processing methods to deal with various types of queries and improve the search efficiency. A system with a user-friendly interface is designed, based on which experiments are performed to evaluate the effectiveness and the efficiency of the proposed methods.

DOI： 10.1587/transinf.2014EDP7023

Language：English  

Slide presentations have become a ubiquitous tool for business and educational purposes. Instead of starting from scratch, slide composers tend to make new presentation slides by reusing materials from existing slides. Understanding how slide elements are copied from one presentation file to another and how presentation files are related to each other are difficult tasks.
In this paper, we investigate the management of multiple presentation files based on reused slide elements.We develop techniques to detect text and images that have been reused across multiple presentation files. Interactive visualization methods are proposed to facilitate understanding the process by which these elements are reused and the relationship between the files that use them. A system with a user-friendly interface is designed, based on which experiments are performed to evaluate the effectiveness of the proposed methods.

Language：English  

Slide presentations have become a ubiquitous tool for business and educational purposes. Instead of starting from scratch, slide composers tend to make new presentation slides by browsing existing slides and reusing materials from them. In this paper, we investigate the problem of reused element detection in presentation slides. We develop respective techniques to identify both textual and visual elements that have been reused across multiple presentation files. Experiments are performed to evaluate the effectiveness of the proposed methods.

Authorship：Lead author   Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：English  

Language：English  

Data stream management systems (DSMSs) are useful for the management and processing of continuous data at a high input rate with low latency. In the automotive domain, embedded systems use a variety of sensor data and communications from outside the vehicle to promote autonomous and safe driving. Thus, the software developed for these systems must be capable of handling large volumes of data and complex processing. At present, we are developing a platform for the integration and management of data in an automotive embedded system using a DSMS. However, compared with conventional DSMS fields, we have encountered new challenges such as precompiling queries when designing automotive systems (which demands time predictability), distributed stream processing in in-vehicle networks, and real-time scheduling and sensor data fusion by stream processing. Therefore, we developed an automotive embedded DSMS (AEDSMS) to address these challenges. The main contributions of the present study are: (1) a clear understanding of the challenges faced when introducing DSMSs into the automotive field; (2) the development of AEDSMS to tackle these challenges; and (3) an evaluation of AEDSMS during runtime using a driving assistance application.

DOI： 10.1109/ICDE.2015.7113377

Language：English  

In recent years, complex event processing has attracted considerable interest in research and industry.Pattern matching is used to find complex events in data streams. In probabilistic data streams, however, the system may find multiple matches in a given time interval. This may result in inappropriate matches, because multiple matches may correspond to a single event. We therefore propose grouping methods of matches for probabilistic data streams, and call such merged matches a group. We describe the definitions and generation methods of groups, propose an efficient approach for calculating an occurrence probability of a group, and compare the proposed approach with a naive one by experiment. The results demonstrate the properties and effectiveness of the proposed method.

DOI： 10.1007/978-3-319-18120-2_6

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

Language：Japanese  

Language：Japanese  

Language：English  

Language：Japanese  

Language：Japanese  

Language：English  

This paper proposes a new spatial query called the reverse direction-based surrounder (RDBS) query, which retrieves a user who is seeing a point of interest (POI) as one of their direction-based surrounders (DBSs). According to a user, one POI can be dominated by a second POI if the POIs are directionally close and the first POI is farther from the user than the second is. Two POIs are directionally close if their included angle with respect to the user is smaller than an angular threshold, θ. If a POI cannot be dominated by another POI, it is a DBS of the user. We also propose an extended query called the competitor RDBS query. POIs that share the same RDBSs with another POI are defined as competitors of that POI. We design algorithms to answer the RDBS queries and competitor queries. The experimental results show that the proposed algorithms can answer the queries efficiently.

DOI： 10.1007/978-3-319-25255-1_23

Language：English  

In this paper, we study the problem of discovering all movement patterns from semantic trajectory databases. We propose a two-step method to solve this problem efficiently. We first retrieve frequent movement patterns of categories from the transformed database of sequential categories, and then cluster dense trajectories in a growth-type way for all movement patterns. Moreover, we define a new metric distance function on trajectories. We also use M-tree to cluster trajectories more efficiently. Our experimental results demonstrate the efficiency of the proposed method.

Language：English  

With the advance of video-on-demand (VOD) services such as Netfix, users are able to watch many kinds of videos anytime and anywhere. While watching a video, recently, users often search related information about it through the Web by using mobile PC. However, users cannot satisfactorily understand and enjoy it because the video keeps playing when they search about it. It is necessary to detect various questions of the video to supplement their related information about each scene for automatic search. However, only one video includes various topics of each scene, furthermore, viewers have different levels of knowledge. Therefore, we have developed a novel automatic video reinforcing system, called TV-Binder, it generates new video contents from one video stream related to viewers' interests and knowledge by adding other related contents (i.e., YouTube videos, images or maps) and by removing unnecessary original scenes, based on topics of each scene. As a result, viewers can satisfy and joyfully watch modified video contents without searching anything. At first, our system extract topics and detect their scenes of a video stream by using closed captions. The system then searches other necessary contents and determines unwanted original scenes based on popularity rating of each original scene and level of detail (LOD) controlling under time pressure. Through this, TVBinder can automatically generate video contents are classified into four quadrants by two axes; one is digest and detailed videos, the other one is videos for experts with knowledge about particular topics and ordinary viewers without special knowledge. In this paper, we discuss our automatic video reinforcing system and an evaluation of its effectiveness.

Language：English  

Probabilistic location information has been attracting more and more attention due to the advances in computing devices and technologies, and has become an important research topic in recent years. In particular, Gaussian distribution is frequently used to represent probabilistic location information. On the other hand, as one of the commonest queries over location information, the distance-based nearest neighbor search, which finds closest objects to a given query point, has extensive applications in various areas. There have been considerable efforts made to extend nearest neighbor search over traditional location information to probabilistic location information. An example is the expected distance, which defines the distance over probabilistic location information. Following this trend, in this paper, we assume that the closeness between objects represented by Gaussian distributions are measured by their expected distance and consider the problem of k-expected nearest neighbor search. We analyze properties of expected distance on Gaussian distributions mathematically and derive its lower bound and upper bound. Based on our analysis, we propose three novel approaches to efficiently solve this problem. The efficiency of our approaches is demonstrated through extensive experiments.

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

The problem of similarity search is a crucial task in many real-world applications such as multimedia databases, data mining, and bioinformatics. In this work, we investigate the similarity search on uncertain data modeled in Gaussian distributions. By employing Kullback-Leibler divergence (KL-divergence) to measure the dissimilarity
between two Gaussian distributions, our goal is to search a database for the top-k Gaussian distributions similar to a given query Gaussian distribution. Especially, we consider non-correlated Gaussian distributions, where there are no correlations between dimensions and their covariance matrices are diagonal. To support query processing, we
propose two types of novel approaches utilizing the notions of rank aggregation and skyline queries. The efficiency and effectiveness of our approaches are demonstrated through a comprehensive experimental performance study.

DOI： 10.2197/ipsjjip.24.152

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

DOI： 10.4018/IJMDEM.2016010101

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：English  

Language：Japanese  

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

DOI： 10.20965/jdr.2016.p0255

Language：Japanese  

Language：Japanese  

Authorship：Lead author   Language：Japanese  

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

DOI： 10.1145/2877201

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

DOI： 10.7763/IJIET.2016.V6.680

Language：English  

DOI： 10.1145/2851613.2851985

Language：English  

DOI： 10.1145/2882903.2915211

Language：English  

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

DOI： 10.1093/comjnl/bxv118

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

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

DOI： 10.17706/jcp.12.2.105-115

Language：Japanese  

Language：Japanese  

Language：English  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Authorship：Lead author   Language：Japanese  

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

As the development of sensor and machine learning technologies has progressed, it has become increasingly important to detect patterns from probabilistic data streams. In this paper, we focus on complex event processing based on pattern matching. When we apply pattern matching to probabilistic data streams, numerous matches may be detected at the same time interval because of the uncertainty of data. Although existing methods distinguish between such matches, they may derive inappropriate results when some of the matches correspond to the real-world event that has occurred during the time interval. Thus, we propose two grouping methods for matches. Our methods output groups that indicate the occurrence of complex events during the given time intervals. In this paper, first we describe the definition of groups based on temporal overlap, and propose two grouping algorithms, introducing the notions of complete overlap and single overlap. Then, we propose an efficient approach for calculating the occurrence probabilities of groups by using deterministic finite automata that are generated from the query patterns. Finally, we empirically evaluate the effectiveness of our methods by applying them to real and synthetic datasets.

DOI： 10.1587/transinf.2016DAP0014

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

Language：English  

As the development of data mining technologies for sensor data streams, more sophisticated methods for complex event processing are demanded. In the case of event recognition, since event recognition results may contain errors, we need to deal with the uncertainty of events. We therefore consider probabilistic event data streams with occurrence probabilities of events, and develop a pattern matching method based on regular expressions. In this paper, we first analyze the semantics of pattern matching over non-probabilistic data streams, and then propose the problem of top-k pattern matching over probabilistic data streams. We introduce the use of an information-theoretic criterion to select appropriate matches as the result of pattern matching. Then, we present an efficient algorithm to detect top-k matches, and evaluate the effectiveness of our approach using real and synthetic datasets.

DOI： 10.1007/978-3-319-63579-8_39

Language：English  

Along with the popularization of location-based social networking (LBSN), semantic trajectories, which are trajectories with additional information such as photographs and texts, are increasing, and their utilization is required. We consider frequent pattern extraction as applicable to analysis of semantic trajectories and extraction of regions of interest (ROIs). In this research, we propose SimDBSCAN, which considers both spatial density and similarity of points, by extending DBSCAN, which uses density-based clustering, in order to capture users' interests. Since SimDBSCAN identifies points that are interested in the same object in the neighborhood as ROIs, it is possible to detect not only known ROIs such as tourist sites but also unknown ROIs. In this paper, we explain the algorithm of SimDBSCAN and present the experimental results using photographs collected from Flickr. The experiments show that useful ROIs and patterns can be extracted by the proposed method.

DOI： 10.1145/3105831.3105870

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

This paper proposes a new spatial query called a reverse direction-based surrounder (RDBS) query, which retrieves a user who is seeing a point of interest (POI) as one of their direction-based surrounders (DBSs). According to a user, one POI can be dominated by a second POI if the POIs are directionally close and the first POI is farther from the user than the second is. Two POIs are directionally close if their included angle with respect to the user is smaller than an angular threshold theta. If a POI cannot be dominated by another POI, it is a DBS of the user. We also propose an extended query called competitor RDBS query. POIs that share the same RDBSs with another POI are defined as competitors of that POI. We design algorithms to answer the RDBS queries and competitor queries. The experimental results show that the proposed algorithms can answer the queries efficiently.

DOI： 10.1007/s11280-016-0422-0

Language：Japanese  

Language：Japanese  

Language：Japanese  

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

DOI： 10.1587/transinf.2017EDP7152

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：English  

Language：Japanese  

Language：Japanese  

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

Today, large-scale simulations are thriving because of the increase of computating performance and storage capacity. Understanding the results of these simulations is not easy, and hence, support for interactive and exploratory analysis is becoming more important. This study focuses on spatio-temporal simulations and attempts to develop an analysis technology to support them. It uses a database system for supporting interactive analysis of large-scale data.
Since the data gained via spatio-temporal simulations is not suitable for management in a relational DBMS (RDBMS), this study uses an array DBMS, a type of DBMS that has been garnering increased attention in recent years. An array DBMS is designed for the management of large-scale array data; it provides a logical model for array data, yet it also supports efficient query processing. SciDB is used as our specific array DBMS in this paper.
This study targets disaster evacuation simulation data and demonstrates via experimentation that the query-processing functions offered by an array DBMS provide effective analysis support.

DOI： 10.20965/jdr.2018.p0338

Language：English  

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

Language：English  

Language：English  

To analyze scientific data, there are frequent demands for comparing multiple datasets on the same subject to detect any differences between them. For instance, comparison of observation datasets in a certain spatial area at different times or comparison of spatial simulation datasets with different parameters are considered to be important. Therefore, this paper proposes a difference operator in spatio-temporal data warehouses, based on the notion of histograms in the database research area. We propose a difference histogram construction method and they are used for effective and efficient data visualization in difference analysis. In addition, we implement the proposed algorithms on an array DBMSs SciDB, which is appropriate to process and manage scientific data. Experiments are conducted using mass evacuation simulation data in tsunami disasters, and the effectiveness and efficiency of our methods are verified.

DOI： 10.1007/978-3-319-92013-9_4

Language：Japanese  

DOI： 36-01

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

In this article, we propose a novel indexing and querying method for trajectories constrained in a road network. We aim to provide efficient algorithms for various types of spatiotemporal queries that involve routing in road networks, such as (1) finding moving objects that have traveled along a given path during a given time interval, (2) extracting all paths traveled after a given spatiotemporal context, and (3) enumerating all paths between two locations traveled during a certain time interval. Unlike the existing methods in spatial database research, we employ indexing techniques and algorithms from string processing. This idea is based on the fact that we can represent spatial paths as strings, because trajectories in a network are represented as sequences of road segment IDs. The proposed SNT-index (suffix-array-based network-constrained trajectory index) introduces two novel concepts to trajectory indexing. The first is FM-index, which is a compact in-memory data structure for pattern matching. The second is an inverse suffix array, which allows the FM-index to be integrated with the temporal information stored in a forest of B+-trees. Thanks to these concepts, we can reduce the number of B+-tree accesses required by the query processing algorithms to a constant number, something that cannot be achieved with existing methods. Although an FM-index is essentially a static index, we also propose a practical method of appending new data to the index. Finally, experiments show that our method can process the target queries for more than 1 million trajectories in a few tens of milliseconds, which is significantly faster than what the baseline algorithms can achieve without string algorithms.

DOI： 10.1145/3200200

Language：English  

In this paper, we propose a method that fully combines top-k query processing with replication strategy in mobile ad hoc networks (MANETs). The goal is to acquire perfect accuracy of query results with a minimal overhead and delay. Currently, no replication strategy achieves efficient allocation of replicas for top-k queries, and no top-k query processing guarantees perfect accuracy of query results in MANETs. We propose a new replication strategy FReT (topology-Free Replication for Top-k query) and new top-k query processing methods. FReT advantages efficient top-k query processing from limited search area even if mobile nodes move. In our top-k query processing method, the search area gradually increases until receiving an exact answer. We demonstrate, through extensive simulations, that our approaches function well in terms of small delay and overhead.

DOI： 10.1109/MDM.2018.00039

Language：Japanese  

DOI： D-003

Language：Japanese  

DOI： D-004

Language：Japanese  

DOI： D-017

Language：Japanese  

DOI： -

Language：English  

DOI： no-page

Language：English  

Language：English  

As smartphones and IoT devices become widespread, event streams, which are continuous analysis results of sensing data, have received a Iot of attention. When we consider the utilization of event streams, it is important to deal with probabilistic event streams due to the noises of sensing data and the limitation of analysis techniques. Although existing methods proposed the monitoring of time series events with regular expressions, there is no efficient method to calculate the occurrence probabilities of time series events with a sliding window. That is, existing methods cannot answer a query such as “does the specified time series event occur in last w time steps?” efficiently. Thus, in this paper, we propose an efficient calculation method by using a deterministic finite automaton (DFA). To calculate occurrence probabilities efficiently, our method divide a window into chunks and reuse the previous calculation results. Besides, we apply lazy evaluation to solve the state explosion problem of a DFA. Experimental results using real and synthetic datasets demonstrate effectiveness and efficiency of our approach.

DOI： 10.1109/BIGCOMP.2019.8679461

Language：English  

Road data is fundamental information for location-based services. We trust that the road data is complete to represent an actual road network when we develop the location-based services. However, road data may be incomplete due to update delays, and thus location-based services may not provide useful results. Several algorithms have been proposed to automatically update road data. In this paper, we study interpolation of missing road segments by using vehicle trajectory data. We can find missing road segments from the trajectories because vehicles may pass through road segments that are not included in road data. However, trajectories are inherently noisy due to GPS errors. Hence, we cannot easily interpolate appropriate road segments. We propose an algorithm based on map matching and clustering techniques for achieving accurate and comprehensive interpolation. Our algorithm first detects trajectories that are probably on missing road segments. It then clusters the trajectories by DBSCAN and integrates the trajectories for interpolating the road data. Through the experiments using real incomplete road data and trajectory data, we verify that our algorithm effectively interpolates the missing road segments.

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

Language：Japanese  

Language：English  

Authorship：Lead author   Language：Japanese  

Authorship：Lead author   Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：English  

DOI： 10.5441/002/edbt.2019.15

Authorship：Lead author   Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.20965/jdr.2019.p0521

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

DOI： 10.1587/transinf.2018DAP0020

Language：English  

Query autocompletion (QAC) is an important interactive feature that assists users in formulating queries and saving keystrokes. Due to the convenience it brings to users, QAC has been adopted in many applications, including Web search engines, integrated development environments (IDEs), and mobile devices. For existing QAC methods, users have to manually type delimiters to separate keywords in their inputs. In this paper, we propose a novel QAC paradigm through which users may abbreviate keywords by prefixes and do not have to explicitly separate them. Such paradigm is useful for applications where it is inconvenient to specify delimiters, such as desktop search, text editors, and input method editors. E.g., in an IDE, users may input getnev and we suggest GetNextValue. We show that the query processing method for traditional QAC, which utilizes a trie index, is inefficient under the new problem setting. A novel indexing and query processing scheme is hence proposed to efficiently complete queries. To suggest meaningful results, we devise a ranking method based on a Gaussian mixture model, taking into consideration the way in which users abbreviate keywords, as opposed to the traditional ranking method that merely considers popularity. Efficient top-k query processing techniques are developed on top of the new index structure. Experiments demonstrate the effectiveness of the new QAC paradigm and the efficiency of the proposed query processing method.

DOI： 10.1145/3299869.3319858

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

Code completion is a traditional popular feature for API access in integrated development environments (IDEs). It not only frees programmers from remembering specific details about an API but also saves keystrokes and corrects typographical errors. Existing methods for code completion usually suggest APIs based on statistics in code bases described by language models. However, they neglect the fact that the user's input is also very useful for ranking, as the underlying patterns can be used to improve the accuracy of predictions of intended APIs. In this paper, we propose a novel method to improve the quality of code completion by incorporating the users' acronym-like input conventions and the APIs' scope context into a discriminative model. The users' input conventions are learned using a logistic regression model by extracting features from collected training data. The weights in the discriminative model are learned using a support vector machine (SVM). To improve the real-time efficiency of code completion, we employ a trie to index and store the scope context information. An efficient top-k algorithm is developed. Experiments show that our proposed method outperforms the baseline methods in terms of both effectiveness and efficiency.

DOI： 10.2197/ipsjjip.27.469

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

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

This article addresses the top-k query processing problem on mobile ad hoc networks (MANETs). Top-k query processing is common to retrieve only highly important data items. However, methods for top-k query processing are not enough efficient and accurate in MANET environments. For improving the efficiency and accuracy, replication is a promising technique that each node in MANETs replicates data items retained by other nodes into its storage. Therefore, we fully combine the top-k query processing with data replication. We propose a framework that efficiently processes top-k queries based on a new replication strategy. We develop new replication strategy FReT (topology-Free Replication for Top-k query). FReT determines near-optimal allocations of replicas. It advantages efficient top-k query processing from limited search area without maintenance costs even if mobile nodes move. Our top-k query processing methods retrieve the exact answer with small overhead and delay by gradually increasing the search area based on FReT. We demonstrate, through extensive experiments, that FReT and query processing methods function well in terms of small delay and overhead without sacrificing exactness of the query result.

DOI： 10.1007/s10707-019-00363-0

Language：English  

Language：Japanese  

DOI： B3-2

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

Language：Japanese  

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

DOI： 10.14923/transinfj.2019DET0001

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

DOI： 10.1587/transinf.2019DAP0009

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

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

DOI： 10.1007/s00778-019-00595-4

Language：English  

DOI： 10.1007/978-3-030-61133-0_8

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：English   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：IEEE Transactions on Knowledge and Data Engineering  

A distance search in Hamming space finds binary vectors whose Hamming distances are no more than a threshold from a query vector. It is a fundamental problem in many applications, such as image retrieval, near-duplicate Web page detection, and scientific databases. State-of-the-art approaches to Hamming distance search are mainly based on the pigeonhole principle to generate a set of candidates and then verify them. We observe that the constraint by the pigeonhole principle is not always tight and may bring about unnecessary candidates. We also observe that the distribution in real data is often skewed, but most existing solutions adopt a simple equi-width partitioning and allocate the same threshold to all the parts, hence failing to exploit the data skewness to optimize query processing. In this paper, we propose a new form of the pigeonhole principle which allows variable partitioning and threshold allocation. Based on the new principle, we develop a tight constraint of candidates and devise cost-aware methods for partitioning and threshold allocation to optimize query processing. In addition, we extend our methods to answer Hamming distance join queries. We also discuss the application of the pigeonhole principle in set similarity search, a problem that can be converted to Hamming distance search equivalently. Our evaluation on datasets with various data distributions shows the robustness of our solution and its superior query processing performance to the state-of-the-art methods.

DOI： 10.1109/TKDE.2019.2899597

Scopus

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：The Institute of Electronics, Information and Communication Engineers  

Edge computing enables communication traffic reduction and load balancing by simple data processing like aggregation or filtering at network edges. Low latency, high reliability, and fault tolerance are important requirements for edge computing applications. In this paper, we assume applications for environmental sensing and propose an approximate streaming aggregation algorithm that meets these requirements. Our method provides the result with theoretical error bounds, even if there are missing data due to sensor failures or communication failures. Furthermore, our method reduces latency by outputting the result when meeting user requirements and guarantees fault tolerance approximately by estimating the lost state.

DOI： 10.14923/transinfj.2020dep0004

CiNii Research

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1145/3448016.3452772

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ACM International Conference Proceeding Series  

A spatial skyline query is a query to find a set of data points that are not spatially dominated by other data points, given a set of data points P and query points Q in a multidimensional space. The query enumerates the skyline points based on distance in a multidimensional space. However, existing spatial skyline queries can lead to large errors with actual travel distances in geo-spaces because the query is based on the Euclidean distance. We propose a spatial skyline query on triangulated irregular networks (TINs), which are frequently used to represent the surfaces of terrain. We define a new spatial skyline query based on more accurate travel distances considering the TIN distance instead of the Euclidean distance. We also propose an efficient solution method using indexes to find nearest-neighbor points in TIN space and reduce the numbers of unnecessary data points and TIN vertices. The proposed method achieves a computational complexity of O(|P′||Q|N′2 + |P′|2|Q|), where P′ and N′ are the reduced sets of data points and number of TIN vertices, respectively, based on the range of query points. The proposed method can process a query faster than the naive method with T(|P||Q|N2 + |P|2|Q|), where N is the number of TIN vertices. Moreover, experiments verify that the proposed method is faster than the naive method by using a spatial index to reduce the numbers of unnecessary data points and TIN vertices.

DOI： 10.1145/3469830.3470901

Scopus

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Communications in Computer and Information Science  

Existing distributed stream processing systems generally guarantee fault tolerance by switching to standby machines and reprocessing lost data. In edge computing environments, however, we have to duplicate each edge for this conventional approach. This duplication cost increases sharply with expansion in the system scale. To solve this problem, we propose an approach to support approximate fault tolerance without edge duplication. We focus on environmental monitoring applications and utilize the correlation between sensors. In this paper, we assume that each edge estimates missing data from the observed data and aggregates them approximately. We provide a method to estimate the outputs of failed edges taking care of the uncertainty of the processing results at each edge. Our method allows the server to continue processing without waiting for the recovery of failed edges. We also show that the validity of our method by experiments using synthetic data.

DOI： 10.1007/978-3-030-87101-7_17

Scopus

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

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (other academic)   Publisher：一般社団法人電子情報通信学会  

DOI： 10.1587/ieiceissjournal.26.3_10

CiNii Research

Authorship：Corresponding author   Language：Japanese   Publishing type：Research paper (international conference proceedings)   Publisher：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

With the development of IoT, edge computing has been attracting attention in recent years. In edge computing, simple data processing, such as aggregation and filtering, can be performed at network edges to reduce the amount of data communication and distribute the processing load. In edge computing applications, it is important to guarantee low latency, high reliability, and fault tolerance. We are working on the solution of this problem in the context of environmental sensing applications. In this paper, we outline our approach. In the proposed method, the aggregate value of each device is calculated approximately and the fault tolerance is also guaranteed approximately even when the input data is missing due to sensor device failure or communication failure. In addition, the proposed method reduces the delay by outputting the processing result when the error guarantee satisfies the user’s requirement.

DOI： 10.1007/978-3-030-96600-3_17

Scopus

Language：Japanese   Publishing type：Research paper (international conference proceedings)   Publisher：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

In recent years, with the increase of data and the sophistication of analysis requirements, query processing in databases has become more important. Recently, approximate query processing (AQP) was proposed for efficiently executing database queries on big data. In this research, we focus on synopsis construction on a relational database and the query technology based on it, which is called Bounded Approximate Query (BAQ) proposed in 2019. BAQ is a synopsis construction method that focuses on aggregate queries using SQL, and realizes error-guaranteed query processing by grouping the dataset into the synopsis. In this paper, we point out the limitations of queries and datasets in BAQ and based on the result of experiments, we prove that the proposed method can be applied efficiently to data wider than the original BAQ with smaller synopsis within the error guarantee.

DOI： 10.1007/978-3-030-96600-3_20

Scopus

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

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

DOI： 10.1587/transinf.2021DAP0011

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

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

DOI： 10.14778/3574245.3574269

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (other academic)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：English   Publishing type：Research paper (scientific journal)   Publisher：The Institute of Electronics, Information and Communication Engineers  

<p>Convolutional Neural Networks (CNNs) have recently demonstrated outstanding performance in image retrieval tasks. Local convolutional features extracted by CNNs, in particular, show exceptional capability in discrimination. Recent research in this field has concentrated on pooling methods that incorporate local features into global features and assess the global similarity of two images. However, the pooling methods sacrifice the image's local region information and spatial relationships, which are precisely known as the keys to the robustness against occlusion and viewpoint changes. In this paper, instead of pooling methods, we propose an alternative method based on local similarity, determined by directly using local convolutional features. Specifically, we first define three forms of local similarity tensors (LSTs), which take into account information about local regions as well as spatial relationships between them. We then construct a similarity CNN model (SCNN) based on LSTs to assess the similarity between the query and gallery images. The ideal configuration of our method is sought through thorough experiments from three perspectives: local region size, local region content, and spatial relationships between local regions. The experimental results on a modified open dataset (where query images are limited to occluded ones) confirm that the proposed method outperforms the pooling methods because of robustness enhancement. Furthermore, testing on three public retrieval datasets shows that combining LSTs with conventional pooling methods achieves the best results.</p>

DOI： 10.1587/transinf.2022edp7163

Scopus

CiNii Research

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：The Institute of Electronics, Information and Communication Engineers  

Data loss due to failure is an important issue in data stream processing for edge computing. In particular, the detection of data loss is a big problem, and the conventional method accumulates delays. In this paper, we propose a watermark management method based on the cooperation of edges and a gateway. Our method estimates lost data at a later stage and generates watermarks based on user's error requirements. We utilize an error guarantee mechanism to calculate the error requirements for edges in each failure situation. We show that our method can recover lost data precisely and reduce delays according to the user's requirements through experiments.

DOI： 10.14923/transinfj.2023dep0007

CiNii Research

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Proceedings of Machine Learning Research  

Approximate nearest neighbor search (ANNS) in high-dimensional spaces is a pivotal challenge in the field of machine learning. In recent years, graph-based methods have emerged as the superior approach to ANNS, establishing a new state of the art. Although various optimizations for graph-based ANNS have been introduced, they predominantly rely on heuristic methods that lack formal theoretical backing. This paper aims to enhance routing within graph-based ANNS by introducing a method that offers a probabilistic guarantee when exploring a node's neighbors in the graph. We formulate the problem as probabilistic routing and develop two baseline strategies by incorporating locality-sensitive techniques. Subsequently, we introduce PEOs, a novel approach that efficiently identifies which neighbors in the graph should be considered for exact distance calculation, thus significantly improving efficiency in practice. Our experiments demonstrate that equipping PEOs can increase throughput on commonly utilized graph indexes (HNSW and NSSG) by a factor of 1.6 to 2.5, and its efficiency consistently outperforms the leading-edge routing technique by 1.1 to 1.4 times. The code and datasets used for our evaluations are publicly accessible at https://github.com/ICML2024-code/PEOs.

Scopus

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

Event date： 1999.12

Language：Japanese   Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2003.3

Language：Japanese   Presentation type：Oral presentation (invited, special)  

Country：Japan  

Event date： 2003.6

Language：Japanese   Presentation type：Oral presentation (invited, special)  

Country：Japan  

Event date： 2005.10

Language：Japanese   Presentation type：Oral presentation (invited, special)  

Country：Japan  

Event date： 2006.1

Language：English   Presentation type：Oral presentation (general)  

Demo presentation

Event date： 2006.6

Language：Japanese   Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2006.6

Language：Japanese   Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2007.9

Language：Japanese   Presentation type：Oral presentation (general)  

Country：Japan  

Event date： 2008.9

Language：English   Presentation type：Oral presentation (invited, special)  

Country：Japan  

Event date： 2008.11

Language：English   Presentation type：Oral presentation (invited, special)  

Event date： 2010.3

Language：English   Presentation type：Oral presentation (invited, special)  

Country：Japan  

Event date： 2011.11

Language：English   Presentation type：Oral presentation (general)  

Country：Japan  

In mobile computing environments, different users generally have different properties and interests. Moreover, their contexts continually change due to their movements and the dynamic surrounding environments. For providing useful information for mobile users and support their decisions, adaptive spatial query processing techniques have been proposed in recent years. In this talk, their underlying requirements and some interesting ideas are introduced, and then our work on adaptive spatial query processing, such as spatial skyline queries and direction-based surrounder queries, are presented. Finally, future research directions on this topic are provided.

Event date： 2011.12

Language：English   Presentation type：Oral presentation (invited, special)  

Country：Japan  

In recent years, representation and management of \emph{uncertain data} have gained much interests in the research field of database technologies. In this talk, we especially focus on spatio-temporal databases and consider the problems due to uncertain location information. Uncertainty of location information in spatio-temporal databases usually occur because of measurement errors, incorrect sensor readings, lack of signals, and movement of the objects, and results in non-accurate and non-reliable query results.

In this talk, we provide an overview of the current database technologies for managing uncertain location information. First, the background and the motivations are introduced. Some examples are taken from the fields of sensor databases and mobile applications. Second, a survey of interesting ideas in this field is provided. It covers not only uncertain location issues but also some related problems such as uncertain data streams and probabilistic frameworks for supporting uncertain queries.

Then we describe our past and current works for supporting adaptive spatial query processing considering uncertain location information. It includes a framework for probabilistic spatial queries, an indexing technique for uncertain spatial objects, and so on. We also show the application of the technologies to the decision support of mobile robots. Finally, the future research directions in uncertain location management are provided.

Event date： 2013.9

Language：English   Presentation type：Oral presentation (invited, special)  

Venue：Shenyang, China   Country：China  

Event date： 2014.2

Language：English   Presentation type：Oral presentation (general)  

Venue：Kumamoto, Japan   Country：Japan  

Event date： 2014.3

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：淡路島   Country：Japan  

Event date： 2014.4

Language：English   Presentation type：Symposium, workshop panel (nominated)  

Venue：Bali, Indonesia   Country：Indonesia  

Event date： 2014.9

Language：English   Presentation type：Oral presentation (general)  

Venue：北京，中国   Country：China  

Event date： 2014.11

Language：Japanese   Presentation type：Poster presentation  

Venue：芝浦工業大学   Country：Japan  

Event date： 2014.11

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：名古屋市   Country：Japan  

Event date： 2015.9

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：名古屋大学   Country：Japan  

Event date： 2018.11

Language：English   Presentation type：Oral presentation (keynote)  

Venue：Incheon, South Korea   Country：Korea, Republic of  

Event date： 2019.4

Language：English   Presentation type：Oral presentation (general)  

Venue：Hong Kong   Country：Hong Kong  

Event date： 2019.9

Language：Japanese   Presentation type：Poster presentation  

Venue：工学院大学   Country：Japan  

Event date： 2019.12

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：名古屋大学   Country：Japan  

Event date： 2019.12

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：名古屋大学   Country：Japan  

Event date： 2021.2

Language：Japanese   Presentation type：Oral presentation (invited, special)  

Venue：オンライン   Country：Japan  

Event date： 2021.10

Language：Japanese   Presentation type：Public lecture, seminar, tutorial, course, or other speech  

Venue：オンライン   Country：Japan  

Event date： 2021.12

Language：English   Presentation type：Oral presentation (keynote)  

Venue：Online  

Event date： 2022.11

Language：English   Presentation type：Oral presentation (invited, special)  

Venue：大阪大学   Country：Japan  

Event date： 2023.1

Language：English   Presentation type：Oral presentation (keynote)  

Venue：Hybrid (Seoul / Online)   Country：Korea, Republic of  

Event date： 2024.8

Language：Japanese   Presentation type：Poster presentation  

Venue：徳島市  

Event date： 2024.8

Language：Japanese   Presentation type：Poster presentation  

Venue：徳島市