論文の概要: 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回の追加実行によるマルチスタートを使用すると、非常に大規模な検索手順のパフォーマンスが改善される。
最後に,大規模近傍探索の複雑性を評価する手法を提案する。
関連論文リスト
- An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-09-30T15:57:14Z) - Gotta match 'em all: Solution diversification in graph matching matched
filters [14.850223878764309]
非常に大きな背景グラフに複数のノイズを埋め込んだテンプレートグラフを見つけるための新しい手法を提案する。
提案手法は,Sussmanらによって提案されたグラフマッチング・マッチング・フィルタ技術に基づいている。
論文 参考訳(メタデータ) (2023-08-25T15:53:30Z) - Doubly Stochastic Matrix Models for Estimation of Distribution
Algorithms [2.28438857884398]
本稿では,自然置換問題のマッチングと割当てにDSM(Douubly Matrices)を用いる方法について検討する。
具体的には、分散アルゴリズムの推定の枠組みを採用し、DSMを置換問題に対する既存の提案と比較する。
二次代入問題の事例に関する予備実験は、この研究の行を検証し、DSMが非常に競争力のある結果が得られることを示した。
論文 参考訳(メタデータ) (2023-04-05T14:36:48Z) - 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) - Determinantal Beam Search [75.84501052642361]
ビームサーチは、ニューラルシーケンスモデルをデコードするためのゴーツー戦略である。
複数のソリューションを要求するユースケースでは、多様あるいは代表的なセットがしばしば望まれる。
ビームサーチを一連の部分決定問題として繰り返し行うことにより、アルゴリズムを多種多様なサブセット選択プロセスに変換することができる。
論文 参考訳(メタデータ) (2021-06-14T13:01:46Z) - Expressivity of Parameterized and Data-driven Representations in Quality
Diversity Search [111.06379262544911]
2つの異なる検索空間で実施した品質多様性進化探索の出力多様性を比較する。
学習モデルは、未知の例への外挿や拡大よりも、既知のデータポイント間の補間が優れている。
論文 参考訳(メタデータ) (2021-05-10T10:27:43Z) - Improving Document Representations by Generating Pseudo Query Embeddings
for Dense Retrieval [11.465218502487959]
反復的なクラスタリングプロセスにより,各文書のクエリを模倣する手法を設計する。
また、2段階のスコア計算手順でマッチング関数を最適化する。
いくつかの人気ランキングとQAデータセットに関する実験結果から、私たちのモデルが最先端の結果を達成できることが示された。
論文 参考訳(メタデータ) (2021-05-08T05:28:24Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。