Proposal and evaluation of a Bloom filter-based user search method for movement records on P2P network

In this paper, we propose a P2P user search method based on movement records. We assume movement records are treated as a sequence of pairs of spot-ID and time, and they are stored in a peer for each user. In our proposal, a Bloom Filter is applied to each spotID and time to combine all movement records for one user as a fixed length bit array. To search a user who followed specified course, we propose a AND/OR search method based on Bloom Finger Table (BFT), which extends a routing table of a Chord DHT system that can retrieve complex searches using Bloom Filter. By this method, user searches based on a sequence of locations with or without time can be realized efficiently. Additionally, in order to reduce the number of messages, the number of hops and error probability of the query transmission for a user search, we propose a peer-ID assignment for BFT based on user's geographical foothold. The number of messages, the number of hops and error probability of the query transmission for a user search can be reduced by this peer-ID assignment since users who visit same places are located closer to each other on the routing table. Evaluation results of simulations show that our proposal without peer-ID assignment reduces the number of messages and hops compared to a naive implementation using existing P2P retrieval method and our proposal with peer-ID assignment more reduces the number of messages, hops and error probability of the query transmission considering user's geographical foothold when we retrieve places where many people visited and did not visit.