범위 검색

심플렉스 범위 검색

컴퓨터 과학에서 범위 검색 문제는 S에서 어떤 개체가 범위라고 불리는 쿼리 개체와 교차하는지를 결정하기 위해 일련의 개체 S를 처리하는 것으로 구성됩니다.예를 들어, S가 여러 도시의 좌표에 해당하는 점 집합인 경우 주어진 위도 및 경도 범위 내에서 도시의 부분 집합을 찾습니다.

범위 탐색 문제와 이를 해결하는 데이터 구조는 계산 기하학의 기본 주제입니다.지리정보시스템(GIS), 컴퓨터지원설계(CAD), 데이터베이스 등의 영역에서 이 문제의 적용이 발생합니다.

바리에이션

문제에는 여러 가지 변형이 있으며, 다른 ^[1]변이에 따라 다른 데이터 구조가 필요할 수 있습니다.효율적인 해결책을 얻으려면 문제의 몇 가지 측면을 지정해야 합니다.

개체 유형:알고리즘은 S가 점, 선, 선분, 상자, 폴리곤으로 구성되어 있는지 여부에 따라 달라집니다.검색하기에 가장 간단하고 가장 많이 연구된 개체는 포인트입니다.
범위 유형:쿼리 범위도 미리 결정된 집합에서 가져와야 합니다.잘 연구된 범위 집합과 각 문제의 이름은 축 정렬 직사각형(직교 범위 검색), 단순함, 반공간 및 구/원입니다.
쿼리 유형:쿼리 범위와 교차하는 모든 객체의 목록을 보고해야 하는 경우 이 문제를 범위 보고라고 하며 쿼리를 보고 쿼리라고 합니다.경우에 따라서는 범위를 교차하는 개체의 수만 필요합니다.이 경우 이 문제를 범위 카운트라고 하고 쿼리를 카운트 쿼리라고 합니다.공백 쿼리는 범위를 교차하는 개체가 하나 이상 있는지 여부를 보고합니다.반그룹 버전에서는 교환 반그룹(S,+)이 특정되고, 각 점은 S로부터 가중치가 할당되며, 범위와 교차하는 점의 가중치의 반그룹 합계를 보고해야 한다.
동적 범위 검색과 정적 범위 검색:정적 설정에서는 세트 S를 미리 알 수 있다.동적 설정에서는 쿼리 간에 개체를 삽입하거나 삭제할 수 있습니다.
오프라인 범위 검색: 개체 집합과 전체 쿼리 집합을 미리 알고 있습니다.

데이터 구조

직교 범위 검색

2D 직교 범위 쿼리입니다.이 경우 범위 보고서 쿼리는 동그라미 두 점을 반환하고 범위 카운트 쿼리는 2를 반환하며 비어 있는 쿼리는 false를 반환합니다.

