Повна версія

Головна arrow Природознавство arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

ОДНОВИМІРНА ІНТЕРВАЛЬНИЙ ПОШУК

Інтервальний пошук має очевидне додаток до систем баз даних. У базі даних, що містить записи про службовців деякої компанії, кожен запис має кілька атрибутів, таких, як вік, платню і т. Д., І може розглядатися як точка в n-вимірному просторі, в якому кожен атрибут відповідає вимірюванню, а число вимірювань простору п дорівнює числу атрибутів. Типова задача інтервального пошуку для двох вимірів полягає у виявленні всіх службовців, чиї вік і платню знаходяться в заданих інтервалах. Інший приклад можна знайти у Д. Кнута (23). Він розглядав базу даних міст США з координатами у вигляді широти і довготи. До такої базі природно постає запитання про перерахування всіх міст, що потрапляють в деякій прямоугольнік- запит. Це типова двовимірна задача інтервального пошуку.

Дослідженню завдання інтервального пошуку (в іншому перекладі з англійської - регіонального пошуку) присвячена велика кількість робіт [52, 67, 68, 79).

В даному розділі розглядається наступне завдання. Дано кінцеве безліч точок з відрізка [0,1]. Запит на пошук задає якийсь відрізок [о, b] З [0,1]. Треба перерахувати всі крапки з безлічі, які потрапляють в відрізок [а, 6). Це відома геометрична задача пошуку, описана, наприклад, в [52] і звана одновимірної завданням інтервального пошуку. В даному розділі досліджується питання, які алгоритми виникають, якщо обмежувати набір доступних засобів, або, більш формально, при різних базових множинах. Отримано також деякі нижні оцінки, за допомогою яких показується, що відповідні отримані алгоритми не можуть бути істотно поліпшені при даних обмеженнях на набір доступних засобів. Результати даного розділу були опубліковані в [10].

Отже, в одновимірної задачі інтервального пошуку безліч записів є відрізок [0,1], безліч запитів Xi n t

є безліч відрізків [і, v] З [0,1], або безліч пар точок (u, v), таких, що 0 <u <i> <1, тобто ХШ = = (n, v): 0 <u < v < 1}.

На Xint задано ймовірнісний простір (Xi nt) a, Р), де а - алгебра підмножин безлічі Xi nt) містить всі прямокутники зі сторонами паралельними осях координат і прямокутні трикутник з катетами також паралельними осях координат, Р - імовірнісна міра на а. Будемо вважати, що міра Р визначається функцією щільності розподілу ймовірностей p (u, v), тобто для будь-якого Вага

Для зручності будемо вважати, що р (і, v) визначена на всьому квадраті [0,1] х [0,1], але p (u, v) = 0 при (u t v) & Xi nt .

Ставлення пошуку, яке будемо позначати через pi nti визначається співвідношенням

де (h, v) € X inti у? Y int .

Тип Si n t = {Xi n ty Yi n t y Pint, сг, P) будемо називати типом одновимірного інтервального пошуку.

 
<<   ЗМІСТ   >>