Back to results
US 9,436,702 B2Granted
Navigation system data base system
AssigneeHarman Becker Automotive Systems GmbH
InventorsAlexey Pryakhin, Peter Kunath, Juergen Welscher
Life of this patent
Estimating the term…
Abstract
A system for performing a similarity search in a navigation device data base uses a metric index structure. The index structure includes a plurality of nodes. When a query object is received, a node of the index structure which is associated with at least one object is accessed. A distance between the query object and the at least one object is determined in accordance with a distance metric. Based on the determined distance, another node of the index structure is selectively accessed.
Claims19
A method of performing a similarity search in a navigation device database using an index structure, the database including a plurality of objects and the index structure including a plurality of nodes, the method comprising:
- receiving a query object at one of a vehicle interface and an input interface of a navigation device, the navigation device further comprising a storage device storing the index structure;
- accessing a first node of the index structure that includes at least one object of the plurality of objects, wherein the plurality of objects stored in the database comprise a plurality of phoneme strings, and the plurality of nodes included in the index structure comprise leaf nodes respectively associated with at least one phoneme string, wherein the index structure further includes a distance information on distances between the at least one object and other objects of the index structure, wherein the first node is associated with a plurality of objects, wherein the distance information has stored therein, for each of the plurality of objects, a coverage radius that defines an upper bound on distances between a respective one of the plurality of objects and any object included in a sub-tree of the index structure associated with the respective one of the plurality of objects;
- for each of the at least one object included in the first node, determining a respective distance between the query object and the object, the distance being determined in accordance with a distance metric;
- determining, for each of the plurality of objects, whether the distance between the query object and the respective object is less than a sum of a fixed predetermined search radius and the coverage radius of the respective object stored in the first node of the index structure;
- and
- selectively accessing a second node of the index structure based on the distance information and the determined distances.
3 more elements
A navigation device, comprising:
- a storage device storing an index structure for a database that includes a plurality of objects that comprise a plurality of phoneme strings, the index structure including a plurality of nodes, the plurality of nodes including leaf nodes respectively associated with at least one phoneme string;
- and
- a processor coupled to the storage device and configured to perform a similarity search for a query object, wherein performing the similarity search comprises:
- receiving the query object at one of a vehicle interface and an input interface of the navigation device;
- accessing a first node of the index structure that includes at least one object of the plurality of objects;
- determining a distance between the query object and the at least one object in accordance with a distance metric;
- determining whether the distance is less than a sum of a fixed predetermined search radius and a coverage radius of the object that is stored in the index structure, the coverage radius stored in the index structure and representing an upper bound on a distance between the object and any object included in a sub-tree of the index structure associated with the object;
- searching the sub-tree associated with the object;
- and
- selectively accessing a second node of the index structure based on the determined distance.
7 more elements
A method of generating a metric index structure for a navigation device database that includes a plurality of objects, the method comprising:
- generating, via a processor, directory nodes of the index structure that include a pointer to other nodes of the index structure;
- and
- generating, via the processor, leaf nodes of the index structure, wherein the plurality of objects stored in the database comprise a plurality of phoneme strings, and at least a fraction of the directory nodes being associated with a phoneme string, wherein generating directory nodes and leaf nodes includes:
- for two or more pairs of the objects, determining a respective distance between the objects of each pair according to a distance metric, and
- identifying, based on the determined distances, objects that are included in a directory node and objects that are included in a leaf node;
- storing distance information derived from the determined distances in at least one of the directory nodes or the leaf nodes, wherein the distance information stored for at least one of the directory nodes includes a coverage radius representing an upper bound on a distance between an object included in the directory node and any object included in a sub-tree of the index structure associated with the object;
- and
- storing the index structure in a storage device of the navigation device, wherein the navigation device is further configured to perform a similarity search using the stored index structure in response to receiving a query object at one of a vehicle interface and an input interface of the navigation device.
5 more elements
Dependencies are inferred from the claim text.