Обновления сохраненных запросов в реальном времени для большого графа

Обновления сохраненных запросов в реальном времени для большого графа

Иллюстрации

Показать все

Реферат

Перекрестная ссылка на родственную заявку

[0001] Эта заявка испрашивает приоритет обычной заявки на патент США № 14/306969, поданной 17 июня 2014 года, озаглавленной REAL-TIME SAVED-QUERY UPDATES FOR A LARGE GRAPH (ОБНОВЛЕНИЯ СОХРАНЕННЫХ ЗАПРОСОВ В РЕАЛЬНОМ ВРЕМЕНИ ДЛЯ БОЛЬШОГО ГРАФА), которая полностью включена в настоящую заявку посредством ссылки.

Уровень техники

[0002] Основанные на большом графе базы знаний представляют фактическую информацию о мире. Например, в графе данных объекты, такие как люди, места, фразы, слова, классы, факты, сущности, концепции и т.д., могут быть сохранены как узлы, и ребра между узлами могут указывать соотношение между объектами. Базовым блоком такого графа данных может являться тройка, которая включает в себя два узла, или объекта, и метку ребра. Первый узел иногда называется исходным узлом или узлом-субъектом, и второй узел иногда называется целевым узлом или узлом-объектом. Безусловно, тройка может включать в себя дополнительную информацию, такую как метаданные об объектах и/или соотношении, в дополнение к идентификации субъекта, предиката и объекта.

[0003] Пользователи могут определять запросы или коллекции для графа. Коллекция или запрос определяет ограничения, которым узел должен удовлетворять, чтобы являться элементом множества узлов, отвечающих на запрос. Ограничения обычно определяют, какое соотношение (соотношения) узел должен иметь или не иметь, чтобы являться элементом результатов запроса, например, элементом коллекции. Такие запросы (т.е. коллекции) экстенсивно используются при поиске, анализе данных, планировании объявлений, в системах рекомендаций и т.д., и принадлежность часто сохраняется, поскольку в большом графе вычисление принадлежности может быть затратным. Но по мере добавления или удаления узлов и соотношений в графе сохраненные элементы могут стать неактуальными, особенно в больших графах, которые часто обновляются.

Сущность изобретения

[0004] Некоторые реализации позволяют системе обновлять результаты сохраненных запросов в реальном времени по мере обновления ребер, например, по мере добавления троек в хранилище данных или удаления троек из хранилища данных на основе графа. Реальное время может включать в себя малую задержку (например, меньше одной минуты), чтобы позволить системе сгруппировать обновления по исходному узлу тройки. Запросы могут быть определены посредством ограничений, которые идентифицируют свойства или соотношения, которые узел должен иметь (или не иметь) в графе, чтобы относиться к результату для сохраненного запроса. Сохраненный запрос может быть определен ограничительным выражением, которое является последовательностью ограничений, соединенных логическими операциями, другими словами, булевым выражением ограничений. Система может включать в себя индекс ограничений, который индексирован по ребрам. Система может использовать индекс, чтобы определить, какие ограничения соответствуют ребру из обновленной тройки, тем самым идентифицируя целевые ограничения для этой тройки. Система использует целевые ограничения, чтобы эффективно определять, какие сохраненные результаты запросов затронуты обновлением, и приводит ли обновление к изменению результатов. Группируя обновления по субъектам, система может повторно использовать работу, например, прямые и обратные обходы в графе, при идентификации и оценке результатов запроса, затронутых обновлениями.

