Encoding and compression of a location beacon database
First Claim
1. In a location-based services system having a reference database of Wi-Fi access points in a target area, each access point in the target area identified by a corresponding fixed size MAC address and each Wi-Fi access point positioned at a corresponding geographical location, a method of encoding MAC addresses and geographical locations of the access points to facilitate storage or transmission of the database contents to Wi-Fi enabled devices using the system, the method comprising the acts of:
- (a) storing as an entry of the database a reset address entry, said reset address entry including a fixed-size MAC address and marker information to indicate that the entry has a complete MAC address for a corresponding access point;
(b) for each access point in at least a subset of access points in the target area, encoding a mathematical difference between (i) the MAC address of a corresponding access point and (ii) one of the other MAC addresses represented in the database, and storing said encoding, as delta information, in a corresponding delta address entry of the database, said delta address entry further including marker information to indicate that the entry has delta information from which a complete MAC address for a corresponding access point can be reconstituted; and
(c) for each entry in the database, including information to represent the geographical location of the corresponding access point.
1 Assignment
0 Petitions
Accused Products
Abstract
A method of delta-encoding and compressing a table containing 6-byte MAC addresses is provided. The MAC addresses are sorted, a first MAC address is stored, and only the binary differences between succeeding MAC addresses are stored. A method of reading a delta-encoded and compressed MAC address table is provided. A first unencoded MAC address is read. The remaining MAC addresses are generated by successively adding stored binary differences to the result of the previous addition. A method of encoding and compressing a location table is provided. A reference latitude and longitude is selected and stored. The offsets from the reference latitude and longitude are stored for the remaining locations. A method of reading an encoded location table is provided. A stored reference latitude and longitude is read. Stored offsets are read and applied to the reference latitude and longitude to generate a set of latitude and longitude locations.
-
Citations
25 Claims
-
1. In a location-based services system having a reference database of Wi-Fi access points in a target area, each access point in the target area identified by a corresponding fixed size MAC address and each Wi-Fi access point positioned at a corresponding geographical location, a method of encoding MAC addresses and geographical locations of the access points to facilitate storage or transmission of the database contents to Wi-Fi enabled devices using the system, the method comprising the acts of:
-
(a) storing as an entry of the database a reset address entry, said reset address entry including a fixed-size MAC address and marker information to indicate that the entry has a complete MAC address for a corresponding access point;
(b) for each access point in at least a subset of access points in the target area, encoding a mathematical difference between (i) the MAC address of a corresponding access point and (ii) one of the other MAC addresses represented in the database, and storing said encoding, as delta information, in a corresponding delta address entry of the database, said delta address entry further including marker information to indicate that the entry has delta information from which a complete MAC address for a corresponding access point can be reconstituted; and
(c) for each entry in the database, including information to represent the geographical location of the corresponding access point. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. In a location-based services system having a reference database of Wi-Fi access points in a target area, each access point in the target area identified by a corresponding fixed size MAC address and each Wi-Fi access point positioned at a corresponding geographical location, a method of encoding MAC addresses and geographical locations of the access points to facilitate storage or transmission of the database contents to Wi-Fi enabled devices using the system, the method comprising the acts of:
-
(a) storing cluster identification information to identify a cluster having a known corresponding longitude and latitude;
(b) for each access point in at least a subset of access points in the target area, storing a longitude offset value and latitude offset value, the longitude offset value encoding the distance from the access point longitude to the known longitude of the identified cluster, and a latitude offset value to represent the distance from the access point latitude to the identified cluster latitude; and
(c) for each entry in the database, including information to represent the MAC address of the corresponding access point. - View Dependent Claims (13, 14)
-
-
15. A Wi-Fi enabled device comprising:
-
(a) first logic to determine the MAC addresses of Wi-Fi access points in the vicinity of the Wi-Fi enabled device, by exchanging Wi-Fi messages with Wi-Fi access points in the vicinity of the Wi-Fi enabled device;
(b) second logic to query a reference database of Wi-Fi access points, using the MAC addresses determined by the first logic, said second logic retrieving from the database information representing at least the physical location for each MAC address-identified Wi-Fi access point in the database; and
(c) third logic, using the queried physical location information from the second logic, to calculate the position of the Wi-Fi enabled device;
(d) wherein said reference database includes a reset entry having a complete MAC address for at least one Wi-Fi access point and includes a plurality of delta entries, each delta entry having a mathematical encoding representing a difference between the MAC address of a corresponding Wi-Fi access point and another MAC address represented in the database, each entry in the database further including information representing the physical location of a corresponding Wi-Fi access point. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25)
-
Specification