論文の概要: Multidimensional Assignment Problem for multipartite entity resolution

• arxiv url: http://arxiv.org/abs/2112.03346v1
• Date: Mon, 6 Dec 2021 20:34:55 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-09 06:56:12.209559
• Title: Multidimensional Assignment Problem for multipartite entity resolution
• Title（参考訳）: 多部分解能の多次元アサインメント問題
• Authors: Alla Kammerdiner and Alexander Semenov and Eduardo Pasiliao
• Abstract要約: Multipartiteエンティティ解決は、複数のデータセットから1つのエンティティにレコードを統合することを目的としている。 代入問題を解くために、グリーディアルゴリズムと大規模近傍探索という2つの手順を適用する。 データベースのサイズが大きくなるにつれて、設計ベースのマルチスタートがより効率的であることを示す。
• 参考スコア（独自算出の注目度）: 69.48568967931608
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multipartite entity resolution aims at integrating records from multiple datasets into one entity. We derive a mathematical formulation for a general class of record linkage problems in multipartite entity resolution across many datasets as a combinatorial optimization problem known as the multidimensional assignment problem. As a motivation for our approach, we illustrate the advantage of multipartite entity resolution over sequential bipartite matching. Because the optimization problem is NP-hard, we apply two heuristic procedures, a Greedy algorithm and very large scale neighborhood search, to solve the assignment problem and find the most likely matching of records from multiple datasets into a single entity. We evaluate and compare the performance of these algorithms and their modifications on synthetically generated data. We perform computational experiments to compare performance of recent heuristic, the very large-scale neighborhood search, with a Greedy algorithm, another heuristic for the MAP, as well as with two versions of genetic algorithm, a general metaheuristic. Importantly, we perform experiments to compare two alternative methods of re-starting the search for the former heuristic, specifically a random-sampling multi-start and a deterministic design-based multi-start. We find evidence that design-based multi-start can be more efficient as the size of databases grow large. In addition, we show that very large scale search, especially its multi-start version, outperforms simple Greedy heuristic. Hybridization of Greedy search with very large scale neighborhood search improves the performance. Using multi-start with as few as three additional runs of very large scale search offers some improvement in the performance of the very large scale search procedure. Last, we propose an approach to evaluating complexity of the very large-scale neighborhood search.
• Abstract（参考訳）: multipartite entity resolutionは、複数のデータセットからのレコードを1つのエンティティに統合することを目的としている。 多次元割当問題(multidimensional assignment problem)として知られる組合せ最適化問題として、多くのデータセットをまたいだ多元エンティティ解決におけるレコード連鎖問題の一般クラスに対する数学的定式化を導出する。 このアプローチのモチベーションとして,シーケンシャルな2部マッチングよりも多部的なエンティティ解決の利点を示す。 最適化問題はNPハードであるため、グリーディアルゴリズムと非常に大規模な近傍探索という2つのヒューリスティックな手順を適用し、複数のデータセットからのレコードの最も起こりそうなマッチングを1つのエンティティに求める。 我々は,これらのアルゴリズムの性能と,それらの修正を合成生成データ上で評価・比較する。 我々は,近年の大規模近傍探索であるヒューリスティックとMAPのもう一つのヒューリスティックであるグリーディアルゴリズムと,一般メタヒューリスティックである遺伝的アルゴリズムの2つのバージョンを比較するために,計算実験を行った。 重要となるのは,前者のヒューリスティックな検索,特にランダムサンプリングによるマルチスタートと決定論的設計に基づくマルチスタートの2つの方法を比較する実験である。 データベースのサイズが大きくなるにつれて、設計ベースのマルチスタートがより効率的であることを示す。 さらに,大規模検索,特にマルチスタートバージョンは,単純なグレディヒューリスティックよりも優れていることを示す。 大規模近傍探索によるグレディ探索のハイブリッド化により性能が向上する。 最大3回の追加実行によるマルチスタートを使用すると、非常に大規模な検索手順のパフォーマンスが改善される。 最後に,大規模近傍探索の複雑性を評価する手法を提案する。

関連論文リスト

• Memetic collaborative approaches for finding balanced incomplete block designs [0.0]
  平衡不完全ブロック設計(BIBD)問題は、多数の対称性を持つ難しい問題である。 本稿では,古典的二元数定式化の代替として機能する双対(整数)問題表現を提案する。
  論文  参考訳（メタデータ） (2024-11-04T16:41:18Z)
• Retrieval with Learned Similarities [2.729516456192901]
  最先端の検索アルゴリズムは、学習された類似点に移行した。 そこで本研究では,Mixture-of-Logits (MoL) を実証的に実現し,多様な検索シナリオにおいて優れた性能が得られることを示す。
  論文  参考訳（メタデータ） (2024-07-22T08:19:34Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Greedy Relaxations of the Sparsest Permutation Algorithm [4.125187280299247]
  我々は, 忠実性よりもますます弱い仮定の下で, 効率的かつ点的に整合したアルゴリズム, GRaSP のクラスを開発する。 GRaSPの最も緩和された形式は、シミュレーションにおいて多くの最先端の因果探索アルゴリズムより優れている。
  論文  参考訳（メタデータ） (2022-06-11T05:00:36Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。 頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。 特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
  論文  参考訳（メタデータ） (2022-01-18T11:16:40Z)
• Expressivity of Parameterized and Data-driven Representations in Quality Diversity Search [111.06379262544911]
  2つの異なる検索空間で実施した品質多様性進化探索の出力多様性を比較する。 学習モデルは、未知の例への外挿や拡大よりも、既知のデータポイント間の補間が優れている。
  論文  参考訳（メタデータ） (2021-05-10T10:27:43Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Optimizing Revenue while showing Relevant Assortments at Scale [1.0200170217746136]
  リアルタイムアソシエーション最適化は、電子商取引業務において欠かせないものとなっている。 我々は、困難な状況下で最適なアソートを見つける高速で柔軟なアルゴリズムを設計する。 実世界のデータセットを用いた実証検証によると、我々のアルゴリズムは、アイテムの数が以前研究されたよりも105$$大きいインスタンスであっても競争力がある。
  論文  参考訳（メタデータ） (2020-03-06T20:16:49Z)

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

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