[0005] Один аспект раскрытия может быть воплощен в системе, которая включает в себя по меньшей мере один процессор и один или более блоков памяти. Один или более блоков памятей могут хранить граф данных, который включает в себя узлы, соединенные ребрами, и множество сохраненных запросов, каждый запрос определен одним или более ограничениями, которые должны быть удовлетворены для принадлежности результатам запроса для запроса, каждое ограничение определяет по меньшей мере одно из ребер. Один или более блоков памяти также могут хранить инструкции, которые при их исполнении по меньшей мере одним процессором побуждают компьютерную систему выполнять операции. Операции могут включать в себя идентификацию целевого ограничения в ответ на операцию, которая обновляет граф данных, с помощью исходного узла, ребра обновления и целевого узла, целевое ограничение определяет путь, который включает в себя ребро обновления и целевое ограничение, принадлежащее первому сохраненному запросу из множества сохраненных запросов. Операции также могут включать в себя оценку целевого ограничения для узла-элемента, чтобы определить состояние для целевого ограничения, посредством обхода графа через путь целевого ограничения, определение, указывает ли свернутое определение для первого сохраненного запроса на основе состояния, что узел-элемент отвечает или не отвечает на первый сохраненный запрос, и обновление результата сохраненного запроса первого сохраненного запроса с помощью узла-элемента в соответствии со свернутым определением, когда свернутое определение указывает, что узел-элемент отвечает или не отвечает.

[0006] Система может включать в себя один или более следующих признаков. Например, целевым ограничением может являться первое целевое ограничение, и операции также могут включать в себя идентификацию второго целевого ограничения, принадлежащего первому сохраненному запросу, второе целевое ограничение определяет путь, включающий в себя ребро обновления, второе целевое ограничение имеет длину пути больше, чем длина пути первого целевого ограничения, и установку состояния для второго целевого ограничения как состояния, указывающего, что второе целевое ограничение не разрешено. Кроме того, состоянием может являться первое состояние, и операции также могут включать в себя определение, что свернутое определение для первого сохраненного запроса на основе первого состояния не указывает, отвечает или не отвечает узел-элемент на первый сохраненный запрос, оценку второго целевого ограничения для узла-элемента, чтобы определить второе состояние для второго целевого ограничения посредством обхода графа через путь второго целевого ограничения, определение, указывает ли свернутое определение для первого запроса на основе первого состояния и второго состояния, что узел-элемент отвечает или не отвечает на первый сохраненный запрос, и обновление результата сохраненного запроса первого сохраненного запроса с помощью узла-элемента в соответствии со свернутым определением, когда свернутое определение указывает, что узел-элемент отвечает или не отвечает на первый сохраненный запрос.

[0007] В качестве другого примера один или более блоков памяти также могут хранить индекс ограничений по ребрам, индекс используется для идентификации целевого ограничения. В качестве другого примера операции также могут включить в себя сохранение результатов обхода графа данных и использование сохраненных результатов для оценки второго целевого ограничения, которое определяет путь, который включает в себя путь целевого ограничения. В качестве другого примера обновлением может являться первое обновление, и операции могут включать в себя сохранение результатов обхода графа данных и удаление сохраненных результатов, когда последующее обновление графа данных включает в себя исходный узел, который отличается от исходного узла первого обновления.

[0008] В качестве другого примера целевым ограничением может являться первое целевое ограничение, и состоянием может являться первое состояние, и операции могут включать в себя сохранение результата обхода графа в памяти, идентификацию второго целевого ограничения для первого запроса, второе целевое ограничение имеет путь, который включает в себя путь первого целевого ограничения, и использование сохраненного результата обхода при оценке второго целевого ограничения, чтобы определить второе состояние для второго целевого ограничения. Операции могут дополнительно включать в себя определение, указывает ли свернутое определение для первого сохраненного запроса на основе первого состояния и второго состояния, что узел-элемент отвечает или не отвечает на первый сохраненный запрос, и обновление результата сохраненного запроса первого сохраненного запроса с помощью узла-элемента в соответствии со свернутым определением, когда свернутое определение указывает, что узел-элемент отвечает или не отвечает на первый сохраненный запрос.

[0009] В качестве другого примера целевым ограничением может являться первое целевое ограничение, и операции также могут включать в себя идентификацию множества целевых ограничений, первым целевым ограничением является одно из множества целевых ограничений, множество целевых ограничений предназначено по меньшей мере для двух запросов, и первым сохраненным запросом является один из по меньшей мере двух запросов. Операции также могут включать в себя интеллектуальную оценку множества целевых ограничений, чтобы отсрочить обходы для целевых ограничений с более длинными путями.

