Re: [MSSQL] Как будет быстрее?
От: Sinclair Россия https://github.com/evilguest/
Дата: 25.01.06 11:48
Оценка: 1 (1)
Здравствуйте, _spin_, Вы писали:

__>Для каждого нового сообщения необходимо выполнить сложное сравнение его коэффициентов со всеми записями в таблице и если результат сравнения "одниаковый найден" — выдать его "ID".


__>Критерий сравнения таков:

__>
__>IF
__>((CurrCoef1 >= Coef1 - @Delta) and (CurrCoef1 <= Coef1 + @Delta)) and
__>((CurrCoef2 >= Coef2 - @Delta) and (CurrCoef2 <= Coef2 + @Delta)) and
__>...
__>((CurrCoefN >= CoefN - @Delta) and (CurrCoefN <= CoefN + @Delta))
__>SET @RESULT = 'SPAM'
__>ELSE SET @RESULT = 'NOT SPAM'
__>


__>Сейчас система работает бодренько на 1000 сообщений, но когда доходит до 30 тыс. сообщений, то скорость обработки падает до 1 сообщения в секунду.


__>Как это можно исправить?

1. Написать все в человеческом виде:
select id from CoefLst where 
  Coef1 between @coef1 - @delta and @coef1 + @delta 
AND 
  Coef2 between @coef2 - @delta and @coef2 + @delta 
AND
  Coef3 between @coef3 - @delta and @coef3 + @delta
...

И никаких курсоров, тем более на клиенте!
2. Сделать индекс по Coef1, Coef2, Coef3...
Можно даже кластерный, т.к. эти значения со временем не изменяются.
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[5]: [MSSQL] Как будет быстрее?
От: Sinclair Россия https://github.com/evilguest/
Дата: 27.01.06 04:52
Оценка: 1 (1)
Здравствуйте, _spin_, Вы писали:
__>Теоретически первая фраза верна, а вот на практике когда размер базы переваливает 500 Гб, а суммарное количество записей — 1 млрд, начинаются задержки выборки на уровне железа, т.к. резко возрастает количество seek'ов raid'а, выполняемое при отработке 1 запроса.
К сожалению, у меня нет достаточной практики для того, чтобы определить, что эффективнее — 10^6 записей с 10 полями или 10^7 записей с двумя полями.
Но в целом предложение Antipov'a выглядит достаточно привлекательно.
Дело в том, что в его случае мы можем сделать примерно так (это идея, а не конечное решение):
select message_id from coef_values where 
(coef_id = @coef_id_1 and coef_value between @coef_1_value-@delta and @coef_1_value+@delta)
 OR 
(coef_id = @coef_id_2 and coef_value between @coef_2_value-@delta and @coef_2_value+@delta)
...

таким образом, мы получаем совпадения коээфициентов. Это можно сделать очень эффективно при помощи кластерного индекса по coef_id, coef_value — сканироваться будет минимум страниц, только фактические попадания. Должен быть index seek, а не index scan.
Теперь можно посчитать количество совпадающих коэффициентов для писем:
select count(*) as hit_count, message_id
from (/*тут наш селект, приведенный выше*/)
group by message_id

Ну, и ограничить их по количеству:
select count(*) as hit_count, message_id
from (select message_id from coef_values where 
(coef_id = @coef_id_1 and coef_value between @coef_1_value-@delta and @coef_1_value+@delta)
 OR 
(coef_id = @coef_id_2 and coef_value between @coef_2_value-@delta and @coef_2_value+@delta)
) hits
group by message_id
having hit_count > @hit_count_threshold

Все зависит от распределения данных по hit_count. Боюсь, что более эффективный способ построить на линейных индексах не удастся.

Альтернатива только одна — рассматривать многомерные индексы. Правда, тут я тоже не очень понимаю, как правильно строить такой индекс, чтобы все было эффективно — большинство многомерных индексов нацелены на решение задачи proximity search, т.е. запросов вида
select * from point 
where 
X  between @x_min and @x_max
AND
Y  between @y_min and @y_max
AND
Z  between @z_min and @z_max

