局所性鋭敏型ハッシュ

LSH族を構築するためのもっとも単純な手法はハミング距離に基づくものである。これは${\displaystyle d}$次元のベクトル${\displaystyle \{0,1\}^{d}}$に対して適応できる。この手法は${\displaystyle d}$次元のベクトルについて${\displaystyle i}$番目の座標値をハッシュ値として与えるような族${\displaystyle {\mathcal {F}}}$により定義され、${\displaystyle {\mathcal {F}}}$とは例えば${\displaystyle {\mathcal {F}}=\{h:\{0,1\}^{d}\to \{0,1\}\mid h(x)=x_{i},i=1...d\}}$のように与えられる。ここで${\displaystyle {\mathcal {F}}}$から${\displaystyle h}$を任意に選ぶということは、入力点から任意にビットを選択するということに他ならない。この時、族は次の性質を持つ。

${\displaystyle P_{1}=1-R/d\,}$, ${\displaystyle P_{2}=1-cR/d\,}$

ハッシュ関数${\displaystyle h_{\mathbf {a} ,b}({\boldsymbol {\upsilon }}):{\mathcal {R}}^{d}\to {\mathcal {N}}}$を${\displaystyle d}$次元のベクトル${\displaystyle v}$を整数の集合に移すような関数であると定義する^[4]。ハッシュ関数${\displaystyle h}$は2つの乱数${\displaystyle a,b}$によって定義される。ここで${\displaystyle a}$とは安定分布から独立に選ばれる乱数であり、${\displaystyle b}$とは${\displaystyle [0,r]}$から一様に選ばれる実乱数である。${\displaystyle a}$および${\displaystyle b}$が選ばれたとき、ハッシュ関数${\displaystyle h_{\mathbf {a} ,b}}$は

${\displaystyle h_{\mathbf {a} ,b}({\boldsymbol {\upsilon }})=\left\lfloor {\frac {\mathbf {a} \cdot {\boldsymbol {\upsilon }}+b}{r}}\right\rfloor }$

のように与えられる。

この他にもデータをより適切に対応させるハッシュ関数が提案されている^[5]。例えばk-平均法に基づくハッシュ関数などは大域的最適解を与えることが保証されていないものの実用的なハッシュ関数として知られている。

1. ↑ Gionis, A.; Indyk, P., Motwani, R. (1999). , “Similarity Search in High Dimensions via Hashing”. Proceedings of the 25th Very Large Database (VLDB) Conference. https://people.csail.mit.edu/indyk/vldb99.ps ,. 
2. ↑ Indyk, Piotr.; Motwani, Rajeev. (1998). , “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.”. Proceedings of 30th Symposium on Theory of Computing. https://people.csail.mit.edu/indyk/nndraft.ps ,. 
3. ↑ Charikar, Moses S.. (2002). “Similarity Estimation Techniques from Rounding Algorithms”. Proceedings of the 34th Annual ACM Symposium on Theory of Computing 2002: (ACM 1–58113–495–9/02/0005)…. doi:10.1145/509907.509965. http://portal.acm.org/citation.cfm?id=509965 2007年12月21日閲覧。. 
4. ↑ Datar, M.; Immorlica, N., Indyk, P., Mirrokni, V.S. (2004). “Locality-Sensitive Hashing Scheme Based on p-Stable Distributions”. Proceedings of the Symposium on Computational Geometry. http://theory.csail.mit.edu/~mirrokni/pstable.ps. 
5. ↑ Pauleve, L.; Jegou, H., Amsaleg, L. (2010). “Locality sensitive hashing: A comparison of hash function types and querying mechanisms”. Pattern recognition Letters. https://hal.inria.fr/inria-00567191/en/. 

• 最近傍探索
• ハッシュ関数
• データ構造

この項目は、工学・技術に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（Portal:技術と産業）。

• 表示
• 編集