[00010] В другом аспекте реализованный с помощью компьютера способ включает в себя идентификацию с использованием по меньшей мере одного процессора целевого ограничения, целевое ограничение определяет путь в графе данных, который включает в себя ребро, определенное в обновлении графа данных, идентификация инициируется посредством обновления, и определение использованием по меньшей мере одного процессора состояния для целевого ограничения посредством обхода графа через путь. Способ также включает в себя определение на основе состояния, что свернутое определение для первого запроса, который включает в себя ограничение, указывает, что узел-элемент отвечает на первый запрос, и обновление результата сохраненного запроса для первого запроса с использованием узла-элемента, идентифицированного во время обхода, в соответствии со свернутым определением. В некоторых реализациях целевое ограничение идентифицируется с использованием индекса множества ограничений, индекс организован по ребрам. Когда обновление включает в себя добавление ребра обновления между исходным узлом и целевым узлом, обновление результата сохраненного запроса в соответствии со свернутым определением включает в себя добавление узла-элемента в результат сохраненного запроса. Когда обновление включает в себя удаление ребра обновления между исходным узлом и целевым узлом, обновление результата сохраненного запроса в соответствии со свернутым определением включает в себя поддержание результата сохраненного запроса.

[00011] Способ может включить в себя один или более следующих признаков. Например, целевым ограничением может являться первое целевое ограничение, и способ дополнительно включает в себя идентификацию второго целевого ограничения, принадлежащего первому запросу, второе целевое ограничение определяет путь, включающий в себя ребро обновления, второе целевое ограничение имеет длину пути, которая больше, чем длина пути первого целевого ограничения, и установку состояния для второго целевого ограничения как состояния, указывающего, что второе целевое ограничение не разрешено. В некоторых реализациях состоянием может являться первое состояние, и способ дополнительно включает в себя определение, что свернутое определение для первого запроса на основе первого состояния не способно указать, отвечает или не отвечает узел-элемент на первый запрос, оценку второго целевого ограничения для узла-элемента, чтобы определить второе состояние для второго целевого ограничения посредством обхода графа через путь второго целевого ограничения, определение, что свернутое определение для первого запроса на основе первого состояния и второго состояния указывает, что узел-элемент отвечает на первый запрос, и обновление результата сохраненного запроса первого запроса с помощью узла-элемента в соответствии со свернутым определением.

[00012] В качестве другого примера целевым ограничением может являться первое целевое ограничение, состоянием может являться первое состояние, и способ также включает в себя сохранение результата обхода графа, идентификацию второго целевого ограничения для первого запроса, второе целевое ограничение имеет путь, который включает в себя путь первого целевого ограничения, и использование сохраненного результата обхода при оценке второго целевого ограничения, чтобы определить второе состояние для второго целевого ограничения. В таких реализациях определение, что свернутое определение для первого запроса указывает, что узел-элемент отвечает на первый запрос, основано на первом состоянии и втором состоянии.

[00013] В качестве другого примера способ также может включать в себя группировку множества обновлений графа данных по исходному узлу, множество обновлений происходят в течение пяти минут друг за другом, и обновление графа данных является одним из множества обновлений, причем идентификация целевого ограничения происходит в реальном времени после группировки.

[00014] В другом аспекте способ включает в себя идентификацию целевого ограничения с использованием по меньшей мере одного процессора, целевое ограничение определяет путь в графе данных, который включает в себя ребро обновления, в ответ на операцию, которая обновляет граф данных, с помощью исходного узла, ребра обновления и целевого узла. Способ также включает в себя определение с использованием по меньшей мере одного процессора состояния для целевого ограничения посредством обхода графа через путь, определение, что свернутое определение на основе состояния для первого запроса, который включает в себя ограничение, указывает, что узел-элемент не отвечает на первый запрос, и обновление результата сохраненного запроса для первого запроса с использованием узла-элемента, идентифицированного во время обхода, в соответствии со свернутым определением.

