Efficient information exchange between encountering vehicles using approximate knowledge via hash functions
First Claim
1. 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.
3 Assignments
0 Petitions
Accused Products
Abstract
A method is provided for efficiently transferring records related to places of interest between two communicating vehicles in a V2V system without initially having to transfer full text records. A determination is made as to whether information stored in a memory of the vehicle is redundant with the respect to the other vehicle. A query request is transmitted from a first vehicle to a second vehicle containing specifics as to what records the first vehicle is seeking. Data satisfying the query request represented by global unique index numbers is hashed to determine the similarity between the data of the two communicating vehicles. The similarity is used to determine whether a full filtered set of global unique index numbers should be transferred to the second vehicle for determining which records are not duplicate records. Thereafter, the second vehicle wirelessly transmits to the first vehicle the non-overlapping data that satisfies the query request.
-
Citations
20 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
Specification