영역 탐색 알고리즘에 대한 질문입니다.

superkkt의 이미지

안녕하세요.

영역 탐색에 대해서 질문을 하려고 합니다. 그런데 제가 생각하는 부분이 영역 탐색이라고 말하는게 맞는지 잘 모르겠네요.

제가 만드려는 프로그램은 우선 실수형 데이터들을 DB로 구축합니다. 그리고 찾으려는 실수값을 주면 해당 값에서 미리 정해진 문턱값을 +-한 범위에 속하는 모든 실수형 데이터를 빠르게 찾아내야 합니다.

예를 들어 0.05라는 값이 쿼리되었을 때, 문턱값이 0.005라면 0.045 ~ 0.055에 해당하는 실수형 데이터들을 DB에서 찾아내야 합니다.

정확히 일치하는 값을 찾는게 아니라 일정 범위 안의 값을 찾아내는 프로그램은 처음 접해보는 것이라서 어떤 방법으로 DB를 구축해야 할지 감이 잘 안잡히네요.

일단 Inverted Index나 Inverted List를 사용해서 실수를 미리 여러 개의 영역으로 나눠놓고, 쿼리된 실수가 속하는 영역과 그 앞, 뒤 영역을 모두 검색해서 보여줄까 생각을 하고 있는데, 별로 좋은 방법이 아니라는 생각이 자꾸 드네요.

이럴 땐 어떤 알고리즘을 사용하는것이 좋은지 조언 부탁 드립니다.

Mr.Big의 이미지

B+ tree index를 만드시고, range scan을 하시는게 좋을것 같습니다.

만일 A라는 값과 threshold t가 있을때, A-t <= x <= A+t 인 값을 찾아야 하는데,

B+ tree를 사용해 A-t 값으로 일단 검색합니다. leaf 까지 내려 가면

A-t값과 같거나 A-t가 없는 경우 A-t보다 큰 값 중 가장 작은 값을 가진 leaf를 찾을 수 있습니다.

그런후 해당 leaf를 따라가며 A+t보다 큰 값이 나올때 까지 range scan을 하면 될것 같습니다.

tigercat의 이미지

보통 지도에서 해당영역에 포함된 데이타가 어떤것이 있는지
(예를들어 여의도에는 어떤데이타가 있는지와 같은)

의 질의를 할때 사용한다고 알고 있습니다. 직접 구현은 안해봤지만

학교수업시간에 배웠는데 기억이 가물가물.

데이타를 R+ 트리에 삽입하시고 영역질의를 이용하시면 될것 같구요.

윗분 말씀처럼 B+ 트리를 이용하신다면 찾고자 하는 데이타의 미니멈 데이타를

리프노드까지 찾아내려간다음 거기서 순차검색으로 맥시멈 데이타가 나올때까지

원하는 데이타를 찾으시는 방법도 한가지 방법이 될 것 같습니다

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.