Database-friendly random projections: Johnson-Lindenstrauss with binary coins
Database-friendly random projections: Johnson-Lindenstrauss with binary coins
复制标题
DOI：
10.1016/s0022-0000(03)00025-4
复制
发表时间：
2003-06-01
影响因子：
1.1
通讯作者：
Achlioptas, D
中科院分区：
文献类型：
--
作者：
Achlioptas, D
Johnson和Lindenstrauss的一个经典结果断言，d维欧几里得空间中的任何n个点的集合都可以嵌入到k维欧几里得空间中，其中k是n的对数，与d无关，因此所有成对距离都保持在任意小的因子内。所有已知的这种嵌入的构造都是通过原点将n个点投影到一个球面随机的k维超平面上。我们给出了这种嵌入的两个构造，它们具有投影矩阵的所有元素都属于{-1,0，+1}的性质。这种结构特别适合于数据库环境，因为嵌入的计算减少到评估k个随机属性分区上的单个聚合。(C) 2003 Elsevier Science（美国）版权所有。
A classic result of Johnson and Lindenstrauss asserts that any set of n points in d-dimensional Euclidean space can be embedded into k-dimensional Euclidean space-where k is logarithmic in n and independent of d-so that all pairwise distances are maintained within an arbitrarily small factor. All known constructions of such embeddings involve projecting the n points onto a spherically random k-dimensional hyperplane through the origin. We give two constructions of such embeddings with the property that all elements of the projection matrix belong in {-1,0,+1}. Such constructions are particularly well suited for database environments, as the computation of the embedding reduces to evaluating a single aggregate over k random partitions of the attributes. (C) 2003 Elsevier Science (USA). All rights reserved.