距離計算の精度測定とパフォーマンス測定

はじめに

こんにちは。次世代システム研究室のT.Tです。
スマホ向けのアプリで、自分の現在地(経緯度)から近いところの情報を検索するサービスの実装を担当する機会があり、距離計算のアルゴリズムを調査し、実用的な精度、パフォーマンスがあるかを測定、検証しました。
今回は、そのアルゴリズムの概要と精度測定、パフォーマンス測定の結果についてお伝えしたいと思います。

距離計算アルゴリズム

要件としては自分の現在地から近いところだけを対象にMySQL上で検索をしたいため、その点まで考慮しているOllieさん紹介のアルゴリズム(以後、本アルゴリズム)を調査しました。
本アルゴリズムの概要は以下の通りです。

• 距離の算出方法
  • 地球を球面モデルとして扱う
  • Haversine formulaにより2点間の度を算出
  • 1度ごとに生じる球面に沿った2点間の距離からkm単位に変換して距離を算出
• SQLの高速化
  • 自分の近いところに含まれる経緯度だけを検索対象となるように経緯度に条件を付ける
  • 経度緯度、緯度経度のインデックスを張ってDB内の検索を高速化
  • 実行速度の遅い数学関数の実行回数を減らすことで高速化

「球面三角法」『フリー百科事典　ウィキペディア日本語版』。2014年10月24日 (金) 09:47 UTC、http://ja.wikipedia.org/wiki/%E7%90%83%E9%9D%A2%E4%B8%89%E8%A7%92%E6%B3%95

実装

FuelPHPで以下のように実装しました。

		$query = implode(' ', array(
			'SELECT zip, primary_city, latitude, longitude, distance',
				'FROM (',
				'SELECT z.zip, z.primary_city, z.latitude, z.longitude, p.radius,',
					'p.distance_unit',
					'* DEGREES(ACOS(COS(RADIANS(p.latpoint))',
					'* COS(RADIANS(z.latitude))',
					'* COS(RADIANS(p.longpoint - z.longitude))',
					'+ SIN(RADIANS(p.latpoint))',
					'* SIN(RADIANS(z.latitude)))) AS distance',
				'FROM zip AS z',
				'JOIN (',
					'SELECT :lat AS latpoint, :lon AS longpoint, :radius AS radius, 111.045 AS distance_unit',
				') AS p',
				'WHERE z.latitude',
					'BETWEEN p.latpoint  - (p.radius / p.distance_unit)',
						'AND p.latpoint  + (p.radius / p.distance_unit)',
					'AND z.longitude',
					'BETWEEN p.longpoint - (p.radius / (p.distance_unit * COS(RADIANS(p.latpoint))))',
						'AND p.longpoint + (p.radius / (p.distance_unit * COS(RADIANS(p.latpoint))))',
			') AS d',
			'WHERE distance <= radius',
			'ORDER BY distance',
			'LIMIT :limit'
		));

		$result = \DB::query($query)->parameters(compact('lat', 'lon', 'radius', 'limit'))->execute()->as_array();

精度の測定

いくつかのサンプル地点を国土地理院の距離計算の結果と比較して精度を測定しました。
このサイトでは、地球を楕円体モデルとして扱う世界測地系で距離を計算していて、精度が高く信頼できるものです。
国土地理院(緯度=36.103775,経度=140.087855)とサンプル地点との距離の実行結果です。

実際のサービスでは誤差は1%以内に収まれば十分なので、比較した範囲では本アルゴリズムを採用して問題なさそうです。
また、測定結果では遠距離程誤差が大きくなる傾向が見られますが、サンプルよりももっと近い距離を対象にするためこの点でも問題なさそうです。

パフォーマンスの測定

先述したOllieさんの記事にある4万件程度の位置データを対象に測定してみました。
測定環境は、MacBook Pro、CPU 2.4GHz Intel Core i5、メモリ 8GB 1600MHz DDR3で実行時間は10回実行した実行時間の平均値となっています。
実行結果は以下のようになりました。

50km圏内で検索対象が少ない場合の実行時間は8.2msで、全件の場合と比べて実行時間は3%程度に抑えられています。
また、50km圏内で検索対象が少ない場合は検索対象が減った分程実行時間の比率は減っていないですが、500km圏内で検索対象が多い場合には検索対象が減った分と同じくらいの比率で実行時間が抑えられていて、件数が多い場合でも十分効果が期待できそうです。

まとめ

本アルゴリズムの精度は実用レベルのもので、実行時間も検索対象が絞れていれば10ms未満の実行時間で実行でき、本アルゴリズムは高速で優れていると思います。
検証結果を受けて、実サービスにも採用することになりました。

参考リンク

• Nearest-location finder for MySQL
• 国土地理院 – 距離と方位角の計算
• GeoHack
• 「球面三角法」『フリー百科事典　ウィキペディア日本語版』
• Wikipedia – Haversine formula

次世代システム研究室では、コンピューターサイエンスの探求に強みを持つ方をオープン採用の形式で広く募集しています。次世代システム研究室にご興味を持って頂ける方がいらっしゃいましたら、ぜひ 募集職種一覧 からご応募をお願いします。

皆さんのご応募をお待ちしています。