Efficient Information Exchange Between Encountering Vehicles Using Approximate Knowledge Via Hash Functions

• US 20120197875A1
• Filed: 01/31/2011
• Published: 08/02/2012
• Est. Priority Date: 01/31/2011
• Status: Active Grant

• Current Assignee: GM Global Technology Operations LLC (General Motors Company)
• Original Assignee: GM Global Technology Operations LLC (General Motors Company)
• Inventors: Bai, Fan, Grimm, Donald K., Yu, Bo
• Granted Patent: US 8,510,324 B2
• Time in Patent Office: Days
• US Class Current: 707/723
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 7/00 Methods or arrangements for processing data by operating upon the order or content of the data handled logic circuits H03K19/00
• CPC Class Codes: G08G 1/163 involving continuous checking

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.

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.

2. The method of claim 1 wherein estimating a similarity between the records of the first vehicle and the second vehicle that satisfy the query is represented by the following formula:

3. The method of claim 1 wherein the similarity is determined as a function of the entire global unique index numbers associated with records of the first vehicle and the second vehicle that satisfy the query, according to the following equation:

4. The method of claim 1 further comprising the steps of:

the first vehicle transmitting to the second vehicle the global unique index numbers associated with the records from the first vehicle as requested by the second vehicle;

the second vehicle determining which respective records stored in the database of the second vehicle to transmit to the first vehicle as a function of the global unique index numbers transmitted from the first vehicle to the second vehicle and a function of the global index numbers associated with the records stored in the database of the second vehicle that satisfies the query; and

transmitting the respective records to the first vehicle.

5. The method of claim 4 wherein the determination of which respective records to transmit from the second vehicle to the first vehicle is represented by the following formula:

N_B−

|NR_A∩

N_B|

where N_B is the global unique index numbers associated with records of the second vehicle that satisfy the query, and NR_A is the global unique index numbers associated with the records from the first vehicle requested by the second vehicle.

6. The method of claim 5 wherein the global unique index numbers NR_A are determined using a bloom filter.

7. The method of claim 5 wherein the global unique index numbers NR_A are all of the index numbers associated with the records of the first vehicle that satisfy the query.

8. The method of claim 1 further comprising the steps of sending no records from the second vehicle to the first vehicle in response to the number of records in the first vehicle and the number of records in the second vehicle being outside of the predetermined range, wherein the number of records of the first vehicle that satisfy the query is greater than the number of records of the second vehicle that satisfy the query by a first predetermined number.

9. The method of claim 1 further comprising the steps of the second vehicle sending all of the records in the database of the second vehicle that satisfy the query to the first vehicle in response to the number of records in the first vehicle and the number of records in the second vehicle being outside of the predetermined range, wherein the number of records of the first vehicle that satisfy the query is less than the number of records of the second vehicle that satisfy the query by a first predetermined number.

10. The method of claim 1 wherein the hashing the identified global unique index numbers of the first vehicle and the identified global unique index numbers of the second vehicle into a same bit vector further comprises the steps of:

the first vehicle and second vehicle mutually identifying a hash function;

the first vehicle hashing each global unique index number associated with each record of the first subset into the identified hash function;

the second vehicle hashing each global unique index number associated with each record of the second subset into the identified hash function; and

the first vehicle communicating hash results as determined by the first vehicle to the second vehicle.

11. The method of claim 1 wherein the hashing the identified global unique index numbers of the first vehicle and the identified global unique index numbers of the second vehicle into a same bit vector further comprises the steps of:

the first vehicle transmitting the identified global unique index numbers associated with each record of the first subset to the second vehicle; and

the second vehicle hashing each global unique index number associated with each record of the second subset and the identified global unique index numbers transmitted by the first vehicle into the same bit vector.

12. The method of claim 1 wherein the first subset of the records and the second set of records randomly selected from the respective databases are selected based on randomly selecting a same percentage from each respective database.

13. The method of claim 12 wherein the percentage is a predetermined percentage.

14. The method of claim 12 wherein the percentage is adaptively determined.

15. The method of claim 1 wherein the queried information includes information relating to a group that includes at least a description of the place.

16. The method of claim 1 wherein the queried information includes information relating to a group that includes at least one of a temporal scope, a spatial scope, a user interest scope.

17. The method of claim 1 wherein the queried information relates to pricing information.

18. The method of claim 1 wherein the queried information relates to rating information.

19. The method of claim 1 wherein the predetermined threshold is a calibrated threshold.

20. The method of claim 1 wherein the predetermined threshold is an adaptive threshold.