hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
이호현 (소방공무원) 개인사
생전에는 응급구조사 자격 취득을 준비하며 직업적 역량을 키우려 했다. 가족에게는 성실하고 담담한 성품으로 기억되며, 순직 이후 유족과 동료들은 경포해변 추모비 인근을 꾸준히 돌보며 그의 희생을 기리고 있다.
배혁
배혁(1990년 11월 23일 – 2019년 10월 31일)은 대한민국의 소방공무원으로, 중앙119구조본부 항공 구조대원으로 복무하다가 2019년 10월 31일 독도 인근 해상에서 환자 이송 임무 중 추락사고로 순직하였다.
배혁 생애
경상북도 칠곡군에서 태어났으며, 해군 해난구조전대(SSU) 복무를 마친 뒤 2012년 5월 4일 소방공무원으로 임용되었다. 이후 중앙119구조본부 항공 구조대원으로 활동했고, 2019년 5월 헝가리 부다페스트 다뉴브강 유람선 침몰 사고 현장에 정부합동 긴급구조대 소속으로 파견되어 수색·구조 임무를 수행했다.
배혁 사고와 순직
2019년 10월 31일 밤, 경북소방본부의 환자 이송 요청에 따라 독도에 착륙해 환자와 보호자를 탑승시킨 뒤 이륙 직후 동도 인근 해상 약 600m 지점에서 사고가 발생했다. 사고 헬기는 중앙119구조본부 소속 에어버스 EC225(H225)로, 등록기호는 HL9619였다. 당시 상황은 당일 심야에 긴급발표와 브리핑으로 공개되었다.
배혁 조사
국토교통부 항공·철도사고조사위원회는 2023년 11월 6일 최종 조사결과를 발표하여, 야간 해상 이륙 구간의 시각적 기준 결여(소위 ‘블랙홀’ 환경)에서 비롯한 공간지각 상실(비행 착각)을 주요 원인으로 지목했고, 사전 브리핑·역할분담과 경보 대응 등 운항관리 측면의 보완 필요성을 제시했다.
배혁 예우와 추모
2019년 12월 10일 합동영결식에서 순직 소방항공대원 5인에 대한 1계급 특진과 예우가 이루어졌으며, 유해는 국립대전현충원에 안장되었다. 또한 ‘영예로운 제복상’ 단체 수상 등을 통해 희생의 뜻이 기려졌다.
배혁 평가와 유산
사고조사 결과는 야간 해상 운항의 인적요인 위험을 구체화하여, 사전 브리핑·임무분담·경보 대응절차 등 운항관리 표준을 정밀화하는 계기가 되었다. 구조대의 헌신과 희생은 합동영결식·현충원 안장·단체표창 등을 통해 공적으로 기려졌고, 조직은 야간 운항 안전성 제고와 장비·훈련의 보완을 추진하였다.
이창국
이창국은 대한민국의 소방청 소속 소방공무원이다. 대구소방안전본부 항공대 헬기 기장으로 경력을 시작해 2020년부터 중앙119구조본부 인명구조견센터장을 맡았다.
이창국 생애
이창국은 2005년부터 대구소방안전본부 항공대에서 헬기 기장으로 근무하며 항공 구조·진화 임무를 수행했다. 2020년 2월 중앙119구조본부로 전보되어 인명구조견센터장을 맡아 수색·수난 대응에서 구조견 운용과 지휘를 담당했다. 2021년에는 미국 코츠빌(시콜스키社)에서 진행된 소방청 S‑92 대형 소방헬기 1차 현지 중간검사 출장 인원으로 참여했다.
이창국 주요 활동
2020년 11월 17일 대구 동구 금호강 아양철교 인근에서 야간 산책 중 투신 시도 상황을 인지하고, 주변 시민과 협조해 구명튜브를 활용한 후 직접 하천으로 진입해 구조를 완수했다. 이후 응급조치가 이어져 생존이 확인되었다.
강원 대형 산불 기간의 헬기 진화 및 울산 남구 주상복합(삼환아르누보) 화재 대응에 참여하는 등 항공전력 운용과 현장 대응에 관여했다는 사실이 정부 공식 채널에 수록되었다. 또한 울산 고층 화재 당시 중앙119 헬기 지원이 요청·투입되는 상황이 언론 기록으로 남아 있다.
소방청 대형 소방헬기(S‑92) 도입 과정에서 2021년 6–7월 1차 현지 중간검사 출장에 참여했다.
이창국 평가
인사혁신처가 운영하는 ‘자랑스러운 공무원 이야기’에서 대형 산불 헬기 진화, 울산 고층 화재 대응, 금호강 수난 구조 사례를 통해 현장 전문성과 공공 안전 가치 기여가 소개되었다.
스웨덴의 주택정책
스웨덴의 주택정책은 스웨덴의 주택 임대료 규제, 공공·민간 임대주택 공급, 토지이용 및 금융규제를 포괄하는 제도 영역을 가리킨다. 정책의 핵심은 임대료를 ‘브룩스베르데(bruksvärde, 사용가치)’ 원칙과 집단교섭으로 정하는 단일 임대시장(unitary rental market)적 성격이며, 수도권 특히 스톡홀름에서 장기 대기열과 높은 진입장벽이 병존한다. 스톡홀름의 공공 임대대기 평균은 2024년 기준 약 8.8년이며, 도심 기존주택의 평균 대기기간은 20.6년, 도심 신축주택은 17.8년에 이른다.
스웨덴의 주택정책 개요
스웨덴의 임대시장은 임대료가 개별 수요·공급에 따라 완전 자유로이 결정되지 않고, 유사 주택의 조건과 위치·면적·상태 등을 비교해 ‘공정임대료’를 산정하는 사용가치 체계를 기본으로 한다. 분쟁 시 임대심판원(하위 법원)이 적정임대 여부를 판단하며, 전국적 차원에서는 임대인 단체와 세입자 단체(하이에레스예스테포레닝엔, Hyresgästföreningen)가 매년 집단교섭으로 인상률을 정한다.
스웨덴의 주택정책 역사적 전개: ‘밀리온 프로그램’에서 시장화까지
1965~1974년 사회민주당 정부가 추진한 ‘밀리온 프로그램(Million Programme)’은 10년간 100만 호 건설을 목표로 한 대형 공공주택 사업으로, 주거위생 개선과 주택재고 확충에 큰 영향을 주었다. 이후 1990년대부터는 공공임대 일부가 조합주택(보스타드스렛)으로 전환되며 소유화가 확대되었고, 이는 임대재고 축소와 대도시 임대수급 긴장을 가져왔다는 연구가 제기된다.
스웨덴의 주택정책 제도 설계: 사용가치 임대료와 집단교섭
브룩스베르데 원칙은 임대료를 유사 주택의 품질·면적·위치·설비 수준 등 객관 요소로 비교 산정하도록 규정한다. 이는 지나친 임대료 급등을 억제하는 장점이 있으나 신규공급 유인을 약화시키고 입주 대기열을 길게 만드는 부작용과 연결된다는 비판도 존재한다. 서브릿(2차 임차)이나 단기계약은 별도 규율을 받는다.
스웨덴의 주택정책 공공임대와 지방공기업: ‘알멘니타’의 역할
스웨덴의 공공임대는 지방자치단체가 소유한 주택회사(일명 알멘니타)가 운영하며, 임차인의 소득·신분을 좁게 한정하지 않는 ‘보편주의’적 성격을 유지한다. 공공주택 업계단체인 Public Housing Sweden은 300개 이상의 회사와 약 95만 호를 대표한다고 소개한다. 임대료는 공공·민간 모두에서 세입자 단체와의 교섭으로 정해지는 이른바 단일 임대체계가 기본이다.
스웨덴의 주택정책 수요·공급 동학과 대도시 대기열
스톡홀름에서는 시(市) 산하 임대주택 중개기관(Bostadsförmedlingen)에 등록해 순번을 쌓는 방식이 일반적이며, 연 200크로나의 대기등록비를 납부한다. 2024년 전체 평균 대기기간은 8.8년, 도심 기존주택 평균은 20.6년, 도심 신축은 17.8년으로 공표되었다. 공식 안내문은 “대기기간은 수개월에서 20년 이상까지 다양”하다고 명시한다. 한국 언론 보도는 도심에서 ‘대기 20년’ 현상을 집중 조명하며, 청년층의 기회비용을 문제로 제기했다.
스웨덴의 주택정책 가격·금융 환경
가격지표(HOX 기준)는 2022년 고점 이후 하락했다가 2024년에 일부 반등했으나, 연말 수준은 여전히 2022년 정점보다 낮았다. 2023~2024년의 건설 급감은 성장과 고용에 부담을 주었고, 2024년 주택착공은 2만 호 미만으로 예상된 바 있다. 한편 2024년 평균 임대료 상승률은 약 5%로 10여 년 만의 높은 수준이라는 시장 보고도 있다.
스웨덴의 주택정책 사회적 영향과 지역격차
보베르케트(Boverket)의 전국 조사에 따르면 2024년에는 148개 기초자치단체가 주택부족을 보고했고, 2025년 조사에서는 ‘부족’ 응답 지자체 수가 더 줄었으나 지역별 편차가 지속된다. 2025년 보고서는 사회적 배제·저투표율·범죄·과밀 등이 결합된 ‘취약 지역’ 증가가 사회통합을 위협한다고 경고했다. 청년층의 취업난은 주거 접근성 악화와 맞물려 논쟁 대상이 되며, 2024년 말 스웨덴의 청년실업률은 24.3%로 집계되었다(유로스타트 전재 수치).
스웨덴의 주택정책 국제 비교와 정책 논쟁
2021년에는 ‘신축주택 임대료 자유화(fri hyressättning vid nyproduktion)’ 추진을 둘러싼 정치적 갈등으로 당시 정부가 불신임을 당하면서 정책이 중단되었다. 정부 의뢰 보고서(SOU 2021:50)는 신축에 한해 자유임대료를 도입하는 모델을 상세히 설계했으나 입법으로 이어지지 못했다.
스웨덴의 주택정책 최근 개혁 논의
고금리기와 건설침체 이후, 정부 위원회와 당국은 주택금융 규제 완화·조정을 둘러싸고 상반된 견해를 보여 왔다. 2024년 말 정부위원회는 주택담보대출 담보인정비율(LTV) 상한을 90%로 높이고 상환의무를 완화하는 방안을 권고했고, 2025년 정부는 초보주택구입자 지원을 위해 규정 완화 계획을 발표했다. 반면 감독당국은 상환의무와 대출총량 규제가 금융안정을 높였다고 평가한다. 스웨덴의 상환규제는 원칙적으로 LTV 70%까지 연 2%, 50%까지 연 1% 상환을 요구하는 방향으로 논의·운영되어 왔다.
스웨덴의 주택정책 평가와 전망
스웨덴의 주택정책은 보편주의적 임대주택과 사용가치 임대료라는 역사적 설계를 통해 임차인의 주거안정과 예측가능성을 제공해 왔다. 그러나 대도시 집중, 건설비와 인허가 병목, 소유화 전환, 금리·물가 충격 등이 맞물리면서 공급부족과 대기열이 고착화되었다는 비판이 제기된다. 공공임대의 보편적 배분과 민간공급의 유인 사이 균형, 신축에 대한 임대료 규제의 설계, 지역 간 수급 격차 해소가 향후 개혁의 쟁점으로 남아 있다.
톰 사키
톰 사키(영어: Tom Szaky, 1982년 1월 14일~)는 헝가리 부다페스트 출생으로 캐나다에서 성장해 미국에서 활동하는 기업가이자 환경운동가로, 난(難)재활용 폐기물의 수거·재자원화 기업 테라사이클(TerraCycle)의 창립자 겸 최고경영자이며 2019년 세계경제포럼 다보스에서 공개된 재사용 포장 플랫폼 루프(Loop)의 공동 설계자이다.
톰 사키 생애
사키는 1982년 헝가리 부다페스트에서 의사인 부모 사이에서 태어났다. 어린 시절 가족과 함께 캐나다로 이주해 토론토에서 자랐다. 이후 프린스턴 대학교에서 심리학과 경제학을 공부했으나, 재활용이 어려운 폐기물 문제를 직접 해결하는 사업 구상에 몰두하며 학부 2학년 무렵 학업을 중단했다.
톰 사키 사상과 경영 기조
사키는 “Eliminating the Idea of Waste(폐기물이라는 개념의 제거)”를 기업의 사명으로 제시하며, 재사용을 소비자·제조사·소매사 모두에게 일회용만큼 편리하게 만드는 것을 목표로 한다. 그는 재활용만으로는 해결이 어려운 포장폐기 문제를 재사용 생태계 구축으로 완화해야 한다는 입장을 일관되게 피력한다. 루프는 내구성 용기를 제조사 소유로 유지하고, 보증금·회수·세척·재충전을 통해 ‘사용당 비용’을 최적화하는 설계를 추구한다.
톰 사키 비판과 논란
2021년 미국 비영리단체 라스트 비치 클린업(The Last Beach Cleanup)은 테라사이클과 여러 브랜드를 상대로 재활용 가능 표기와 라벨링이 소비자에게 오인될 수 있다고 캘리포니아주 법원에 소송을 제기했고, 같은 해 11월 당사자들은 합의에 도달해 라벨 투명성 강화와 기록 유지 등 시정조치를 진행하기로 했다.
톰 사키 평가
난재활용 소재의 상업적 수거·재자원화와 재사용 유통 실험을 결합한 점에서, 사키는 ‘폐기물의 개념을 경제적 자원으로 전환’하려는 시도를 대표하는 인물로 언급된다.
김진 (금융인)
김진(영어: Jin (Yongjin) Kim)은 헤지펀드·투자은행을 대상으로 생성형 인공지능 기반 투자 리서치/서치 소프트웨어를 제공하는 LinqAlpha(법인: Wecover Platforms, Inc.)의 공동창업자이며, 회사의 FRE(Fundamental Research Engineering) 총괄이다. 그는 캘리포니아 대학교 버클리에서 금융공학 석사(MFE)를 취득했고, 미국보험계리사협회(SoA) 준회원(ASA) 자격을 보유한다. 2025년 Forbes 30 Under 30 Asia(AI)에 선정되었다.
김진 (금융인) 개요
LinqAlpha는 다중 에이전트와 도메인 특화 검색·검증을 결합한 투자 리서치 자동화 소프트웨어를 제공한다. 회사는 Techstars Boston을 거쳐 2024년 6월 660만 달러 규모의 시드 투자를 유치했으며, 금융 애널리스트 워크플로(필링·콜·뉴스·프리젠테이션) 전반을 자동화하는 접근을 내세운다. 회사의 FRE(Fundamental Research Engineering)는 현업 애널리스트의 판단 구조를 다중 에이전트와 RAG에 임베딩하는 조직·역할 개념으로 정의된다.
김진 (금융인) 생애와 교육
김진은 UC 버클리 하스 경영대학원의 MFE 과정(Class of 2023)을 마쳤다. 또한 2020년 2월 미국보험계리사협회(SoA)로부터 ASA 자격을 취득했다.
김진 (금융인) 주요 활동
Fundamental Research Engineering(FRE)
FRE는 도메인 특화 검색·출처 검증·정형화(표준 KPI·약어 정규화)를 결합해 애널리스트의 프라이머·스크리닝·요약·가설 검증을 자동화하는 조직·방법론이다.
산업·행사 기여
2025년 뉴욕에서 ‘AI for Finance Summit(초청제·비공개·Chatham House Rule)’을 개최·주관하고 패널 모더레이터로 참여했다.
김진 (금융인) 연구 · 논문
최찬열; 권지훈; 로페스‑리라 알레한드로; 김채운; 김민재; 황준하; 하재선; 최호준; 윤수열; 김용진; 이영재 (2025). ‘‘FinAgentBench: 금융 질의응답에서 에이전트형 검색을 위한 벤치마크/FinAgentBench: A Benchmark Dataset for Agentic Retrieval in Financial Question Answering’’(arXiv). arXiv:2508.14052
이 논문은 금융 도메인에서 다단계 추론을 요구하는 ‘에이전트형 검색’ 성능을 정량화하기 위한 대규모 벤치마크를 제안한다. 벤치마크는 문서 유형 선택과 핵심 구절 식별을 분리해 맥락 한계를 줄인다. 여러 최신 LLM을 평가해 실제 리서치 시나리오에서의 정확도와 추론 특성을 비교한다. 표본 구축은 공개 공시·실적자료 등 실제 재무 문서를 기반으로 전문가 주석을 활용한다. 결과는 파인튜닝이 성능을 유의미하게 개선할 수 있음을 보인다.
김진 (금융인) 연구 · 논문
최찬열; 하재선; 윤수열; 김진; 외 (2025). ‘‘다중 에이전트 시스템을 이용한 재무 문서 정량정보 추출 및 질의/A Multi-Agent System for Extracting and Querying Financial Insights from Unstructured Documents’’(arXiv). arXiv:2505.19197
본 연구는 실적 공시·콜 트랜스크립트 등 비정형 재무 텍스트에서 KPI를 추출·정규화하는 ‘추출 에이전트’와 분석가 질의를 SQL로 변환하는 ‘Text‑to‑SQL 에이전트’를 제시한다. 표준화된 수치와 출처를 함께 제공합니다. 구조화된 결과를 대상으로 추가 질의를 수행할 수 있게 하여 리서치 반복 작업을 줄인다. 실제 애널리스트 워크플로에 맞춘 프롬프트·검증 루프를 통해 정확도를 높인다.
친애하는 X
친애하는 X(Dear X)는 2025년 11월 6일부터 12월 4일까지 공개되는 TVING 오리지널 드라마. 동명의 웹툰을 원작으로 한다.
권영달
권영달(1986년 4월 24일 ~ 2019년 6월 25일)은 대한민국의 소방공무원이다. 충청북도 소방본부 괴산소방서 119구조대에서 근무했으며, 2019년 6월 25일 충청북도 괴산군 청천면 달천강 일원에서 수난 구조훈련 중 발생한 안전사고로 순직하였다. 그는 순직에 따라 1계급 특별승진(소방교→소방장)과 옥조근정훈장을 받았고, 유해는 국립대전현충원에 안장되었다.
권영달 생애
1986년 충청북도 청주시에서 태어났다. 2017년 4월 1일 충청북도 소방공무원으로 임용되어 괴산소방서 119구조대에서 구조업무를 담당했다.
권영달 순직
2019년 6월 25일 14시 41분경 괴산소방서 119구조대의 수난 구조훈련 도중, 잠수장비 분실 상황이 발생하자 6명으로 탐색조를 편성해 수중 수색을 실시하였다. 잠수장비를 발견한 뒤 구조보트로 이동하는 과정에서 그가 보이지 않아 추가 수색을 벌였고, 같은 날 15시 20분경 수중에서 발견되었다. 당시 현장 보도에는 머리 부상이 확인됐다는 내용도 포함되었다.
권영달 영결식과 추서
2019년 6월 27일 괴산국민체육센터에서 영결식이 엄수되었다. 소방청은 1계급 특진과 옥조근정훈장을 추서했으며, 유해는 국립대전현충원에 안장되었다. 같은 기간 소방 당국은 국가유공자 지정 절차를 추진하였다.
권영달 조사와 후속 조치
사고 경위를 둘러싼 수사에서, 당시 훈련에 참여했던 동료 소방관 3명이 업무상과실치사 혐의로 검찰에 송치되었다(2019년 11월 22일).
권영달 평가와 영향
본 사건은 수난 구조훈련의 위험 관리와 현장 지휘·안전관리 체계 강화 필요성을 환기시켰다. 이후 소방 조직 내에서 교육훈련 사전 위험성 평가, 수중 수색 절차 표준화, 보트 운용 중 인원 관측체계(헤드카운트) 강화 등 개선 과제가 논의되었다.
권영달 개인사
사고 9일 전 혼인했다. 배우자 또한 소방공무원이다.
류소현
류소현(柳昭賢, 1951년 ~ )은 대한민국의 소방공무원으로, 제2기 소방간부후보생으로 임용되어 전라북도 소방(안전)본부장(제6·8대)과 경기도 북부소방재난본부 초대 본부장을 역임했다. 현장 중심의 예방 정책과 취약시설 관리 강화에 중점을 두었으며, 임실 전북119안전체험관 건립 추진을 비롯해 북부권 119 구조·구급 서비스 혁신을 이끌었다.
류소현 생애
1951년 전라남도 여천군에서 태어났다. 1980년 제2기 소방간부후보생으로 임용되었다. 서울소방방재본부 예방계장, 청와대 소방대장, 서울 양천·중부·종로소방서장, 행정자치부 방호과장, 소방방재청 구조구급과장 등을 거쳤다.
류소현 정책 및 기조
류소현은 “예방” 중심의 소방행정과 취약시설 관리 강화를 강조했다. 전북 부임 직후 예방활동과 장비 현대화, 신속 대응체계를 핵심 과제로 제시했다. 경기도 북부에서는 지역 특성을 반영해 ‘불조심 강조의 달’ 집중 캠페인과 위험물 운반 불시 단속을 병행했다.
류소현 리더십과 평가
전북 부임 시 “도민에게 감동을 주는 소방서비스”를 내세워 현장 중심 예방·대응, 인력·장비 현대화, 안전문화 확산을 동시에 추진했다는 평가가 있다. 경기도 북부에서는 지역 맞춤형 재난대응 전략과 대국민 홍보·교육을 강화해 119 이용 접근성을 높였다.
류소현 개인사
배우자는 박삼녀이며, 1남 2녀를 두었다.
강기봉
강기봉(1987년 8월 4일~2016년 10월 5일)은 대한민국의 소방공무원이다. 2016년 10월 5일 태풍 차바로 인한 울산광역시 울주군 회야강 일대 침수차량 구조 현장에서 급류에 휩쓸려 순직했다. 2016년 10월 8일 울산 종하체육관에서 울산광역시청장(葬)으로 영결식이 거행되었고, 1계급 특진(소방사→소방교)과 옥조근정훈장이 추서되었다. 유해는 제주 가족납골당에 안치되었다. 2017년 1월 ‘제6회 영예로운 제복상’ 시상식에서 위민소방관상이 사후 수여되었으며, 부친 강상주가 대리 수상하였다.
강기봉 생애
1987년 제주에서 태어났다. 부친 강상주는 1983년부터 2014년까지 31년간 제주에서 소방관으로 근무한 뒤 정년퇴직했다. 대학에서 간호학을 전공한 뒤 서울에서 간호사로 일했고, 2015년 4월 27일 울산광역시 구급대원(경력경쟁 특별채용)으로 임용되어 온산소방서에서 근무를 시작했다. 온산소방서 ‘체력 최강팀’에 선발되는 등 현장 대응 능력을 갖춘 구급대원으로 평가받았다.
강기봉 2016년 태풍 차바 대응과 순직
2016년 10월 5일 낮 “고립된 차량 안에 2명이 있는 것 같다”는 신고를 받고 동료 2명과 함께 울주군 회야댐 수질개선사업소 앞 회야강변으로 출동했다. 현장은 집중호우와 범람으로 수위가 급격히 올라 접근과 정착이 어려웠다. 구조 접근 중 낮 12시 6분경 갑작스러운 급류에 휩쓸려 실종되었고, 다음 날 오전 11시 10분경 실종 지점에서 하류로 약 3km 떨어진 덕망교 하류에서 발견되었다. 10월 8일 울산 종하체육관에서 울산광역시청장(葬)으로 영결식이 엄수되었고, 1계급 특진과 옥조근정훈장이 추서되었다.
강기봉 추모와 기념
2017년 제62회 현충일 중앙추념식에서 순직 소방공무원 유족으로서 부친 강상주에게 대통령 명의의 국가유공자증서가 수여되었다. 2018년 1월 2일 부친과 유족은 제주사회복지공동모금회에 강기봉의 이름과 부친의 이름으로 각각 1억 원씩, 총 2억 원을 기부하여 고인의 뜻을 기렸다.
강기봉 평가
동료들은 생전의 강기봉을 “몸을 사리지 않고 먼저 남을 생각하는 모범 대원”으로 회고하였다.
Unknow Softworks
언노우 소프트웍스(영어: Unknow Softworks)는 2019년 대한민국에 설립된 콘텐츠 개발 회사. 사업 분야로는 미디어 기획, 모바일 게임, 브랜드 디자인, 디자인 컨설턴트 등이 있다.
말레이시아-싱가포르 관계
말레이시아-싱가포르 관계(말레이어: Hubungan Malaysia–Singapura)는 말레이시아와 싱가포르의 양자 관계에 대해서 다루며, 두 나라의 정치, 경제, 그리고 사회와 문화 영역에 대해서 설명한다. 두 국가는 모두 영연방 및 동남아시아 국가 연합의 회원국이다.
말레이시아-싱가포르 관계 역사
믈라카 해협을 아우르는 말레이반도와 자와섬, 보르네오섬은 여러 국가들이 흥망성세를 경험한 곳이었다. 7세기에는 스리위자야의 영토에 포함되었으며, 이후 마자파힛 제국 등이 이 지역을 다스렸다. 15세기 즈음에 이르려, 동남아시아 서부로부터 이슬람교의 유입에 따라서 이 지역은 무슬림의 국가인 술탄국이 여럿 등장하였다. 대표적인 술탄국 중 하나가 바로 믈라카 술탄국이며, 14세기까지 존속하였던 싱가푸라 왕국과 혈통이 이어져 있다. 이후 조호르 술탄국이 이 지역을 다스렸다.
말레이시아-싱가포르 관계 역사
현대적인 의미에서 말레이시아와 싱가포르가 건국되기 이전에, 이 지역은 대영제국의 식민지였으며, 싱가포르는 토머스 스탬퍼드 래플스가 이 지역을 개발하면서 역사가 시작되었다. 특히 영국 동인도 회사가 피낭섬을 할양받고, 싱가포르와 믈라카를 통합하여 해협 식민지로 다스렸다. 반면에 말레이시아는 영국이 보호령을 선언하고, 말레이 연합주와 말레이 비연합주라는 이름 아래 술탄들의 권력을 어느 정도 인정하면서 영국의 영향력과 지배력 아래 두었다. 제2차 세계 대전 당시 이 지역은 말레이 전역으로 분류되어, 영연방군과 일본군 간 산발적인 전투가 벌어졌다. 이 지역에 주둔하고 있던 영연방군의 항복과 함께, 말레이반도의 일부가 마라야, 즉 일본 제국의 영토로 편입되기도 하였다. 2차 대전이 끝난 이후에는, 이 지역은 다시 영국의 식민지로 반환되었다. 영국령 말라야는 이후 말라야 연합은 말라야 연방으로 개편되었으며, 1957년에 영국으로부터 독립하는데 성공한다. 이후 싱가포르, 사라왁주, 사바주가 말라야 연방에 동참하면서 1963년 말레이시아로 새롭게 개편되었다. 이 당시 싱가포르는 말레이시아 연방 안에 싱가포르주라는 이름으로 1963년부터 1965년까지 편입되어 있었다. 두 나라가 하나의 나라였다는 점은 말레이시아 싱가포르 항공의 존재에서도 잘 확인된다.
말레이시아-싱가포르 관계 역사
리콴유와 툰쿠 압둘 라만은 국가를 공동 운영하는데 있어서 어려움을 겪었으며, 특히 인종 문제에 있어서 상이한 시각을 드려냈다. 리콴유는 다민족 평등주의와 세속주의를 주장하며, 모든 말레이인이 평등해야 한다고 주장하였으나, 툰쿠 압둘 라만은 오늘날 부미푸트라 정책으로 잘 알려진 일종의 말레이 민족 우선주의을 주장하며, 말레이인이 원주민로서 특권을 가져야 한다고 입장을 밝혔다. 이는 일종의 중국계 싱가포르인과 말레이시아인 간 갈등이라는 논란적인 주제였으며, 싱가포르 내 인종 간 폭동이 발생하면서 갈등과 상황의 심화를 발생시켰다. 특히 국내 정치적 측면에서는, 말레이시아 의회 내 인민행동당과 통일말레이국민조직 간 갈등도 존재하였다. 인종적인 문제와 별개로, 싱가포르와 말레이시아는 경제와 산업 정책에서도 다른 입장을 보였으며, 싱가포르의 자유 무역 및 개방경제 노선은 말레이시아의 보호무역 및 농업 중심 경제 노선과 일치되기에는 어려운 것이었다.
이렇게 정치 및 경제 체제에서 방향성 차이와, 인종 간 갈등이 격화되는 가운데, 말레이시아 내각은 1965년 8월 7일에 싱가포르를 말레이시아로부터 분리를 논의하고, 8월 9일 싱가포르의 분리독립을 승인하였다.
말레이시아-싱가포르 관계 역사
두 나라는 지리적으로 인접하고 문화적으로 공유하는 점이 많지만, 분리 이후 다른 노선을 걸었다. 싱가포르는 비동맹 운동에 가담하였으나, 말레이시아는 이슬람교를 바탕으로 한 외교 노선을 운영하였다. 말레이시아-싱가포르 국경이 확정되고, 한동안 인적 왕래와 이주 등 교류가 제한되었던 적도 있었다. 그러나 1980년대부터 양국 관계는 1960년대보다 누그러졌으며, 리콴유와 말레이시아 총리 마하티르 빈 모하맛의 정상회담을 통해서 양국 간 협력이 논의되었다. 두 국가의 관계는 경쟁하면서도, 서로 의존하는 모습을 보여줬다. 1990년대에 들어 두 국가 간 상호 무역량이 증대되고, 국방 협력을 시작하는 등 관계 개선을 지속적으로 이뤄냈다. 2000년대에는 싱가포르는 말레이시아의 최대 투자국 중 하나  되었으며, 양국 간 경제 의존도가 심화되었다.
동남아시아 조약 기구를 제외하고, 동남아시아 지역에서는 지역주의 차원에서 별다른 다자주의를 바탕으로 한 지역협력이 가시적으로 드려나지 않았다. 그러나 1967년, 정치·경제 협력 강화, 공산주의 확산 방지, 지역 평화와 안정 유지 등을 목표로 동남아시아 국가 연합이 창립되었으며, 말레이시아와 싱가포르는 창립국으로서 다시 만나게 되었다.
지리적으로 인접한 두 국가의 특성 때문에, 해상 및 영토에 관련된 분쟁이 일부 존재한다. 대표적으로 페드라브랑카섬 분쟁으로 섬에 대한 영유권을 두고 두 나라는 관계 개선에 대한 어려움을 겪었다.
말레이시아-싱가포르 관계 교통
조호르-싱가포르 코즈웨이와 말레이시아-싱가포르 세컨드 링크 등 육로로 연결되어 있다. 두 국가 간 고속철도 건설이 논의되고 있다.
말레이시아 쿠알라룸푸르 국제공항과 싱가포르 창이 공항 간 직항이 여러 개 개설되어있다.
무르그 무살람
무르그 무살람(힌디어: मुग़लाई खाना, 우르두어: مغلائی پکوان, 벵골어: মুঘলাই রন্ধনশৈলী)은 인도 무굴식 닭고기 요리이다. 닭고기 전체를 생강-마늘 페이스트에 재워 삶은 달걀을 채워넣고 사프란, 계피, 정향나무, 양귀비씨, 카다멈, 고추 등의 향신료로 양념한 요리이다. 마른 상태로 굽거나 소스에 넣어 조리하며, 아몬드와 바르크로 장식한다.
무르그 무살람 역사
무르그 무살람은 페르시아어로 문자 그대로 '통닭'을 의미한다. 이 요리는 현재 인도의 우타르프라데시주에 해당하는 아와드의 무굴 왕실 가족들 사이에서 인기가 많았다. 또한 '잘 익은'이라는 의미도 있다.
이븐 바투타는 무르그 무살람을 무함마드 빈 투글루크가 가장 좋아하는 요리라고 묘사했다. 이 요리는 델리 술탄국에서도 제공되었다.
자기상관
자기상관(영어: Autocorrelation)은 이산 시간의 경우 계열 상관(영어: serial correlation)이라고도 불리며, 신호와 그 신호가 지연된 사본 사이의 상관을 측정한다. 본질적으로, 이는 서로 다른 시점에서의 확률 변수 관측값 간의 유사성을 정량화한다. 자기상관 분석은 잡음에 의해 가려진 신호 내에서 반복되는 패턴이나 숨겨진 주기성을 식별하기 위한 수학적 도구이다. 자기상관은 신호 처리, 시간 영역 및 시계열 분석에서 시간 경과에 따른 데이터의 동작을 이해하는 데 널리 사용된다.
연구 분야마다 자기상관을 다르게 정의하며, 이러한 정의가 모두 동등하지는 않다. 일부 분야에서는 이 용어가 자기공분산과 상호 교환적으로 사용된다.
다양한 시계열 모델은 단위근 과정, 추세 정상 과정, 자기회귀 과정, 이동평균 과정과 같은 자기상관을 포함한다.
자기상관 확률 과정의 자기상관
통계학에서 실수를 갖거나 복소수를 갖는 확률 과정의 자기상관은 서로 다른 시간에서의 과정 값 간의 피어슨 상관이며, 두 시간 또는 시간 지연의 함수로 나타난다. 를 확률 과정이라고 하고, 를 임의의 시점이라고 하자(는 이산 시간 과정의 경우 정수일 수 있고, 연속 시간 과정의 경우 실수일 수 있다). 그러면 는 시간 에서의 특정 실행에 의해 생성된 값(또는 관측값)이다. 과정이 각 에 대해 시간 에서 평균 와 분산 을 가진다고 가정하자. 그러면 시간 과  사이의 자기상관 함수의 정의는 다음과 같다.:{{{1}}}:{{{1}}}
여기서 는 기댓값 연산자이고 위 막대는 켤레 복소수를 나타낸다. 기댓값이 잘 정의된 것이 아닐 수도 있다는 점에 유의한다.
곱셈 전에 평균을 빼면 시간 과  사이의 자기공분산 함수가 산출된다.:{{{1}}}:{{{1}}}
이 표현식은 모든 시계열 또는 과정에 대해 잘 정의되지 않을 수 있는데, 이는 평균이 존재하지 않거나, 분산이 0(상수 과정의 경우)이거나 무한대(특정 유형의 멱법칙과 같이 잘 동작하는 모멘트가 없는 분포를 가진 과정의 경우)일 수 있기 때문이다.
자기상관 확률 과정의 자기상관
가 광의의 정상 과정이라면 평균 와 분산 은 시간에 독립이며, 또한 자기공분산 함수는 과  사이의 시차에만 의존한다. 즉, 자기공분산은 값 쌍 사이의 시간 거리에만 의존하며 시간상의 위치에는 의존하지 않는다. 이는 자기공분산과 자기상관이 시간 지연의 함수로 표현될 수 있고, 이것이 지연 의 짝함수가 될 것임을 의미한다. 이것은 자기상관 함수에 대한 더 익숙한 형태를 제공한다.:{{{1}}}
그리고 자기공분산 함수:
특히, 다음을 유의한다.
일부 분야(예: 통계학 및 시계열 분석)에서는 자기공분산 함수를 정규화하여 시간에 의존하는 피어슨 상관 계수를 얻는 것이 일반적이다. 그러나 다른 분야(예: 공학)에서는 일반적으로 정규화를 생략하고 "자기상관" 및 "자기공분산"이라는 용어를 상호 교환적으로 사용한다.
확률 과정의 자기상관 계수 정의는 다음과 같다.:{{{1}}}
함수 가 잘 정의되면 그 값은  범위에 있어야 하며, 1은 완벽한 상관을 나타내고 -1은 완벽한 역상관을 나타낸다.
자기상관 확률 과정의 자기상관
광의의 정상(WSS) 과정의 경우, 정의는 다음과 같다.
정규화는 자기상관을 상관으로 해석하는 것이 통계적 의존성 강도에 대한 척도 불변 측정을 제공한다는 점과 정규화가 추정된 자기상관의 통계적 특성에 영향을 미친다는 점에서 중요하다.
자기상관 함수 가 짝함수라는 사실은 다음과 같이 표현할 수 있다.:{{{1}}}