Это ограничение расстояния по норме таксиста.
А нам нужен индекс для оптимизации запросов с другой нормой:
select * from point 
where 
(X  between @x_min and @x_max AND Y  between @y_min and @y_max)
OR
(Y  between @y_min and @y_max AND Z  between @z_min and @z_max)
OR
(Z  between @z_min and @z_max AND X  between @x_min and @x_max)

(это для поиска попаданий 2 из 3).

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

Впрочем, я не уверен, что и это поможет. Дело в том, что лучшие из известных мне многомерных индексов могут гарантировать заполнение страниц порядка 1/(K+1) для K-мерного пространства. Это еще приемлемо для двух-трех измерений; для 10-мерного индекса расход дискового пространства будет просто кошмарным. Более компактные представления имеют время вставки порядка O(N), вместо О(logN), что делает их неприемлемыми для шибко динамических данных (а у тебя, как я понимаю, именно такой случай).
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re: [MSSQL] Как будет быстрее?
От: Igor Trofimov  
Дата: 24.01.06 19:25
Оценка: +1
__>Сейчас система работает бодренько на 1000 сообщений, но когда доходит до 30 тыс. сообщений, то скорость обработки падает до 1 сообщения в секунду.
__>Как это можно исправить?

Никак не исправишь. Такой уж ты алгоритм придумал — сравнивать каждое входящее сообщение с каждым имеющимся.
Твой алгоритм имеет сложность порядка O(n^2), где n — число сообщений в базе.
Допустим, пришло 100 сообщений и имеется 100 000 сообщений. Это нормальные такие числа. Не очень большие.
Придется сделать 10 000 000 чтений и проверок.

Короче, меняй алгоритм.
[MSSQL] Как будет быстрее?
От: _spin_ Россия  
Дата: 24.01.06 18:35
Оценка:
Делаю серверный спам-фильтр. Алгоритм анализа сообщений уже отработан, но вот возникла проблема с длительной работой.

В общих чертах, система выглядит так:

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

Все коэффициенты хранятся в одной таблице:

CREATE TABLE CoefLst(
[ID] int IDENTITY(1,1) PRIMARY KEY CLUSTERED,
Coef1 float NOT NULL,
Coef2 float NOT NULL,
...
...
CoefN float NOT NULL,
AddDate datetime DEFAULT (getdate()) NOT NULL,
ParentID int NULL

)


Для каждого нового сообщения необходимо выполнить сложное сравнение его коэффициентов со всеми записями в таблице и если результат сравнения "одниаковый найден" — выдать его "ID".

Критерий сравнения таков:
IF
((CurrCoef1 >= Coef1 - @Delta) and (CurrCoef1 <= Coef1 + @Delta)) and
((CurrCoef2 >= Coef2 - @Delta) and (CurrCoef2 <= Coef2 + @Delta)) and
...
((CurrCoefN >= CoefN - @Delta) and (CurrCoefN <= CoefN + @Delta))
SET @RESULT = 'SPAM'
ELSE SET @RESULT = 'NOT SPAM'


Сейчас система работает бодренько на 1000 сообщений, но когда доходит до 30 тыс. сообщений, то скорость обработки падает до 1 сообщения в секунду.

Как это можно исправить?
... << Тишина>>
Не восхрапи на работе, ибо храпом своим разбудишь начальника своего.
Re: [MSSQL] Как будет быстрее?
От: Serginio1 СССР https://habrahabr.ru/users/serginio1/topics/
Дата: 24.01.06 20:23
Оценка:
Здравствуйте, _spin_, Вы писали:

Вычисляй Хэш, и отбирай зписи по этому хэшу и сравнивай значения. Надо понимать,что у тебя сравниваются все записи?
и солнце б утром не вставало, когда бы не было меня
Re[2]: [MSSQL] Как будет быстрее?
От: Serginio1 СССР https://habrahabr.ru/users/serginio1/topics/
Дата: 24.01.06 20:31
Оценка:
Здравствуйте, Serginio1, Вы писали:

