An Efficient Signature-based Strategy For Supporting Inexact Filtering In Information Filtering Systems

摘要

To help users find the right information from a great quantity of data, Information Filtering (IF) sends information from servers to passive users through broadcast mediums, rather than being searched by them. To efficiently store many user profiles in servers and filter irrelevant users, many signature-based index techniques are applied in IF systems. By using signatures, IF does not need to compare each item of profiles to filter out irrelevant ones. However, because signatures are incomplete information of profiles, it is very hard to answer the complex queries by using only the signatures. Therefore, a critical issue of the signature-based IF service is how to index the signatures of user profiles for an efficient filtering process. The inexact filtering query is one kind of queries in the signature-based IF systems which is used to filter out the non-qualified data compared with queries. In this paper, we propose an ID-tree index strategy, which indexes signatures of user profiles by partitioning them into subgroups using a binary tree structure according to all of the different items among them. In an ID-tree, each path from the root to a leaf node is the signature of the profile pointed by the leaf node. Because each profile is pointed by only one leaf node of the ID-tree, there will be no collision in the structure. Moreover, only the different items among subgroups of profiles will be checked at one time to filter out irrelevant profiles for queries. Therefore, our strategy can answer the inexact filtering query with less number of accessed profiles as compared to Chen's signature tree strategy. From our simulation results, we have shown that our strategy can access less number of profiles to answer the queries than Chen's signature tree strategy for the inexact filtering.