СПОСОБ И УСТРОЙСТВО ГЕНЕРИРОВАНИЯ ДВУМЕРНОЙ МАТРИЦЫ И СПОСОБ И УСТРОЙСТВО ЗАПРОСА ЭЛЕМЕНТА С КЛЮЧЕВЫМ ЗНАЧЕНИЕМ

1. Способ запроса элемента с ключевым значением, включающий в себя этапы, на которых:
определяют, из множества хеш-функций, подмножество хеш-функций, соответствующее каждой группе элементов с ключевыми значениями;
вычисляют, для любого элемента с ключевым значением из каждой группы элементов с ключевыми значениями, хеш-значение в соответствии с подмножеством хеш-функций, соответствующим группе элементов с ключевыми значениями, которой принадлежит упомянутый элемент с ключевым значением, и устанавливают элемент, соответствующий местоположению, являющемуся местоположением вычисленного хеш-значения и расположенному в двумерной матрице, равным второму заданному идентификатору;
определяют, для запрашиваемого элемента с ключевым значением, подмножество хеш-функций, соответствующее группе элементов с ключевыми значениями, которой принадлежит запрашиваемый элемент с ключевым значением, и вычисляют хеш-значение запрашиваемого элемента с ключевым значением на основе соответствующего подмножества хеш-функций;
получают элемент, соответствующий местоположению, являющемуся местоположением хеш-значения запрашиваемого элемента с ключевым значением и расположенному в двумерной матрице; и
определяют, когда полученный элемент является вторым заданным идентификатором, соответствующим местоположению, являющемуся местоположением хеш-значения запрашиваемого элемента с ключевым значением и расположенному в двумерной матрице, что запрашиваемый элемент с ключевым значением принадлежит множеству элементов с ключевыми значениями, представленному двумерным фильтром.
2. Способ по п. 1, в котором хеш-функции, содержащиеся в подмножествах хеш-функций, соответствующих любым двум разным группам элементов с ключевыми значениями, различны; или
хеш-функции, содержащиеся в подмножествах хеш-функций, соответствующих любым двум разным группам элементов с ключевыми значениями, совпадают, но хеш-функции различаются по способу расстановки.
3. Способ по п. 1, в котором этап вычисления хеш-значения запрашиваемого элемента с ключевым значением, в частности, включает в себя подэтапы, на которых:
получают первое хеш-значение, посредством вычисления первого подэлемента с ключевым значением, элемента с ключевым значением подлежащего запросу на основе подмножества хеш-функций, соответствующего группе элементов с ключевыми значениями, которой принадлежит элемент с ключевым значением, подлежащий запросу; и
получают второе хеш-значение, посредством вычисления второго подэлемента с ключевым значением, элемента с ключевым значением подлежащего запросу на основе подмножества хеш-функций, соответствующего группе элементов с ключевыми значениями, которой принадлежит элемент с ключевым значением подлежащей запросу.
4. Способ по п. 3, в котором получение элемента, соответствующего местоположению, являющемуся местоположением хеш-значения запрашиваемого элемента с ключевым значением и расположенному в двумерной матрице, в частности, включает в себя этапы, на которых:
получают, из двумерной матрицы, элемент, использующий первое хеш-значение в качестве строки и использующий второе хеш-значение в качестве столбца; или получают, из двумерной матрицы, элемент, использующий второе хеш-значение в качестве строки и использующий первое хеш-значение в качестве столбца.
5. Способ генерирования двумерного фильтра, включающий в себе этапы, на которых:
создают двумерную матрицу, содержащую по меньшей мере две вектор-строки и по меньшей мере два вектор-столбца;
определяют множество хеш-функций, при этом каждая хеш-функция из множества хеш-функций соответствует по меньшей мере одной группе элементов с ключевыми значениями; и получают первое хеш-значение, посредством вычисления хеш-значения для первого подэлемента с ключевым значением любого элемента с ключевым значением по меньшей мере из одной соответствующей группы элементов с ключевыми значениями с использованием любой хеш-функции из множества хеш-функций, и получают второе хеш-значение посредством вычисления хеш-значения второго подэлемента с ключевым значением любого элемента с ключевым значением, при этом первое хеш-значение является положительным целым числом, меньшим или равным длине вектор-строк, а второе хеш-значение является положительным целым числом, меньшим или равным длине вектор-столбцов; и
генерируют двумерный фильтр, содержащий двумерную матрицу и множество хеш-функций.
6. Способ по п. 5, в котором как длина вектор-строк, так и длина вектор-столбцов больше или равна ; где
Sr представляет собой количество всех элементов с ключевыми значениями во всех группах элементов с ключевыми значениями; или Sr представляет собой количество элементов с ключевыми значениями, полученных после фильтрации всех элементов с ключевыми значениями из всех групп элементов с ключевыми значениями с использованием условия запроса.
7. Способ по п. 5, в котором первый подэлемент с ключевым значением содержит элемент с ключевым значением, образованный всеми нечетными битами любого элемента с ключевым значением, когда упомянутый любой элемент с ключевым значением представлен в двоичном виде, а второй подэлемент с ключевым значением содержит элемент с ключевым значением, образованный всеми четными битами любого элемента с ключевым значением, когда упомянутый любой элемент с ключевым значением представлен в двоичном виде; или
го
ый
го
ый
первый подэлемент с ключевым значением содержит элемент с ключевым значением, образованный битами с 1 по K любого элемента с ключевым значением, когда упомянутый любой элемент с ключевым значением представлен в двоичном виде, а второй подэлемент с ключевым значением содержит элемент с ключевым значением, образованный битами с (K+1) по N любого элемента с ключевым значением, когда упомянутый любой элемент с ключевым значением представлен в двоичном виде, при этом N является количеством битов любого элемента с ключевым значением, когда упомянутый любой элемент с ключевым значением представлен в двоичном виде, 1 ≤ K ≤ N, и K является положительным целым числом.
8. Способ по п. 5, дополнительно включающий в себя этап, на котором:
инициируют элемент, определенный любой вектор-строкой и любым вектор-столбцом, расположенными в двумерной матрице, первому заданному идентификатору.
9. Устройство запроса элемента с ключевым значением, содержащее:
по меньшей мере, один процессор;
память, выполненную с возможностью электронной связи с процессором; и
программный код, хранящийся в памяти, при этом процессор исполняет программный код для:
определения, из множества хеш-функций, подмножества хеш-функций, соответствующего каждой группе элементов с ключевыми значениями;
вычисления, для любого элемента с ключевым значением из каждой группы элементов с ключевыми значениями, хеш-значения в соответствии с подмножеством хеш-функций, соответствующим группе элементов с ключевыми значениями, которой принадлежит упомянутый элемент с ключевым значением, и установки элемента, соответствующего местоположению, являющемуся местоположением вычисленного хеш-значения и расположенному в двумерной матрице, равным второму заданному идентификатору;
определения, для запрашиваемого элемента с ключевым значением, подмножества хеш-функций, соответствующего группе элементов с ключевыми значениями, которой принадлежит запрашиваемый элемент с ключевым значением, и вычисления хеш-значения запрашиваемого элемента с ключевым значением на основе соответствующего подмножества хеш-функций;
получения элемента, соответствующего некоторому местоположению, являющемуся местоположением хеш-значения группы запрашиваемого элемента с ключевым значением и расположенному в двумерной матрице; и
определения, когда полученный элемент является вторым заданным идентификатором, соответствующим местоположению, являющемуся местоположением хеш-значения запрашиваемого элемента с ключевым значением и расположенному в двумерной матрице, что запрашиваемый элемент с ключевым значением принадлежит множеству элементов с ключевыми значениями, представленному двумерным фильтром.
10. Устройство по п. 9, в котором хеш-функции, содержащиеся в подмножествах хеш-функции, соответствующих любым двум разным группам элементов с ключевыми значениями и определенных процессором, различны; или
хеш-функции, содержащиеся в подмножествах хеш-функций, соответствующих любым двум разным группам элементов с ключевыми значениями и определенных процессором, совпадают, но хеш-функции различны по способу расстановки.
11. Устройство по п. 9, в котором процессор, в частности, выполнен с возможностью:
получения первого хеш-значения, посредством вычисления первого подэлемента с ключевым значением элемента с ключевым значением подлежащего запросу на основе подмножества хеш-функций, соответствующего группе элементов с ключевыми значениями, которой принадлежит запрашиваемый элемент с ключевым значением; и
получения второго хеш-значения посредством вычисления второго подэлемента с ключевым значением элемента с ключевым значением подлежащего запросу на основе подмножества хеш-функций, соответствующего группе элементов с ключевыми значениями, которой принадлежит запрашиваемый элемент с ключевым значением.
12. Устройство по п. 11, в котором процессор, в частности, выполнен с возможностью:
получения, из двумерной матрицы, элемента, использующего первое хеш-значение в качестве строки и использующего второе хеш-значение в качестве столбца; или получения, из двумерной матрицы, элемента, использующего второе хеш-значение в качестве строки и использующего первое хеш-значение в качестве столбца.
13. Устройство генерирования двумерного фильтра, содержащее:
по меньшей мере, один процессор;
память, выполненную с возможностью электронной связи с процессором; и
программный код, хранящийся в памяти, при этом процессор исполняет программный код для:
создания двумерной матрицы, содержащий по меньшей мере две вектор-строки и по меньшей мере два вектор-столбца;
определения множества хеш-функций, при этом каждая хеш-функция из множества хеш-функций соответствует по меньшей мере одной группе элементов с ключевыми значениями; и получения первого хеш-значения, посредством вычисления хеш первого подэлемента с ключевым значением любого элемента с ключевым значением по меньшей мере из одной соответствующей группы элементов с ключевыми значениями с использованием любой хеш-функции из множества хеш-функций, и получения второго хеш-значения посредством вычисления хеш второго подэлемента с ключевым значением любого элемента с ключевым значением, при этом первое хеш-значение является положительным целым числом, меньшим или равным длине вектор-строк, и второе хеш-значение является положительным целым числом, меньшим или равным длине вектор-столбцов; и
генерирования двумерного фильтра, содержащего двумерную матрицу и множество хеш-функций.
14. Устройство по п. 13, в котором как длина вектор-строк, так и длина вектор-столбцов больше или равна , при этом вектор-строки и вектор-столбцы содержатся в двумерной матрице, сгенерированной процессором, при этом
Sr представляет собой количество всех элементов с ключевыми значениями во всех группах элементов с ключевыми значениями; или Sr представляет собой количество элементов с ключевыми значениями, полученных после фильтрации всех элементов с ключевыми значениями из всех групп элементов с ключевыми значениями с использованием условия запроса.
15. Устройство по п. 13, в котором первый подэлемент с ключевым значением, полученный процессором, содержит элемент с ключевым значением, образованный всеми нечетными битами любого элемента с ключевым значением, когда упомянутый любой элемент с ключевым значением представлен в двоичном виде, а второй подэлемент с ключевым значением, полученный процессором, содержит элемент с ключевым значением, образованный всеми четными битами любого элемента с ключевым значением, когда упомянутый любой элемент с ключевым значением представлен в двоичном виде; или
го
ый
го
ый
первый подэлемент с ключевым значением, полученный процессором, содержит элемент с ключевым значением, образованный битами с 1 по K любого элемента с ключевым значением, когда упомянутый любой элемент с ключевым значением представлен в двоичном виде, а второй подэлемент с ключевым значением, полученный процессором, содержит элемент с ключевым значением, образованный битами с (K+1) по N любого элемента с ключевым значением, когда упомянутый любой элемент с ключевым значением представлен в двоичном виде, при этом N является количеством битов любого элемента с ключевым значением, когда упомянутый любой элемент с ключевым значением представлен в двоичном виде, 1 ≤ K ≤ N, и K является положительным целым числом.
16. Устройство по п. 13, в котором процессор дополнительно выполнен с возможностью инициирования элемента, определенного любой вектор-строкой и любым вектор-столбцом, расположенными в двумерной матрице, первому заданному идентификатору.