Intelligent agents have been shown to be a good approach to addressing the issues of limited capacity and unreliable wireless links in mobile computing. However, before the approach can be commercially viable, a set of management capabilities that support the controls of intelligent agents in a mobile environment need to be in place. Since controls can only be applied after the target agent is located, an effective agent search algorithm is an indispensable part of the management functions. In this paper, we propose a new algorithm, the highest probability first algorithm, for locating the target agent. The approach makes use of the execution time information to reduce cost and network traffic. The execution time of the agent on a server is assumed to be binomial distributed and therefore is more realistic.

In a mobile computing environment that supports mobile agents, a client can send an agent to visit a sequence of servers in the network. To track the location of agents becomes a critical problem in managing a mobile agent service network. This paper studies the agent search problem based on an open architecture proposed by Lien (see Proc. of the First Workshop on Mobile Computing, Hsing-Chu, Taiwan, p.2-9, 1995) and is currently being implemented in the National Chengchi University.

Previous work on superimposed coding has been characterized by two aspects. First, it is generally assumed that signatures are generated from logical text blocks of the same size; that is, each block contains the same number of unique terms after stopword and duplicate removal. We call this approach the fixed-size block (FSB) method, since each text block has the same size, as measured by the number of unique terms contained in it. Second, with only a few exceptions [6,7,8,9,17], most previous work has assumed that each term in the text contributes the same number of ones to the signature (i.e., the weight of the term signatures is fixed). The main objective of this paper is to derive an optimal weight assignment that assigns weights to document terms according to their occurrence and query frequencies in order to minimize the false-drop probability. The optimal scheme can account for both uniform and nonuniform occurence and query frequencies, and the signature generation method is still based on hashing rather than on table lookup. Furthermore, a new way of generating signatures, the fixed-weight block (FWB) method, is introduced. FWB controls the weight of every signature to a constant, whereas in FSB, only the expected signature weight is constant. We have shown that FWB has a lower false-drop probability than that of the FSB method, but its storage overhead is slightly higher. Other advantages of FWB are that the optimal weight assignment can be obtained analytically without making unrealistic assumptions and that the formula for computing the term signature weights is simple and efficient.

A partitioning method is introduced for reducing the search space required on the signature file. A partitioned signature file is better than the multilevel signature file and the S-tree in that it has an extremely small storage and processing overhead. Three partitioning schemes are outlined and their performance discussed. A description is given of the data structure necessary to support the partitioning schemes and the algorithms for signature insertion, deletion, and retrieval.>

A signature file acts as a filtering mechanism to reduce the amount of text that needs to be searched for a query. Unfortunately, the signature file itself must be exhaustively searched, resulting in degraded performance for a large file size. We propose to use a deterministic algorithm to divide a signature file into partitions, each of which contains signatures with the same “key.” The signature keys in a partition can be extracted and represented as the partition's key. The search can then be confined to the subset of partitions whose keys match the query key. Our main concern here is to study methods for obtaining the keys and their performance in terms of their ability to reduce the search space. Owing to the reduction of search space, partitioning a signature file has a direct benefit in a sequential search (single-processor) environment. In a parallel environment, search can be conducted in parallel effectively by allocating one or more partitions to a processor. Partitioning the signature tile with a deterministic method (as opposed to a random partitioning scheme) provides intraquery parallelism as well as interquery parallelism. In this paper, we outline the criteria for evaluating partitioning schemes. Three algorithms are described and studied. An analytical study of the performance of the algorithms is provided and the results are verified with simulation.