(57)【特許請求の範囲】
【請求項１】
ガソリンスタンドＰＯＩの自動発見装置によって実行される方法であって、
車載診断システムであるＯＢＤ機器がアップロードした、自動車の位置情報と、車速と、ガソリン残量とを含む情報を収集する情報収集ステップと、
前記車速及び前記ガソリン残量の情報に基づいて油量急増点を決定するステップであって、前記油量急増点は、前記ＯＢＤ機器を有する自動車を抽象化し、油量が急増する自動車が対応するポイントである油量急増点決定ステップと、
クラスタリングアルゴリズムによって、前記油量急増点の対応するＯＢＤ機器からアップロードされた位置情報に基づいて、前記油量急増点をクラスタリングするクラスタリング処理ステップと、
クラスタリング結果に基づいてガソリンスタンドＰＯＩが存在する位置領域を決定する位置決定ステップと、を含む
ことを特徴とする前記方法。
【請求項２】
前記情報収集ステップは、複数のＯＢＤ機器がアップロードした情報を設定時間おきに収集するステップを含み、
前記油量急増点決定ステップは、各ＯＢＤ機器に対して、現在のＯＢＤ機器のアップロードしたガソリン残量に基づいて前記現在のＯＢＤ機器に対応する油量急増程度値を計算し、算出した油量急増程度値が第１設定閾値以上で、且つ前記現在のＯＢＤ機器のアップロードした車速が第２設定閾値以下である場合、前記現在のＯＢＤ機器の対応するポイントを油量急増点として決定するステップと、を含む
ことを特徴とする請求項１に記載の方法。
【請求項３】
下式      
【数１】
0006651006.tif 000010
を用いて油量急増程度値を計算し、
ここで、Ｗは油量急増程度値を示し、ｎは前記設定時間を示し、単位は秒であり、Ｏ１〜Ｏｎはそれぞれ現在のｎ秒の期間内秒ごとのガソリン残量を示すことを特徴とする請求項２に記載の方法。
【請求項４】
前記クラスタリングアルゴリズムはｇｅｏハッシュアルゴリズムであり、前記位置情報は経緯度情報であり、
前記位置決定ステップは、
クラスタリング後に生成したｇｅｏハッシュグリッドにおけるポイントの数に基づいて前記ｇｅｏハッシュグリッドにおいてガソリンスタンドＰＯＩが存在するか否かを判断する判断ステップと、
前記ｇｅｏハッシュグリッドにおいてガソリンスタンドＰＯＩが存在する場合、前記ｇｅｏハッシュグリッドが示す経緯度範囲領域をガソリンスタンドＰＯＩの存在する位置領域と決定するステップと、を含む
ことを特徴とする請求項１に記載の方法。
【請求項５】
前記判断ステップは、
前記ｇｅｏハッシュグリッドにおけるポイントの数が第３設定閾値に達した場合、前記ｇｅｏハッシュグリッドにガソリンスタンドＰＯＩが存在すると決定し、前記ｇｅｏハッシュグリッドにおけるポイントの数が第３設定閾値に達していない場合、前記ｇｅｏハッシュグリッドにガソリンスタンドＰＯＩが存在しないと決定するステップをさらに含む
ことを特徴とする請求項４に記載の方法。
【請求項６】
ｇｅｏハッシュアルゴリズムによって、前記油量急増点の対応するＯＢＤ機器からアップロードされた位置情報に基づいて、前記油量急増点をクラスタリングする時に、用いられるｇｅｏハッシュ文字列の長さが７である
ことを特徴とする請求項４又は５に記載の方法。
【請求項７】
車載診断システムであるＯＢＤ機器がアップロードした、自動車の位置情報と、車速と、ガソリン残量とを含む情報を収集する情報収集モジュールと、
前記車速及び前記ガソリン残量の情報に基づいて油量急増点を決定するモジュールであって、前記油量急増点は、前記ＯＢＤ機器を有する自動車を抽象化し、油量が急増する自動車が対応するポイントである油量急増点決定モジュールと、
クラスタリングアルゴリズムによって、前記油量急増点の対応するＯＢＤ機器からアップロードされた位置情報に基づいて、前記油量急増点をクラスタリングするクラスタリング処理モジュールと、
クラスタリング結果に基づいてガソリンスタンドＰＯＩが存在する位置領域を決定する位置決定モジュールと、を備える
ことを特徴とするガソリンスタンドＰＯＩの自動発見装置。
【請求項８】
前記情報収集モジュールは、複数のＯＢＤ機器がアップロードした、車速及びガソリン残量を含む情報を設定時間おきに収集し、
前記油量急増点決定モジュールは、各ＯＢＤ機器に対して、現在のＯＢＤ機器がアップロードしたガソリン残量に基づいて前記現在のＯＢＤ機器に対応する油量急増程度値を計算し、算出した油量急増程度値が第１設定閾値以上で、且つ前記現在のＯＢＤ機器のアップロードした車速が第２設定閾値以下である場合、前記現在のＯＢＤ機器の対応するポイントを油量急増点として決定する
ことを特徴とする請求項７に記載の装置。
【請求項９】
前記油量急増点決定モジュールは、下式      
【数２】
0006651006.tif 000011
を用いて油量急増程度値を計算し、
ここで、Ｗは油量急増程度値を示し、ｎは前記設定時間を示し、単位は秒であり、Ｏ１〜Ｏｎはそれぞれ現在のｎ秒の期間内秒ごとのガソリン残量を示す
ことを特徴とする請求項８に記載の装置。
【請求項１０】
前記クラスタリングアルゴリズムはｇｅｏハッシュアルゴリズムであり、前記位置情報は経緯度情報であり、
前記位置決定モジュールは、
クラスタリング後に生成したｇｅｏハッシュグリッドにおけるポイントの数に基づいて前記ｇｅｏハッシュグリッドにおいてガソリンスタンドＰＯＩが存在するか否かを判断するＰＯＩ判断ユニットと、
前記ＰＯＩ判断ユニットが、前記ｇｅｏハッシュグリッドにガソリンスタンドＰＯＩが存在すると判断した時に、前記ｇｅｏハッシュグリッドが示す経緯度範囲領域をガソリンスタンドＰＯＩの存在する位置領域と決定するＰＯＩ決定ユニットと、を備える
ことを特徴とする請求項７に記載の装置。
【請求項１１】
前記ＰＯＩ判断ユニットは、
前記ｇｅｏハッシュグリッドにおけるポイントの数が第３設定閾値に達した場合、前記ｇｅｏハッシュグリッドにガソリンスタンドＰＯＩが存在すると決定し、前記ｇｅｏハッシュグリッドにおけるポイントの数が第３設定閾値に達していない場合、前記ｇｅｏハッシュグリッドにガソリンスタンドＰＯＩが存在しないと決定する
ことを特徴とする請求項１０に記載の装置。
【請求項１２】
前記クラスタリング処理モジュールは、ｇｅｏハッシュアルゴリズムによって、前記油量急増点の対応するＯＢＤ機器からアップロードされた位置情報に基づいて、前記油量急増点をクラスタリングする時に、用いられるｇｅｏハッシュ文字列の長さは７である
ことを特徴とする請求項１０又は１１に記載の装置。
【請求項１３】
１つ以上のモジュールが記憶される不揮発性コンピュータ記憶媒体であって、前記１つ以上のモジュールが、ガソリンスタンドＰＯＩの自動発見方法を実行する装置により実行される時に、前記装置に、次の動作をさせ、
ＯＢＤ機器がアップロードした、自動車の位置情報と、車速と、ガソリン残量とを含む情報を収集し、
前記車速及び前記ガソリン残量の情報に基づいて油量急増点を決定し、
前記油量急増点は、前記ＯＢＤ機器を有する自動車を抽象化し、油量が急増する自動車が対応するポイントであり、
クラスタリングアルゴリズムによって、前記油量急増点の対応するＯＢＤ機器からアップロードされた位置情報に基づいて、前記油量急増点をクラスタリングし、
クラスタリング結果に基づいてガソリンスタンドＰＯＩが存在する位置領域を決定することを実行させる
ことを特徴とする不揮発性コンピュータ記憶媒体。
【請求項１４】
１つ以上のプロセッサと、
メモリと、
１つ以上のプログラムとを備えており、
前記１つ以上のプログラムが前記メモリに記憶され、前記１つ以上のプロセッサにより実行される時に、
ＯＢＤ機器がアップロードした、自動車の位置情報と、車速と、ガソリン残量とを含む情報を収集し、
前記車速及び前記ガソリン残量の情報に基づいて油量急増点を決定し、
前記油量急増点は、前記ＯＢＤ機器を有する自動車を抽象化し、油量が急増する自動車が対応するポイントであり、
クラスタリングアルゴリズムによって、前記油量急増点の対応するＯＢＤ機器からアップロードされた位置情報に基づいて、前記油量急増点を位置情報に応じてクラスタリングし、
クラスタリング結果に基づいてガソリンスタンドＰＯＩが存在する位置領域を決定することを実行する
ことを特徴とする装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は２０１５年０９月３０日に提出した、出願番号が２０１５１０６４２１６０．０で、出願人が百度オンラインネットワーク技術（北京）有限公司（Ｂａｉｄｕ  Ｏｎｌｉｎｅ  Ｎｅｔｗｏｒｋ  Ｔｅｃｈｎｏｌｏｇｙ  （Ｂｅｉｊｉｎｇ）  Ｃｏ．，  Ｌｔｄ.）で、発明名称が「ガソリンスタンドＰＯＩの自動発見方法及び装置」である中国特許出願に基づく優先権を主張し、当該出願の全文を引用することにより本願に組み込む。
【０００２】
本発明は検索技術分野に関し、特にガソリンスタンドＰＯＩの自動発見方法、自動発見装置、記憶媒体及びその装置に関する。
【背景技術】
【０００３】
従来技術では、ガソリンスタンド情報ポイント（Ｐｏｉｎｔ  ｏｆ  Ｉｎｔｅｒｅｓｔ、ＰＯＩ）の収集方法は主に歩行による収集、車両による収集及び空撮の方法を使って人工的な収集による。
【０００４】
上記技術方案では、歩行による収集であっても、車両による収集であっても、ガソリンスタンドの具体的な位置を事前に知らず、人や収集車が対応の位置に到着してはじめて発見することができ、収集コストが高く、且つガソリンスタンドを見落としてしまう場合がある。また、ある場所でガソリンスタンドが新しく建てられたり、ガソリンスタンドが撤去されたりする場合、従来の収集方法では速やかに発見できず、次の収集サイクルになってはじめて発見できるようになるので、ガソリンスタンドＰＯＩの更新周期が長くなってしまう。
【発明の概要】
【０００５】
本発明は、ガソリンスタンドＰＯＩの収集コストが高く、更新周期が長いという問題を解決するために、ガソリンスタンドＰＯＩの自動発見方法、自動発見装置、記憶媒体及びその装置を提供することを目的とする。
【０００６】
第１態様によれば、本発明はガソリンスタンドＰＯＩの自動発見方法を提供し、前記自動発見方法は、
車載診断システム（Ｏｎ−Ｂｏａｒｄ  Ｄｉａｇｎｏｓｔｉｃ、ＯＢＤ）機器がアップロードした情報を収集し、前記情報に基づいて油量急増点を決定するステップと、
クラスタリングアルゴリズムによって前記油量急増点を位置情報に応じてクラスタリングするステップと、
クラスタリング結果に基づいてガソリンスタンドＰＯＩが存在する位置領域を決定するステップと、を含む。
【０００７】
第２態様によれば、本発明はガソリンスタンドＰＯＩの自動発見装置を提供し、この装置は、
ＯＢＤ機器がアップロードした情報を収集し、前記情報に基づいて油量急増点を決定する油量急増点決定モジュールと、
クラスタリングアルゴリズムによって前記油量急増点を位置情報に応じてクラスタリングするクラスタリング処理モジュールと、
クラスタリング結果に基づいてガソリンスタンドＰＯＩが存在する位置領域を決定する位置決定モジュールとを備える。
【０００８】
第３態様によれば、本発明は１つ以上のモジュールが記憶される不揮発性コンピュータ記憶媒体を提供し、前記１つ以上のモジュールがガソリンスタンドＰＯＩの自動発見方法を実行する装置により実行される時に、前記機器に以下の動作をさせ、
ＯＢＤ機器がアップロードした情報を収集し、前記情報に基づいて油量急増点を決定する操作と、
クラスタリングアルゴリズムによって前記油量急増点を位置情報に応じてクラスタリングする操作と、
クラスタリング結果に基づいてガソリンスタンドＰＯＩが存在する位置領域を決定する操作と、を実行させる。
【０００９】
第４態様によれば、本発明は装置を提供し、前記装置は、
１つ以上のプロセッサと、
メモリと、
１つ以上のプログラムとを備え、
前記１つ以上のプログラムが前記メモリに記憶され、前記１つ以上のプロセッサにより実行される時に、
ＯＢＤ機器がアップロードした情報を収集し、前記情報に基づいて油量急増点を決定する操作と、
クラスタリングアルゴリズムによって前記油量急増点を位置情報に応じてクラスタリングする操作と、
クラスタリング結果に基づいてガソリンスタンドＰＯＩが存在する位置領域を決定する操作と、を実行する。
【００１０】
本発明に係るガソリンスタンドＰＯＩの自動発見方法、自動発見装置、及び記憶媒体とその装置は、ＯＢＤ機器がアップロードした関連情報に基づいて、関連情報を処理することにより油量急増点を決定し、さらにクラスタリングアルゴリズムによって処理結果の関連ポイントをクラスタリングして、ガソリンスタンドＰＯＩの位置領域を自動的に決定し、人や収集車が対応位置に到着していなくてもガソリンスタンドＰＯＩを発見することができるため、ガソリンスタンドＰＯＩ情報の収集コストを低減させることができるとともに、ガソリンスタンドＰＯＩの更新周期を短縮させることができる。
【図面の簡単な説明】
【００１１】
本発明の実施形態における技術方案をより明確的に説明するために、以下、実施形態の記載に使用される添付図面について簡単に紹介する。無論、次に説明される添付図面は、本発明に関するいくつかの実施例にすぎず、当業者にとって、創造的労働をしなくても、これらの添付図面を修正したり、置き換えたりすることができる。
【００１２】
【図１】本発明の実施例１に係るガソリンスタンドＰＯＩの自動発見方法のフローチャートを示す図である。
【図２】本発明の実施例２に係るガソリンスタンドＰＯＩの自動発見方法のフローチャートを示す図である。
【図３】本発明の実施例３に係るｇｅｏハッシュ文字列が位置領域をマークする模式図である。
【図４】本発明の実施例４に係るガソリンスタンドＰＯＩの自動発見装置の構造模式図である。
【図５】本発明の実施例６に係るガソリンスタンドＰＯＩの自動発見方法を実行する機器のハードウェア構造の模式図である。
【発明を実施するための形態】
【００１３】
以下、図面と実施例を参照しながら、本発明における技術方案を明確で完全に説明する。明らかに、説明される実施例は、本発明の一部の実施例にすぎず、全部の実施例ではなく、本発明の原理を解釈するためのものであって、本発明を、これらの一部の実施例によって限定されるものではない。本発明における実施例に基づいて、当業者が創造的労働をしなくても得られる全ての他の実施例は、本発明の保護範囲に属する。
【００１４】
実施例１
図１は本発明の実施例１に係るガソリンスタンドＰＯＩの自動発見方法のフローチャートを示す図である。本実施例はガソリンスタンドＰＯＩを収集する場合に応用することができる。当該方法はガソリンスタンドＰＯＩの自動発見装置により実行されてもよく、前記装置はソフトウェア及び／又はハードウェアにより実現される。図１に示されるように、本発明の実施例に係るガソリンスタンドＰＯＩの自動発見方法は、具体的には、以下のステップを含む。
【００１５】
Ｓ１１０：ＯＢＤ機器がアップロードした情報を収集し、前記情報に基づいて油量急増点を決定する。
【００１６】
ＯＢＤ機器は自動車に搭載され、自動車の運転状態を監視し、自動車における複数のシステムと部材をリアルタイムで検出し、自動車が故障状態であるか否かを判断することができる。ＯＢＤ機器がアップロードした情報は、自動車の位置、速度、ガソリン残量、瞬間燃費、タイヤ空気圧、及び水温等の情報を含む。油量急増のポイントはＯＢＤ機器に対応する油量急増点であり、ＯＢＤ機器を有するこれらの自動車を抽象化するようにしたいくつかのポイントであり、ＯＢＤ機器がアップロードした自動車の速度と油量等の情報が所定の条件を満たすと、当該ＯＢＤ機器が油量急増点となる。
【００１７】
Ｓ１２０：クラスタリングアルゴリズムによって前記油量急増点を位置情報に応じてクラスタリングする。
【００１８】
位置情報は油量急増点に対応するＯＢＤ機器がアップロードした自動車の位置情報であり、自動車位置の経緯度情報を含む。
【００１９】
クラスタリングアルゴリズムによって油量急増点を経緯度等の位置情報に基づいてクラスタリングした後、地理的範囲を複数の領域に分けて、位置の近い油量急増点を一つの類にクラスタリングし、これらの同類の油量急増点は１つの位置領域を共有し、ここで、当該クラスタリングアルゴリズムはｇｅｏハッシュアルゴリズム等を含む。
【００２０】
Ｓ１３０：クラスタリング結果に基づいてガソリンスタンドＰＯＩが存在する位置領域を決定する。
【００２１】
本実施例に係る技術方案は、ＯＢＤ機器がアップロードした関連情報に基づいて、関連情報を処理して油量急増点を決定し、さらにクラスタリングアルゴリズムによって処理結果をクラスタリングして、ガソリンスタンドＰＯＩの位置領域を自動的に決定し、ガソリンスタンドＰＯＩの収集コストを低減させることができるとともに、ガソリンスタンドＰＯＩの更新周期を短縮させることができる。
【００２２】
実施例２
図２は本発明の実施例２に係るガソリンスタンドＰＯＩの自動発見方法のフローチャートを示す図である。本実施例は実施例１をもとにして操作Ｓ１１０を最適化する。図２に示されるように、当該方法の具体的なフローは、以下のステップを含む。
【００２３】
Ｓ２１０：複数のＯＢＤ機器がアップロードした情報を設定時間おきに収集し、当該情報は、車速及びガソリン残量を含む。
【００２４】
Ｓ２２０：各ＯＢＤ機器に対して、現在のＯＢＤ機器がアップロードしたガソリン残量に基づいて現在のＯＢＤ機器に対応する油量急増程度値を計算し、算出した油量急増程度値が第１設定閾値以上で、且つ現在のＯＢＤ機器のアップロードした車速が第２設定閾値以下である場合、現在のＯＢＤ機器を油量急増点として決定する。
【００２５】
自動車に給油する時に、自動車のエンジンがかからない状態になり、自動車の速度が通常ゼロ又はほとんどゼロであることを考慮し、従ってこの２つの条件に基づいて自動車がガソリンスタンドの近くに給油されるか否かを判断する。通常、自動車に給油する時間が数秒〜数分であるので、複数のＯＢＤ機器がアップロードした車速とガソリン残量等の情報を所定の設定時間おきに収集することができる。次に各ＯＢＤ機器に対して、現在のＯＢＤがアップロードしたガソリン残量の情報に基づいて現在のＯＢＤ機器に対応する油量急増程度値を計算する。オプションとして、油量急増程度値は、下式
【数１】
0006651006.tif 000002
を用いて計算し、
ここで、Ｗは油量急増程度値を示し、ｎは前記設定時間を示し、単位が秒であり、Ｏ１〜Ｏｎはそれぞれ現在のｎ秒の期間において各秒のガソリン残量を示す。
【００２６】
例示として、設定時間が５ｓで、即ちＯＢＤ機器がアップロードした経緯度、車速等の情報を５ｓおきに１回収集し、当該情報はこの連続した５秒内の情報を含む場合、油量急増値は、
【数２】
0006651006.tif 000003
であり、Ｏ１〜Ｏ５は連続した５秒内の第１秒〜第５秒のガソリン残量である。当該計算方法を用いることで、油量急増値を精確に算出することができる。
【００２７】
好ましくは、算出した油量急増程度値が１．５９以上で、且つ現在の車速が０である場合、現在のＯＢＤ機器が油量急増点であると決定する。
【００２８】
ＯＢＤ機器がアップロードした情報の設定時間が異なっており、且つ給油過程で、自動車の油量は次第に増加するため、油量急増の程度が、給油の時間、給油の速度に関係する。さらに給油過程において、車両の速度が必ずしもゼロとは限らず、ガソリンスタンドの所在する領域の地面が平坦であるか否か又はガソリンスタンドの近くの風速等の要素が、いずれも収集した自動車の現在速度に影響を与える可能性がある。従って、実際の必要に応じて第１設定閾値と第２設定閾値を柔軟に設定してもよく、第１設定閾値がゼロより大きい他の数値と設定してもよく、第２設定閾値が０より大きく且つ０に近い数値等と設定してもよい。
【００２９】
Ｓ２３０：クラスタリングアルゴリズムによって前記油量急増点を位置情報に応じてクラスタリングする。
【００３０】
位置情報は油量急増点に対応するＯＢＤ機器がアップロードした自動車の位置情報であり、自動車位置の経緯度情報を含む。
【００３１】
Ｓ２４０：クラスタリング結果に基づいてガソリンスタンドＰＯＩが存在する位置領域を決定する。
【００３２】
本実施例に係る技術方案は、関連のアルゴリズムと原理を用い、油量急増点を精確に決定し、さらにクラスタリングアルゴリズムによって処理結果の関連ポイントをクラスタリングして、ガソリンスタンドＰＯＩの位置領域を自動的に決定し、人や収集車が対応位置に到着していなくてもガソリンスタンドＰＯＩを発見することができるため、ガソリンスタンドＰＯＩ情報の収集コストを低減させるとともに、ガソリンスタンドＰＯＩの更新周期を短縮させることができる。
【００３３】
実施例３
本実施例は上記各実施例をもとにして最適化したものである。上記各実施例では、前記ＯＢＤ機器がアップロードした情報は経緯度情報を含み、即ちＯＢＤ機器がアップロードした自動車の位置情報は経緯度情報であり、前記クラスタリングアルゴリズムはｇｅｏハッシュアルゴリズムであり、前記位置情報は経緯度情報であり、
前記クラスタリング結果に基づいてガソリンスタンドＰＯＩが存在する位置領域を決定するステップには、
クラスタリング後に生成したｇｅｏハッシュグリッドにおけるポイントの数に基づいて前記ｇｅｏハッシュグリッドにおいてガソリンスタンドＰＯＩが存在するか否かを判断するステップを含み、
さらに、前記ｇｅｏハッシュグリッドにおけるポイントの数が第３設定閾値に達した場合、前記ｇｅｏハッシュグリッドにガソリンスタンドＰＯＩが存在すると決定し、前記ｇｅｏハッシュグリッドにおけるポイントの数が第３設定閾値に達していない場合、前記ｇｅｏハッシュグリッドにガソリンスタンドＰＯＩが存在しないと決定する。
【００３４】
前記ｇｅｏハッシュグリッドにガソリンスタンドＰＯＩが存在する場合、前記ｇｅｏハッシュグリッドが示す経緯度範囲領域をガソリンスタンドＰＯＩの存在する位置領域と決定する。
【００３５】
ｇｅｏハッシュアルゴリズムによって位置情報に基づいて前記油量急増点をクラスタリングする過程は、次の通りになる。すなわち、各油量急増点に対応するＯＢＤ機器がアップロードした経緯度情報に基づいて、それぞれ各油量急増点に１つのｇｅｏハッシュ文字列を設定し、ｇｅｏハッシュ文字列が油量急増点に対応する位置をマークし、次に各油量急増点のｇｅｏハッシュ文字列に基づいて、ｇｅｏハッシュアルゴリズムによって各油量急増点をクラスタリングする。
【００３６】
例示として、１つの油量急増点の経緯度をそれぞれ１１６．３８９５５０と３９．９２８１６７とする場合、経緯度に対してｇｅｏハッシュコーディングを行う過程は、以下の通りになる。
【００３７】
地球の緯度区間は［−９０，９０］であり、以下のアルゴリズムにより緯度３９．９２８１６７に対して近似コーディングを行い、
（１）区間［−９０，９０］を［−９０，０）と［０，９０］とに二分し、左右区間と呼び、３９．９２８１６７が右区間［０，９０］に属すると決定することができ、１と標識する。
（２）続いて区間［０，９０］を［０，４５）と［４５，９０］とに二分し、３９．９２８１６７が左区間［０，４５）に属すると決定することができ、０と標識する。
（３）上記過程を再帰し、３９．９２８１６７は常に、ある区間［ａ，ｂ］に属する。反復するたびに区間［ａ，ｂ］が縮小し、且つ次第に３９．９２８１６７に近づいていく。
（４）設定された緯度ｘ（３９．９２８１６７）が左区間に属する場合、０と標識し、右区間に属する場合、１と標識する。
【００３８】
このようにアルゴリズムを行うことに伴って１つの配列１０１１１００が生成され、配列の長さが設定された区間の分割回数に関連し、緯度に基づいてコードを取得する過程は下表に示す。
【表１】
0006651006.tif 000004
【００３９】
緯度によって生成されたコードは１０１１１  ０００１１であり、同様に、地球の経度区間は［−１８０，１８０］であり、経度１１６．３８９５５０をコーディングして得られたコードは１１０１０  ０１０１１である。偶数ビットを経度として、奇数ビットを緯度とすれば、組み合わせた新しいコードは１１１００  １１１０１  ００１００  ０１１１１になる。次にコードを１０進数の数字に変換し、５ビットコードが１つの１０進数の数字に対応するため、変換される１０進数の範囲は０〜３１である。上記したコードに対応する１０進数字は２８、２９、４、１５であり、最後に下記表の対応関係に応じて、１０進数を文字列、即ちハッシュ文字列に変換し、本例示では、用いるハッシュ文字列の長さが４であり、経緯度に対応する文字列がＷＸ４Ｇである。
【表２】
0006651006.tif 000005
【００４０】
図３に示されるように、当該図は９個の領域に対応するｇｅｏハッシュ文字列を示し、各文字列が１つの矩形領域に対応し、つまり、この矩形領域内のあらゆるポイント（経緯度座標）はいずれも同一ｇｅｏハッシュ文字列を共有している。
【００４１】
各ハッシュ文字列は１つのハッシュグリッドに対応し、クラスタリングされた後に、同一ハッシュグリッド、即ち同一矩形領域におけるポイントの数が第３設定閾値に達した時に、当該ハッシュグリッドに対応する領域内にガソリンスタンドＰＯＩが存在すると判断し、当該第３設定閾値がガソリンスタンドの所在する領域で給油される自動車の実際の数量に関連し、いくつかの遠隔地域で、あるガソリンスタンドで給油される自動車の数が少なく、算出したハッシュグリッドにおけるポイントの数が少ないので、実際の必要に応じて又は異なる位置領域によって異なる第３設定閾値を設定し、当該第３設定閾値はゼロより大きい任意の数値であってもよい。
【００４２】
好ましくは、ｇｅｏハッシュグリッドにおけるポイントの数が２１．５に達した場合、このｇｅｏハッシュグリッドが示す経緯度座標範囲内にガソリンスタンドＰＯＩが存在するとする。
【００４３】
好ましくは、ｇｅｏハッシュアルゴリズムによって前記油量急増点を位置情報に基づいてクラスタリングする時に、用いられるｇｅｏハッシュ文字列の長さは７である。
【００４４】
ｇｅｏハッシュアルゴリズムによってクラスタリングする時に、用いられるｇｅｏハッシュ文字列の長さが長いほど、領域内にガソリンスタンドＰＯＩが存在すると最後に決定する誤差が小さく、ｇｅｏハッシュ文字列の長さと最後のクラスタリング結果との誤差の対応関係は下表に示す。精度と収集したガソリンスタンドＰＯＩの粒度とを両立して考慮するため、ｇｅｏハッシュ文字列の長さを７に選択する。勿論、文字列の長さも他の値を選択してもよい。
【表３】
0006651006.tif 000006
【００４５】
本実施例に係る技術方案は、油量急増点に対してｇｅｏハッシュクラスタリング処理を行うことで、領域内にガソリンスタンドＰＯＩが存在するか否かを精確に決定することができ、ガソリンスタンドＰＯＩの収集コストを低減させることができるとともに、ＰＯＩ更新速度が速くなる。
【００４６】
実施例４
図４は本発明の実施例４に係るガソリンスタンドＰＯＩの自動発見装置の構造模式図である。図４に示されるように、当該ガソリンスタンドＰＯＩの自動発見装置の具体的な構造は、
ＯＢＤ機器がアップロードした情報を収集し、前記情報に基づいて油量急増点を決定する油量急増点決定モジュール４１０と、
クラスタリングアルゴリズムによって前記油量急増点を位置情報に応じてクラスタリングするクラスタリング処理モジュール４２０と、
クラスタリング結果に基づいてガソリンスタンドＰＯＩが存在する位置領域を決定する位置決定モジュール４３０と、を備える。
【００４７】
前記油量急増点決定モジュール４１０は、具体的に、
複数のＯＢＤ機器がアップロードした、車速及びガソリン残量を含む情報を設定時間おきに収集し、
各ＯＢＤ機器に対して、現在のＯＢＤ機器がアップロードしたガソリン残量に基づいて現在のＯＢＤ機器に対応する油量急増程度値を計算し、算出した油量急増程度値が第１設定閾値以上で、且つ現在のＯＢＤ機器のアップロードした車速が第２設定閾値以下である場合、現在のＯＢＤ機器が油量急増点であると決定する。
【００４８】
好ましくは、下式
【数３】
0006651006.tif 000007
を用いて油量急増程度値を計算してもよく、
ここで、Ｗは油量急増程度値を示し、ｎは前記設定時間を示し、単位が秒であり、Ｏ１〜Ｏｎはそれぞれ現在のｎ秒の期間において各秒のガソリン残量を示す。
【００４９】
さらに、前記ＯＢＤ機器がアップロードした情報は経緯度情報を含み、前記クラスタリングアルゴリズムはｇｅｏハッシュアルゴリズムであり、前記位置情報は経緯度情報であり、
前記位置決定モジュール４３０は、
クラスタリング後に生成したｇｅｏハッシュグリッドにおけるポイントの数に基づいて前記ｇｅｏハッシュグリッドにおいてガソリンスタンドＰＯＩが存在するか否かを判断するＰＯＩ判断ユニット４３１を備え、
さらに、前記ＰＯＩ判断ユニット４３１は、具体的に、
前記ｇｅｏハッシュグリッドにおけるポイントの数が第３設定閾値に達した場合、前記ｇｅｏハッシュグリッドにガソリンスタンドＰＯＩが存在すると決定し、前記ｇｅｏハッシュグリッドにおけるポイントの数が第３設定閾値に達していない場合、前記ｇｅｏハッシュグリッドにガソリンスタンドＰＯＩが存在しないと決定する。
【００５０】
ＰＯＩ決定ユニット４３２は、前記ＰＯＩ判断ユニットは前記ｇｅｏハッシュグリッドにガソリンスタンドＰＯＩが存在すると判断する時に、前記ｇｅｏハッシュグリッドが示す経緯度範囲領域をガソリンスタンドＰＯＩの存在する位置領域と決定する。
【００５１】
好ましくは、前記クラスタリング処理モジュール４２０はｇｅｏハッシュアルゴリズムによって前記油量急増点を位置情報に基づいてクラスタリングする時に、用いられるｇｅｏハッシュ文字列の長さが７である。
【００５２】
上記装置は本発明の実施例のいずれかに係るガソリンスタンドＰＯＩの自動発見方法を実行することができ、方法の実行に対応する機能モジュールと有益な効果を有する。
【００５３】
実施例５
本実施例は不揮発性コンピュータ記憶媒体を提供し、前記コンピュータ記憶媒体に１つ以上のモジュールが記憶され、前記１つ以上のモジュールがガソリンスタンドＰＯＩの自動発見方法を実行する装置により実行される時に、前記装置に、次の動作をさせ、すなわち
ＯＢＤ機器がアップロードした情報を収集し、前記情報に基づいて油量急増点を決定する操作と、
クラスタリングアルゴリズムによって前記油量急増点を位置情報に応じてクラスタリングする操作と、
クラスタリング結果に基づいてガソリンスタンドＰＯＩが存在する位置領域を決定する操作と、を実行させる。
【００５４】
上記記憶媒体に記憶されるモジュールは前記機器により実行される時に、前記のＯＢＤ機器がアップロードした情報を収集し、前記情報に基づいて油量急増点を決定する操作には、
複数のＯＢＤ機器がアップロードした、車速及びガソリン残量を含む情報を設定時間おきに収集するステップと、
各ＯＢＤ機器に対して、現在のＯＢＤ機器がアップロードしたガソリン残量に基づいて現在のＯＢＤ機器に対応する油量急増程度値を計算し、算出した油量急増程度値が第１設定閾値以上であり、且つ現在のＯＢＤ機器のアップロードした車速が第２設定閾値以下である場合、現在のＯＢＤ機器が油量急増点であると決定するステップとを含んでもよい。
【００５５】
上記記憶媒体に記憶されるモジュールは前記機器により実行される時に、下式
【数４】
0006651006.tif 000008
用いて油量急増程度値を計算することができ、
ここで、Ｗは油量急増程度値を示し、ｎは前記設定時間を示し、単位は秒であり、Ｏ１〜Ｏｎはそれぞれ現在のｎ秒の期間内秒ごとのガソリン残量を示す。
【００５６】
上記記憶媒体に記憶されるモジュールは前記機器により実行される時に、前記ＯＢＤ機器がアップロードした情報は経緯度情報を含んでもよく、前記クラスタリングアルゴリズムはｇｅｏハッシュアルゴリズムであってもよく、前記位置情報は経緯度情報であってもよく、
上記記憶媒体に記憶されるモジュールは前記機器により実行される時に、前記のクラスタリング結果に基づいてガソリンスタンドＰＯＩが存在する位置領域を決定する操作には、
クラスタリング後に生成したｇｅｏハッシュグリッドにおけるポイントの数に基づいて前記ｇｅｏハッシュグリッドにおいてガソリンスタンドＰＯＩが存在するか否かを判断するステップと、
前記ｇｅｏハッシュグリッドにおいてガソリンスタンドＰＯＩが存在する場合、前記ｇｅｏハッシュグリッドが示す経緯度範囲領域をガソリンスタンドＰＯＩの存在する位置領域と決定するステップとを含んでもよい。
【００５７】
上記記憶媒体に記憶されるモジュールは前記機器により実行される時に、前記クラスタリング後に生成したｇｅｏハッシュグリッドにおけるポイントの数に基づいて前記ｇｅｏハッシュグリッドにおいてガソリンスタンドＰＯＩが存在するか否かを判断するステップには、
前記ｇｅｏハッシュグリッドにおけるポイントの数が第３設定閾値に達した場合、前記ｇｅｏハッシュグリッドにガソリンスタンドＰＯＩが存在すると決定し、前記ｇｅｏハッシュグリッドにおけるポイントの数が第３設定閾値に達していない場合、前記ｇｅｏハッシュグリッドにガソリンスタンドＰＯＩが存在しないと決定するステップを含んでもよい。
【００５８】
上記記憶媒体に記憶されるモジュールは前記装置により実行される時に、ｇｅｏハッシュアルゴリズムによって前記油量急増点を位置情報に基づいてクラスタリングする時に、好ましくは、用いられるｇｅｏハッシュ文字列の長さは７であってもよい。
【００５９】
上記実施形態の説明によれば、当業者は、本発明がソフトウェア、および必要な汎用ハードウェアにより実現されてもよく、勿論ハードウェアにより実現されてもよいが、多くの場合、前者が好ましい実施形態であると理解すべきである。このような理解に基づいて、本発明の技術方案は、実体的な部分、または従来技術を改良する部分をソフトウェア製品の形態で実現してもよい。当該コンピュータソフトウェア製品は、コンピュータ可読記憶媒体、例えばコンピュータのフロッピーディスク、光ディスク、読み出し専用メモリ（Ｒｅａｄ−Ｏｎｌｙ  Ｍｅｍｏｒ、ＲＯＭ）、ランダムアクセスメモリ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ、ＲＡＭ）などに記憶されてもよく、且つコンピュータ機器（パソコン、サーバ、またはネットワーク機器などであってもよく）に本発明の各実施例に係る方法を実行させる複数のコマンドを含む。
【００６０】
実施例６
図５は本発明の実施例６に係るガソリンスタンドＰＯＩの自動発見方法を実行する機器のハードウェア構造模式図である。図５に示されるように、前記装置は、
１つ以上のプロセッサ５１０と（図５中、一つのプロセッサ５１０を例にする）、
メモリ５２０と、
１つ以上のモジュールとを備える。
【００６１】
前記装置はさらに、入力装置５３０と出力装置５４０と、を備えてもよい。前記装置のプロセッサ５１０、メモリ５２０、入力装置５３０及び出力装置５４０はバス又はその他の方式によって接続されることができ、図５において、バス接続を一例とする。
【００６２】
メモリ５２０はコンピュータ読み取り可能な記憶媒体として、ソフトウェアプログラム、コンピュータ実行可能なプログラム及びモジュール、例えば本発明の実施例におけるガソリンスタンドＰＯＩの自動発見方法に対応するプログラム命令／モジュール（例えば、図４に示されるガソリンスタンドＰＯＩの自動発見装置における油量急増点決定モジュール４１０、クラスタリング処理モジュール４２０及び位置決定モジュール４３０）を記憶することに用いられてもよい。プロセッサ５１０はメモリ５２０に記憶されるソフトウェアプログラム、命令及びモジュールを実行して、それによりサーバの各種の機能アプリケーション及びデータ処理を実行し、即ち上記方法の実施例におけるナビゲーション方法を実現する。
【００６３】
メモリ５２０はオペレーティングシステム、少なくとも１つの機能に必要なアプリケーションプログラムを記憶できるプログラム記憶領域、及び端末装置の使用に応じて作成されるデータ等を記憶できる記憶データ領域を備える。また、メモリ５２０は高速ランダムアクセスメモリを備えてもよく、さらに不揮発性メモリ、例えば少なくとも１つのディスク記憶デバイス、フラッシュメモリデバイス、又は他の不揮発性ソリッドステートメモリデバイスを備えてもよい。いくつかの例では、メモリ５２０は、プロセッサ５１０に対して遠隔に設置されるメモリを備えてもよく、これらの遠隔メモリはネットワークで端末装置に接続されてもよい。上記ネットワークの例はインターネット、イントラネット、ローカルエリアネットワーク、移動体通信ネットワーク及びその組合せを含むが、それらに限定されない。
【００６４】
入力装置５３０は入力された数字又は文字情報を受信し、及び端末のユーザ設定及び機能制御に関連するキー信号入力を生成することに用いられてもよい。出力装置５４０はディスプレイスクリーン等の表示装置を備えてもよい。
【００６５】
前記１つ以上のモジュールは前記メモリ５２０に記憶され、前記１つ以上のプロセッサ５１０により実行される時に、次の動作をさせ、すなわち、
ＯＢＤ機器がアップロードした情報を収集し、前記情報に基づいて油量急増点を決定する操作と、
クラスタリングアルゴリズムによって前記油量急増点を位置情報に応じてクラスタリングする操作と、
クラスタリング結果に基づいてガソリンスタンドＰＯＩが存在する位置領域を決定する操作と、を実行する。
【００６６】
さらに、前記のＯＢＤ機器がアップロードした情報を収集し、前記情報に基づいて油量急増点を決定する操作には、
複数のＯＢＤ機器がアップロードした、車速及びガソリン残量を含む情報を設定時間おきに収集するステップと、
各ＯＢＤ機器に対して、現在のＯＢＤ機器がアップロードしたガソリン残量に基づいて現在のＯＢＤ機器に対応する油量急増程度値を計算し、算出した油量急増程度値が第１設定閾値以上であり、且つ現在のＯＢＤ機器のアップロードした車速が第２設定閾値以下である場合、現在のＯＢＤ機器が油量急増点であると決定するステップと、を含んでもよい。
【００６７】
さらに、下式
【数５】
0006651006.tif 000009
を用いて油量急増程度値を計算することができ、
ここで、Ｗは油量急増程度値を示し、ｎは前記設定時間を示し、単位は秒であり、Ｏ１〜Ｏｎはそれぞれ現在のｎ秒の期間内秒ごとのガソリン残量を示す。
【００６８】
さらに、前記ＯＢＤ機器がアップロードした情報は経緯度情報を含んでもよく、前記クラスタリングアルゴリズムはｇｅｏハッシュアルゴリズムによってあってもよく、前記位置情報は経緯度情報であってもよく、
前記のクラスタリング結果に基づいてガソリンスタンドＰＯＩが存在する位置領域を決定する操作には、
クラスタリング後に生成したｇｅｏハッシュグリッドにおけるポイントの数に基づいて前記ｇｅｏハッシュグリッドにおいてガソリンスタンドＰＯＩが存在するか否かを判断するステップと、
前記ｇｅｏハッシュグリッドにおいてガソリンスタンドＰＯＩが存在する場合、前記ｇｅｏハッシュグリッドが示す経緯度範囲領域をガソリンスタンドＰＯＩの存在する位置領域と決定するステップとを含んでもよい。
【００６９】
さらに、前記のクラスタリング後に生成したｇｅｏハッシュグリッドにおけるポイントの数に基づいて前記ｇｅｏハッシュグリッドにおいてガソリンスタンドＰＯＩが存在するか否かを判断するステップには、
前記ｇｅｏハッシュグリッドにおけるポイントの数が第３設定閾値に達した場合、前記ｇｅｏハッシュグリッドにガソリンスタンドＰＯＩが存在すると決定し、前記ｇｅｏハッシュグリッドにおけるポイントの数が第３設定閾値に達していない場合、前記ｇｅｏハッシュグリッドにガソリンスタンドＰＯＩが存在しないと決定するステップを含んでもよい。
【００７０】
さらに、ｇｅｏハッシュアルゴリズムによって前記油量急増点を位置情報に基づいてクラスタリングする時に、用いられるｇｅｏハッシュ文字列の長さは７であってもよい。
【００７１】
なお、上記ガソリンスタンドＰＯＩの自動発見装置の実施例では、含まれている各ユニット及びモジュールは機能ロジックに応じて分割したものに過ぎず、上記分割に限定されるものではなく、対応する機能を達成すればよく、さらに、各機能ユニットの具体的な名称も単に相互に区別するために便宜上付けたものであり、本発明の保護範囲を限定するものではない。
【００７２】
上述したのは、本発明の具体的な実施形態にすぎず、本発明の保護範囲は、これらに限定されるものではない。いかなる当業者が本発明に開示された技術範囲内に容易に想到できる変更または置換の全ては、本発明の保護範囲内に入るべきである。従って、本発明の保護範囲は、添付される特許請求の範囲を基準とするものである。
【図１】
0006651006.tif 000012
【図２】
0006651006.tif 000013
【図３】
0006651006.tif 000014
【図４】
0006651006.tif 000015
【図５】
0006651006.tif 000016