S>Здравствуйте, _spin_, Вы писали:


S> Вычисляй Хэш, и отбирай зписи по этому хэшу и сравнивай значения. Надо понимать,что у тебя сравниваются все записи?

Прошу прощения, а чем не подходят индексы с попаданием в некоторый диапозон
Coefn +- @Delta???
и солнце б утром не вставало, когда бы не было меня
Re: [MSSQL] Как будет быстрее?
От: Antipov  
Дата: 25.01.06 09:37
Оценка:
Здравствуйте, _spin_, Вы писали:

__>Делаю серверный спам-фильтр. Алгоритм анализа сообщений уже отработан, но вот возникла проблема с длительной работой.


__>В общих чертах, система выглядит так:


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


__>Все коэффициенты хранятся в одной таблице:


__>
__>CREATE TABLE CoefLst(
__>[ID] int IDENTITY(1,1) PRIMARY KEY CLUSTERED,
__>Coef1 float NOT NULL,
__>Coef2 float NOT NULL,
__>...
__>...
__>CoefN float NOT NULL,
__>AddDate datetime DEFAULT (getdate()) NOT NULL,
__>ParentID int NULL

__>)
__>


__>Для каждого нового сообщения необходимо выполнить сложное сравнение его коэффициентов со всеми записями в таблице и если результат сравнения "одниаковый найден" — выдать его "ID".


__>Критерий сравнения таков:

__>[pascal]

Логику лучше реализовывать на сервере

CREATE TRIGGER ins_rec ON [dbo].[CoefLst] FOR INSERT
AS
    DECLARE @Coef1 float
    DECLARE @Coef2 float
    DECLARE @Coef3 float 
    
    DECLARE @id int

    DECLARE @delta float

    --Можно прочитать откуданибудь если хочется
    SET @delta = 0.1    

    DECLARE ins_rec CURSOR FOR SELECT [Coef1], [Coef2], [Coef3], [id] FROM [inserted]

    OPEN ins_rec
    FETCH NEXT FROM ins_rec INTO @Coef1, @Coef2, @Coef3, @id
    WHILE @@FETCH_STATUS = 0
    BEGIN
        IF EXISTS (SELECT [id] FROM CoefLst
        WHERE (@Coef1 BETWEEN ([Coef1] - @delta) AND ([Coef1] + @delta)) AND
              (@Coef2 BETWEEN ([Coef2] - @delta) AND ([Coef2] + @delta)) AND
              (@Coef3 BETWEEN ([Coef3] - @delta) AND ([Coef3] + @delta)) AND
              [id] <> @id --Запись кот. проверяется на спам уже в таблице
                  --Но в случае спама удалится при откате
        )
        BEGIN
            ROLLBACK TRANSACTION
            RAISERROR ('Error: ins_rec Спам', 15, 1)
            RETURN
        END
        FETCH NEXT FROM ins_rec INTO @Coef1, @Coef2, @Coef3, @id
    END
    CLOSE ins_rec
    DEALLOCATE ins_rec
GO


__>Сейчас система работает бодренько на 1000 сообщений, но когда доходит до 30 тыс. сообщений, то скорость обработки падает до 1 сообщения в секунду.


Сейчас на порядок быстрее и будет зависеть от скорости сервера

__>Как это можно исправить?


Твоё задание в качестве факультатива

Подсказки:

для начала:

CREATE TABLE CoefLst(
[ID] int IDENTITY(1,1) PRIMARY KEY CLUSTERED,
Coef float NOT NULL,
CoefType int NOT NULL,
AddDate datetime DEFAULT (getdate()) NOT NULL,
ParentID int NULL
)


затем добавить индекс на Coef и переписать запрос в тригере.
Re: [MSSQL] Как будет быстрее?
От: Аноним  
Дата: 25.01.06 10:49
Оценка:
Здравствуйте, _spin_, Вы писали:

как вариант — иметь две таблицы для оригиналов и для спама:

в таблице оригиналов иметь уникальный индекс по полям коэфициентов, если индекс срабатывает помещать в таблицу спамов.
Re[2]: [MSSQL] Как будет быстрее?
От: _spin_ Россия  
Дата: 25.01.06 15:57
Оценка:
Здравствуйте, Igor Trofimov, Вы писали:

iT>Никак не исправишь. Такой уж ты алгоритм придумал — сравнивать каждое входящее сообщение с каждым имеющимся.

iT>Твой алгоритм имеет сложность порядка O(n^2), где n — число сообщений в базе.
iT>Допустим, пришло 100 сообщений и имеется 100 000 сообщений. Это нормальные такие числа. Не очень большие.
iT>Придется сделать 10 000 000 чтений и проверок.

iT>Короче, меняй алгоритм.


А как работают другие антиспамовые фильтры? Даже элементарные на основе списка адресов спамеров?
... << Тишина>>
Не восхрапи на работе, ибо храпом своим разбудишь начальника своего.
Re[3]: [MSSQL] Как будет быстрее?
От: _spin_ Россия  
Дата: 25.01.06 15:57
Оценка:
Здравствуйте, Serginio1, Вы писали:

S>Здравствуйте, Serginio1, Вы писали:


S> Прошу прощения, а чем не подходят индексы с попаданием в некоторый диапозон

S>Coefn +- @Delta???

Суть в том, что критерий сравнения — "K из N". Т.е. необходимо, чтобы совпало только K коэффициентов из N, где N — общее число коэффициентов для текущего файла. Поэтому способ использовать BETWEEN я пока не придумал. Или под диапазонами имелось ввиду что-то другое, не between?
... << Тишина>>
Не восхрапи на работе, ибо храпом своим разбудишь начальника своего.
Re[2]: [MSSQL] Как будет быстрее?
От: _spin_ Россия  
Дата: 25.01.06 15:57
Оценка:
Здравствуйте, Antipov, Вы писали:


A>Логику лучше реализовывать на сервере


A>
<sorry, skipped>
A>


Использовать триггер с курсором на милионах записей — не самое удачное решение. Необходима скорость обработки не ниже 30 сообщений в секунду.

A>Сейчас на порядок быстрее и будет зависеть от скорости сервера


Сервер будет мощный, сейчас всё испытывается на 2х хьюлетовских друхпроцессорных рабочих станциях.

A>Твоё задание в качестве факультатива


A>Подсказки:


A>для начала:


A>
A>CREATE TABLE CoefLst(
A>[ID] int IDENTITY(1,1) PRIMARY KEY CLUSTERED,
A>Coef float NOT NULL,
A>CoefType int NOT NULL,
A>AddDate datetime DEFAULT (getdate()) NOT NULL,
A>ParentID int NULL
A>)
A>


Добавляет сложностей с получением значения критерия отбора "K из N". Тип коэффициента всегда один, имеет значение его номер. Плюс такое изменение таблицы увеличивает количество записей в 20 с лишним раз. И из 10 миллионов мы получим 200. Не многовато ли? У меня сейчас есть базы, в которых более 500 млн.записей и работать с ними достаточно сложно.

A>затем добавить индекс на Coef и переписать запрос в тригере.
... << Тишина>>
Не восхрапи на работе, ибо храпом своим разбудишь начальника своего.
Re[2]: [MSSQL] Как будет быстрее?
От: _spin_ Россия  
Дата: 25.01.06 15:57
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>1. Написать все в человеческом виде:

S>
S>select id from CoefLst where 
S>  Coef1 between @coef1 - @delta and @coef1 + @delta 
S>AND 
S>  Coef2 between @coef2 - @delta and @coef2 + @delta 
S>AND
S>  Coef3 between @coef3 - @delta and @coef3 + @delta
S>...
S>

Красиво, согласен, но вот реализовать K из N? Т.е. считать сообщение спамом только если из N коэффициентов в соответствующие диапазоны попало K.
Я пока такого способа не придумал. Может есть свежие мысли?


S>И никаких курсоров, тем более на клиенте!

И не планировал

S>2. Сделать индекс по Coef1, Coef2, Coef3...