직교 범위 검색에서 세트 S는 d ${displaystyle$ d $}$ 의 $n$ $d$ n개 $n$ 으로 구성되며 쿼리는 각 차원의 간격으로 구성됩니다.따라서 쿼리는 다차원 축 정렬 직사각형으로 구성됩니다.출력 $k$ 가k(\ $displaystyle$ k $k$ 인 Jon Bentley는 k-d 트리를 사용하여 (Big O $O(n)$ 에서 $)$ O $n$ $O{\big (}n^{1-{\frac {1}{d}}}+k{\big )}$ 및 O( $O{\big (}n^{1-{\frac {1}{d}}}+k{\big )}$ - $O{\big (}n^{1-{\frac {1}{d}}}+k{\big )}$ $O{\big (}n^{1-{\frac {1}{d}}}+k{\big )}$ + k $)$ { $displaystyle$ O ${1-{\frac {1$ }{d $}+k}}$ ^[2] 쿼리를 $O{\big (}n^{1-{\frac {1}{d}}}+k{\big )}$ 실현했습니다.벤틀리 또한 O(로그 d⁡ n+k){O(\log ^{d}n+k)\displaystyle}에 질문 응답 시간을 개선 범위 나무를 사용하여 O에{O(n\log ^{d-1}n)\displaystyle}.[3]댄 윌러드 더 O까지의 쿼리 시간을 줄이기 위해 downpointers, 분별 cascading의 특별한 경우 사용(n로그 d− 1⁡ n)공간 증가했다 제안했다(통나무 d − $O(\log ^{d-1}n+k)$ $O(\log ^{d-1}n+k)$ + $O(\log ^{d-1}n+k)$ $)(\displaystyle$ O $(\log$ ^{ $d-1}n+k$

상기 결과는 포인터 머신 모델에서는 달성되었지만, 저차원(2D, 3D, 4D)에서의 연산의 RAM 모델에서는 한층 더 개선되었습니다.Bernard Chazelle은 압축 범위 트리를 사용하여 O $O(\log n)$ n $)$ { $displaystyle$ O $(\log$ n)} 쿼리 $O(\log n)$ 시간과 ^[5] $)$ { $displaystyle$ O $(n)}$ 공간을 $O(n)$ $O(\log n)$ 했습니다.이후 Joseph JaJa 등은 범위 카운팅을 위해 이 쿼리 시간을 O $O\left({\dfrac {\log n}{\log \log n}}\right)$ log $O\left({\dfrac {\log n}{\log \log n}}\right)$ n log $O\left({\dfrac {\log n}{\log \log n}}\right)$ ) $O\left({\dfrac {\log n}{\log \log n}}\right)$ {\ $display style$ O $\left({\dfrac {\log$ \ $log n}}\$ right $)$ 로 $O\left({\dfrac {\log n}{\log \log n}}\right)$ 개선했습니다.이 값은 하한과 일치하므로 점근적으로 ^[6]최적입니다.

2015년 현재 Timothy M이 발견한 범위 보고에 대한 최상의 결과(2D, 3D, 4D)입니다. Chan, Kasper Larsen 및 Mihai Pütracucu도 RAM 계산 모델에서 압축 범위 트리를 사용합니다.^[7]

$O(n)$ $O(n)$ ) $O(n)$ \ $displaystyle$ O ( $n$ )공간 $O(n)$ $O(\log ^{\epsilon }n+k\log ^{\epsilon }n)$ $O(\log ^{\epsilon }n+k\log ^{\epsilon }n)$ ( $O(\log ^{\epsilon }n+k\log ^{\epsilon }n)$ $O(\log ^{\epsilon }n+k\log ^{\epsilon }n)$ n + $O(\log ^{\epsilon }n+k\log ^{\epsilon }n)$ $O(\log ^{\epsilon }n+k\log ^{\epsilon }n)$ $O(\log ^{\epsilon }n+k\log ^{\epsilon }n)$ ) $O(\log ^{\epsilon }n+k\log ^{\epsilon }n)$ \ $displaystyle$ O ( \ $log$ ^ { \ $epsilon } n$ + k \ $log$ ^ { \ $epsilon }$ } $쿼리$ 시간
$O(n\log \log n)$ $O(\log \log n+k\log \log n)$ $O(n\log \log n)$ $O(n\log \log n)$ log $O(n\log \log n)$ log $O(n\log \log n)$ n ) $O(n\log \log n)$ { $displaystyle$ O ( $n$ \ $log$ \ $log$ \ log n ) $O(\log \log n+k\log \log n)$ } $O(\log \log n+k\log \log n)$ , $O(\log \log n+k\log \log n)$ ( log $O(\log \log n+k\log \log n)$ n + k log $O(\log \log n+k\log \log n)$ log $O(\log \log n+k\log \log n)$ log n $O(\log \log n+k\log \log n)$ ){ $displaystyle O$ ( \ $log$ \ k + $log$ \ $log$ \ log n $)$ } $쿼리$ 시간
$O(n\log ^{\epsilon }n)$ ( $O(n\log ^{\epsilon }n)$ log $O(n\log ^{\epsilon }n)$ ) { $displaystyle$ O ( $n$ \ $log$ ^ { \ $epsilon } n$ } 공간 $O(n\log ^{\epsilon }n)$ , $O(\log \log n+k)$ ( $O(\log \log n+k)$ log $O(\log \log n+k)$ n $O(\log \log n+k)$ + $O(\log \log n+k)$ ) $O(\log \log n+k)$ \ $displaystyle$ O ( \ $log n$ + k $)쿼리$ 시간

직교인 경우 경계 중 하나가 무한대인 경우 조회를 3면이라고 합니다.두 개의 경계가 무한대인 경우 쿼리는 양면이며, 무한대가 아닌 경우 쿼리는 4면입니다.

다이내믹 레인지 검색

정적 범위 검색에서는 세트 S를 미리 알고 있는 동안 동적 범위 검색, 점 삽입 및 삭제가 허용된다.문제의 증분 버전에서는 삽입만 허용되지만 증분 버전에서는 삭제만 허용됩니다.직교 케이스의 경우 Kurt Mehlhorn과 Stefan Néher는 동적 프랙셔널 캐스케이드를 사용하여 O $n$ log $O(n\log n)$ n $O(n\log n)$ ) $O(\log n\log \log n+k)$ 과 $O(n\log n)$ $O(\log n\log \log n+k)$ $O(\log n\log \log n+k)$ $O(\log n\log \log n+k)$ + $){$ $displaystyle$ O $(\log$ n $)\log n+k$ }^[8]쿼리를 $O(\log n\log \log n+k)$ $O(n\log n)$ 하는 동적 범위 검색을 위한 데이터 구조를 작성했습니다.문제의 증분 버전 및 증분 버전 모두 $O(\log n+k)$ O( $O(\log n+k)$ + k $)$ { $displaystyle$ O(\ $log$ n $+k)}$ 쿼리 $O(\log n+k)$ 시간으로 $O(\log n+k)$ 할 수 있지만 일반적인 다이내믹 범위 검색이 해당 쿼리 시간으로 수행될 수 있을지는 알 수 없습니다.

