Способ индексации и пространственного поиска данных на основе хэширования


 


Владельцы патента RU 2579014:

Закрытое акционерное общество научно-производственное предприятие "Реляционные экспертные системы" (RU)

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

 

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

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

Существует строгое математическое определение метрики. Функция двух аргументов R(x,y) является метрикой, если, во-первых, она равна нулю только в том случае, если поданные на вход аргументы идентичны. Во-вторых, функция R(x,y)>0, если x и у представляют собой не идентичные объекты. В-третьих, функция R(x,y) симметрична, то есть R(x,y)=R(y,x) для любых x и y. В-четвертых, для функции R(x,y) выполняется неравенство треугольника: расстояние между двумя объектами всегда меньше либо равно сумме расстояний от этих объектов до любого третьего объекта. Наконец, функция R(x,y) определена для любых двух объектов x и y.

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

Способ Z-order заключается в проецировании пространственных объектов на числовую ось, а затем работе с полученными числами-проекциями. Это позволяет выполнять индексацию и поиск с помощью различных методов работы с числовыми данными. В частности, способ UB-Tree подразумевает использование В-деревьев [VOLKER GAEDE, Multidimensional Access Methods, URL: http://www-static.cc.gatech.edu/computing/Database/readinggroup/articles/p170-gaede.pdf].

Недостатком данного способа является то, что он применим только тогда, когда данные можно проецировать на ось.

Квадрантные деревья используются при работе с множествами точек на плоскости. Создание индекса заключается в построении дерева. Множество всех обрабатываемых точек соответствует корню дерева. Далее плоскость разбивается на четыре квадранта, а у корня дерева создается четыре дочерних узла, каждый из которых соответствует одному из квадрантов. Если в квадранте оказывается более одной точки, то операция построения дерева рекурсивно повторяется для этого квадранта: он разбивается на четыре части, а у узла дерева создается четыре подузла. Для работы с множествами трехмерных точек используются октантные деревья, принцип работы которых схож с квадрантными [Samet, Hanan; Webber, Robert (July 1985). "Storing a Collection of Polygons Using Quadtrees" URL: http://infolab.usc.edu/csci585/Spring2008/den_ar/p182-samet.pdf].

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

Способ R-tree (R-деревья) позволяет работать с множеством векторов в многомерном пространстве. Каждый узел дерева соответствует некоторому прямоугольному параллепипеду в данном пространстве и множеству точек, лежащему внутри этого параллепипеда. У узла может быть несколько подузлов, при этом соответствующие им параллепипеды могут пересекаться, но обязательно лежат внутри охватывающего паралепипеда, соответствующего данному родительскому узлу. Корень дерева соответствует прямоугольному параллепипеду, охватывающему все обрабатываемое множество векторов. Существуют различные модификации R-деревьев, среди которых следует упомянуть R+-деревья, R*-деревья, Гильбертовы R-деревья и Х-деревья.

[Antonin Guttman (1984). "R-trees: A Dymamic index structure for spatial searching" URL: http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf]

Недостатком является то, что R-деревья применимы только для случая числовых векторов. Кроме того, строение R-дерева существенно зависит от того, в каком порядке информация добавляется в дерево.

Достаточно распространенные М-деревья также можно считать модификацией R-деревьев, у которых узлы соответствуют не прямоугольным параллелепипедам, а шарам в пространстве объектов. Это позволяет применять М-деревья для информационных объектов, которые не представимы как векторы чисел, но для которых задана метрика [Guttman, А. (1984). "R-Trees: А Dynamic Index Structure for Spatial Searching" URL: http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf; Ciaccia, Paolo; Patella, Marco; Zezula, Pavel (1997). "M-tree An Efficient Access Method for Similarity Search in Metric Spaces" URL: http://www.v1db.org/conf/1997/P426.PDF].

Недостатком является то, что эффективность использования М-деревьев (прежде всего, скорость вставки и поиска значений) существенно зависит от выбора эвристических алгоритмов, используемых при работе с деревом.

KD-деревья имеют много общего с R-деревьями: происходит работа с векторами чисел, корень дерева соответствует множеству всех объектов, узел дерева - подмножеству, которое целиком входит в подмножество, соответствующее родительскому узлу. KD-деревья являются бинарными. Для каждого узла KD-дерева задается некоторая поверхность, разбивающая множество объектов на две части. Одна часть соответствует одному дочернему узлу, а другая часть - другому дочернему узлу [Chandran, Sharat. Introduction to kd-trees URL: http://www.cs.umd.edu/class/spring2002/cmsc420-0401/pbasic.pdf].

Недостатком является то, что KD-деревья применимы только для случая числовых векторов.

Наиболее близким аналогом является способ Grid, который применяется для работы с точками на поверхности, которая предварительно разбивается на множество непересекающихся ячеек, покрывающих всю поверхность и имеющих регулярную структуру: квадраты, прямоугольники, треугольники, шестиугольники и т.п. Форма ячеек может быть различной и выбирается исходя из реальных данных, а также постановки конкретной задачи. Любая точка всегда относится к одной и только одной ячейке, но при этом к одной и той же ячейке может относится сразу несколько точек. Для любой точки можно легко вычислить индекс соответствующей ей ячейки. При поиске сначала происходит определение индекса необходимой ячейки, а уже затем анализируются точки внутри этой и соседних с ней ячеек. Способ несложно обобщить для случая многомерных данных [Kevin Sahr, Denis White, and A. Jon Kimerling, Geodesic Discrete Global Grid Systems URL: http://www.sou.edu/cs/sahr/dgg/pubs/gdggs03.pdf#search=%22hexagonal%20grid%20kimerling%22].

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

Технический результат изобретения - повышение эффективности поиска информационных объектов, для которых задана метрика сравнения.

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

При сравнении с описанными выше подходами заявляемое изобретение больше всего похоже на подход Grid, но имеет существенное преимущество: оно позволяет работать с произвольными пространственными объектами, а не только точками на плоскости. Единственное условие применимости заявляемого изобретения состоит в том, что для информационных объектов должна быть задана функция вычисления расстояния (метрика).

Основная идея заявляемого изобретения состоит в следующем. Для работы с множеством пространственных объектов предварительно задается N фиксированных информационных объектов A1, …, AN, далее называемых опорными объектами. Для каждого из них задается набор положительных чисел Ri,1, …, Ri,k, где i - номер опорного объекта, а k - количество чисел. Число k может быть фиксированным, а может быть отличаться для различных опорных объектов. Числа Ri,1, …, Ri,k задают радиусы шаров с центром в Ai и, таким образом, разбивают пространство на k+1 областей, далее называемых кольцами опорного объекта Ai. В первом кольце лежат все объекты, находящиеся от Ai на расстоянии, не большем Ri,1. Во втором кольце лежат все объекты, находящиеся от Ai на расстоянии, большем Ri,1, но не большем Ri,2, и так далее. В последнем кольце лежат все объекты, находящиеся от Ai на расстоянии, большем Ri,k. Тогда для любого информационного объекта X известны натуральные числа I1, …, IN, где IK - это номер кольца объекта AK, в котором расположен объект X. Числа I1, …, IN представляют собой код области, в которой расположен объект X. Все пространство разбивается на конечное множество областей, каждая из которых однозначно идентифицируется своим кодом.

Коды областей обладают важным свойством. Пусть объект X расположен в области с кодом I1, …, IN, а объект Y - в области с кодом J1, … ,JN. Во-первых, если коды областей совпадают (то есть вектор I1, …, IN полностью совпадает с вектором J1, …, JN), то X и Y могут быть сколь угодно близки друг к другу. Во-вторых, если соответствующие друг другу компоненты векторов I1, …, IN и J1, …, JN различаются не более чем на 1, то X и Y также могут быть сколь угодно близки друг к другу, поскольку содержащие их области имеют общую границу. Наконец, если для некоторого i, обозначающего номер опорного информационного объекта, значение Ii отличается от Ji более чем на единицу, то можно вычислить нижнюю оценку расстояния между X и Y. Пусть число Ii меньше Ji. Тогда расстояние от X до Y не меньше, чем Rp-Rq, где p=Ji-1, a q=Ii. Фактически, число Rp-Rq представляет собой суммарную ширину колец, расположенных между кольцами Ii и Ji.

В заявляемом изобретении индексация заключается в построении N-мерного массива D, измерения которого соответствуют опорным информационным объектам, а значения индексов - номерам колец этих опорных объектов. В ячейках массива D хранятся информационные объекты.

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

При добавлении нового информационного объекта в обрабатываемое множество сначала происходит определение кода области, к которой относится данный объект. Затем этот объект добавляется в соответствующую ячейку многомерного массива D. Под добавлением информационного объекта в ячейку многомерного массива подразумевается добавление этого информационного объекта в подмножество, содержащееся в данной ячейке многомерного массива.

При удалении информационного объекта из обрабатываемого множества сначала происходит определение кода области, к которой он относится. Затем происходит удаление объекта из соответствующей ячейки многомерного массива D. Под удалением информационного объекта из ячейки многомерного массива подразумевается удаление этого информационного объекта из подмножества, содержащегося в данной ячейке многомерного массива.

При поиске М объектов, наиболее близких к заданному объекту X, сначала происходит определение кода области I1…IN, в которой располагается объект X. Затем осуществляется поиск объектов в этой области (т.е. в подмножестве объектов, содержащемся в ячейке массива D), а также в областях с кодами J1…JN, при этом области с кодами J1…JN рассматриваются в порядке увеличения минимального расстояния от объектов области J1…JN до объектов области I1…IN. Определение минимального расстояния происходит согласно сформулированному выше свойству кодов областей. По мере рассмотрения областей J1…JN все находящиеся в них объекты добавляются в список найденных объектов Y1, …, YF Список объектов Y1, …, YF автоматически сортируется в порядке возрастания расстояния от X до элементов этого списка.

Процедура поиска останавливается в следующем случае: список Y1, …, YF содержит не меньше, чем М элементов, а расстояние от X до YM (М-й элемент списка Y1, …, YF) меньше, чем минимально возможное расстояние от объекта из области I1…IN до объекта из рассматриваемой области J1…JN, рассматриваемой на текущей итерации алгоритма. Результатом поиска является список Y1, …, YM. Также, процедура поиска заканчивается, если рассмотрены все возможные J1…JN.

Если выполняется поиск объектов, находящихся от X на расстоянии, не большем заданного Т, то поиск останавливается в случае, когда минимальное расстояние от объекта из области I1…IN до объекта из области J1…JN становится большим, чем Т. Результатом поиска являются все объекты из списка Y1, …, YF, для которых выполняется R(X,Y)<=T.

Вместо многомерного массива D можно использовать ассоциативный массив, у которого ключом будет код области, а значением - соответствующее подмножество информационных объектов. Возможна любая известная реализация ассоциативного массива, начиная от линейного списка и заканчивая деревьями поиска [https://ru.wikipedia.org/wiki/%D0%90%D1%81%D1%81%D0%BE%D1%86%D0%B8%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2#.D0.A0.D0.B5.D0.B0.D0.BB.D0.B8.D0.B7.D0.B0.D1.86.D0.B8.D0.B8_.D0.B0.D1.81.D1.81.D0.BE.D1.86.D0.B8.D0.B0.D1.82.D0.B8.D0.B2.D0.BD.D0.BE.D0.B3.D0.BE_.D0.BC.D0.B0.D1.81. D1.81.D0.B8.D0.B2.D0.B0)

Преимущество использования заявляемого изобретения состоит в следующем: если опорные объекты и значения радиусов подобраны так, что количество коллизий сравнительно невелико, то при вставке, удалении и поиске потребуется работа с небольшими множествами информационных объектов. Эффективность применения изобретения напрямую зависит от того, насколько удачно выбраны опорные объекты и значения радиусов.

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

Возможен способ, предполагающий подбор опорных векторов путем решения задачи минимизации с помощью генных алгоритмов, методов радиентного списка и других методов оптимизации (https://ru.wikipedia.org/wiki/%D0%9B%D0%BE%D0%BA%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA_(%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F); подбираемыми параметрами являются опорные информационные объекты и радиусы колец, а целевой функцией - количество коллизий, возникающих при индексации тестового множества объектов.

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

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

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

3. Способ по из любому из пп. 1, 2, предполагающий подбор опорных векторов путем решения задачи минимизации; подбираемыми параметрами являются опорные информационные объекты и радиусы колец, а целевой функцией - количество коллизий, возникающих при индексации тестового множества объектов.

4. Способ по любому из пп. 1, 2, предполагающий подбор опорных векторов на основе результатов кластеризации тестового множества объектов; центры кластеров выбираются в качестве опорных объектов, а количество и радиусы колец определяются так, чтобы все множество объектов было разделено на несколько подмножеств, содержащих примерно одинаковое количество объектов.



 

Похожие патенты:

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

Изобретение относится к области выдачи рекомендаций пользователям сети. Технический результат - эффективное управление выдачей рекомендаций.

Изобретение относится к предоставлению контактной информации между абонентами сети, в частности к системе и способу для глобальной службы каталогов с использованием объектов электронной визитной карточки (ЕВС).

Изобретение относится к области поиска информации в компьютерных сетях. Техническим результатом является ускорение поиска информации.

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

Изобретение относится к области поисковых систем. Технический результат - обеспечение предоставления настраиваемых для пользователя изображений на основании пользовательского запроса или пользовательских данных.

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

Предложена система управления личными данными и событиями на транспортном средстве. Изобретение включает в себя систему транспортного средства и способ управления личными данными и событиями пользователя.

Изобретение относится к вычислительной технике, а именно к носителям информации. Технический результат - обеспечение формата расширяемой файловой системы для портативных носителей информации.

Изобретение относится к устройствам вычислительной техники и может быть использовано для разработки, представления, обновления и хранения информационно-методических ресурсов.

Изобретение относится к области музыкальной терапии. Технический результат заключается в создании персонифицированной базы данных благотворных звуков. В частности, изобретение относится к способу для создания персонифицированной базы данных звуков и музыкальных композиций. Определяют предпочтительные значения характеристик звука элементов первой базы данных, содержащей звуки, создавая тем самым первый фильтр. Применяют упомянутый первый фильтр ко второй базе данных, содержащей элементы, такие как звуки, тем самым создавая отфильтрованную вторую базу данных. Применяют второй фильтр к первой базе данных, содержащей элементы, такие как звуки, тем самым создавая отфильтрованную первую базу данных. Объединяют упомянутую отфильтрованную первую базу данных с упомянутой отфильтрованной второй базой данных, тем самым предоставляя персонифицированную базу данных звуков. 3 н. и 8 з.п. ф-лы, 2 ил.

Изобретение относится к области электронной коммуникации через сеть передачи данных. Технический результат - эффективная кластеризация хранящихся на сервере объектов, связанных с пользователем. Способ структуризации хранящихся объектов в связи с пользователем на сервере включает в себя: получение через сеть передачи данных от электронного устройства, связанного с пользователем, первого запроса на кластеризацию для привязки первых метаданных первого подмножества объектов в по меньшей мере первый кластер; получение метаданных, связанных с каждым объектом из первого подмножества; на основе, по меньшей мере, части метаданных, создание первой привязки метаданных первого подмножества объектов по меньшей мере к одному кластеру; передачу через сеть передачи данных первой привязки метаданных электронному устройству, причем первая привязка метаданных позволяет электронному устройству отображать первое подмножество объектов, собранных по меньшей мере в один первый кластер; получение через сеть передачи данных от электронного устройства указания на действие пользователя в первом подмножестве, которое отображается на электронном устройстве, причем действие пользователя инициирует изменение первого подмножества объектов во второе подмножество объектов; получение метаданных, связанных с каждым объектов из второго подмножества; на основе по меньшей мере метаданных, связанных со вторым подмножеством объектом, создание второй привязки метаданных второго подмножества объектов по меньшей мере ко второму кластеру, и передачу второй привязки вторых метаданных электронному устройству, причем вторая привязка метаданных позволяет электронному устройству отображать подмножество объектов, собранных по меньшей мере во второй кластер. 2 н. и 36 з.п. ф-лы, 3 ил.

Изобретение относится к области представления пользователям результатов информационного поиска, а именно к формированию персонализированной модели ранжирования на электронном устройстве, связанном с пользователем. Технический результат заключается в повышении релевантности предоставляемой пользователю информации, наиболее соответствующей его индивидуальным потребностям. Для этого осуществляют получение данных от сервера поисковой системы через коммуникационную сеть, содержащих информацию о свойствах, характерных для ресурса. Затем производят оценку взаимодействия пользователя с веб-ресурсом, выполняемого пользователем посредством использования электронного устройства, и определение значений параметров для веб-ресурса на основе взаимодействия пользователя. На основании полученных значений параметров, а также свойств, характерных для ресурса, формируют персонализированную модель ранжирования. 4 н. и 44 з.п. ф-лы, 4 ил.

Изобретение относится к машинам баз данных и может быть использовано для построения средств нечисловой обработки информации. Технический результат заключается в расширении функциональных возможностей за счет обеспечения поиска двух строк, содержащих по восемнадцать произвольно заданных символов, в проходящем потоке символов. Устройство поиска информации содержит запоминающее устройство (1) объемом 2048×3 бит, синхронный двоичный счетчик (2), цифровой мультиплексор (3), цифровой компаратор (4), элемент ИСКЛЮЧАЮЩЕЕ ИЛИ (5), мажоритарный элемент (6), первый и второй двухразрядные регистры (71 и 72). За счет указанного аппаратурного состава обеспечивается поиск двух строк, содержащих по восемнадцать произвольно заданных символов, в проходящем потоке символов. В результате достигнуто расширение функциональных возможностей устройства поиска информации. 2 ил.

Изобретение относится к области пользовательского интерфейса для проведения информационного поиска. Технический результат заключается в возможности увеличения количества различных приложений, в которых может быть проведен поиск в отношении поисковых запросов, вводимых в единый централизованный интерфейс. Для этого модуль поиска системного уровня принимает регистрационную информацию поискового интерфейса пользователя системного уровня для приложения вычислительного устройства. Регистрационная информация включает в себя указание того, как модуль поиска системного уровня может запускать приложение. Регистрационная информация добавляется в хранилище регистраций, и приложение включается в качестве приложения из одного или нескольких приложений, в которых можно проводить поиск с использованием поискового интерфейса пользователя системного уровня. 2 н. и 8 з.п. ф-лы, 13 ил.

Группа изобретений относится к области вычислительной техники, может быть использована в специализированных устройствах аппаратной поддержки типовых операций задач распознавания образов, в аппаратной поддержке в высокопроизводительных системах и устройствах параллельной обработки символьной информации, в аппаратных средствах поддержки вывода в информационно-поисковых и экспертных системах, осуществляющих обработку строк (строковых данных), и позволяет реализовать операции поиска по образцу и модификации строки на основе ассоциативной памяти. Техническим результатом является обеспечение реверсивной обработки строк. Способ содержит этапы, на которых: символы обрабатываемой строки замещаются первой подстрокой модификатора при двумерном представлении обрабатываемой строки, выполняется параллельный межстрочный сдвиг влево символов обрабатываемой строки при ее двумерном представлении, вторая подстрока модификатора вставляется в строку матрицы, удаляются незначащие символы обрабатываемой строки при ее одномерном представлении в выделенной маской ее части с помощью последовательного сдвига вправо, при этом маска формируется динамически для выделения рабочей части обрабатываемой строки на четвертом шаге. 2 н.п. ф-лы, 6 ил.

Изобретение относится к области построения корпуса документов. Технический результат заключается в обеспечении автоматизации анализа корпуса документов для определения тем корпуса документов. Технический результат достигается за счет выполнения классификации, с использованием классификатора, каждого документа во втором наборе документов по одной или более темам из числа исходных тем, где классификация включает определение неклассифицированного подмножества документов из второго набора документов, которые не были отнесены ни к одной из исходных тем, кластеризацию неклассифицированного подмножества документов по новым темам, не входящим в исходные темы, и классификацию каждого документа из неклассифицированного подмножества документов по одной или более темам из числа новых тем. 3 н. и 16 з.п. ф-лы, 7 ил.

Изобретение относится к устройству для обработки данных в логической системе с компьютерной поддержкой. Техническим результатом является обеспечение возможности создания или выполнения критичных к времени запросов и логических выводов без увеличения объема требуемой памяти. Устройство (V) для обработки данных содержит устройство (R) логических выводов с блоком (RP) рассуждений, источник (4, 5) данных и приложение (1). Устройство (R) на основании данных вырабатывает логические выводы на основе семантической модели, содержащей терминологические понятия онтологии, и экземпляра модели семантической модели, содержащего конкретные экземпляры терминологических понятий онтологии. Источник (4, 5) предоставляет данные для обработки посредством устройства (R). Приложение (1) направляет запрос (А) на устройство (R) и получает результаты логических выводов от устройства (R). Устройство (R) на основе наступающего события источника (4, 5), в особенности к определенным моментам времени, получает основанные на событии данные от источника (4, 5) для генерации причинного и/или основанного на времени логического вывода. Информации об основанных на событии данных источника (4, 5) включают в себя временные и причинные компоненты. 3 н. и 21 з.п. ф-лы, 1 ил.

Изобретение относится к отображению поисковой информации. Технический результат - предоставление оптимизированного графического пользовательского интерфейса для отображения ряда результатов поиска от поисковых систем для эффективной формулировки поискового запроса. Для этого способ отображения поисковой информации включает в себя обработку аппаратным процессором поискового запроса, введенного пользователем; предоставление с помощью компонента пользовательского интерфейса возможности предварительно просматривать ряд результатов поиска, соответствующих по меньшей мере части обработанного введенного поискового запроса; обнаружение аппаратным процессором активации компонента пользовательского интерфейса, и отображение по меньшей мере части результатов поиска в ответ на активацию компонента пользовательского интерфейса. 4 н. и 14 з.п. ф-лы, 6 ил.

Изобретение относится к области поиска в Интернете. Техническим результатом является экономия энергии клиентского устройства. В системе для получения информации из Интернета осуществляется отправка клиентским устройством серверу поискового запроса для поиска. Получают от сервера результаты поиска, соответствующие поисковому запросу. Отображают результаты поиска на клиентском устройстве в области просмотра веб-браузера на странице результатов поиска, причем результаты поиска включают в себя упорядоченные группы гиперссылок, ведущие к Интернет-ресурсам. Получают указания на выбор пользователем одной из упорядоченных групп гиперссылок и отправляют серверу инструкции по предоставлению клиентскому устройству Интернет-ресурса, на который ведет выбранная группа гиперссылок. Получают выбранный Интернет-ресурс и реорганизуют отображение страницы результатов поиска в области просмотра веб-браузера. Отображают выбранный Интернет-ресурс в области просмотра веб-браузера в визуальной близости к реорганизованной странице результатов поиска при продолжении отображения реорганизованной страницы результатов поиска. 4 н. и 22 з.п. ф-лы, 8 ил.
Наверх