[00015] В некоторых реализациях обновление представляет собой удаление ребра обновления между исходным узлом и целевым узлом, и обновление результата сохраненного запроса в соответствии со свернутым определением включает в себя удаление узла-элемента из результата сохраненного запроса. В некоторых реализациях обновление представляет собой добавление ребра обновления между исходным узлом и целевым узлом, и обновление результата сохраненного запроса в соответствии со свернутым определением включает в себя поддержание результата сохраненного запроса.

[00016] В другом общем аспекте компьютерный программный продукт, воплощенный на непереходном машиночитаемом запоминающем устройстве, включает в себя инструкции, которые при их исполнении по меньшей мере одним процессором, сформированным в подложке, побуждают вычислительное устройство выполнять любые из раскрытых способов, операций или процессов. Другой общий аспект включает в себя систему и/или способ обновления результатов сохраненных запросов в режиме реального времени, в значительной степени как показано по меньшей мере на одной из фигур и/или описано в отношении по меньшей мере одной из фигур, и как более полно изложено в формуле изобретения.

[00017] Одна или более реализаций описанного здесь предмета могут быть осуществлены таким образом, чтобы реализовать одно или более следующих преимуществ. В качестве одного примера система может обновлять результаты сохраненных запросов в реальном времени, и это означает, что процесс для обновления результатов сохраненных запросов начинается в течение нескольких минут после обновления и инициируется обновлением вместо ожидания периодического, офлайнового пакетного процесса для обновления принадлежности. Реализации могут быстро и эффективно оценивать целевые ограничения, делая возможными обновления в реальном времени результатов сохраненных запросов. Другими словами, система минимизирует количество дополнительных поисков, требуемых для поддержания корректных результатов сохраненных запросов посредством использования информации при обновлении графа, чтобы идентифицировать минимальное количество дополнительных ограничений в затронутых запросах для оценки и группирования обновлений графа, чтобы повторно использовать результат предыдущей работы. Другие признаки будут очевидны из описания, рисунков и формулы изобретения.

Краткое описание чертежей

[00018] Фиг. 1 демонстрирует примерную систему в соответствии с некоторыми реализациями.

[00019] Фиг. 2 демонстрирует представление примерного графа данных с объектами как узлами и соотношениями как ребрами между узлами.

[00020] Фиг. 3 демонстрирует пример сохраненных запросов и индекс ребер запросов, совместимые с раскрытыми реализациями.

[00021] Фиг. 4 демонстрирует блок-схему последовательности операций примерного процесса для эффективного обновления принадлежности запроса в реальном времени, совместимого с раскрытыми реализациями.

[00022] Фиг. 5 демонстрирует блок-схему последовательности операций примерного процесса для интеллектуальной оценки ограничения после добавления ребра к графу, совместимого с раскрытыми реализациями.

[00023] Фиг. 6 демонстрирует блок-схему последовательности операций примерного процесса для интеллектуальной оценки ограничения после удаления ребра из графа, совместимого с раскрытыми реализациями.

[00024] Фиг. 7 демонстрирует пример обновления принадлежности запроса в реальном времени после удаления ребра в графе данных на фиг. 2.

[00025] Фиг. 8 демонстрирует пример обновления принадлежности запроса в реальном времени после добавления ребра в графе данных на фиг. 2.

[00026] Фиг. 9 показывает пример компьютерного устройства, которое может использоваться для реализации описанных методик.

[00027] Фиг. 10 показывает пример распределенного компьютерного устройства, которое может использоваться для реализации описанных методик.

[00028] Аналогичные символы на разных чертежах указывают аналогичные элементы.

Подробное описание

[00029] Фиг. 1 является блок-схемой системы 100 в соответствии с примерной реализацией. Система 100 обновляет результаты сохраненных запросов в реальном времени в ответ на обновления ребер в графе данных. Система на фиг. 1 является одной примерной реализацией, и могут использоваться другие конфигурации и приложения. Хотя система 100 может использоваться для поддержания сохраненных результатов запроса актуальными в любом графе данных, система 100 особенно полезна для больших графов, поскольку время обработки для определения результатов запросов в таких графах часто является чрезмерно затратным по стоимости и по времени.