S>Можно даже кластерный, т.к. эти значения со временем не изменяются.
Есть, только не кластерные.
... << Тишина>>
Не восхрапи на работе, ибо храпом своим разбудишь начальника своего.
Re[3]: [MSSQL] Как будет быстрее?
От: Sinclair Россия https://github.com/evilguest/
Дата: 26.01.06 03:38
Оценка:
Здравствуйте, _spin_, Вы писали:
__>Красиво, согласен, но вот реализовать K из N? Т.е. считать сообщение спамом только если из N коэффициентов в соответствующие диапазоны попало K.
__>Я пока такого способа не придумал. Может есть свежие мысли?
пока нет.
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[4]: [MSSQL] Как будет быстрее?
От: Serginio1 СССР https://habrahabr.ru/users/serginio1/topics/
Дата: 26.01.06 05:54
Оценка:
Здравствуйте, _spin_, Вы писали:

__>Здравствуйте, Serginio1, Вы писали:


S>>Здравствуйте, Serginio1, Вы писали:


S>> Прошу прощения, а чем не подходят индексы с попаданием в некоторый диапозон

S>>Coefn +- @Delta???

__>Суть в том, что критерий сравнения — "K из N". Т.е. необходимо, чтобы совпало только K коэффициентов из N, где N — общее число коэффициентов для текущего файла. Поэтому способ использовать BETWEEN я пока не придумал. Или под диапазонами имелось ввиду что-то другое, не between?

Если К из N то достаточно сложно, что либо оптимизировать. Хотя можно на первом этапе посмотреть, есть ли вообще K Coefn входящих вдиапозон используя индексы по Coef.
Все зависит от относительной величины Delta.
и солнце б утром не вставало, когда бы не было меня
Re[3]: [MSSQL] Как будет быстрее?
От: Antipov  
Дата: 26.01.06 06:19
Оценка:
Здравствуйте, _spin_, Вы писали:

__>Использовать триггер с курсором на милионах записей — не самое удачное решение. Необходима скорость обработки не ниже 30 сообщений в секунду.


Если быть внимательным курсор только то таблице inserted т.е. по тем записям кот. вставляются, как ты иначе обработаеш вставку 100 записей?

A>>Сейчас на порядок быстрее и будет зависеть от скорости сервера


__>Сервер будет мощный, сейчас всё испытывается на 2х хьюлетовских друхпроцессорных рабочих станциях.


Попробуй у меня на более слабом сервере скорость на порядок больше приведённой выше в топике.

__>Добавляет сложностей с получением значения критерия отбора "K из N". Тип коэффициента всегда один, имеет значение его номер. Плюс такое изменение таблицы увеличивает количество записей в 20 с лишним раз. И из 10 миллионов мы получим 200. Не многовато ли? У меня сейчас есть базы, в которых более 500 млн.записей и работать с ними достаточно сложно.


Тип коэффициента это и есть его номер в данном случае. Количество записей в таблице никого не должно смущать т.к. СКОРОСТЬ ВЫБОРКИ ЗАВИСИТ НЕ ОТ КОЛИЧЕСТВА ЗАПИСЕЙ А ОТ СЕЛЕКТИВНОСТИ И ИНДЕКСИРОВАННОСТИ, которые мы и повышаем: накладываем индекс на поле Coef, а затем ограничиваем выборку нижним и верхним значением коэффициента. В результате при наличии индекса сканирования всей таблицы не происходит и ты получаеш минимальную выборку а затем как следствие минимальные дальнейшие сравниения.
Re: [MSSQL] Как будет быстрее?
От: sch  
Дата: 26.01.06 10:29
Оценка:
__>На вход поступает сообщение, для него считается набор коэффициентов, потом эти коэффициенты сравниваются с уже рассчитанными для других, пришедщих ранее сообщений. Если по выбранному критерию коэффициенты текущие совпадают с коэффициентами, имеющимися в списке — сообщение считается повтором, помечается как подозрительное на спам и его коэффициенты далее не учитываются. Если же совпадение не отмечено — коэффициенты заносятся в список и сообщение считается оригиналом.

