Високоефективно йерархично текстово търсене

Сега съм във финалните етапи на надграждане на йерархичния дизайн в голяма транзакционна система и известно време се взирам в тази заявка от 150 реда (която ще ви спестя досадата от четене) и си мисля, че има трябва да е по-добър начин.

Кратко обобщение на въпроса е както следва:

Как бихте приложили йерархично търсене, което отговаря на няколко думи за търсене на различни нива в йерархията, оптимизирано за най-бързо време за търсене?


Намерих донякъде свързан въпрос, но всъщност е само около 20% от отговора, от който всъщност се нуждая. Ето пълния сценарий/спецификация:

  • Крайната цел е да намерите един или няколко произволни елемента на произволни позиции в йерархията.
  • Пълната йерархия е около 80 000 възли, които се очаква да нараснат до 1 милион в рамките на няколко години.
  • Пълният текст на целия път надолу по йерархията е уникален и описателен; обаче текстът на отделен възел може да не е такъв. Това е бизнес реалност, а не решение, взето с лека ръка.
  • Пример: възел може да има име като „Врата“, което е безсмислено само по себе си, но пълният контекст, „Аарон > Къща > Дневна > Шкаф за алкохол > Врата“ има ясно значение, описва конкретна врата на определено място. (Имайте предвид, че това е само пример, реалният дизайн е много по-малко тривиален)
  • За да намери тази конкретна врата, потребителят може да напише "aaron liquor door", което вероятно ще покаже само един резултат. Заявката се превежда като последователност: елемент, съдържащ текста "door", под елемент, съдържащ текста "liquor", под друг елемент, съдържащ текста "aaron."
  • Или потребителят може просто да напише "домашен алкохол", за да изброи всички шкафове за алкохол в къщите на хората (не би ли било хубаво). Споменавам този пример изрично, за да посоча, че търсенето не трябва да съответства на конкретно коренно или листно ниво. Този потребител знае точно коя врата търси, но не може да си спомни веднага кой я притежава и би запомнил, ако името изскочи пред него.
  • Всички термини трябва да бъдат съпоставени в указаната последователност, но както показват горните примери, нивата в йерархията могат да бъдат "пропуснати". Терминът „шкаф за алкохол на Аарон“ няма да съответства на този възел.
  • Платформата е SQL Server 2008, но смятам, че това е проблем, който не зависи от платформата и предпочитам да не ограничавам отговорите до тази платформа.
  • Самата йерархия се основава на hierarchyid (материализиран път), индексиран както в ширина, така и в дълбочина. Всеки йерархичен възел/запис има Name колона, към която трябва да се направи заявка. Йерархичните заявки, базирани на възела, са изключително бързи, така че не се притеснявайте за тях.
  • Няма строга йерархия - един корен може изобщо да не съдържа възли или може да съдържа 30 поддървета, разпръснати до 10 000 листови възли.
  • Максималното влагане е произволно, но на практика има тенденция да бъде не повече от 4-8 нива.
  • Йерархията може и се променя, макар и рядко. Всеки възел може да бъде преместен във всеки друг възел, с очевидните изключения (родител не може да бъде преместен в собствения си дъщерен възел и т.н.)
  • В случай, че това вече не се подразбира: имам контрол върху дизайна и мога да добавя индекси, полета, таблици, каквото може да е необходимо за постигане на най-добри резултати.

Моята „мечта“ е да предоставя незабавна обратна връзка на потребителя, както при прогресивно търсене/филтър, но разбирам, че това може да е невъзможно или изключително трудно. Ще се радвам на всяко значително подобрение спрямо текущия метод, който обикновено отнема между 0,5s до 1s в зависимост от броя на резултатите.

За пълнота съществуващата заявка (съхранена процедура) започва със събиране на всички листови възли, съдържащи крайния термин, след което се присъединява нагоре и изключва всички, чиито пътища не съвпадат с по-ранните термини. Ако на някого това изглежда назад, бъдете сигурни, че е много по-ефективно, отколкото да започнете с корените и да ги разпръснете. Това беше „старият“ начин и лесно можеше да отнеме няколко секунди на търсене.

И така, въпросът ми отново: Има ли по-добър (по-ефективен) начин за извършване на това търсене?