[00030] Система 100 может представлять собой вычислительное устройство или устройства, которые принимают форму многих разных устройств. Например, система 100 может представлять собой стандартный сервер, группу таких серверов, системы клиент-сервер или серверную систему в стойке. Кроме того, система 100 может быть реализована в персональном компьютере. Система 100 может являться примером компьютерного устройства 900, изображенного на фиг. 9, или компьютерного устройства 1000, изображенного на фиг. 10.

[00031] Система 100 может включать в себя подсистему 110 графа и подсистему 150 сохраненных запросов. В некоторых реализациях каждая из подсистемы 110 графа и подсистемы 150 сохраненных запросов может представлять собой отдельное вычислительное устройство, или они могут совместно использовать компоненты, такие как процессоры и память. Например, подсистема 110 графа и подсистема 150 сохраненных запросов могут быть реализованы в персональном компьютере, сервере, одном или нескольких логических разделов компьютера и т.д. В некоторых реализациях одна или более из подсистемы 110 графа и подсистемы 150 сохраненных запросов могут представлять собой распределенные системы, реализованные в последовательности вычислительных устройств, таких как группа серверов, таких как компьютерное устройство 1000, изображенное на фиг. 10.

[00032] Система 100 может включать в себя хранилище 190 данных на основе графа. Хранилище данных на основе графа представляет собой граф данных, который хранит информацию в форме узлов и ребер, и узлы соединены ребрами. Узел в графе данных может представлять объект, например, человека, место, элемент, слово, фразу, идею, тему, абстрактное понятие, конкретный элемент, другую подходящую сущность или любую их комбинацию или свойство объекта. Таким образом, узлы могут называться объектами и наоборот. Объекты в графе могут быть соотнесены друг с другом с помощью ребер, которые могут представлять соотношения между объектами. Например, граф данных может иметь объект, который соответствует Аврааму Линкольну, и граф данных может иметь соотношение "вид_деятельности" между объектом "Авраам Линкольн" и объектом "Президент" и другое такое соотношение между объектом "Авраам Линкольн" и объектом "Адвокат". Подсистема индексации может поддерживать хранилище 190 данных на основе графа, чтобы позволить поисковой подсистеме осуществлять поиск в графе данных, например, находя объекты, относящиеся к другим объектам посредством одного или более соотношений или путей в графе. В некоторых реализациях подсистема индексации и/или поисковая подсистема могут быть включены в подсистему 110 графа. Хранилище 190 данных на основе графа может включать в себя индекс или некоторый другой способ поиска и извлечения данных из хранилища данных.

[00033] Хранилище 190 данных на основе графа может включать в себя информацию, из которой может быть создан граф, такой как граф 200, проиллюстрированный на фиг. 2. Используемая здесь ссылка на граф данных может рассматриваться как ссылка на индекс для графа данных и наоборот. Узлы графа данных могут называться объектами, и ребра могут называться соотношениями между двумя объектами. Используемый здесь термин "объект" может относиться к физическому воплощению человека, места или сущности, или к представлению физического объекта, например, к тексту или другой информации, которая относится к объекту. Например, объект может являться физическим местоположением во Франции или абстрактным понятием, которое относится к Франции. Подсистема 110 графа может включать в себя пользовательский интерфейс, который позволяет пользователям, например, пользователям клиента 170, искать, обновлять и иным образом поддерживать информацию в хранилище 190 данных на основе графа. Подсистема 110 графа также может включать в себя пакетные или офлайновые процессы, которые обновляют хранилище 190 данных на основе графа. Подсистема 110 графа может представлять собой отдельное вычислительное устройство со своим собственным аппаратным процессором 113 и памятью 114 или оно может совместно использовать один или несколько аппаратных процессоров и память с другими компонентами системы 100.

