Consider a variant of the maximum-sum segment problem for a sequence X₀ of n real numbers, which asks an arbitrary contiguous subsequence of X_a that maximizes the sum of its elements for any given real number a, where X_a is the sequence obtained by subtracting a from each element in X₀. Although this problem can be solved in O(n) time from scratch for any given X₀ and a, appropriate data structures for X₀ could support efficient queries of the solution for arbitrary a. We propose an O(n log² n)-time, O(n)-space algorithm that takes X₀ as input and outputs such a data structure supporting O(log n)-time queries.

Abstract The similarity between a pair of time series, i.e., sequences of indexed values in time order, is often estimated by the dynamic time warping (DTW) distance, instead of any in the well-studied family of measures including the longest common subsequence (LCS) length and the edit distance. Although it may seem as if the DTW and the LCS(-like) measures are essentially different, we reveal that the DTW distance can be represented by the longest increasing subsequence (LIS) length of a sequence of integers, which is the LCS length between the integer sequence and itself sorted. For a given pair of time series of lengthnsuch that the dissimilarity between any elements is an integer between zero andc, we propose an integer sequence that represents any substring-substring DTW distance as its band-substring LIS length. The length of the produced integer sequence is $$O(c n^2)$$ O(cn2) , which can be translated to $$O(n^2)$$ O(n2) for constant dissimilarity functions. To demonstrate that techniques developed under the LCS(-like) measures are directly applicable to analysis of time series via our reduction of DTW to LIS, we present time-efficient algorithms for DTW-related problems utilizing the semi-local sequence comparison technique developed for LCS-related problems.

The similarity between a pair of time series, i.e., sequences of indexed values in time order, is often estimated by the dynamic time warping (DTW) distance, instead of any in the well-studied family of measures including the longest common subsequence (LCS) length and the edit distance. Although it may seem as if the DTW and the LCS(-like) measures are essentially different, we reveal that the DTW distance can be represented by the longest increasing subsequence (LIS) length of a sequence of integers, which is the LCS length between the integer sequence and itself sorted. For a given pair of time series of n integers between zero and c, we propose an integer sequence that represents any substring-substring DTW distance as its band-substring LIS length. The length of the produced integer sequence is O(c⁴ n²) or O(c² n²) depending on the variant of the DTW distance used, both of which can be translated to O(n²) for constant cost functions. To demonstrate that techniques developed under the LCS(-like) measures are directly applicable to analysis of time series via our reduction of DTW to LIS, we present time-efficient algorithms for DTW-related problems utilizing the semi-local sequence comparison technique developed for LCS-related problems.

A common subsequence of two strings is maximal, if inserting any character into the subsequence can no longer yield a common subsequence of the two strings. The present article proposes a (sub)linearithmic-time, linear-space algorithm for finding a maximal common subsequence of two strings and also proposes a linear-time algorithm for determining if a common subsequence of two strings is maximal.

Fresh information is important for real business. However, conventional search engines are not suited for fresh information retrieval because they are based on centralized architecture. So, we have developed a distributed search engine, cooperative search engine (CSE), which based on distributed architecture. CSE can search fresh information in a short time. The cost of fresh information retrieval is O(1) in the average case, but O(n) in the worst case. So, CSE is scalable, because it is not depended on the system scale. However, even if the performance is good, it is not enough for fresh information retrieval. The value of information is determined by both freshness and relevance. Traditional ranking methods consider either freshness or relevance. So, we propose FTF-IDF scoring which considers both freshness and relevance. In this paper, we evaluate its effects.

For most businesses, fresh information retrieval is very important. However, it is difficult for conventional search engines based on centralized architecture to retrieve really fresh information, because they take a long time to collect documents via Web robots. In contrast to a centralized architecture, a search engine based on a distributed architecture does not need to collect documents, because each site independently makes an index. As this result, distributed search engines can retrieve really fresh information. However, fast indexing is not enough to easily retrieve fresh information. The value of information is determined by both freshness and relevance. Traditional ranking methods consider either freshness or relevance; so, we proposed FTFIDF (fresh term frequency multiplied by inverse document frequency) as a scoring method that considers both freshness and relevance.

Crawling and indexing have been considered regarding existing search engines, but whereas high speed crawling has been studied widely, improvements in the speed of indexing have seldom been discussed. Building a fresh information search engine should, however, unify these arguments concerning crawling and indexing. In this report, an index updating process based on a pipeline that unifies crawling and indexing was proposed. The techniques of a distributed index updating process are discussed with regards to a distributed cooperative search engine.

We have developed a distributed search engine, called Cooperative Search Engine (CSE), in order to retrieve fresh information. In CSE, a local search engine located in each Web server makes an index of local pages. A meta search server integrates these local search engines in order to realize a global search engine. This meta server is a single point of failure in CSE. So, we propose redundancy of meta search servers in order to increase availability of CSE. In this paper, we describe the reliable architecture of CSE and its evaluations.

We have developed distributed search engine, called cooperative search engine (CSE), in order to retrieve fresh information. In CSE, a local search engine located in each Web server makes an index of local pages. And, a meta search server integrates these local search engines in order to realize a global search engine. This meta server is single point of failure in CSE. We propose redundancy, of meta search servers in order to increase availability of CSE. In this paper, we describe reliable architecture of CSE and its evaluations.

We have developed a distributed search engine, called cooperative search engine (CSE), in order to retrieve fresh information. In CSE, a local search engine located in each Web server makes an index of local pages. A meta search server integrates these local search engines in order to realize a global search engine. In such a way, the communication delay occurs at retrieval time. So, it is thought to be difficult to search quickly. However we have developed several speedup techniques in order to realize real time retrieval. In addition, the meta server is a single point of failure in CSE. So, we propose redundancy of meta search servers in order to increase availability of CSE. In this paper we describe scalability and reliability of CSE and their evaluations.

Algorithms for learning feasibly Boolean functions from examples are explored.A class of as a hyp ot, hesis class, it, remains open whether it is properly learnable under distribution free setting. 1

Based on the uniform distribution PAC learning model, the learnability for monotone disjunctive normal form formulas with at most $O(\log n)$ terms ( $O(\log n)$ -term MDNF) is investigated.Using the technique of restriction, an algorithm that learns $O(\log n)$ -term MDNF in polynomial time is given.