Не търся непременно код, просто подходи. Обмислих няколко възможности, но всички изглежда имат някои проблеми:

  • Създайте разделена колона „текст на пътя“ и я индексирайте с пълнотекстово търсене. Проблемът е, че търсене в тази колона ще върне и всички дъщерни възли; "къща на Аарон" съвпада и с "кухня в къщата на Аарон" и "сутерен на къща на Аарон".
  • Създаде колона NamePath, която всъщност е вложена последователност от низове, използвайки тип CLR, подобен на самия hierarchyid. Проблемът е, че нямам представа как Microsoft може да "преведе" заявки от този тип в индексни операции и дори не съм сигурен дали е възможно да се направи на UDT. Ако крайният резултат е просто сканиране на пълен индекс, не съм спечелил нищо с този подход.

Всъщност не е краят на света, ако не мога да направя нещо по-добро от това, което вече имам; търсенето е "доста бързо", никой не се е оплакал от него. Но съм готов да се обзаложа, че някой вече се е занимавал с този проблем и има някои идеи. Моля, споделете ги!


database search performance database-design hierarchy
person Aaronaught    schedule 30.12.2009    source източник
comment
+1 Вярно. Какво прави текущото изпълнение?   -  person Hamish Grubijan    schedule 31.12.2009
comment
Освен това какъв е максималния брой нива? Броят на нивата фиксиран ли е?   -  person Hamish Grubijan    schedule 31.12.2009
comment
Опитах се да обясня какъв е текущият метод. Ако можете да бъдете по-конкретни относно това, което не е ясно, ще се радвам да допълня.   -  person Aaronaught    schedule 31.12.2009
comment
Вие описвате системата като транзакционна. Това означава ли, че самата йерархия се променя - изтрити или изменени възли, както и добавени? Също така, само листни възли ли са или могат да се добавят цели пътеки? Може ли листен възел да бъде преместен от един клон в друг?   -  person APC    schedule 31.12.2009
comment
@APC: Добър въпрос и отговорът е да. Добавих бележка за това във въпроса.   -  person Aaronaught    schedule 31.12.2009

Отговори (2)


arrow_upward
3
arrow_downward

разгледайте Apache Lucene. Можете да приложите много гъвкави, но ефективни търсения с помощта на Lucene. Може да е полезно.

Разгледайте и моделите за търсене – това, което описвате, може да се впише в модела за фасетирано търсене.

Доста лесно е да се приложи тривиален алгоритъм „Aaron House Living Door“, но не съм сигурен, че обикновените алгоритми, базирани на SVM/класификация/ентропия, ще се мащабират до голям набор от данни. Може също да искате да разгледате концепциите за „търсене на приближение“ от Motwani и Raghavan.

Моля, публикувайте обратно това, което сте намерили, ако е възможно :-)

person srini.venigalla    schedule 30.12.2009
comment
Погледнах търсенето на приближения и първият резултат съдържаше текста NP-hard - scary! Lucene изглежда обещаващо; ще ми отнеме известно време, за да премина, и все пак бих предпочел самостоятелно решение, но това отваря някои възможности, така че +1 и за вашия отговор. - person Aaronaught; 31.12.2009

arrow_upward
3
arrow_downward

Здравей Арън, имам следната идея:
От твоето описание имам следния образ в съзнанието си: 

          Aaron
         /     \
        /       \
       /         \
  House           Cars
    |            /    \
Living Room   Ferrari  Mercedes
    |
Liquor Cabinet
    /    |    \
Table   Door   Window

Ето как може да изглежда вашето дърво за търсене. Сега бих сортирал възлите на всяко ниво:

               Aaron
              /     \
             /       \
            /         \
         Cars         House
         /   \       /
        /     \     /
       /       \   /
      /         \ /
     /           X
    /           / \
   /           /   \
  /           /     \
 /           /       \
|           /         \
|          /           \ 
Ferrari   Living Room   Mercedes
                        |
                  Liquor Cabinet
                   /    |    \
               Door   Table   Window

Сега трябва да е лесно и бързо да се обработи заявка:

  1. Започнете с последната дума в заявката и най-ниското ниво на възел (листа)
  2. Тъй като всички възли са сортирани в рамките на едно ниво, можете да използвате двоично търсене и следователно да намерите съвпадение за O(log N) време, където N е броят на възлите.
  3. Направете това за всяко ниво. В дървото има O(log N) нива.
  4. След като намерите съвпадение, обработете всички родителски възли, за да видите дали пътят съответства на вашата заявка. Пътят има дължина O(log N). Ако съвпада, запазете го в резултатите, които трябва да бъдат показани на потребителя.