[00034] Система 100 также может включать в себя сохраненные запросы 140. Запрос определен посредством ограничительного выражения, которое может представлять собой одно ограничение или булево выражение из ограничений. Ограничительное выражение определяет запрос и, таким образом, может называться определением запроса или коллекции. Ограничительное выражение представляет условия, которым объект в хранилище 190 данных на основе графа должен удовлетворять, чтобы считаться отвечающим на запрос и включенным в результаты запроса, т.е. в качестве элемента результатов запроса. В этом смысле запрос может считаться коллекцией, а объекты, отвечающие на запрос - элементами коллекции. Таким образом, сохраненные запросы 140 могут называться сохраненными принадлежностями коллекции.

[00035] Ограничение связано с путем в графе. Путь часто имеет единичную длину, но может иметь большую длину. Ограничение может включать в себя логические операторы, такие как "равно" (==), "не равно" (!=), и может определять или не определять целевой узел. Примерами ограничения с единичной длиной пути являются ограничение "родитель" != "пусто", означающее, что узел должен быть соединен с другим узлом ребром "родитель", ограничение "родственник" == "пусто", означающее, что узел не должен иметь ребра "родственник", и ограничение "родитель" == "Джон Доу", означающее, что узел должен быть соединен с узлом "Джон Доу" посредством ребра "родитель". Ограничение также может включать в себя более длинный путь, такой как "выпускники.родитель.вид_деятельности"="Президент". Узел, удовлетворяющий этому ограничению, будет узлом, соединенным с первым целевым узлом соотношением "выпускники", при этом первый целевой узел соединен со вторым целевым узлом соотношением "родитель", и второй целевой узел соединен с узлом "Президент" соотношением "вид_деятельности". Ограничения могут быть объединены в ограничительное выражение с использованием других логических операторов, таких как "и" (&&), "или" (||) и т.д.

[00036] Система 100 может факультативно включать в себя индекс 145 ребер запросов. Индекс 145 ребер запросов может индексировать ограничения в сохраненных запросах 140 с помощью ребра. Индекс 145 ребер запросов может улучшить время обработки при определении, какие сохраненные запросы потенциально затронуты обновлением хранилища 190 данных на основе графа, но система 100 также может просто считывать ограничения из сохраненных запросов 140, чтобы определить, какие сохраненные запросы потенциально затронуты.

[00037] Фиг. 3 иллюстрирует пример информации, которая может храниться в сохраненных запросах 140, и индекс 145 ребер запросов, совместимый с раскрытыми реализациями. Сохраненные запросы 340 могут включать в себя идентификатор 305 запроса, который может включать в себя название запроса. Каждый запрос может быть определен одним или более ограничениями 310, которые могут быть объединены в ограничительное выражение 315 с использованием логических операторов. Ограничения 310 могут представлять единичную длину пути, например, "вид_деятельности" == "Президент", или большую длину пути, например, "выпускники.родитель.год_рождения.китайский_зодиак" == "бык". Для объекта, который будет считаться отвечающим на запрос, ограничительное выражение 315 должно быть расценено как "истина" для объекта.

[00038] Пример пяти сохраненных запросов проиллюстрирован в сохраненных запросах 340. Запрос Q1 иллюстрирует ограничение, которое не определяет целевой узел. Например, ограничение "год_смерти"="пусто" указывает, что узел, удовлетворяющий этому ограничению, не будет иметь ребра "год_смерти". С другой стороны, если сохраненный запрос был для умерших президентов, ограничение может представлять собой "год_смерти" != "пусто", и это означает, что узел, который удовлетворяет этому ограничению, должен иметь соотношение "год_смерти" с другим узлом, но какой это узел, не имеет значения. Запрос Q5 иллюстрирует сохраненный запрос только одним ограничением в ограничительном выражении.