Для таких задач лучще всего подойдут k-D деревья -- гарантированное логарифмическое время поиска.
Re[2]: [MSSQL] Как будет быстрее?
От: _spin_ Россия  
Дата: 26.01.06 15:11
Оценка:
Здравствуйте, sch, Вы писали:

sch>Для таких задач лучще всего подойдут k-D деревья -- гарантированное логарифмическое время поиска.


А поподробнее?
... << Scorpions — Holiday>>
Не восхрапи на работе, ибо храпом своим разбудишь начальника своего.
Re[4]: [MSSQL] Как будет быстрее?
От: _spin_ Россия  
Дата: 26.01.06 15:11
Оценка:
Здравствуйте, Antipov, Вы писали:

A>Попробуй у меня на более слабом сервере скорость на порядок больше приведённой выше в топике.


Попробую, может ты и прав, но я сильно сомневаюсь.

A>Тип коэффициента это и есть его номер в данном случае. Количество записей в таблице никого не должно смущать т.к. СКОРОСТЬ ВЫБОРКИ ЗАВИСИТ НЕ ОТ КОЛИЧЕСТВА ЗАПИСЕЙ А ОТ СЕЛЕКТИВНОСТИ И ИНДЕКСИРОВАННОСТИ,

Где это написано? Из своего опыта могу сказать, что эту фразу лучше переделать так:

СКОРОСТЬ ВЫБОРКИ в болшей мере зависит ОТ СЕЛЕКТИВНОСТИ И ИНДЕКСИРОВАННОСТИ, а не ОТ КОЛИЧЕСТВА ЗАПИСЕЙ

Теоретически первая фраза верна, а вот на практике когда размер базы переваливает 500 Гб, а суммарное количество записей — 1 млрд, начинаются задержки выборки на уровне железа, т.к. резко возрастает количество seek'ов raid'а, выполняемое при отработке 1 запроса.

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

Возможно. Но реализовать мой критерий отбора на модифицированной таблице я не представляю как.
... << Scorpions — Holiday>>
Не восхрапи на работе, ибо храпом своим разбудишь начальника своего.
Re[3]: [MSSQL] Как будет быстрее?
От: sch  
Дата: 26.01.06 15:29
Оценка:
http://en.wikipedia.org/wiki/Kd_tree

Hint: надо работать с N параметрами сообщения как с точкой в N-мерном пространстве с координатами (x1, x2 ... xN).

P.S. Здесь вполне можно применить и упрощенные варианты k-D деревьев, такие как quadtree и octree, если конечно распределение значений параметров более-менее линейное.
Re[4]: [MSSQL] Как будет быстрее?
От: Sinclair Россия https://github.com/evilguest/
Дата: 27.01.06 05:54
Оценка:
Здравствуйте, sch, Вы писали:

sch>P.S. Здесь вполне можно применить и упрощенные варианты k-D деревьев, такие как quadtree и octree, если конечно распределение значений параметров более-менее линейное.

Ты не мог бы поподробнее об этом рассказать? Я плохо представляю, как можно применить k-D деревья для пространств, где близко расположенными точками считаются те, которые совпадают по K координатам из N, независимо от расстояния по остальным N-K координатам.
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[5]: [MSSQL] Как будет быстрее?
От: sch  
Дата: 27.01.06 08:54
Оценка:
S>Ты не мог бы поподробнее об этом рассказать? Я плохо представляю, как можно применить k-D деревья для пространств, где близко расположенными точками считаются те, которые совпадают по K координатам из N, независимо от расстояния по остальным N-K координатам.

Вместо одного поиска по N координатам делаем N поисков по одной координате.
Re[6]: [MSSQL] Как будет быстрее?
От: Sinclair Россия https://github.com/evilguest/
Дата: 27.01.06 10:06
Оценка:
Здравствуйте, sch, Вы писали:


S>>Ты не мог бы поподробнее об этом рассказать? Я плохо представляю, как можно применить k-D деревья для пространств, где близко расположенными точками считаются те, которые совпадают по K координатам из N, независимо от расстояния по остальным N-K координатам.