색상 범위 검색

색상 범위 카운트의 문제에서는 점이 범주형 속성을 갖는 경우를 고려합니다.범주가 기하학적 공간에서 점의 색상으로 간주되는 경우 쿼리는 특정 범위에서 나타나는 색상의 수에 대한 것입니다.Prosenjit Gupta 등은 1995년에 O $O(\log ^{2}n)$ ^[9]n 2 $O(n^{2}\log ^{2}n)$ 2 $O(n^{2}\log ^{2}n)$ n $O(n^{2}\log ^{2}n)$ )({ $displaystyle$ $O(n^{2$ }\log $O(n^{2}\log ^{2}n)$ $^{2}n$ $)}$ $O(\log ^{2}n)$ 과 $O($ 2 ${\$ n $)$ $쿼리$ 시간으로 2D 직교 색상 범위 카운트를 해결한 데이터 구조를 기술했다.

적용들

계산 지오메트리, 범위 검색 및 직교 범위 검색에서 고려될 뿐만 아니라 데이터베이스의 범위 쿼리에 대한 응용 프로그램도 있습니다.색상 범위 검색은 범주형 데이터를 검색하는 데에도 사용되며, 이를 통해 동기 부여됩니다.예를 들어, 25세에서 40세 사이이고 $10000에서 $20000 사이의 사람들을 나타내는 은행 계좌 데이터베이스에서 행을 결정하는 것은 나이와 돈이 2차원인 직교 범위 보고 문제가 될 수 있습니다.

「」를 참조해 주세요.

레퍼런스

^ Agarwal, P. K.; Erickson, J. (1999), "Geometric Range Searching and Its Relatives", in Chazelle, Bernard; Goodman, Jacob; Pollack, Richard (eds.), Advances in Discrete and Computational Geometry: proceedings of the 1996 AMS-IMS-SIAM joint summer research conference, Discrete and Computational Geometry--Ten Years Later, July 14-18, 1996, Mount Holyoke College, Contemporary Mathematics, vol. 223, American Mathematical Society Press, pp. 1–56
^ Bentley, Jon (1975). "Multidimensional binary search trees used for associative searching". Communications of the ACM. 18 (9): 509–517. doi:10.1145/361002.361007. S2CID 13091446.
^ Bentley, Jon (1980). "Multidimensional divide-and-conquer". Communications of the ACM. 23 (4): 214–229. doi:10.1145/358841.358850. S2CID 3997186.
^ Willard, Dan (1985). "New data structures for orthogonal range queries". SIAM Journal on Computing. 14 (1): 232–253. doi:10.1137/0214019.
^ Chazelle, Bernard (1988). "A functional approach to data structures and its use in multidimensional searching". SIAM Journal on Computing. 17 (3): 427–462. doi:10.1137/0217026.
^ JaJa, Joseph; Mortensen, Christian; Shi, Qingmin (2005). "Space-efficient and fast algorithms for multidimensional dominance reporting and counting". International Symposium on Algorithms and Computation: 558–568.
^ Chan, Timothy; Larsen, Kasper; Pătrașcu, Mihai (2011). "Orthogonal range searching on the RAM, revisited". Symposium on Computational Geometry: 1–10. arXiv:1103.5510.
^ Mehlhorn, Kurt; Näher, Stefan (1990). "Dynamic fractional cascading". Algorithmica. 5 (2): 215–241. doi:10.1007/BF01840386. S2CID 7721690.
^ Gupta, Prosenjit; Janardan, Ravi; Smid, Michiel (1995). "Further results on generalized intersection searching problems: Counting, reporting, and dynamization". Journal of Algorithms. 19 (2): 282–317. doi:10.1006/jagm.1995.1038. hdl:11858/00-001M-0000-0014-B721-F.

추가 정보

de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000), Computational Geometry (2nd ed.), Berlin: Springer-Verlag, ISBN 3-540-65620-0
를 클릭합니다Matoušek, Jiří (1994), "Geometric range searching", ACM Computing Surveys, 26 (4): 421–461, doi:10.1145/197405.197408, S2CID 17729301.

[Agarwal99-1] Agarwal, P. K.; Erickson, J. (1999), "Geometric Range Searching and Its Relatives", in Chazelle, Bernard; Goodman, Jacob; Pollack, Richard (eds.), Advances in Discrete and Computational Geometry: proceedings of the 1996 AMS-IMS-SIAM joint summer research conference, Discrete and Computational Geometry--Ten Years Later, July 14-18, 1996, Mount Holyoke College, Contemporary Mathematics, vol. 223, American Mathematical Society Press, pp. 1–56

[Bentley75-2] Bentley, Jon (1975). "Multidimensional binary search trees used for associative searching". Communications of the ACM. 18 (9): 509–517. doi:10.1145/361002.361007. S2CID 13091446.

[Bentley80-3] Bentley, Jon (1980). "Multidimensional divide-and-conquer". Communications of the ACM. 23 (4): 214–229. doi:10.1145/358841.358850. S2CID 3997186.

[Willard85-4] Willard, Dan (1985). "New data structures for orthogonal range queries". SIAM Journal on Computing. 14 (1): 232–253. doi:10.1137/0214019.

[Chazelle88-5] Chazelle, Bernard (1988). "A functional approach to data structures and its use in multidimensional searching". SIAM Journal on Computing. 17 (3): 427–462. doi:10.1137/0217026.

[JaJa05-6] JaJa, Joseph; Mortensen, Christian; Shi, Qingmin (2005). "Space-efficient and fast algorithms for multidimensional dominance reporting and counting". International Symposium on Algorithms and Computation: 558–568.

[Chan11-7] Chan, Timothy; Larsen, Kasper; Pătrașcu, Mihai (2011). "Orthogonal range searching on the RAM, revisited". Symposium on Computational Geometry: 1–10. arXiv:1103.5510.

[Mehlhorn90-8] Mehlhorn, Kurt; Näher, Stefan (1990). "Dynamic fractional cascading". Algorithmica. 5 (2): 215–241. doi:10.1007/BF01840386. S2CID 7721690.

[Gupta95-9] Gupta, Prosenjit; Janardan, Ravi; Smid, Michiel (1995). "Further results on generalized intersection searching problems: Counting, reporting, and dynamization". Journal of Algorithms. 19 (2): 282–317. doi:10.1006/jagm.1995.1038. hdl:11858/00-001M-0000-0014-B721-F.

[1]

[2]

[5]

[6]

[7]

[8]

[9]

Search

범위 검색

네임스페이스

더

목차

바리에이션

데이터 구조

직교 범위 검색

다이내믹 레인지 검색

색상 범위 검색

적용들

「」를 참조해 주세요.

레퍼런스

추가 정보

Search

범위 검색

바리에이션

데이터 구조

직교 범위 검색

다이내믹 레인지 검색

색상 범위 검색

적용들

「 」를 참조해 주세요.

레퍼런스

추가 정보

「」를 참조해 주세요.