[00039] Фиг. 3 также демонстрирует примерный индекс 345 ребер запросов. Индекс 345 ребер запросов является факультативным, и реализации могут не включать в себя индекс 345 ребер запросов. Индекс 345 ребер запросов хранит ограничения для каждого сохраненного запроса посредством ребра. Таким образом, например, в индексе 345 ребер запросов имеется запись "вид_деятельности". Каждое ограничение для записи "вид_деятельности" включает в себя идентификатор запроса для ограничения и само ограничение. Ограничения с единичной длиной, безусловно, связаны с записью ребра, которая связана с путем. Таким образом, ограничение "вид_деятельности" == "Президент" из запроса Q1 включено в записи для ребра вида деятельности. Если ребро вида деятельности имеет место в ограничении с более длинным путем, ограничение также включено в записи ребра. Таким образом, например, ограничение "выпускники.супруг.вид_деятельности" == "Президент из запроса Q3 также включено в запись "вид_деятельности". Это ограничение также включено в записи для ребра "выпускники" и ребра "супруг". Таким образом, когда ребро обновляется (например, добавляется или удаляется) в хранилище данных на основе графа, система может использовать индекс 345 ребер запросов, чтобы быстро идентифицировать все сохраненные запросы и целевые ограничения из сохраненных запросов, потенциально затронутых обновлением. Безусловно, в реализации без индекса 345 ребер запросов система может исследовать сохраненные запросы 340, чтобы получить ту же самую информацию.

[00040] Возвращаясь к фиг. 1, можно видеть, что система 100 также включает в себя результаты 160 сохраненных запросов. Результаты 160 сохраненных запросов идентифицируют объекты в хранилище 190 данных на основе графа, которые отвечают на запросы, идентифицированные в сохраненных запросах 140. Хотя нет необходимости для каждого сохраненного запроса иметь соответствующие элементы в результатах 160 сохраненных запросов, вследствие продолжительности времени обработки для определения результатов запроса для всех узлов в большом графе данных многие, если не все, запросы в сохраненных запросах 140 имеют соответствующие результаты, сохраненные в результатах 160 сохраненных запросов. Таким образом, система может однажды определить принадлежность к результатам запроса с использованием всего хранилища 190 данных на основе графа однажды и обновляет принадлежность по мере возникновения обновлений хранилища 190 данных на основе графа. Результаты 160 сохраненных запросов могут иметь различные форматы. В качестве одного примера каждый сохраненный запрос может быть представлен как узел в хранилище 190 данных на основе графа, и объекты, отвечающие на сохраненный запрос, могут совместно использовать ребро с узлом для сохраненного запроса. Таким образом, в некоторых реализациях результаты 160 сохраненных запросов могут являться подмножеством хранилища 190 данных на основе графа. Такая реализация проиллюстрирована в графе 200 на фиг. 2 как узел "Первые семьи" и ребра, соединяющие этот узел с другими узлами в графе 200. В качестве другого примера результаты 160 сохраненных запросов могут являться файлом или базой данных, устанавливающими соотношение идентификатора запроса с идентификаторами узлов, которые отвечают на запрос (например, результат сохраненного запроса).

[00041] Хранилище 190 данных на основе графа, результаты 160 сохраненных запросов, сохраненные запросы 140 и индекс 145 ребер запросов хранятся на материальных машиночитаемых запоминающих устройствах, например, на диске, во флэш-памяти, в кэш-памяти или их комбинации, выполненных с возможностью хранить данные в полупостоянной или непереходной форме. В некоторых реализациях хранилище 190 данных на основе графа, результаты 160 сохраненных запросов, сохраненные запросы 140 и индекс 145 ребер запросов могут быть сохранены в комбинации различных видов памяти и/или могут быть сохранены распределенным образом на нескольких физических или логических вычислительных устройствах.

