Как эффективно построить и хранить семантический граф? - PullRequest
Новая
       2

Как эффективно построить и хранить семантический граф?

1 голос
/ 20 января 2011

Занимаясь серфингом в сети, я столкнулся с Aquabrowser (не нужно нажимать, я выложу фото соответствующей части).

Это хороший способ представления результатов поиска и обнаружения семантически связанных сущностей.

Вот скриншот, взятый из one из demos .

На левой стороне у вас есть слово, которое вы набрали, и связанные слова. Нажатие на них уточняет ваши результаты.

aqua

Теперь в качестве примера проекта у меня есть набор данных о сущностях и предметах фильма (например, wolrd-war-2 или побег из тюрьмы) и их отношениях.

Теперь я представляю несколько вариантов использования, во-первых, когда пользователь начинает с ключевого слова. Например "Вторая мировая война".

Тогда я бы хотел вычислить связанные ключевые слова и оценить их.

Я думаю о каком-то sql-запросе, подобном этому:

Предположим, что "мировая война 2" имеет идентификатор 3. 

select keywordId, count(keywordId) as total from keywordRelations 
WHERE movieId IN (select movieId from keywordRelations 
                  join movies using (movieId)      
                  where keywordId=3) 
 group by keywordId order by total desc

, который в основном должен выбирать все фильмы, которые также имеют ключевое слово world-war-2, а затем ищет ключевые слова, которые есть у этих фильмов, и выбирает те, которые встречаются чаще всего.

Я думаю, с помощью этих ключевых слов я могу выбрать фильмы, которые лучше всего подходят и имеют красивое облако тегов, содержащее похожие фильмы и связанные ключевые слова.

Я думаю, что это должно работать, но очень, очень, очень неэффективно.

И это также только один уровень или отношение.

Должен быть лучший способ сделать это, но как ??

У меня в основном есть коллекция сущностей. Это могут быть разные объекты (фильмы, актеры, сюжеты, сюжетные ключевые слова) и т. Д.

У меня тоже есть отношения между ними.

Каким-то образом должна быть возможность эффективно рассчитать "семантическое расстояние" для сущностей.

Я также хотел бы реализовать больше уровней отношений.

Но я полностью застрял. Ну, я пробовал разные подходы, но все заканчивается в некоторых алгоритмах, для расчета которых требуются возрасты, а время выполнения растет в геометрической прогрессии.

Существуют ли системы баз данных, оптимизированные для этого?

Может кто-нибудь указать мне правильное направление?

Ответы [ 2 ]

5 голосов
/ 20 января 2011

Возможно, вы хотите RDF триплет . Redland довольно часто используется, но это действительно зависит от ваших потребностей.Запросы выполняются в SPARQL , а не в SQL.Кроме того ... Вы должны выпить семантическую сеть koolaid.

1 голос
/ 20 января 2011

Из ваших тегов я вижу, что вы более знакомы с sql, и я думаю, что все еще возможно эффективно использовать его для вашей задачи.

У меня есть приложение, в котором пользовательский полнотекстовый поиск реализован с использованием sqlite в качестве базы данных. В поле поиска я могу ввести термины, и во всплывающем списке будут отображаться предложения по слову, а для любого следующего слова показываются только те, которые появляются в статьях, где появились ранее введенные слова. Так что это похоже на задачу, которую вы описали

Для упрощения предположим, что у нас всего три таблицы. Я полагаю, у вас другая схема, и даже детали могут отличаться, но мое объяснение - просто дать идею.

  • Слова [Id, Word] Таблица содержит слова (ключевые слова)

  • Индекс [Id, WordId, ArticleId] В этой таблице (индексируемой также WordId) перечислены статьи, в которых появился этот термин

  • ArticleRanges [ArticleId, IndexIdFrom, IndexIdTo] В этой таблице перечислены диапазоны Index.Id для любой данной статьи (очевидно, также индексируемые ArticleId). Эта таблица требует, чтобы для любой новой или обновленной статьи индексная таблица содержала записи с известным диапазоном. Я полагаю, что это может быть достигнуто с любой СУБД с помощью функции автоинкремента

Так что для любой заданной строки слов вы

  • Пересечь все статьи, где появились все предыдущие слова. Это сузит поиск. ВЫБЕРИТЕ ArticleId ИЗ ИНДЕКСА, где WordId = ... INTERSECT ...
  • Для списка статей вы можете получить диапазоны записей из таблицы ArticleRanges
  • Для этого диапазона вы можете эффективно запрашивать списки WordId из Index, группируя результаты, чтобы получить Count и, наконец, отсортировать его.

Хотя я перечислил их как отдельные действия, конечный запрос может быть просто большим sql на основе проанализированной строки запроса.

...