Efficient information exchange between encountering vehicles using approximate knowledge via hash functions

A method of exchanging records in a vehicle-to-vehicle communication system, the records relating to places of interest to a user of a vehicle that are stored within a vehicle-based database, each respective record identifying at least a name of the place and other attributes relating to the place that are capable of being queried from the database, wherein a respective place in a respective record is identified by a global unique index number, wherein a specific global unique index number relating to a specific place is common among all vehicles within the vehicle-to-vehicle communication system, the method comprising the steps of:

• a first vehicle and a second vehicle detecting that they are within a predetermined proximity of one another;
• communicating a query from the first vehicle to the second vehicle relating to a desired scope of information contained within the records of the second vehicle, the query further including a number of records in a database of the first vehicle that satisfies the query;
• the second vehicle determining a number of records within a database of the second vehicle that satisfies the query;
• the second vehicle determining if the number of records in the first vehicle that satisfy the query and the number of records in the second vehicle that satisfy the query are within a predetermined range;
• the second vehicle estimating a similarity between the records of the first vehicle and the second vehicle that satisfy the query when the number of records of the first vehicle and the second vehicle satisfying the query are within the predetermined range, wherein estimating the similarity comprises the steps of:
• the first vehicle randomly selecting a first subset of the records satisfying the query from the database of the first vehicle;
• the first vehicle identifying each global unique index number associated with each record in the first subset;
• the second vehicle randomly selecting a second subset of records satisfying the query from the database of the second vehicle;
• the second vehicle identifying each global unique index number associated with each record in the second subset;
• hashing the identified global unique index numbers of the first and second subsets using a same hash function;
• and
• calculating a similarity as a function of the hashed global unique index numbers of the first vehicle and the second vehicle;
• the second vehicle requesting all of the global unique index numbers associated with the records from the first vehicle that satisfy the query in response to the similarity being greater than a predetermined threshold, otherwise, the second vehicle requesting a compressed number of global unique index numbers associated with the records from the first vehicle that satisfy the query.