sch>Вместо одного поиска по N координатам делаем N поисков по одной координате.

А-а. С этим эффективнее справится совершенно обычный линейный индекс: заводим N индексов по каждой координате, строим union из N запросов и вуаля...
Кстати, это почти что то же самое, что и развертка в нормализованную таблицу коэффициентов — только индексов много, а не один.

k-d деревья, AFAIK, помогают тогда, когда селективность поиска по одной координате низка, так что join результатов отдельных запросов дорого стоит.
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[7]: [MSSQL] Как будет быстрее?
От: sch  
Дата: 27.01.06 12:21
Оценка:
S>А-а. С этим эффективнее справится совершенно обычный линейный индекс: заводим N индексов по каждой координате, строим union из N запросов и вуаля...
Если распределение значенйи координаты абсолютно линейное, то фактически линейный индекс и k-D деревья будут очень похожими и дадут одинаковые результаты.
В обратном случае, особенно если функция распределения имеет большие скачки, k-D дерево конечно будет быстрее, но будет стоить больше памяти.
Хотя это все копейки, согласен?

S>k-d деревья, AFAIK, помогают тогда, когда селективность поиска по одной координате низка, так что join результатов отдельных запросов дорого стоит.

В пределах нашей задачи, насколько я понимл, join не нужен -- достаточно совпадения хотя бы по одной координате.
Re[8]: [MSSQL] Как будет быстрее?
От: Sinclair Россия https://github.com/evilguest/
Дата: 27.01.06 13:38
Оценка:
Здравствуйте, sch, Вы писали:

sch>Если распределение значенйи координаты абсолютно линейное, то фактически линейный индекс и k-D деревья будут очень похожими и дадут одинаковые результаты.

sch>В обратном случае, особенно если функция распределения имеет большие скачки, k-D дерево конечно будет быстрее
Это почему? Че-то я не догоняю, каким образом распределение значения повлияет на B-tree линейный индекс. Кстати, не подскажешь, что такое "линейное" распределение?
sch>Хотя это все копейки, согласен?
Дык вот именно. Хочется, чтобы объем сканирования был O(R + logN), где N — количество образцов, R — количество найденных.
S>>k-d деревья, AFAIK, помогают тогда, когда селективность поиска по одной координате низка, так что join результатов отдельных запросов дорого стоит.
sch>В пределах нашей задачи, насколько я понимл, join не нужен -- достаточно совпадения хотя бы по одной координате.
Неа, надо совпадение по K
Автор: _spin_
Дата: 25.01.06
.
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[8]: [MSSQL] Как будет быстрее?
От: _spin_ Россия  
Дата: 27.01.06 13:44
Оценка:
В общем, я так понял, что никто с подобной задачей сам не сталкивался. Очень жаль

Кто прав в споре "линейные индексы vs k-D tree" — покажет практика.

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

Если у кого возникнут ещё интересные варианты — готов рассмотреть
... << Тишина>>
Не восхрапи на работе, ибо храпом своим разбудишь начальника своего.
Re[9]: [MSSQL] Как будет быстрее?
От: sch  
Дата: 27.01.06 14:15
Оценка:
S>Это почему? Че-то я не догоняю, каким образом распределение значения повлияет на B-tree линейный индекс. Кстати, не подскажешь, что такое "линейное" распределение?
Струтура k-D дерева более адекватна исходным данным, поэтому поиск и будет быстрее. Хотя зависит от реализации.
Под "линейным" распределением я понимаю то, что вероятность попадания значения в интервал пропорциональна длине интервала (оно же равномерное распределение).

S>Дык вот именно. Хочется, чтобы объем сканирования был O(R + logN), где N — количество образцов, R — количество найденных.

Я имел в виду совершенно не то, что разница между O(n) и O(log(n)) -- копейки, а то, что и k-D дерево и линейный индекс дадут O(log(n)), но дерево побыстрее будет.

