{"id":"W4232943531","doi":"10.1145/1109557.1109644","title":"Oblivious string embeddings and edit distance approximations","year":2006,"lang":"en","type":"article","venue":"Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":49,"is_retracted":false,"has_abstract":true,"ca_institutions":"Simon Fraser University","funders":"","keywords":"Edit distance; Embedding; Combinatorics; String (physics); Distortion (music); Approximation algorithm; Discrete mathematics; Mathematics; Algorithm; Computer science; Artificial intelligence","routes":{"ca_aff":true,"ca_fund":false,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.001271982,0.001361506,0.001515083,0.001347062,0.0007320627,0.002604861,0.004009307,0.002234647,0.004242427],"category_scores_gemma":[0.01679778,0.0009143192,0.000987153,0.002704248,0.001553785,0.01038757,0.003720789,0.003306946,0.002048926],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00238648,"about_ca_system_score_gemma":0.001185446,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.001673685,"about_ca_topic_score_gemma":0.001748053,"domain_scores_codex":[0.9963533,0.0008605585,0.0002752525,0.0008759529,0.001293388,0.0003416342],"domain_scores_gemma":[0.9915592,0.003401706,0.000760979,0.003641743,0.0004562396,0.000180033],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"simulation_or_modeling","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.0007541944,0.0002930541,0.001361395,0.0003721482,0.0001075858,0.0002464811,0.0004017309,0.5978806,0.009300991,0.1905442,0.006172647,0.1925649],"study_design_scores_gemma":[0.00005359076,0.00009631454,0.0001817931,0.00002397024,0.00002486623,0.0002108495,0.00004930002,0.8024178,0.006650481,0.1854507,0.004812004,0.00002836564],"study_design_candidate":"simulation_or_modeling","study_design_consensus":"simulation_or_modeling","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.01968241,0.0004757719,0.974861,0.0003054425,0.00005737911,0.00005450277,0.0002393872,0.001836989,0.002487109],"genre_scores_gemma":[0.3564612,0.0006400464,0.633437,0.0002885243,0.0001387787,0.0003334756,0.001251939,0.0005590546,0.00688996],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.004242427,"threshold_uncertainty_score":0.01731521,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.006974374443870286,"score_gpt":0.2227324276354105,"score_spread":0.2157580531915402,"validation_status":"score_only:v0-immature-baseline","note":"Baseline scores from an immature model (maturity gate not passed). Scores rank; they never assert a category."}}