[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN103047988A - 压缩的导航地图数据 - Google Patents

压缩的导航地图数据 Download PDF

Info

Publication number
CN103047988A
CN103047988A CN2012103891051A CN201210389105A CN103047988A CN 103047988 A CN103047988 A CN 103047988A CN 2012103891051 A CN2012103891051 A CN 2012103891051A CN 201210389105 A CN201210389105 A CN 201210389105A CN 103047988 A CN103047988 A CN 103047988A
Authority
CN
China
Prior art keywords
block
map data
substring
tectonic
frequently
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
CN2012103891051A
Other languages
English (en)
Inventor
P.库纳思
M.海特曼
S.巴普蒂斯特
Cc.斯平德勒
S.米特拉基斯
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Harman Becker Automotive Systems GmbH
Original Assignee
Harman Becker Automotive Systems GmbH
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Harman Becker Automotive Systems GmbH filed Critical Harman Becker Automotive Systems GmbH
Publication of CN103047988A publication Critical patent/CN103047988A/zh
Pending legal-status Critical Current

Links

Images

Classifications

    • GPHYSICS
    • G01MEASURING; TESTING
    • G01CMEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/38Electronic maps specially adapted for navigation; Updating thereof
    • G01C21/3863Structures of map data
    • G01C21/387Organisation of map data, e.g. version management or database structures
    • GPHYSICS
    • G09EDUCATION; CRYPTOGRAPHY; DISPLAY; ADVERTISING; SEALS
    • G09BEDUCATIONAL OR DEMONSTRATION APPLIANCES; APPLIANCES FOR TEACHING, OR COMMUNICATING WITH, THE BLIND, DEAF OR MUTE; MODELS; PLANETARIA; GLOBES; MAPS; DIAGRAMS
    • G09B29/00Maps; Plans; Charts; Diagrams, e.g. route diagram
    • G09B29/003Maps
    • G09B29/004Map manufacture or repair; Tear or ink or water resistant maps; Long-life maps
    • GPHYSICS
    • G01MEASURING; TESTING
    • G01CMEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/26Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
    • G01C21/34Route searching; Route guidance
    • G01C21/3446Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
    • GPHYSICS
    • G01MEASURING; TESTING
    • G01CMEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/38Electronic maps specially adapted for navigation; Updating thereof
    • G01C21/3863Structures of map data
    • G01C21/387Organisation of map data, e.g. version management or database structures
    • G01C21/3881Tile-based structures
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90Details of database functions independent of the retrieved data types
    • G06F16/95Retrieval from the web
    • G06F16/954Navigation, e.g. using categorised browsing
    • HELECTRICITY
    • H03ELECTRONIC CIRCUITRY
    • H03MCODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/3084Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method

Landscapes

  • Engineering & Computer Science (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Remote Sensing (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Databases & Information Systems (AREA)
  • Automation & Control Theory (AREA)
  • Business, Economics & Management (AREA)
  • Educational Administration (AREA)
  • Educational Technology (AREA)
  • Mathematical Physics (AREA)
  • Data Mining & Analysis (AREA)
  • General Engineering & Computer Science (AREA)
  • Navigation (AREA)
  • Instructional Devices (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

本发明涉及用于从未压缩的导航地图数据产生压缩的导航地图数据库的方法,所述未压缩的导航地图数据包含导航数据的不同构造块,每个构造块处理所述导航数据的特定功能方面,每个块包含数据串,所述方法包括下列步骤:-为所述未压缩的导航地图数据的每个块确定该块的最频繁的子串,-对于每个块,将所述确定的该块的最频繁的子串存储在种子块中,-对于每个块,用对所述种子块的引用代替在所述串中的存储在所述种子块中的所述确定的最频繁的子串,从而为每个块产生压缩块,-为每个块存储所述压缩块和所述种子块,以便产生所述压缩的导航地图数据库。

Description

压缩的导航地图数据
技术领域
本发明涉及用于从未压缩的导航地图数据产生压缩的导航地图数据的方法,涉及配置成产生压缩的导航地图数据的压缩模块,涉及用于向用户提供导航信息的方法以及涉及向用户提供导航信息的导航系统。
背景技术
执行功能例如在两个位置之间的路线搜索的导航系统是已知的。现代导航系统也可提供额外的功能,例如用作在要求时输出关于名胜的信息的旅行指南,等等。一些导航系统甚至可包括旅行指南功能以输出详细的解释、m正文和/或多媒体形式。
此外,显示车辆周围环境的三维视野变得普遍,其中除了道路以外,建筑物等也显示在三维形式中。三维表示应便于找到正确的路。
给用户提供的不同类型的信息都存储在可移动数据存储单元例如CD ROM或DVD上,或信息在硬盘上被提供。
在本上下文中,存在对最小化导航地图数据所需的存储空间的需要,导航地图数据包括用于通知用户所需的信息的不同类型的信息。
发明内容
因此,存在对提供允许有效地减小存储导航地图数据所需的存储空间的方法的需要。
这个需要由独立权利要求的特征满足。在从属权利要求中,描述了另外的实施方案。
根据本发明的第一方面,提供了用于从未压缩的导航地图数据产生压缩的导航地图数据库的方法。未压缩的导航数据包含导航数据的不同构造块,每个构造块处理导航数据的特定功能方面,且每个构造块包含数据的字节序列或串。为未压缩的导航地图数据的不同构造块确定包含在构造块中的最频繁的子串。此外,对于构造块,构造块的所确定的最频繁的子串存储在至少一个种子块中。此外,在构造块中,用对所述至少一个种子块的引用(reference)代替在串中的存储在所述至少一个种子块中的所确定的最频繁的子串,从而产生压缩块。此外,压缩块和所述至少一个种子块被存储,以便产生压缩的导航地图数据库。
所有导航数据被视为属于构造块之一,每个构造块描述导航数据的预定功能方面,例如功能块是路线构造块、名称构造块。应理解,导航地图数据进一步分成不同的地理区,以及数据可另外划分成不同水平的细节。然而在本发明的上下文中,分成功能块被讨论,每个功能构造块描述在导航系统中使用的不同方面以向用户提供输出,例如驾驶推荐。作为例子,路线构造块提供路线选择计算的特征,名称构造块包含在地图上显示的街道的名称。在每个构造块中,数据存储在串中,且根据块的内容,串可以是街道名称或可提供图像的颜色信息。通过在构造块中确定存在于每个块中的最频繁的子串,可能组合所述至少一个种子块中的最频繁的子串,并在构造块中包括对所述至少一个种子块的来代替最频繁的子串。以这种方式,获得需要比未压缩的导航地图数据更小的存储容量的压缩块。从上文中很清楚,压缩程度取决于存储在种子块中的最频繁的子串的数量,以及哪些子串不再包含在压缩块中,但用对种子块的引用代替哪些子串。
在一个实施方案中,可能多个构造块的最频繁的子串存储在一个种子块中。这意味着,两个或更多个构造块的最频繁的子串可包含在一个种子块中。在另一实施方案中,然而可能为每个构造块确定包含最频繁的子串的种子块。在该实施方案中,对于每个构造块,种子块和压缩块存在,而在该实施方案中,对于每个构造块,压缩块存在,但不一定对于每个压缩块都有一个种子块。
此外,可能每个构造块在压缩之前分成几个部分,其中为构造块的每个部分确定最频繁的子串。构造块的不同部分的最频繁的子串可接着存储在单个种子块中。
优选地,代替的引用包含偏移信息和长度信息,偏移信息指示所代替的最频繁的子串位于种子块中什么地方。长度信息提供关于所代替的最频繁的子串的长度的信息。当压缩的导航地图数据应再次由导航系统使用时,对偏移信息和长度信息的引用可能是必要的。为了产生完整的信息,用存储在种子块中的最频繁的子串再次代替引用。对于该代替,在相应的代替的最频繁的子串存储在种子块中的地方使用该信息。此外,代替的最频繁的子串多长的信息被使用。
确定块的最频繁的子串的一个可能性是产生包含在块中的串的前缀树以及确定前缀树中的最频繁的子串。在前缀树中,在树中的串的位置定义它所相关的串。节点的所有后代具有与该节点相关的串的共同前缀。当频率值与每个节点相关时,确定块的最频繁的子串无疑是可能的。
未压缩的导航地图数据可包含不同的块、路线构造块、名称构造块、交通信息构造块、3D物体构造块、枢纽站视野构造块或数字地形构造块。
本发明此外涉及配置成产生压缩的导航地图数据的压缩模块,该模块包括包含未压缩的导航地图数据的第一数据库,未压缩的导航地图数据包含导航数据的不同的构造块,每个构造块处理导航地图数据的特定功能方面,且每个块包含数据的串。此外,提供在压缩模块中的第二数据库和配置成确定如上提到的压缩块和所述至少一个种子块的处理单元。
本发明此外涉及向用户提供导航信息的导航系统,导航系统包括包含压缩的导航地图数据的存储单元,压缩的导航地图数据包含导航地图数据的不同构造块,且每个构造块处理导航地图数据的特定功能方面。压缩的导航数据包含至少一个种子块和压缩块,所述至少一个种子块包含压缩块的最频繁的子串,其中在压缩块中,用对所述至少一个种子块的引用代替存储在所述至少一个种子块中的所确定的最频繁的子串。此外,导航系统包括向用户提供导航信息的信息单元。作为例子,导航信息可以是2D或3D的视觉输出。导航系统此外包括配置成从压缩的导航地图数据产生未压缩的导航地图数据的解压缩单元。解压缩单元对于每个构造块访问压缩块和所述至少一个种子块,并用所述至少一个种子块的相应的最频繁的子串代替包含在压缩块中的引用,以便产生未压缩的导航地图数据。解压缩单元此外配置成基于未压缩的导航地图数据产生导航信息,信息单元使用未压缩的导航地图数据来向用户提供导航信息。
在一个实施方案中,对于解压缩,种子块用作压缩和解压缩的虚拟前缀,以简化压缩和解压缩算法。自然地,在没有每个块的种子块的情况下,解压缩不是可能的。这也提供导航地图数据的轻量级加密,如果种子块与压缩块分开地被存储,因为当没有为压缩块提供种子块时导航地图数据的使用不是可能的。本发明此外提供了用于向用户提供导航信息的方法,其中未压缩的导航地图数据从压缩的导航数据产生,其中通过访问压缩块和所述至少一个种子块并通过用存储在所述至少一个种子块中的相应的最频繁的子串代替包含在压缩块中的引用来为每个块产生未压缩的导航数据。用户的导航信息接着基于未压缩的导航地图数据而产生,且导航信息基于未压缩的导航地图数据提供给用户。
附图说明
当结合附图阅读时,从实施方案的下面的详细描述中,前述和其它特征和实施方案将变得更明显。在附图中,
图1是配置成产生压缩的导航地图数据的压缩模块的示意图,
图2是包含为了产生压缩的地图导航数据而执行的步骤的流程图,
图3是使用以图1的系统产生的压缩的导航地图数据的导航系统的示意图,以及
图4是包括为了在使用之前对压缩的导航地图数据解压缩而执行的步骤的流程图。
具体实施方式
在图1中,示出了能够从未压缩的导航地图数据产生压缩的导航地图数据的压缩模块的示意图。压缩模块包括第一数据库110,其中数据111的不同块存储在第一数据库110中。存储在数据库110中的地图数据覆盖某个地理区域。此外,导航地图数据可例如通过将地理区域分成瓦片来分成不同的地理区。在图1所示的实施方案中,所示的实施方案并不反映分成不同的地理区。在所示实施方案中,考虑到地图数据的功能方面来执行导航地图数据的划分。作为例子,图1所示的第一个块可以是路线选择构造块,路线选择块将用于路线选择应用的地图数据的特征聚集在一起。路线选择构造块可包含将用于计算路线的道路网络的表示。图1所示的第二个构造块可以是向地图上示出的不同物体特别提供名称的名称构造块。图1所示的构造块3可以是将地图显示应用的特征聚集在一起的地图显示构造块。它可包含提供二维地图以及其几何数据所必需的特征。应理解,可在数据库110中提供更多的构造块,例如交通信息构造块、PoI(名胜)构造块、语音构造块、3D物体构造块等。处理单元110访问第一数据库并处理块111中的每个,使得它预先计算包含在每个块中的最频繁的子串。存储在块中的信息条是串。处理单元将识别在每个块中的多个最频繁的子串。块的最频繁的子串的数量可取决于包含在每个块中的串的数量和数据的类型,该数量例如在100和大约5000之间变化。可通过为每个块产生前缀树并通过识别在这个前缀树中的最频繁的子串来确定最频繁的子串。在本上下文中,子串是串的子单元。在名称构造块中,最频繁的子串可包含以不同的名称出现的最频繁的字符序列。
最多的子串被识别为将被代替的最频繁的子串,压缩率将更高。处理单元100现在将用对块指定的种子块的引用代替出现在不同的块111中的所确定的最频繁的子串,所确定的最频繁的子串存储在该种子块中。具有最频繁的子串的这个种子块可起待压缩的数据的(虚拟)前缀的作用。处理单元将压缩的数据存储在第二数据库中。如图1所示,为块111产生包括块1的最频繁的子串的种子块121a以及压缩块122a,在压缩块122a中,用对种子块121a的引用代替包含在种子块121a中的最频繁的子串。该引用此外包含指示省略的子串存储在种子块内的哪个位置的偏移信息。此外,该引用包含指示所代替的子串的长度的长度信息。此外,为数据库110的块2产生种子块121b和压缩块122b。种子块121c包括块3的最频繁的子串,且压缩块122c包括其它未代替的串以及对种子块的引用。
在所示实施方案中,为包含在第一存储单元110中的构造块中的每个构造块产生压缩的导航地图数据。然而,应理解,不一定为包含在数据库110中的每个块都产生压缩块和种子块。作为例子,如果数据库110的块111之一与其它块比较在尺寸上小得多,则这样的块的压缩可被省略。
在图1所示的实施方案中,为每个构造块产生一个种子块。然而,也可能两个或更多个构造块的最频繁的子串存储在单个种子块中,在该实施方案中,一个种子块例如种子块121a将包括压缩块1和压缩块2的最频繁的子串。
此外,可能块111在压缩之前分成不同的部分,其中为构造块的不同部分中的每个确定最频繁的子串,以便为每个压缩块产生压缩部分例如图1中的部分125、126和127。在该实施方案中,不同的压缩部分125-127的最频繁的子串存储在一个种子块中。在不同的压缩部分中的压缩块的划分可与多于一个的构造块的最频繁的子串存储在单个种子块中的实施方案组合。因此,在该实施方案中,压缩块1的压缩部分和例如压缩块2的压缩部分将存储在单个种子块中。然而,也可能为包含压缩部分的每个压缩块产生种子块。
在图2中,概述了为了产生压缩的导航地图数据而执行的步骤。方法在步骤20中开始,且在步骤21中,为包含在块中的串确定最频繁的子串。在下一步骤22中,在步骤21中确定的最频繁的子串在种子块中被存储并聚集在一起。此外,当将被存储在种子块中的子串的数量被确定时,用对种子块的引用代替在块中的三个子串(步骤23)。在步骤24中,接着存储种子块和压缩块。该方法在步骤25结束。
在图1所示的实施方案中,第一数据库110和第二数据库120被示为单独的实体。应理解,第一数据库和第二数据库可由单个物理存储单元表示,使得未压缩块111存储在与相应的压缩数据相同的物理存储单元上。
存储在存储块120中的压缩的导航地图数据可由图3所示的导航系统使用。图3所示的导航系统300包括存储单元310,具有种子块121和相应的压缩块122的压缩的导航地图数据存储在存储单元310中。存储在数据库310中的数据相应于存储在图1的数据库120中的数据。数据库310可包括各种存储器或存储介质的任一个或任何组合,例如随机存取存储器、闪存或硬盘,但也可以是可移动存储器,例如光盘、DVD、存储卡等。导航系统此外包括配置成计算从第一位置到第二位置的最快或最短路线的路线计算单元320。用户可经由输入单元330控制导航系统的运行。输入单元可包括触觉设备,例如可被压下或旋转的按钮。输入单元此外可包含允许使用语音命令控制导航系统的运行的语音识别模块。由路线计算单元计算的信息可显示在显示器340上。此外,也可使用话音命令来输出驾驶推荐。可提供接收卫星信号的天线350,其中用于计算导航系统的位置的信号被接收。导航系统如何计算从规定的位置到期望目的地的方法在本领域中是已知的,且将不被详细描述。为了清楚起见,只示出导航系统的对本发明的理解有帮助的部件。应理解,导航系统可包含不同的模块和没有在图3的示意图中示出的另外的特征。
此外,不同的模块可通过软件或硬件或通过软件和硬件的组合来合并。
导航系统还包括解压缩单元,其在存储在数据库310中的导航数据可由路线计算单元使用之前或在它们可显示在显示器340上之前对它们进行解压缩。解压缩单元用存储在相应的种子块121a、121b中的子串代替压缩块122a、122b中的引用。
换句话说,对于解压缩,种子块或子串块用作压缩的数据块的虚拟前缀,当它与种子块一起被存储为虚拟前缀时。如也可从上文看到的,导航地图数据的解压缩在没有种子块的情况下是不可能的。这意味着对于不同的功能块,种子块和压缩块的使用提供对数据的加密,因为导航数据不能在没有相应的种子块的情况下被使用。当解压缩单元350通过用相应的子串代替所有引用来对块解压缩时,未压缩的导航地图数据可接着由路线计算单元和导航系统的其它模块使用。
当种子块与压缩块分开地被存储时,第一加密被获得。此外,可能存储该种子块或多个种子块以及压缩块,并使用已知的加密方法例如AES(高级加密标准)或RSA(Rivest Shamir和Adleman Encryption)来对种子块进行加密。
在图4中,概述了用于解压缩的不同步骤。方法在步骤40中开始,且在步骤41中,访问种子块,以及在步骤42中,访问压缩块。在每个压缩块中,在相应的种子块中识别由引用代替的子串,且将所代替的子串再次引入压缩块中,以便产生未压缩块(步骤43)。基于未压缩的导航地图数据,将被输出给用户的导航信息可在步骤44中产生。该方法在步骤45中结束。
如可从上文中看到的,本发明提供导航地图数据的有效压缩。同时,压缩方法提供数据的加密,因为导航地图数据不能在没有相应的种子块的情况下被使用。为了改进加密,此外可使用已知的加密方法来加密在种子块中提供的信息。

Claims (12)

1.一种用于从未压缩的导航地图数据产生压缩的导航地图数据库的方法,所述未压缩的导航地图数据包含导航数据的不同构造块(111),每个构造块处理所述导航数据的特定功能方面,且每个块包含数据串,所述方法包括下列步骤:
-为所述未压缩的导航地图数据的构造块确定包含在所述构造块中的最频繁的子串,
-对于所述构造块,将所述确定的最频繁的子串存储在至少一个种子块(121)中,
-在所述构造块中,用对所述至少一个种子块的引用代替在所述串中的存储在所述至少一个种子块(121)中的所述确定的最频繁的子串,从而为每个构造块产生压缩块(122),
-存储所述压缩块(122)和所述至少一个种子块(121),以便产生所述压缩的导航地图数据库。
2.如权利要求1所述的方法,其中所述代替的引用包含偏移信息和长度信息,所述偏移信息指示所述代替的最频繁的子串位于所述种子块中什么地方,所述长度信息指示所述代替的最频繁的子串的长度。
3.如权利要求1或2所述的方法,其中通过确定块的前缀树并通过确定所述前缀树中的最频繁的子串来产生所述块的所述最频繁的子串。
4.如前述权利要求中任一项所述的方法,其中所述未压缩的导航地图数据包含下列块中的至少一个:路线构造块、名称构造块、交通信息构造块、3d物体构造块、枢纽站视野构造块或数字地形构造块。
5.如前述权利要求中任一项所述的方法,其中多个构造块的所述最频繁的子串存储在一个种子块中。
6.如权利要求1至4中任一项所述的方法,其中为每个构造块确定包含所述最频繁的子串的种子块。
7.如前述权利要求中任一项所述的方法,其中每个构造块在压缩之前分成几个部分,其中为构造块的每个部分确定所述最频繁的子串,构造块的所述不同部分的所述最频繁的子串存储在一个种子块中。
8.一种配置成产生压缩的导航地图数据库的压缩模块,所述模块包括:
-第一数据库(110),其包含未压缩的导航地图数据,所述未压缩的导航地图数据包含导航数据的不同的构造块(111),每个构造块处理导航地图数据的特定功能方面,每个构造块包含数据串,
-第二数据库(120),
-处理单元(100),其配置成为所述未压缩的导航地图数据的所述构造块(111)确定所述构造块的最频繁的子串,配置成对于所述构造块将所述构造块的所述确定的最频繁的子串存储在至少一个种子块(121)中,配置成对于所述构造块用对所述至少一个种子块(121)的引用代替在所述串中的存储在所述至少一个种子块中的所述确定的最频繁的子串,从而为每个构造块产生压缩块(122),并配置成将压缩块(122)和所述至少一个种子块(121)存储在所述第二数据库(122)中,以便产生所述压缩的导航地图数据库。
9.如权利要求8所述的压缩模块,其中所述处理单元(100)配置成在所述代替的引用中包括偏移信息和长度信息,所述偏移信息指示所述代替的最频繁的子串位于所述种子块中什么地方,所述长度信息指示所述代替的最频繁的子串的长度。
10.如权利要求8或9所述的压缩模块,其中所述处理单元(100)配置成通过产生块的前缀树并通过确定所述前缀树中的所述最频繁的子串来确定所述块的所述最频繁的子串。
11.一种向用户提供导航信息的导航系统(300),所述系统包括:
-存储单元(310),其包含压缩的导航地图数据的导航地图数据库,所述压缩的导航数据包含导航数据的不同构造块,每个构造块处理所述导航数据的特定功能方面,每个构造块包含数据串,所述地图数据库包含至少一个种子块(121)和压缩块(122),所述种子块(121)包含至少一个构造块的所述最频繁的子串,其中在所述压缩块(122)中,用对所述至少一个种子块的引用代替存储在所述至少一个种子块(121)中的所述确定的最频繁的子串,
-信息单元(340),其向所述用户提供所述导航信息,
-解压缩单元(350),其配置成从所述压缩的导航地图数据产生未压缩的导航地图数据,其中所述解压缩单元(350)配置成访问所述压缩块(122)和所述至少一个种子块(121),用存储在所述至少一个种子块(121)中的所述相应的最频繁的子串代替包含在所述压缩块(122)中的引用,以便产生所述未压缩的导航地图数据,并配置成基于所述未压缩的导航地图数据产生所述导航信息,其中所述信息单元(340)使用所述未压缩的导航地图数据来向所述用户提供所述导航信息。
12.一种向用户提供导航信息的方法,所述方法包括下列步骤:
-从压缩的导航地图数据产生未压缩的导航地图数据,所述压缩的导航地图数据包含导航地图数据的不同构造块,每个构造块处理所述导航地图数据的特定功能方面,每个构造块包含数据串,所述压缩的导航数据包含至少一个种子块(121)和所述压缩块(122),所述至少一个种子块(121)包含所述构造块的所述最频繁的子串,其中在所述压缩块(122)中,用对所述至少一个种子块(121)的引用代替存储在所述至少一个种子块中的所述确定的最频繁的子串,其中通过访问所述压缩块(122)和所述至少一个种子块(121)并通过用存储在所述至少一个种子块中的所述相应的最频繁的子串代替包含在所述压缩块中的引用来产生所述未压缩的导航数据,以便产生所述未压缩的导航地图数据,
-基于所述未压缩的导航地图数据产生所述导航信息,并基于所述未压缩的导航地图数据向所述用户提供所述导航信息。
CN2012103891051A 2011-10-14 2012-10-15 压缩的导航地图数据 Pending CN103047988A (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
EP11185269.5A EP2581704A1 (en) 2011-10-14 2011-10-14 Method for compressing navigation map data
EP11185269.5 2011-10-14

Publications (1)

Publication Number Publication Date
CN103047988A true CN103047988A (zh) 2013-04-17

Family

ID=44905491

Family Applications (1)

Application Number Title Priority Date Filing Date
CN2012103891051A Pending CN103047988A (zh) 2011-10-14 2012-10-15 压缩的导航地图数据

Country Status (7)

Country Link
US (1) US20160320196A9 (zh)
EP (1) EP2581704A1 (zh)
JP (1) JP6116185B2 (zh)
KR (1) KR102050576B1 (zh)
CN (1) CN103047988A (zh)
BR (1) BR102012026011A2 (zh)
CA (1) CA2791033A1 (zh)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN110914777A (zh) * 2016-12-30 2020-03-24 迪普迈普有限公司 用于自主车辆的高清地图以及路线存储管理系统

Families Citing this family (27)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8811431B2 (en) 2008-11-20 2014-08-19 Silver Peak Systems, Inc. Systems and methods for compressing packet data
US8489562B1 (en) 2007-11-30 2013-07-16 Silver Peak Systems, Inc. Deferred data storage
US8929402B1 (en) * 2005-09-29 2015-01-06 Silver Peak Systems, Inc. Systems and methods for compressing packet data by predicting subsequent data
US8755381B2 (en) 2006-08-02 2014-06-17 Silver Peak Systems, Inc. Data matching using flow based packet data storage
US8885632B2 (en) 2006-08-02 2014-11-11 Silver Peak Systems, Inc. Communications scheduler
US8307115B1 (en) 2007-11-30 2012-11-06 Silver Peak Systems, Inc. Network memory mirroring
US8743683B1 (en) 2008-07-03 2014-06-03 Silver Peak Systems, Inc. Quality of service using multiple flows
US10805840B2 (en) 2008-07-03 2020-10-13 Silver Peak Systems, Inc. Data transmission via a virtual wide area network overlay
US9717021B2 (en) 2008-07-03 2017-07-25 Silver Peak Systems, Inc. Virtual network overlay
US10164861B2 (en) 2015-12-28 2018-12-25 Silver Peak Systems, Inc. Dynamic monitoring and visualization for network health characteristics
US9130991B2 (en) 2011-10-14 2015-09-08 Silver Peak Systems, Inc. Processing data packets in performance enhancing proxy (PEP) environment
US9626224B2 (en) 2011-11-03 2017-04-18 Silver Peak Systems, Inc. Optimizing available computing resources within a virtual environment
DE102013209168A1 (de) * 2013-05-17 2014-11-20 Bayerische Motoren Werke Aktiengesellschaft Verfahren zum Betreiben eines Navigationssystems, Navigationssystem und Kraftfahrzeug
US9948496B1 (en) 2014-07-30 2018-04-17 Silver Peak Systems, Inc. Determining a transit appliance for data traffic to a software service
US9875344B1 (en) 2014-09-05 2018-01-23 Silver Peak Systems, Inc. Dynamic monitoring and authorization of an optimization device
KR102258844B1 (ko) * 2015-12-30 2021-05-28 에스케이플래닛 주식회사 네비게이션서비스장치 및 그 동작 방법
US10432484B2 (en) 2016-06-13 2019-10-01 Silver Peak Systems, Inc. Aggregating select network traffic statistics
US9967056B1 (en) 2016-08-19 2018-05-08 Silver Peak Systems, Inc. Forward packet recovery with constrained overhead
US10480951B2 (en) * 2016-10-18 2019-11-19 Microsoft Technology Licensing, Llc Generating routes using information from trusted sources
US10892978B2 (en) 2017-02-06 2021-01-12 Silver Peak Systems, Inc. Multi-level learning for classifying traffic flows from first packet data
US10257082B2 (en) 2017-02-06 2019-04-09 Silver Peak Systems, Inc. Multi-level learning for classifying traffic flows
US10771394B2 (en) 2017-02-06 2020-09-08 Silver Peak Systems, Inc. Multi-level learning for classifying traffic flows on a first packet from DNS data
US11044202B2 (en) 2017-02-06 2021-06-22 Silver Peak Systems, Inc. Multi-level learning for predicting and classifying traffic flows from first packet data
US11212210B2 (en) 2017-09-21 2021-12-28 Silver Peak Systems, Inc. Selective route exporting using source type
JP7542294B2 (ja) 2017-12-01 2024-08-30 株式会社ソニー・インタラクティブエンタテインメント 情報処理装置およびゲーム画像配信方法
US10637721B2 (en) 2018-03-12 2020-04-28 Silver Peak Systems, Inc. Detecting path break conditions while minimizing network overhead
CN110048725B (zh) * 2019-05-14 2023-07-07 四川九洲空管科技有限责任公司 一种基于taws系统的地形数据压缩解压缩算法

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6670897B1 (en) * 2002-10-03 2003-12-30 Motorola, Inc. Compression/decompression techniques based on tokens and Huffman coding
US20050288836A1 (en) * 2004-03-16 2005-12-29 Glass Paul M Geographic information data base engine
WO2011095603A2 (en) * 2010-02-04 2011-08-11 Tomtom International B.V. Map storage for navigation systems
CN102168983A (zh) * 2010-02-12 2011-08-31 三星电子株式会社 用于发送和接收地图数据的方法和装置

Family Cites Families (20)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6393149B2 (en) * 1998-09-17 2002-05-21 Navigation Technologies Corp. Method and system for compressing data and a geographic database formed therewith and methods for use thereof in a navigation application program
US6829690B1 (en) * 2000-05-23 2004-12-07 Navteq North America, Llc Method and system for accessing spatially organized geographic data in blocks
JP2002311821A (ja) * 2001-04-13 2002-10-25 Mitsubishi Electric Corp ナビゲーションにおける地図表示方法およびナビゲーション装置
US6978206B1 (en) * 2002-06-21 2005-12-20 Infogation Corporation Distributed navigation system
US7054888B2 (en) * 2002-10-16 2006-05-30 Microsoft Corporation Optimizing media player memory during rendering
EP1544829B1 (en) * 2003-12-19 2017-02-15 Samsung Electronics Co., Ltd. Navigation system and navigation method
JP3842799B2 (ja) * 2004-06-15 2006-11-08 株式会社ザナヴィ・インフォマティクス 地図データ提供装置
US20060064671A1 (en) * 2004-09-20 2006-03-23 Klaus Herter Creating and using a building block
WO2006123429A1 (ja) * 2005-05-20 2006-11-23 Fujitsu Limited 情報検索方法、装置、プログラム、該プログラムを記録した記録媒体
US7512487B1 (en) * 2006-11-02 2009-03-31 Google Inc. Adaptive and personalized navigation system
US7769729B2 (en) * 2007-05-21 2010-08-03 Sap Ag Block compression of tables with repeated values
US20090216732A1 (en) * 2008-02-27 2009-08-27 Kyte Feng Method and apparatus for navigation system for searching objects based on multiple ranges of desired parameters
JP5782214B2 (ja) * 2008-05-30 2015-09-24 富士通株式会社 情報検索プログラム、情報検索装置および情報検索方法
US8214404B2 (en) * 2008-07-11 2012-07-03 Avere Systems, Inc. Media aware distributed data layout
US7669147B1 (en) * 2009-01-02 2010-02-23 International Business Machines Corporation Reorienting navigation trees based on semantic grouping of repeating tree nodes
JP5054734B2 (ja) * 2009-06-26 2012-10-24 クラリオン株式会社 カーナビゲーション装置、プログラムおよび地図データ更新方法
US20110087425A1 (en) * 2009-10-08 2011-04-14 Telenav, Inc. Navigation system with map compression and method of operation thereof
US8667383B2 (en) * 2010-03-09 2014-03-04 David Schnitt Unified electronic forms management system
US20120191231A1 (en) * 2010-05-04 2012-07-26 Shazam Entertainment Ltd. Methods and Systems for Identifying Content in Data Stream by a Client Device
US9690770B2 (en) * 2011-05-31 2017-06-27 Oracle International Corporation Analysis of documents using rules

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6670897B1 (en) * 2002-10-03 2003-12-30 Motorola, Inc. Compression/decompression techniques based on tokens and Huffman coding
US20050288836A1 (en) * 2004-03-16 2005-12-29 Glass Paul M Geographic information data base engine
WO2011095603A2 (en) * 2010-02-04 2011-08-11 Tomtom International B.V. Map storage for navigation systems
CN102168983A (zh) * 2010-02-12 2011-08-31 三星电子株式会社 用于发送和接收地图数据的方法和装置

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN110914777A (zh) * 2016-12-30 2020-03-24 迪普迈普有限公司 用于自主车辆的高清地图以及路线存储管理系统
CN110914777B (zh) * 2016-12-30 2023-05-26 辉达公司 用于自主车辆的高清地图以及路线存储管理系统

Also Published As

Publication number Publication date
CA2791033A1 (en) 2013-04-14
US20160320196A9 (en) 2016-11-03
KR20130040707A (ko) 2013-04-24
US20140108360A1 (en) 2014-04-17
KR102050576B1 (ko) 2019-11-29
EP2581704A1 (en) 2013-04-17
BR102012026011A2 (pt) 2013-11-26
JP2013088815A (ja) 2013-05-13
JP6116185B2 (ja) 2017-04-19

Similar Documents

Publication Publication Date Title
CN103047988A (zh) 压缩的导航地图数据
JP5675751B2 (ja) ナビゲーションデータベースを構造化するための技法
US9546872B1 (en) Hybrid road network and grid based spatial-temporal indexing under missing road links
CN102419752B (zh) 一种工业数据库报文存储方法
JP5895545B2 (ja) プログラム、圧縮ファイル生成方法、圧縮符号伸張方法、情報処理装置、および記録媒体
CN100595758C (zh) 游戏地图的存储方法及系统、游戏地图的获取方法及系统
CN111247518A (zh) 数据库分片
CN101010699A (zh) 纹理编码装置、纹理解码装置、方法及程序
CN102947676A (zh) 导航装置及在其上实行的方法
KR20090011000A (ko) 데이터 갱신 시스템, 네비게이션 장치, 서버 장치, 및 데이터 갱신 방법
JP2011166750A (ja) マップデータ送受信装置及びナビゲーションシステムの動作方法
US9441983B2 (en) Navigation system with content curation mechanism and method of operation thereof
CN110879807A (zh) 用于快速地并且有效地访问数据的文件格式
US9453741B2 (en) Navigation system with indexed term searching and method of operation thereof
US12093341B2 (en) Method and apparatus for processing matrix data through relaxed pruning
CN109117433B (zh) 一种索引树对象的创建及其索引方法和相关装置
JP2022019682A (ja) 動的メディアを生成するシステム及び方法
KR20140038441A (ko) 압축 매치 열거 기법
CN105930104A (zh) 数据存储方法和装置
TWI543008B (zh) 資料管理設備及資料管理方法
KR101242860B1 (ko) 누적 이동 평균에 기반하여 다원 탐색 트리의 노드를 분할하는 방법 및 장치
US9214097B2 (en) Method for creating a directory of road sections, method for ascertaining all road sections within a search area, and computer program
JP5261439B2 (ja) データ更新システム、ナビゲーション装置、及びデータ更新方法
TW201211509A (en) Navigation devices
Lv et al. A data frame based spatiotemporal indexing algorithm for moving objects

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
RJ01 Rejection of invention patent application after publication
RJ01 Rejection of invention patent application after publication

Application publication date: 20130417