sch>>В пределах нашей задачи, насколько я понимл, join не нужен -- достаточно совпадения хотя бы по одной координате.

S>Неа, надо совпадение по K
Автор: _spin_
Дата: 25.01.06
.

Ну вместо одного поиска делаем от K до N поисков, пока количество найденных результатов не станет равно K. Какая разница? O(C*f(x)) = O(f(x)), где C=const. Время все равно логарифмическое будет, хоть 1000 элементов, хоть 1000*1000.

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

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

Пусть у нас характеристический вектор 256-мерный. Тогда весь вектор займет килобайт. Если сообщений 30,000 -- памяти надо будет всего 30 мегабайт.
Опять же, можно развивать эту идею как угодно. Можно распаралелить поиск, можно хранить не все дерево в памяти.
Re[10]: [MSSQL] Как будет быстрее?
От: Sinclair Россия https://github.com/evilguest/
Дата: 30.01.06 03:54
Оценка:
Здравствуйте, sch, Вы писали:

S>>Это почему? Че-то я не догоняю, каким образом распределение значения повлияет на B-tree линейный индекс. Кстати, не подскажешь, что такое "линейное" распределение?

sch>Струтура k-D дерева более адекватна исходным данным, поэтому поиск и будет быстрее.
Вот этого места я и не понимаю. B-tree уже сбалансировано независимо от распределения значений ключей. За счет чего должно получиться улучшение?
К тому же, kd-деревья совершенно четко специализированы для многомерных данных. А ты предлагаешь использовать их для линейного индекса. Ты не мог бы пролить чуть больше света?
sch>Я имел в виду совершенно не то, что разница между O(n) и O(log(n)) -- копейки, а то, что и k-D дерево и линейный индекс дадут O(log(n)), но дерево побыстрее будет.
За счет чего?
sch>>>В пределах нашей задачи, насколько я понимл, join не нужен -- достаточно совпадения хотя бы по одной координате.
S>>Неа, надо совпадение по K
Автор: _spin_
Дата: 25.01.06
.

sch>Ну вместо одного поиска делаем от K до N поисков, пока количество найденных результатов не станет равно K. Какая разница? O(C*f(x)) = O(f(x)), где C=const. Время все равно логарифмическое будет, хоть 1000 элементов, хоть 1000*1000.
По-моему, ты что-то путаешь. Никаким log(N) здесь и не пахнет. Каким алгоритмом ты собрался считать пересечение списков полученных на шагах 1-K?
sch>Грубо говоря, мы с тобой говорим об одной и той же структуре, за тем исключением что ты предпологаешь считать критерием построения дерева его сбалансированность, а я предлагаю считать критерием построения дерева распределение ключей. Что, опять же, в конечном итоге -- одно и то же.
Я теряю ход твоей мысли.
sch>С другой стороны, я настаиваю на том, что не стоит полагаться в такой большой по объему данных задаче на БД, а стоит держать дерево целиком в памяти и искать самостоятельно, что даст огромный выигрыш по производительности.
Все зависит от очень многих параметров. В частности, совершенно не факт, что все влезет в память. А смоае милое — это объем отладки. Как только ты включишь многопотоковость, тебя ждут многочисленные грабли. Вот ты, к примеру, сможешь навскидку вспомнить корректный алгоритм раздачи блокировок в дереве? Хоть в B, хоть в KD?
sch>Пусть у нас характеристический вектор 256-мерный. Тогда весь вектор займет килобайт. Если сообщений 30,000 -- памяти надо будет всего 30 мегабайт.
К сожалению, речь идет о том, чтобы хранить порядка 500000 этих векторов. Это уже полгига чистых данных, а ведь нужны еще служебные структуры. Уже есть необходимость реализовывать кэширование и своп части данных на диск.
sch>Опять же, можно развивать эту идею как угодно. Можно распаралелить поиск, можно хранить не все дерево в памяти.
Есть у меня подозрение, что при развитии ты придешь к самописаной RDBMS. Потому, что надо не только читать, но и модифицировать дерево, и flush-ить его на диск, а тут возникает вопрос об ACIDности...
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.