정적 네트워크에서의 최단 경로 쿼리 (Shortest-path queries in static networks)
Source
Evernote/IFTTT Feedly/Shortest-path queries in static networks.md
Summary
이 문서는 정적 네트워크(그래프) 환경에서의 점대점(point-to-point) 최단 경로 쿼리 문제를 다룬 ACM Computing Surveys 논문 소개입니다. 단일 출발점 최단 경로(SSSP) 및 모든 쌍 최단 경로(APSP) 문제의 일반화로, 네트워크에 대한 전처리(preprocessing)를 통해 데이터 구조나 인덱스를 구축한 후, 실제 쿼리 시 응답 속도를 최적화하는 접근법을 설명합니다. 교통, 네트워킹, 사회과학 등 다양한 분야에서 응용되며, 알고리즘 엔지니어링(경로 계획), 데이터베이스(물리화 트레이드오프, 공간 네트워크 쿼리), 이론 컴퓨터 과학(거리 오라클, 희박 스패너) 등 여러 학문적 관점에서 연구되어 왔음을 강조합니다.
Key Points
- 점대점 최단 경로 쿼리는 SSSP 및 APSP 문제의 일반화 형태임.
- 전처리(preprocessing) 단계를 통해 인덱스나 데이터 구조를 구축하여 쿼리 응답 속도를 향상시키는 것이 핵심.
- 교통, 네트워킹, 사회과학 등 다양한 실용적 응용 분야를 가짐.
- 알고리즘 엔지니어링, 데이터베이스 시스템, 이론 컴퓨터 과학 등 다양한 연구 커뮤니티에서 관련 기술을 개발하고 분석함.
Related
-
Quantifying and Verifying Reachability for Access Controlled Networks
-
Scheduling in a Random Environment: Stability and Asymptotic Optimality
-
Backward Path Growth for Efficient Mobile Sequential Recommendation
-
Joint consideration of energy-efficiency and coverage-preservation in microsensor networks
-
Node-Capture Resilient Key Establishment in Sensor Networks Design Space and New Protocols
-
Privacy- and Integrity-Preserving Range Queries in Sensor Networks
-
Scalable Network Virtualization in Software-Defined Networks
-
People reidentification in surveillance and forensics: A survey
-
Wireless Networks Design in the Era of Deep Learning Model-Based, AI-Based, or Both
-
A Proxy View of Quality of Domain Name Service, Poisoning Attacks and Survival Strategies
-
Behavior-Oriented Data Resource Management in Medical Sensing Systems
-
Approximation Algorithms for the Directed k-Tour and k-Stroll Problems
-
Semantic Multimodal Compression for Wearable sensing Systems
-
Efficient Multiview Maintenance under Insertion in Huge Social Networks
-
Anomaly Extraction in Backbone Networks Using Association Rules