Нека M е общият брой съвпадения (брой възли, съответстващи на последната дума в заявката). Тогава нашето време за обработка е: O( (log N)^2 + M * (log N) ):
Двоичното търсене отнема O(log N) време на ниво и има O(log N) нива, следователно ние трябва да отделите поне O( (log N)^2) време. Сега, за всяко съвпадение, трябва да тестваме дали пълният път от нашия съвпадащ възел до корена съответства на пълната заявка. Пътят има дължина O(log N). По този начин, при дадени M съвпадения като цяло, ние изразходваме още едно M * O(log N) време, като по този начин полученото време за изпълнение е O( (log N)^2 + M * (log N) ).

Когато имате малко съвпадения, времето за обработка доближава O( (log N)^2), което е доста добре. Обратно, ако възникне най-лошият случай (всеки един път съответства на заявката (M = N)), времето за обработка се доближава до O(N log N), което не е твърде добро, но и не е твърде вероятно.

Внедряване: Вие казахте, че искате само идея. Освен това познанията ми за базите данни са много ограничени, така че няма да пиша много тук, просто ще очертая някои идеи.
Таблицата на възлите може да изглежда така:

  • ID: вътр
  • Текст: низ
  • Родител: int -> ID на възел
  • Ниво : int //Не очаквам това да се променя твърде често, така че можете да го запазите и актуализирате, тъй като базата данни се променя.

Тази таблица трябва да бъде сортирана по колоната „Текст“. Използвайки алгоритъма, описан по-горе, sql заявка вътре в цикъла може да изглежда така:
SELECT ID FROM node WHERE Level = $i AND Text LIKE $text
Надявам се, че някой може да разбере моята гледна точка.

Човек може да ускори още повече нещата, като не само сортира таблицата по колоната „Текст“, но и по комбинираните колони „Текст“ и „Ниво“, т.е. всички записи в рамките на Level=20 са сортирани, всички записи в рамките на Level= 19 сортирани и т.н. (но не е необходимо цялостно сортиране върху цялата таблица). Въпреки това, броят на възлите НА НИВО е в O(N), така че няма асимптотично подобрение на времето за изпълнение, но мисля, че си струва да опитате, като се имат предвид по-ниските константи, които получавате в действителност.

Редактиране: Подобрение

Току-що забелязах, че итеративният алгоритъм е напълно ненужен (по този начин информацията за нивото може да бъде изоставена). Напълно достатъчно е да:

  1. Съхранявайте всички възли, сортирани по тяхната текстова стойност
  2. Намерете всички съвпадения за последната дума от заявката наведнъж, като използвате двоично търсене във всички възли.
  3. От всяко съвпадение проследете пътя до корена и проверете дали пътят съответства на цялата заявка.

Това подобрява времето за изпълнение до O(log N + M * (log N)).

person Dave O.    schedule 31.12.2009
comment
Определено ще разгледам това и +1 за добре написания и добре обмислен отговор. Не съм сигурен колко ефективно ще бъде на практика, тъй като листовите възли са най-малко селективни (може да има 50 000 врати) и това ще трябва да работи с поддървета едно по едно, за разлика от прогресивното филтриране на набор. Все пак добра идея! - person Aaronaught; 31.12.2009
comment
Благодаря за обратната връзка, Аарон. Редактирах публикацията и мисля, че трябва да я разгледате. - person Dave O.; 31.12.2009
comment
@Dave - каква е разликата между подобрената версия и съществуващия подход, описан във въпроса? Въпреки че анализът на Big-O е ценно прозрение и в двата случая. - person Aaronaught; 31.12.2009
comment
Във втората версия правите само 1 двоично търсене за пълния набор от възли, вместо едно търсене на ниво в дървото. От моя гледна точка това прави много по-лесно кодирането на алгоритъма и подобрява времето за изпълнение. - person Dave O.; 31.12.2009
comment
+ Докато чета въпроса ви, двата подхода изглеждат доста сходни. Това не ми хрумна на първо място, тъй като не даде твърде много подробности за решението си. Е, ако наистина са равни (можете да прецените по-добре), тогава мисля, че няма по-добро решение от това, което имате в момента :-P - person Dave O.; 31.12.2009
comment
@Dave - Добре описано. Виждам обаче известна твърдост в дизайна. Информацията не винаги се разглежда по определен начин. Така че структурата на данните трябва да бъде направена от слабо свързани атрибути (може или не може да са налични), поддържащи търсене със свободно определени входове (може или не могат да бъдат предоставени). - person srini.venigalla; 31.12.2009