[00042] Система 100 может включать в себя подсистему 150 сохраненных запросов. Подсистема 150 сохраненных запросов может включать в себя один или несколько аппаратных процессоров 153, выполненных с возможностью исполнять одну или более исполняемых на машине инструкций, или фрагменты программного обеспечения, программно-аппаратного обеспечения или их комбинации для приема сохраненных запросов 140 и обновления результатов 160 сохраненных запросов по мере обновления хранилища 190 данных на основе графа. Подсистема 150 сохраненных запросов может иметь свои собственные процессор и память, или она может совместно использовать один или более процессоров и память с другими компонентами системы 100. Подсистема 150 сохраненных запросов может собирать обновления хранилища 190 данных на основе графа, использовать обновления для идентификации сохраненных запросов, на которые повлияли обновления, и в случае необходимости модифицировать сохраненные результаты (например, принадлежность) затронутых запросов. Для обработки обновлений хранилища 190 данных на основе графа эффективным образом подсистема 150 сохраненных запросов может хранить и повторно использовать результаты поисков в графе. Подсистема 150 сохраненных запросов может сохранить результаты предыдущих поисков в графе во временных результатах 147 поиска. В некоторых реализациях предыдущие поиски могут быть сохранены посредством исходного узла, например, узла, с которого начался поиск. Поиск в графе представляет собой прямой или обратный обход графа, начинающийся от исходного узла и следующий по всем возможным путям, которые соответствуют критериям поиска. Поскольку обходы графа могут занимать много времени, сохранение обходов, относящихся к обновленному ребру, для повторного использования может значительно улучшить производительность подсистемы 150 сохраненных запросов при определении обновлений результатов 160 сохраненных запросов. В некоторых реализациях временные результаты 147 поиска могут быть удалены, когда исходный узел для обновления изменяется. Таким образом, в реализации, в которой система группирует обновления по исходному узлу, предыдущие поиски могут использоваться по обновлениям. В некоторых реализациях подсистема 150 сохраненных запросов может включать в себя пользовательский интерфейс (UI) сохраненных запросов, который принимает определения запроса, например, от клиента 170. Подсистема 150 сохраненных запросов может использовать хранилище 190 данных на основе графа для офлайнового определения результатов сохраненных запросов для недавно введенного сохраненного запроса.

[00043] Система 100 также может включать в себя другие компоненты, не проиллюстрированные для краткости. Например, система 100 может включать в себя подсистему индексации для создания и поддержания хранилища 190 данных на основе графа. Подсистема индексации может получать информационное содержание, например, из одного или более серверов и использовать информационное содержание, чтобы поддерживать хранилище 190 данных на основе графа. В некоторых реализациях серверы могут представлять собой веб-серверы, серверы в частной сети или другие источники, которые доступны для подсистемы индексации. Подсистема индексации может представлять собой одно или более отдельных вычислительных устройств, и в некоторых реализациях подсистема 110 графа может включать в себя подсистему индексации для хранилища 190 данных на основе графа. Система 100 также может включать в себя поисковую подсистему, которая использует хранилище 190 данных на основе графа, чтобы определять результаты поиска для запросов с использованием традиционных или других методик информационного поиска. В некоторых реализациях поисковая подсистема также может использовать результаты 160 сохраненных запросов для определения результатов поиска.

[00044] Система 100 может осуществлять связь с клиентом (клиентами) 170 по сети 180. Сеть 180 может представлять собой, например, Интернет, или сеть 180 может являться проводной сетью или беспроводной локальной сетью (LAN), широкомасштабной сетью (WAN) и т.д., реализованными с использованием, например, устройств шлюзов, мостов, переключателей и/или т.д. Через сеть 180 подсистема 110 графа и/или подсистема 150 сохраненных запросов могут осуществлять связь с клиентами 170 и передавать данные клиентам 170.

[00045] Фиг. 4 иллюстрирует блок-схему последовательности операций примерного процесса 400 для эффективного обновления результатов сохраненных запросов в реальном времени, совместимого с раскрытыми реализациями. Процесс 400 может быть выполнен системой, такой как система 100 на фиг. 1. Система может использовать процесс 400 для обновления результатов сохраненных запросов в реальном времени по мере того, как происходят обновления хранилища данных на основе графа, вместо того, чтобы ожидать периодического пакетного или офлайнового процесса обновления. Это позволяет системе избежать устаревания данных в принадлежности сохраненных запросов. В некоторых реализациях процесс 400 может быть выполнен подсистемой сохраненных запросов.

[00046] Процесс 400 может начаться с приема системой обновления графа, которое идентифицирует исходный узел, ребро и целевой узел (этап 405). В некоторых реализациях система может принять несколько обновлений графа и сгруппировать обновления по исходному узлу таким образом, чтобы все обновления, подразумевающие один и тот же исходный узел, были сгруппированы. Например, вместо того чтобы сразу переходить к работе после возник