какой индекс можно применить к этому условию с высокой эффективностью?

Question

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

Учитывая набор данных, для каждого элемента существует D размерностии C значения могут быть установлены для каждой размерности.
например, набор данных ВЕЩИ (идентификатор, владелец, цвет, вес) , ID является первичным ключом
атрибут owner может быть alice, jack, zuck ;
color *Атрибут 1026 * может быть красный, желтый, зеленый ;
Атрибут weight может быть high, medium, low ;
в этом наборе данных, D = 3, C = 3

Теперь я хочу сделать много запросов много раз, например:
"есть ли данные с owner = red и color = red"?
"есть ли какие-либо данные с weight = low "?
" есть ли какие-либо данные с owner = red и color = red и weight = high "?
Мне нужно только" Да или Нет ", чтобы ответить на этот запрос.

Мне нужно сделать это изначально, я имею в виду без базы данных.
На ПК я пытаюсьied Bitmap и инвертированный индекс для выполнения требования, но размер набора данных будет миллион, а Dimensionality будет 8 ~ 18, Cardinality будет 5 ~ 15.В результате эффективность недостаточно хороша.

Не могли бы вы дать мне какое-нибудь предложение, чтобы сделать его намного более эффективным?
Заранее спасибо!

Answer 1

Возможно, вы захотите отсортированный словарь для каждого измерения, где KEY - это возможные элементы измерения, а VALUE - список идентификаторов.

OWNER_DICTIONARY = {
    Bob: [1,5],
    Jim: [2],
    Sally: [3,4],
    Will: []
}
COLOR_DICTIONARY = {
    Blue: [5],
    Green: [2],
    Red: [],
    Yellow: [1,3,4]
}
WEIGHT_DICTIONARY = {
    Low: [1,2,4],
    High: [3,5]
}

Затем вы просто используете ИНТЕРСЕКТ в ЗНАЧЕНИЯХ (список идентификаторов) ваших словарей. Если размер пересечения больше 0, у вас есть положительное совпадение.

Owner=Bob AND Weight=High

([1,5] UNION [3,5]) = [5]

Если одно из ЗНАЧЕНИЙ для ваших критериев (или одно из предыдущих ВЗАИМОДЕЙСТВИЙ) пусто [], вы можете сразу же замкнуть накоротко (вернуть ложное) без необходимости дальнейшей оценки.

В терминах базы данных вы должны поместить НЕКЛАСТЕРНЫЙ ИНДЕКС в каждое поле / столбец. и делает

EXISTS(SELECT ID FROM Table WHERE Col1=@Val1 AND Col2=@Val2 AND Col3=@Val3)

РЕДАКТИРОВАТЬ СОЮЗ -> ПЕРЕКЛЮЧЕНИЕ хороший улов @ElKamina