Классика баз данных - статьи
При использовании сэмпинга по маске
При использовании сэмпинга по маске гарантируется, что если некоторая группа выбирается в образец, то эта группа будет в нем в достаточной мере представлена независимо от своих относительных размеров.
Этот метод было бы разумно применить к Bigtable, в которой сохраняются Web-страницы, а именами строк данных является соответствующие URL. При использовании сэмплинга по маске можно определить, каким образом извлекается домен из URL, и постановить, что события появления в образце каждого домена равновероятны.
Более точно, данная процедура должна возвращать, возможно, не однородный образец, содержащий ‹k.m›, т.е. проекции имен строк k на маску m. Имеются, по крайней мере, две детали, делающие данную проблему интересной. Во-первых, множество разных ‹k.m› может быть большим, и из него потребуется брать образец. Если вернуться к предыдущему примеру, то для всех доменов может просто не хватить желаемого размера образца. Во-вторых, хотя имена строк данных являются уникальными, их проекции на маску часто свойством уникальности не обладают. Для каждого значения ‹k.m› имеется множество строк из Bigtable, и нужно решить, какие из них сохранять в Minitable. Если опять обратиться к примеру с таблицей Web-страниц, может потребоваться выбирать образец внутри заданного домена. Рассмотрим множество S(n) строк данных, для которых ‹k.m› = n. Тогда в идеале хотелось бы сохранять все строки r из S(n), если значение |S(n)| невелико, делать умеренную выборку при больших значениях |S(n)|, и сокращать относительный размер образца из S(n) при совсем больших значениях |S(n)|.
Для пристрастного взятия образцов можно обобщить процедуру взятия образцов с использованием хэш-функции. Как и раньше, в процедуре используется хэш-функция h1 : ‹k.m› ?> [0 .. p], и в образце сохраняются те ‹k.m›, для которых h1(‹k.m›) ∈ [0, fp?1]. Затем для каждой группы S(n), для которой n было сохранено в первом образце, к полным именам строк применяется хэш-функция h2 (зависящая от n).Здесь предполагается, что имеется побочная таблица T : ‹k.m&rsaquo = n ?> gn, которая на практике часто подготавливаются автономным образом или легко поддерживается в отложенном режиме. (Ее можно получить неявно, если имеется однородная Minitable.) Авторы называются эту таблицу gtable, поскольку она содержит некоторую строку для каждой группы, задаваемой маской.
На практике эта схема сэмплинга может обеспечить пристрастную Minitable с репрезентативным образцом доменов на основе Bigtable с Web-страницами. Для каждого из этих доменов будет иметься достаточно много строк, чтобы позволить, например, приближенно вычислять агрегаты, даже если для выбранных доменов сильно разнится число строк в базовой Bigtable.
