論文の概要: Real-Time Device Reach Forecasting Using HLL and MinHash Data Sketches

• arxiv url: http://arxiv.org/abs/2502.14785v1
• Date: Thu, 20 Feb 2025 18:05:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-21 14:28:32.667997
• Title: Real-Time Device Reach Forecasting Using HLL and MinHash Data Sketches
• Title（参考訳）: HLLとMinHashデータスケッチを用いたリアルタイムデバイスリーチ予測
• Authors: Chandrashekar Muniyappa, Kendall Willets, Sriraman Krishnamoorthy,
• Abstract要約: ユーザが指定したターゲティング属性に基づいて、テレビ(デバイスリーチ)の正確な数をリアルタイムで予測することは、数百万ドルのADビジネスを実行する上で必須である。 我々はMinHashとHyperLogLog(HLL)データスケッチを用いた新しいリアルタイム予測システムを構築した。 さらに,1つの命令多重データ(SIMD)ベクトル化演算を用いて,数十億のレコードを処理するため,MinHashアルゴリズムを4倍高速に動作させるように改良した。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Predicting the right number of TVs (Device Reach) in real-time based on a user-specified targeting attributes is imperative for running multi-million dollar ADs business. The traditional approach of SQL queries to join billions of records across multiple targeting dimensions is extremely slow. As a workaround, many applications will have an offline process to crunch these numbers and present the results after many hours. In our case, the solution was an offline process taking 24 hours to onboard a customer resulting in a potential loss of business. To solve this problem, we have built a new real-time prediction system using MinHash and HyperLogLog (HLL) data sketches to compute the device reach at runtime when a user makes a request. However, existing MinHash implementations do not solve the complex problem of multilevel aggregation and intersection. This work will show how we have solved this problem, in addition, we have improved MinHash algorithm to run 4 times faster using Single Instruction Multiple Data (SIMD) vectorized operations for high speed and accuracy with constant space to process billions of records. Finally, by experiments, we prove that the results are as accurate as traditional offline prediction system with an acceptable error rate of 5%.
• Abstract（参考訳）: ユーザが指定したターゲティング属性に基づいて、テレビ(デバイスリーチ)の正確な数をリアルタイムで予測することは、数百万ドルのADビジネスを実行する上で必須である。 SQLクエリの従来のアプローチは、複数のターゲット範囲にわたる数十億のレコードを結合するのは非常に遅い。 回避策として、多くのアプリケーションは、これらの数字を整理し、何時間も後に結果を提示するオフラインプロセスを持つだろう。 私たちの場合、ソリューションはオフラインのプロセスで、顧客を乗せるのに24時間かかり、ビジネスが失われる可能性がありました。 この問題を解決するために,MinHashとHyperLogLog(HLL)データスケッチを用いたリアルタイム予測システムを構築した。 しかし、既存のMinHashの実装では、多レベルアグリゲーションと交差という複雑な問題を解決できない。 この研究は,MinHashアルゴリズムを改良し,SIMD(Single Instruction Multiple Data)ベクトル化演算を高速かつ高精度に行うことで,数十億のレコードを処理することができることを示す。 最後に、実験により、従来のオフライン予測システムと同等の精度で、許容誤差率は5%であることを示す。

関連論文リスト

• GraphHash: Graph Clustering Enables Parameter Efficiency in Recommender Systems [51.64666652517944]
  本稿では,モジュール性に基づく二部グラフクラスタリングを利用したグラフベースの最初のアプローチであるGraphHashを紹介する。 高速クラスタリングアルゴリズムを使用することで、GraphHashはプリプロセス中のメッセージパッシングの計算効率のよいプロキシとして機能する。 実験では、GraphHashは検索およびクリックスルーレート予測タスクの両方において、多様なハッシュベースラインを大幅に上回る。
  論文  参考訳（メタデータ） (2024-12-23T03:37:58Z)
• Minwise-Independent Permutations with Insertion and Deletion of Features [0.07252027234425332]
  Broder textitet. al.citepBroderCFM98は、バイナリデータの低次元スケッチを計算する$mathrmminHash$アルゴリズムを導入している。 アルゴリズムの厳密な理論的解析を行い、実世界の複数のデータセットに関する広範な実験を補完する。
  論文  参考訳（メタデータ） (2023-08-22T07:27:45Z)