각각 WSS 과정의 경우::{{{1}}}
WSS 과정의 경우::{{{1}}}

는 항상 실수라는 점에 유의한다.
코시-슈바르츠 부등식, 확률 과정에 대한 부등식::{{{1}}}
연속 시간 백색 잡음 신호의 자기상관은 에서 강한 피크(주로 디랙 델타 함수로 표현됨)를 가지며, 다른 모든 에 대해서는 정확히 이 된다.
위너-힌친 정리는 자기상관 함수 와 전력 스펙트럼 밀도 를 푸리에 변환을 통해 연결한다.
실수 값 함수에 대해 대칭 자기상관 함수는 실수 대칭 변환을 가지므로, 위너-힌친 정리는 실수 코사인만으로 재표현될 수 있다.
자기상관 확률 벡터의 자기상관
(잠재적으로 시간에 의존하는) 확률 벡터 의 (잠재적으로 시간에 의존하는) 자기상관 행렬(두 번째 모멘트라고도 함)은 확률 벡터 의 모든 요소 쌍의 자기상관을 요소로 포함하는  행렬이다. 자기상관 행렬은 다양한 디지털 신호 처리 알고리즘에 사용된다.
기댓값과 분산이 존재하는 확률 요소를 포함하는 확률 벡터 에 대해 자기상관 행렬은 다음과 같이 정의된다.:{{{1}}}:{{{1}}}
여기서 는  크기의 전치 행렬을 나타낸다.
구성 요소별로 작성:
가 복소 확률 벡터인 경우, 자기상관 행렬은 대신 다음과 같이 정의된다.
여기서 는 에르미트 전치를 나타낸다.
예를 들어, 가 확률 벡터이면 는 -번째 원소가 인  행렬이다.
자기상관 결정론적 신호의 자기상관
신호 처리에서 위 정의는 종종 정규화 없이, 즉 평균을 빼거나 분산으로 나누지 않고 사용된다. 자기상관 함수가 평균과 분산으로 정규화되면 때로는 자기상관 계수 또는 자기공분산 함수라고 불린다.
신호 가 주어졌을 때, 연속 자기상관 는 대부분  자체와의 연속 교차상관 적분으로, 지연 로 정의된다.:{{{1}}}
여기서 는 의 켤레 복소수를 나타낸다. 적분 내의 매개변수 는 더미 변수이며 적분을 계산하는 데만 필요하다는 점에 유의한다. 특정 의미는 없다.
이산 시간 신호 에 대한 지연 에서의 이산 자기상관 은 다음과 같다.
위 정의는 제곱 적분 가능하거나 제곱 합산 가능, 즉 유한 에너지를 가진 신호에 적용된다. "영원히 지속되는" 신호는 대신 확률 과정으로 취급되며, 이 경우 기댓값을 기반으로 다른 정의가 필요하다. 광의의 정상 확률 과정의 경우, 자기상관은 다음과 같이 정의된다.
정상 과정이 아닌 과정의 경우, 이들은  또는 의 함수가 된다.
자기상관 결정론적 신호의 자기상관
또한 에르고딕 과정의 경우, 기댓값은 시간 평균의 극한으로 대체될 수 있다. 에르고딕 과정의 자기상관은 때때로 다음과 같이 정의되거나 동일시된다.
이러한 정의는 함수가 정상 에르고딕 과정의 출력이 아니더라도 주기 함수에 대해 합리적이고 잘 정의된 단일 매개변수 결과를 제공한다는 장점이 있다.
또는, 영원히 지속되는 신호는 유한 시간 적분을 사용하는 단시간 자기상관 함수 분석으로 처리할 수 있다. (관련 과정은 단시간 푸리에 변환을 참조한다.)
가 주기 를 가진 연속 주기 함수인 경우, 에서 까지의 적분은 길이 인 임의의 구간 에 대한 적분으로 대체된다.
이는 다음와 동등하다.
다음에서는 1차원 자기상관의 속성만 설명할 것인데, 대부분의 속성은 1차원 경우에서 다차원 경우로 쉽게 전이되기 때문이다. 이러한 속성은 광의의 정상 과정에 적용된다.
자기상관 다차원 자기상관
다차원 자기상관도 유사하게 정의된다. 예를 들어, 3차원 공간에서 제곱 합산 가능한 이산 신호의 자기상관은 다음과 같다.
자기상관 함수를 계산하기 전에 신호에서 평균값을 빼면, 그 결과 함수는 일반적으로 자기공분산 함수라고 불린다.
자기상관 효율적인 계산
이산 시퀀스로 표현된 데이터의 경우, 자기상관을 높은 계산 효율성으로 계산해야 하는 경우가 많다. 신호 처리 정의 에 기반한 무차별 대입법은 신호 크기가 작을 때 사용할 수 있다. 예를 들어, 실수 신호 시퀀스  (즉, , 그리고 다른 모든 i 값에 대해 )의 자기상관을 손으로 계산하려면, 주어진 정의가 "일반적인" 곱셈과 동일하지만, 오른쪽 시프트가 있으며, 각 세로 덧셈이 특정 지연 값에 대한 자기상관을 제공한다는 것을 먼저 인식해야 한다.
따라서 필요한 자기상관 시퀀스는 이며, 여기서   그리고  다른 지연 값에 대한 자기상관은 0이다. 이 계산에서 우리는 일반적인 곱셈에서처럼 덧셈 중 올림 연산을 수행하지 않는다. 자기상관의 내재된 대칭성을 활용하여 필요한 연산 수를 절반으로 줄일 수 있다는 점에 유의한다. 만약 신호가 주기적이라면, 즉 이라면, 우리는 이전 자기상관 시퀀스의 왼쪽과 오른쪽 꼬리가 겹쳐져 를 생성하는 원형 자기상관( 원형 합성곱과 유사)을 얻게 되는데, 이는 신호 시퀀스 와 동일한 주기를 갖는다. 이 절차는 이산 신호의 Z변환의 합성곱 속성을 적용한 것으로 볼 수 있다.
자기상관 효율적인 계산
무차별 대입 알고리즘은 차수 n2이지만, n log(n) 차수로 자기상관을 계산할 수 있는 여러 효율적인 알고리즘이 존재한다. 예를 들어, 위너-힌친 정리는 두 번의 고속 푸리에 변환 (FFT)을 사용하여 원본 데이터 X(t)에서 자기상관을 계산할 수 있게 한다.
여기서 IFFT는 역 고속 푸리에 변환을 나타낸다. 별표는 켤레 복소수를 나타낸다.
또는, 다중 τ 상관은 낮은 τ 값에 대해 무차별 대입 계산을 수행한 다음, 로그 밀도로 X(t) 데이터를 점진적으로 묶어 더 높은 값을 계산함으로써 동일한 n log(n) 효율성을 얻지만, 메모리 요구 사항은 더 낮아진다.
자기상관 추정
평균과 분산이 알려진 이산 과정에서 개의 관측치 를 관찰했을 때, 자기상관 계수의 추정치는 다음과 같이 얻을 수 있다.
모든 양의 정수 에 대해. 실제 평균 와 분산 이 알려져 있을 때, 이 추정치는 불편 추정량이다. 과정의 실제 평균과 분산이 알려져 있지 않은 경우 몇 가지 가능성이 있다.
마지막 유형의 추정치들의 장점은 의 함수로서 추정된 자기상관 세트가 정확히 그 자기상관을 갖는 이론적 과정을 정의할 수 있다는 의미에서 유효한 자기상관 함수를 형성한다는 것이다. 다른 추정치들은 의 선형 조합의 분산을 계산하는 데 사용될 경우, 계산된 분산이 음수가 될 수 있다는 문제점을 가질 수 있다.
자기상관 회귀 분석
시계열 데이터를 사용하는 회귀 분석에서는 관심 변수의 자기상관이 일반적으로 자기회귀모형 (AR), 이동평균 모델 (MA), 이들의 조합인 자기회귀-이동평균 모델 (ARMA), 또는 후자의 확장인 자기회귀 누적 이동평균 모델 (ARIMA)로 모델링된다. 여러 상호 관련 데이터 계열의 경우 벡터자기회귀모형 (VAR) 또는 그 확장이 사용된다.
정규방정식 (OLS)에서 모델 사양의 적절성은 부분적으로 회귀 잔차의 자기상관이 있는지 여부를 확인하여 점검할 수 있다. 관찰되지 않는 오차의 문제적 자기상관은 일반적으로 관찰 가능한 잔차에서 자기상관을 생성하므로 감지할 수 있다. (오차는 계량경제학에서 "오차 항"으로도 알려져 있다.) 오차의 자기상관은 오차 항이 상관 없다는 정규방정식 가정을 위반하며, 이는 가우스-마르코프 정리가 적용되지 않고 OLS 추정량이 더 이상 최량 선형 불편 추정량(BLUE)이 아님을 의미한다. OLS 계수 추정량을 편향시키지는 않지만, 낮은 지연에서 오차의 자기상관이 양수일 때 표준 오차는 과소평가되는 경향이 있다 (그리고 t-점수는 과대평가된다).
자기상관 회귀 분석
1차 자기상관 존재에 대한 전통적인 검정은 더빈-왓슨 통계량이거나, 설명 변수에 지연된 종속 변수가 포함된 경우 더빈의 h 통계량이다. 그러나 더빈-왓슨은 값과 그 지연 사이의 피어슨 상관으로 선형적으로 매핑될 수 있다. 더 높은 차수의 자기상관을 다루고, 회귀 변수에 종속 변수의 지연이 포함되는지 여부에 관계없이 적용 가능한 더 유연한 검정은 브뢰슈-갓프리 검정이다. 이 검정은 보조 회귀를 포함하는데, 여기서 관심 모델을 추정하여 얻은 잔차를 (a) 원래 회귀 변수와 (b) 잔차의 k개 지연(여기서 'k'는 검정의 차수)에 대해 회귀한다. 이 보조 회귀에서 검정통계량의 가장 간단한 버전은 TR2인데, 여기서 T는 표본 크기이고 R2는 결정계수이다. 자기상관이 없다는 귀무 가설 하에서, 이 통계량은 k 자유도를 가진 카이제곱 분포 로 점근적으로 분포한다.
0이 아닌 자기상관에 대한 대응책에는 일반화 최소제곱과 뉴웨이-웨스트 HAC 추정량 (이분산성 및 자기상관 일관성)이 포함된다.
이동평균 모델 (MA)의 추정에서 자기상관 함수는 포함될 지연 오차 항의 적절한 수를 결정하는 데 사용된다. 이는 q차 MA 과정의 경우 에 대해 이고, 에 대해 이라는 사실에 기반한다.
자기상관 응용
자기상관이 자료에서 반복되는 패턴을 찾는 능력은 다음과 같은 많은 응용 분야를 낳는다.
자기상관은 동적 광산란 데이터를 분석하는 데 사용되며, 이는 유체에 부유된 나노미터 크기 입자 또는 미셀의 입자 크기 분포를 결정할 수 있게 한다. 혼합물에 레이저를 비추면 입자의 움직임으로 인해 스페클 패턴이 생성된다. 신호의 자기상관은 입자의 확산 측면에서 분석할 수 있다. 이를 통해 유체의 점도를 알면 입자의 크기를 계산할 수 있다.
GPS 시스템에서 위성에서 반송파 신호가 전송되는 시점과 지상 수신기에서 수신되는 시점 사이의 전달 지연 또는 시간 이동을 보정하는 데 활용된다. 이는 수신기가 1,023비트 C/A (Coarse/Acquisition) 코드의 복제 신호를 생성하고, 들어오는 위성 신호의 도플러 편이를 수용하기 위해 약간씩 이동하면서 10개씩 또는 10,230개 칩 (1,023 × 10)의 코드 칩 [-1,1] 라인을 생성하여, 수신기 복제 신호와 위성 신호 코드가 일치할 때까지 계속된다.
자기상관 계열 의존성
계열 의존성은 자기상관 개념과 밀접하게 관련되어 있지만, 별개의 개념을 나타낸다 ( 상관 분석과 의존성 참조). 특히, 계열 의존성이 있지만 (선형) 상관이 없을 수도 있다. 그러나 일부 분야에서는 두 용어가 동의어로 사용된다.
확률 변수의 시계열은 계열에서 어떤 시간 의 값이 다른 시간 의 값에 통계적으로 의존하는 경우 계열 의존성을 갖는다. 계열은 어떤 쌍 사이에도 의존성이 없는 경우 계열 독립적이다.
시계열 가 정상이면, 쌍  사이의 통계적 의존성은 동일한 지연 에서 모든 값 쌍 사이에 통계적 의존성이 있음을 의미한다.
자기상관 추가 자료
솔타날리안, 모즈타바; 스토이카, 페트르 (2012). 《Computational Design of Sequences with Good Correlation Properties》. 《IEEE Transactions on Signal Processing》 60. 2180쪽. Bibcode:2012ITSP...60.2180S. doi:10.1109/TSP.2012.2186134.
스킵 그래프
스킵 그래프(영어: Skip graph)는 스킵 리스트를 기반으로 하는 일종의 분산 자료 구조이다. 이것은 2003년 제임스 아스프네스(James Aspnes)와 가우리 샤(Gauri Shah)가 발명했다. 거의 동일한 자료 구조인 스킵넷(SkipNet)은 2003년에 니콜라스 하비(Nicholas Harvey), 마이클 존스(Michael Jones), 스테판 사로이우(Stefan Saroiu), 마빈 타임머(Marvin Theimer), 알렉 울먼(Alec Wolman)이 독자적으로 발명했다.
스킵 그래프는 분산 시스템에서 균형 잡힌 트리의 모든 기능을 수행한다. 스킵 그래프는 주로 P2P 네트워크 검색에 사용된다. 키 정렬을 통해 쿼리 기능을 제공하므로 해시 테이블 기능에만 의존하는 검색 도구보다 개선되었다. 스킵 리스트 및 다른 트리 자료 구조와 달리 매우 탄력적이며 많은 노드 실패를 허용할 수 있다. 또한 노드 실패로 인해 방해받는 스킵 그래프를 구성하고, 삽입하고, 검색하고, 복구하는 것은 간단한 알고리즘으로 수행할 수 있다.
스킵 그래프 설명
스킵 그래프는 스킵 리스트를 기반으로 하는 분산 자료 구조로, 균형 잡힌 탐색 트리를 닮도록 설계되었다. 스킵 그래프는 네트워크 전반에 걸쳐 다른 위치에 저장된 리소스를 리소스의 이름(또는 키)을 기반으로 찾아내는 데 사용되는 분산 해시 테이블을 구현하는 여러 방법 중 하나이다.
스킵 그래프는 Chord 및 Tapestry와 같은 다른 분산 해시 테이블 방식에 비해 여러 이점을 제공한다. 예상 로그 시간 내에 추가 및 삭제가 가능하며, 인덱싱 정보 저장에 리소스당 로그 공간이 필요하고, 세트에 있는 노드 수를 알 필요가 없으며, 복잡한 범위 쿼리를 지원한다. Chord 및 Tapestry와의 주요 차이점은 리소스의 검색 키를 해싱하지 않아 관련 리소스가 스킵 그래프에서 서로 가까이 있을 수 있다는 점이다. 이 속성 덕분에 주어진 범위 내의 값을 검색하는 것이 가능하다. 스킵 그래프의 또 다른 장점은 무작위 및 적대적 실패 모델 모두에서 노드 실패에 대한 탄력성이다.
스킵 그래프 구현 세부 사항
스킵 리스트와 마찬가지로, 노드는 여러 레벨에 걸쳐 증가하는 순서로 배열된다. 레벨 i의 각 노드는 확률 p(조정 가능한 매개변수)로 레벨 i+1에 포함된다.
레벨 0은 세트의 모든 노드를 포함하는 하나의 이중 연결 리스트로 구성된다. 리스트는 상위 레벨로 갈수록 점점 희소해져, 결국 하나의 노드만으로 구성된 리스트가 된다. 스킵 그래프가 스킵 리스트와 다른 점은 각 레벨 i≥1에 여러 개의 리스트가 포함된다는 것이다. 리스트에 키 x가 포함되는지 여부는 멤버십 벡터 에 의해 정의된다. 멤버십 벡터는 고정된 알파벳에 대한 무한 임의 단어로 정의되며, 스킵 그래프의 각 리스트는 동일한 알파벳의 유한 단어 w로 식별된다. 이 단어가 의 접두사이면 노드 x는 해당 리스트의 멤버이다.
스킵 그래프 작업
스킵 그래프는 검색, 삽입 및 삭제의 기본 작업을 지원한다. 스킵 그래프는 더 복잡한 범위 검색 작업도 지원한다.
스킵 그래프의 검색 알고리즘은 스킵 리스트의 검색 알고리즘과 거의 동일하지만, 분산 시스템에서 실행되도록 수정되었다. 검색은 최상위 레벨에서 시작하여 구조를 통과한다. 각 레벨에서 검색은 다음 노드가 더 큰 키를 포함할 때까지 리스트를 통과한다. 더 큰 키가 발견되면 검색은 다음 레벨로 내려가 키를 찾거나 키가 노드 집합에 포함되어 있지 않다고 판단될 때까지 계속된다. 키가 노드 집합에 포함되어 있지 않으면 검색 키보다 작은 가장 큰 값이 반환된다.
리스트의 각 노드에는 다음 필드가 있다.
key
노드의 값.
neighbor[R/L][level]
레벨 i에서 노드의 이중 연결 리스트에 있는 오른쪽 및 왼쪽 이웃에 대한 포인터를 포함하는 배열.
스킵 그래프 작업
윌리엄 퍼그(William Pugh)의 분석에 따르면, 평균적으로 스킵 리스트는 고정된 p 값에 대해  레벨을 포함하며, 이는 스킵 그래프에도 확장된다. 각 레벨당 평균  노드만 검색된다고 가정하면, 전송되는 총 메시지 수는 이며, 검색 예상 시간은 이다. 따라서 고정된 p 값에 대해, 검색 작업은 O(log n) 메시지를 사용하여 O(log n) 시간이 걸릴 것으로 예상된다.
삽입은 두 단계로 이루어지며, 새로운 노드 u가 소개 노드 v를 알고 있어야 한다. 소개 노드는 현재 스킵 그래프에 있는 다른 어떤 노드라도 될 수 있다. 첫 번째 단계에서 새로운 노드 u는 소개 노드 v를 사용하여 자신의 키를 검색한다. 이 검색은 실패하고 u보다 작은 가장 큰 키를 가진 노드 s를 반환할 것으로 예상된다. 두 번째 단계에서 u는 최상위 레벨의 리스트에서 유일한 요소가 될 때까지 각 레벨에 자신을 삽입한다. 각 레벨에서의 삽입은 표준 이중 연결 리스트 연산을 사용하여 수행된다. 왼쪽 이웃의 다음 포인터는 새 노드를 가리키도록 변경되고, 오른쪽 이웃의 이전 포인터는 새 노드를 가리키도록 변경된다.
스킵 그래프 작업
검색과 유사하게, 삽입 작업은 예상 O(log n) 메시지와 O(log n) 시간을 소비한다. 고정된 p 값으로, 1단계의 검색 작업은 O(log n) 시간과 메시지를 소비할 것으로 예상된다. 2단계에서 각 레벨 L ≥ 0에서, u는 평균적으로 1/p의 다른 노드와 통신하여 s'를 찾는데, 이는 O(1/p) 시간과 메시지를 필요로 하며, 2단계의 각 단계마다 O(1) 시간과 메시지로 이어진다.
노드는 각 레벨에서 병렬로 O(1) 시간과 O(log n) 메시지로 삭제될 수 있다. 노드가 그래프를 떠나기를 원할 때, 즉시 이웃에게 메시지를 보내 다음 및 이전 포인터를 재배열해야 한다.
스킵 그래프는 평균 O(log n) 레벨을 포함한다. 각 레벨에서 u는 이중 연결 리스트에서 삭제 작업을 완료하기 위해 2개의 메시지를 보내야 한다. 각 레벨의 작업은 병렬로 수행될 수 있으므로, 삭제 작업은 O(1) 시간과 예상 O(log n) 메시지를 사용하여 완료될 수 있다.
스킵 그래프 결함 허용
스킵 그래프에서 결함 허용은 다른 노드의 실패로 인해 스킵 그래프에서 연결이 끊어질 수 있는 노드의 수를 의미한다. 무작위 실패와 적대적 실패의 두 가지 실패 모델이 조사되었다. 무작위 실패 모델에서는 어떤 노드든지 다른 노드와 독립적으로 어떤 확률로든 실패할 수 있다. 적대적 모델은 노드 실패가 각 단계에서 최악의 실패를 달성하도록 계획되며, 전체 스킵 그래프 구조가 알려져 있고 노드 단절을 최대화하도록 실패가 선택된다고 가정한다. 스킵 그래프의 단점은 복구 메커니즘이 없다는 것이다. 현재 스킵 그래프를 제거하고 복구하는 유일한 방법은 살아남은 노드로 새로운 스킵 그래프를 구축하는 것이다.
스킵 그래프 결함 허용
스킵 그래프는 무작위 오류에 매우 강하다. 이웃 노드의 상태 정보를 유지하고, 실패한 이웃을 피하기 위해 중복 링크를 사용함으로써 많은 노드 오류에도 불구하고 정상적인 작업을 계속할 수 있다. 실패한 노드의 수가  미만인 동안 스킵 그래프는 정상적으로 계속 작동할 수 있다. 제임스 아스프네스가 수행한 시뮬레이션에 따르면, 131072개의 노드를 가진 스킵 그래프는 살아남은 노드들이 고립되기 전까지 최대 60%의 노드 오류를 견딜 수 있었다. 다른 분산 데이터 구조들이 더 높은 수준의 탄력성을 달성할 수도 있지만, 그들은 훨씬 더 복잡한 경향이 있다.
적대적 실패는 최악의 실패 패턴을 찾기 어렵기 때문에 대규모 네트워크에서 시뮬레이션하기 어렵다. 이론적 분석에 따르면, 탄력성은 그래프의 정점 확장 비율에 따라 달라지며, 이는 다음과 같이 정의된다. 그래프 G에서 노드 집합 A에 대해, 확장 요소는 A에 속하지 않지만 A의 노드에 인접한 노드의 수를 A의 노드 수로 나눈 값이다. 스킵 그래프가 의 충분히 큰 확장 비율을 가진다면, f개의 실패가 특별히 목표로 설정되더라도 최대 개의 노드만 분리될 수 있다.