この記事では、近似最近傍（ANN）探索と近似カーネル密度推定（A-KDE）に関する新しいスケッチアルゴリズムを提案しています。これらは、データ分析や大規模な意思決定など、現代の機械学習の中核をなす基本的な問題です。特に、大規模で動的なデータストリームにおいて、重要な構造的特性を保持しつつ、効率的なクエリを可能にするコンパクトなスケッチを設計することが課題となっています。著者たちは、ANNおよびA-KDE用のサブリニアな空間とクエリ時間を保証する新しいスケッチ手法を開発。ANNでは、サブリニアなメモリで近似エラーとメモリサイズの最適なトレードオフを達成し、一方のA-KDEでは、スライディングウィンドウモデルにおける初の理論的なサブリニアスケッチ保証を提案。実験では、提案されたスケッチが軽量かつ低エラーであることが示されています。