• Computationally Budgeted Continual Learning: What Does Matter? [128.0827987414154]
  CL (Continuous Learning) は、新しいデータに適応しながら、以前の知識を保存し、分布の異なる入力データのストリーム上でモデルを逐次訓練することを目的としている。 現在のCL文献では、以前のデータへのアクセス制限に焦点が当てられているが、トレーニングの計算予算に制約は課されていない。 本稿では,この問題を大規模ベンチマークで再検討し,計算制約条件下での従来のCL手法の性能解析を行う。
  論文  参考訳（メタデータ） (2023-03-20T14:50:27Z)
• SC-Block: Supervised Contrastive Blocking within Entity Resolution Pipelines [75.5113002732746]
  本稿では,教師付きコントラスト学習を利用した埋め込み空間におけるレコードの位置決め手法であるSC-Blockを提案する。 SC-Blockを8つの最先端のブロッキング手法と比較した。 全体の実行時間を測定するため、99.5%の完全性を持つ候補集合を決定し、それらをマーカに渡す。
  論文  参考訳（メタデータ） (2023-03-06T13:49:41Z)
• Fast Online Hashing with Multi-Label Projection [15.85793225585693]
  本稿では,データベースの小さな部分のバイナリコードのみを更新するFast Online Hashing(FOH)手法を提案する。 実験結果から,提案したFOHは,最先端のベースラインよりも6.28秒少ないクエリ時間で劇的な優位性が得られることが示された。
  論文  参考訳（メタデータ） (2022-12-03T03:19:28Z)
• SLOSH: Set LOcality Sensitive Hashing via Sliced-Wasserstein Embeddings [18.916058638077274]
  本稿では,ANN (Non-parametric and data-independent learning from set-structured data using almost near neighbor (ANN) solutions。 Sliced-Wasserstein set embedding as a computerly efficient "set-2-vector" mechanism that possible downstream ANN。 本稿では,SLOSH (Set-LOcality Sensitive Hashing) と呼ばれるアルゴリズムの有効性を,様々なデータセットで示す。
  論文  参考訳（メタデータ） (2021-12-11T00:10:05Z)
• OMPQ: Orthogonal Mixed Precision Quantization [64.59700856607017]
  混合精度量子化は、ハードウェアの多重ビット幅演算を利用して、ネットワーク量子化の全ポテンシャルを解き放つ。 本稿では、整数プログラミングの損失と高い相関関係にあるネットワーク性の概念であるプロキシメトリックを最適化することを提案する。 このアプローチは、量子化精度にほとんど妥協することなく、検索時間と必要なデータ量を桁違いに削減する。
  論文  参考訳（メタデータ） (2021-09-16T10:59:33Z)
• Approximating Aggregated SQL Queries With LSTM Networks [31.528524004435933]
  本稿では、近似クエリ処理(AQP)とも呼ばれるクエリ近似法を提案する。 我々は、LSTMネットワークを用いて、クエリと結果の関係を学習し、クエリ結果を予測するための高速な推論層を提供する。 提案手法では,1秒間に最大12万のクエリを予測でき,クエリのレイテンシは2ms以下であった。
  論文  参考訳（メタデータ） (2020-10-25T16:17:58Z)
• The Sparse Vector Technique, Revisited [67.57692396665915]
  我々は、微分プライバシーの文献において最も基礎的で広く適用可能なテクニックの1つを再考する。 この単純なアルゴリズムは、データベース上のあるクエリの値が、私たちが期待している値に近いかどうかをプライベートにテストします。 一つの個人が過剰なクエリの回答に寄与しない限り、クエリのテストを継続できる代替の、等しくシンプルなアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-02T10:50:52Z)
• A Genetic Algorithm for Obtaining Memory Constrained Near-Perfect Hashing [0.0]
  本稿では,検索時の比較回数の最小化と,総コレクションサイズを最小化することに焦点を当てたハッシュテーブルに基づくアプローチを提案する。 論文は、ほぼ完全なハッシュはバイナリ検索よりも高速であるが、完全なハッシュよりも少ないメモリを使用することを示した。
  論文  参考訳（メタデータ） (2020-07-16T12:57:15Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。