|
|
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
sysprgЕсли бы по 5 атрибутам, но ПРОИЗВОЛЬНО выбранным (из тысячи доступных), база искала бы быстро - остальное было бы делом техники...Строим инвертированные индексы на нормализованных значениях аттрибутов и ориентировочно получаем O(A * R * lnN) где А - число аттрибутов R - колличество найденных записей N - всего записей. В особо неудавшихся случаях будем иметь O(A * N) что есть полный перебор и что статистически будет маловероятно. При поиске по 5 аттрибутам и сотне миллионам N вполне разумная сложность. Требуемые показатели придется выжимать распараллеливанием. Так что нанимайте кодеров и педалить, педалить, педалить... Если оно того стоит - придется несколько потратится на разработчиков ;) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2006, 14:51 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
PS ващето это стандартная задача полнотекстового поиска по обязательному вхождениию нескольких слов в текст. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2006, 14:56 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
pavelvp sysprgВ одном случае у нас есть битовая маска содержащая 10 тысяч единиц, в другом случае - 10 миллионов (при общей длине несжатой маски в 100 миллионов битов). Первую битовую маску хорошая СУБД эффективно сожмет. Вторую тоже может немножко поджать, но накладные расходы на компрессию велики и она не станет с ней заморачиваться. Битовые индексы очень хорошо сжимаются - в десятки раз - простыми алгоритмами. Да вы о чём говорите?! По его же расчетам выходит несчастных 11 мегабайт, и он их собрался по кластеру "размазывать". А вы их сжимать. Дурдом какой-то. Всё, ухожу в монастырь. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2006, 20:01 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
Я про макеты спросил только потому, что топик уже разросся нереально, а если б выложили хоть какой-то пример, проще к чему-то прийти. Выложите материал, по которому можно будет судить о задуманной системе, иначе задача, которую Вы сформулировали, слишком широка. По крайней мере, мне не совсем понятно, что Вы хотите сделать. Если есть продуманная схема, то хотелось бы взглянуть на неё. К примеру, информацию о каких именно сущностях собираетесь хранить? Я знаю о поисковой системе в не то чтобы узкой, но всё ж таки ограниченной технической области. В ней 15 тысяч различных атрибутов, причём одно изделие характеризуется в среднем с помощью 40 (из них 5 встречаются относительно часто). Согласен, что обычно технических параметров больше каких-либо других, но всё ж таки Ваши прикидки числа атрибутов можно смело увеличить на пару порядков до 100 тысяч, судя по тому что я прочитал. В поисковой системе, которую я привёл в пример, есть по крайней мере 600 единиц измерения и пользователям нужно переводить миллиметры в метры и т.п. Опять же, судя по размаху, в Вашей системе их будет больше, даже если не брать особенности отдельных стран вроде языков, денежных единиц и систем мер. И у Вас появится неслабая система классификации всего этого добра. Сделайте пробный работающий вариант, не исключено, что найдёте кучу мест, которые нельзя было предусмотреть в теории. ИМХО, если бы я делал что-то подобное, то начал именно с малой системы, на которой можно будет обкатать идею и тогда она уже может быть превратиться в проект. Хотя, как говорится, хозяин - барин. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2006, 20:17 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
Anton DemidovПо его же расчетам выходит несчастных 11 мегабайт, и он их собрался по кластеру "размазывать". А вы их сжимать. Дурдом какой-то. Всё, ухожу в монастырь.В монастыре между размышлениями о вечном поищите (для саморазвития) ответы на следующие два вопроса: - Сколько раз в секунду можно прокачать через память 11 мегабайтов данных на серийном компьютере, который стоит вменяемых денег? (Hint: это будет Ваш лимит на число запросов в секунду без кластера). - До какого минимального объема можно сжать битовый индекс, содержащий 2 миллиона единиц в случайных позициях с помощью "идеального" алгоритма? (Hints: белый шум, количество информации). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2006, 20:50 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
Ваша лень, sysprg, наводит на грустные размышления. Может это, все-таки, курсовик, "зависший" с прошлого семестра ? Написал за Вас пару строк кода. Индексирование записи при n(количество заполненных атрибутов в записи из 1000 атрибутов)=6,7,8,9 (напомню, в индекс помещается n! сочетаний, то есть все сочетания) делается мгновенно. Индексирование записи, в которой заполнены все 1000 атрибутов (в индекс помещаются все сочетания пар атрибутов) делается так же мгновенно. Область индекса разбивается на подобласти. В первой содержатся индексы по всем записям, в которых значения имеют от 1 до 9 атрибутов. И т.д. Если Вас, все-таки, отчислят, это будет справедливо - нельзя же базы данных только "на бумаге" строить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2006, 20:54 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
> 15 тысяч различных атрибутов ;)) Вы уверены в том, что это именно _различные атрибуты_? > 600 единиц измерения ;)) Не смущает, что в SI их меньше сотни? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2006, 23:16 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
guest_20040621> 600 единиц измерения ;)) Не смущает, что в SI их меньше сотни?Возможно под единицами измерения в том числе подразумевались цвет, вкус, запах, ворсистость и прочая в том же духе. Как бы шкала существует, хотя и не всегда имеющая порядок, измерения - тоже. С некоторой натяжкой можно принять за единицу измерения. То же самое и с атрибутами. Каждый товар может иметь свои особенности, тот же цвет в одном товаре может фиксироваться для трех позиций, а в другом - для десяти. Причем позиции для разных товаров по смыслу могут напрочь не совпадать и сократить их число не представляется возможным. P.S. Допускаю, что автор на самом деле имел ввиду что-то иное. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2006, 23:40 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
> Как бы шкала существует Возьмем, например, цвет (он просто первый в списке). Ваши варианты шкал? > хотя и не всегда имеющая порядок В корень зрите. Т. е. легко можно различать стандартные единицы измерений и хм... дополнительные (которые к тому же могут существовать параллельно). > С некоторой натяжкой можно принять за единицу измерения. Imho неверная посылка. Смотря по тому, что за шкала. > по смыслу могут напрочь не совпадать Как Вы этот "смысл" собираетесь определять? ;) Есть варианты? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.09.2006, 01:35 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
guest_20040621> по смыслу могут напрочь не совпадать Как Вы этот "смысл" собираетесь определять? ;) Есть варианты?Вообще, это наверное лучше к sysprg. Возьмем с потолка: белый верх, черный низ для одного из товаров, для другого - белый перед, черный зад, бежевый корпус. Как бы атрибуты есть, и для конкретного товара их вряд ли много, но если их посчитать для всего спектра товаров, то их много и они абсолютно не пересекаются. Отсюда выплывает полный список из "15 тысяч атрибутов". Повторюсь, это всего лишь попытка понять, что имеет в виду sysprg. IMHO, он просто свалил все в кучу, не заботясь о деталях. guest_20040621> С некоторой натяжкой можно принять за единицу измерения. Imho неверная посылка. Смотря по тому, что за шкала.Боюсь, это тоже к sysprg, я всего лишь пытался понять, что он имеет в виду. Полагаю, что подразумевалось нечто в духе этого . ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.09.2006, 02:24 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
> лучше к sysprg Человек себе все уже построил. И на мой взгляд это "все" - полное дерьмо. Так что ничего нового sysprg мне не скажет. Даже если сильно захочет. На самом деле вы думаете в правильном направлении: атрибуты будут иметь смысл только и исключительно в сочетании с семантической схемой. > Возьмем с потолка Зачем? ;) Вернемся к тому, с чего начали. Единиц измерения, конечно, будет не сильно больше стандартных. Подавляющее большинство дополнительных шкал будут представлять собой потребительские или технологические шкалы. Фишка только и исключительно в их структуре. > свалил все в кучу Так и есть. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.09.2006, 03:35 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
guest_20040621;)) Вы уверены в том, что это именно _различные атрибуты_? guest_20040621;)) Не смущает, что в SI их меньше сотни? ChA по большей части объяснил насчёт характеристик (только система в технической области). С единицами измерения почти тоже, только они ещё ввели собственные показатели и собственные же единицы измерения - по большей части отношение одной величины к другой (условно, Ватты на метры - вместо цвета, запаха и т.п.). Это-то, по-моему, элементарно понятно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.09.2006, 18:43 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
Кстати, sysprg этого Как бы атрибуты есть, и для конкретного товара их вряд ли много, но если их посчитать для всего спектра товаров, то их много и они абсолютно не пересекаются. Отсюда выплывает полный список из "15 тысяч атрибутов". Повторюсь, это всего лишь попытка понять, что имеет в виду sysprg. не говорил. Во-первых, это сказал я и указал на то, что атрибутов у него будет больше. Во-вторых ни слова не было о том, как эти атрибуты будут представлены. Я указал на масштаб и возможный подводный камень при построении системы классификации атрибутов и единиц измерения, если она вообще задумывалась, конечно. А уж для международной мегапоисковой системы-то :) К примеру, guest_20040621 В корень зрите. Т. е. легко можно различать стандартные единицы измерений и хм... дополнительные (которые к тому же могут существовать параллельно). Люди, давайте о конкретике, а то только уведёте от темы. Говорите о семантике и тут же предалагаете такое "лобовое" решение - основные и дополнительные. И что с того, что одни основные, а другие дополнительные? Проще от этого никому не будет. Или Вы имеете ввиду, что их можно отличить одни от других? Это да, трудно не заметить ;)) А вот система поможет реально, поскольку это добро УЖЕ работает. Подводя черту вышесказанному, опять же говорю о том, что нужно обдумать систему классификации, что-то реализовать, а потом уже смотреть на производительность. Если она вообще будет узким местом. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.09.2006, 19:11 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
> Это-то, по-моему, элементарно понятно. Дружище, лично мне абсолютно очевидно, что то, что Вы описали, единицами измерения не является. И еще мне абсолютно очевидна абсурдность существования 15 тысяч различных независимых атрибутов. Типичный пример корявого проектирования. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.09.2006, 19:17 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
guest_20040621Типичный пример корявого проектирования.А корявое оно от того что РБД такого делать не умеют? ;) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.09.2006, 20:50 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
> А корявое оно от того что РБД такого делать не умеют? ;) Дима, Вам учиться нужно, а не ахинею в форумах писать. Криворукость кодеров никак не характеризует возможности СУБД. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.09.2006, 22:21 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
guest_20040621Дружище, лично мне абсолютно очевидно, что то, что Вы описали, единицами измерения не является. И еще мне абсолютно очевидна абсурдность существования 15 тысяч различных независимых атрибутов. Типичный пример корявого проектирования. О майн готт! Родной Вы мой человече, неужели хотя бы в паре постов нельзя обойтись без своего "фи"? Прям как пенсионер, который сидит на лавке и ругает всех подряд Ну что с того что Вам она очевидна? Делали систему классификации специалисты в своей предметной области, отнюдь не программеры. Отмечу, поскольку Вы плохо читаете, систему классификации атрибутов и единиц измерения, а не поисковую систему. И им нужна именно эта система, а не та, которую предложит проектировщик, даже не въехавший в суть вопроса. Если люди занимаются подобными вопросами уже много лет, сделали кучу наработок, то что, придёт программер и скажет - это плохо, потому что много? И при этом он даже НЕ ВИДЕЛ самой системы в работе? P.S. Атрибуты не независимые, а различные. Зависимость-то есть, иначе б не было системы классификации атрибутов и единиц измерения. P.P.S. Эх, выделяете цитированием фразы и придираетесь. Может уже пора наконец-то съездить в отпуск? Когда были в последний раз-то? Пару лет назад? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.09.2006, 07:27 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
shuklinPS ващето это стандартная задача полнотекстового поиска по обязательному вхождениию нескольких слов в текст.Многие задачи похожи в чем-то, но имеют и свои существенные особенности. При "классическом" поиске слова нас интересует только точное совпадение или несовпадение, а тут может быть запрос по диапазону значений. Плюс статистику для частоты встречаемости слов можно считать неизменной в первом приближении. Правда, нечеткий поиск (например, в пределах какой-то edit distance) уже похож на мою задачу, согласен. Это, кстати, тоже проблема - судя по публикациям. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.09.2006, 14:38 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
sysprgа тут может быть запрос по диапазону значений. В таком случае ориентировочные оценки сложности в моих предыдущих сообщениях следует считать неприменимыми. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.09.2006, 16:18 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
> неужели хотя бы в паре постов нельзя обойтись без своего "фи"? Нельзя, дружище. Объясню, почему: все это дерьмо читают в том числе люди с никакой подготовкой; важно, чтобы у них складывалось правильное представление о существующем положении вещей. "Работает" - никак не связано с тем, что "работает правильно". Видите ли, в чем дело: плохая структура данных - гарантия плохого качества приложения в целом. Независимо от качества не-ddl кода. И мне бы сильно хотелось, чтобы студент (пофиг, курсовую он пишет или пытается денег заработать) не читал статейки Тенцера или Celco, не участвовал в тупых обсуждениях о применении суррогатных ключей или именовании объектов на родном языке, а работал с первоисточниками и думал головой. > что с того что Вам она очевидна? Приведенный пример - хм... крайне низкого качества и в лучшем случае может служить иллюстрацией того, как не нужно делать. А отнюдь не примером для подражания. > систему классификации атрибутов и единиц измерения При чем здесь классификация? > им нужна именно эта система Я за них рад Вы себе не представляете как. Знаете, дружище, читая такие обсуждения я, с одной стороны, понимаю, что отсутствие работы в ближайшие десять лет мне не грозит, а с другой - поверьте, действительно хочется обсуждать реально интересные проблемы, а не бред сивой кобылы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.09.2006, 16:32 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
2 guest_20040621. Уже веселее читать, а то, ей-богу, я воспринимал это как брюзжание :)) Может у Вас мало времени, но хотелось бы чтобы конструктив не тонул в море критики :)) guest_20040621Приведенный пример - хм... крайне низкого качества и в лучшем случае может служить иллюстрацией того, как не нужно делать. А отнюдь не примером для подражания. Да я и не даю пример, хотя, пожалуй, могло так и показаться. Я хотел очертить масштаб и самое слабое место в системе. Мне показалось, что автор топика не рассматривал атрибуты с точки зрения их смысла и близости и привязку к единицам измерения и особенностям стран. Поэтому не стоило бы бежать впереди паровоза и заниматься проблемами производительности вот так с налёта. Что касается приведённой в пример системы - а что делать? Система уже была спроектирована, данные под неё были, а пользователи считали, что так и должно быть. Может что посоветуете: как идти против всех остальных, которые считают себя специалистами-предметниками? Без классификации эта куча атрибутов была бы просто нереализуема. Наверное, тогда это было меньшим из зол. Сейчас-то видно, что нужно изменить, а тогда вряд-ли. Если у Вас большой опыт, то да, конечно, Вы бы, вероятно, предусмотрели множество вещей. Но если сроки установлены жёстко, на перепроектирование времени нет и нужно уложиться в заданные рамки, то можно, конечно, пойти ва-банк, но для этого нужно иметь очень большой авторитет и "вес". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.09.2006, 19:20 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
guest_20040621Видите ли, в чем дело: плохая структура данных - гарантия плохого качества приложения в целом. Интересно, в чем вы оцениваете плохость и хорошесть структуры данных? И на основании чего вешаете на одну структуру ярлык плохой, а на другую - хорошей? Вот оставаясь в теме топика, чем плоха структура данных, предполагающая увеличение числа колонок некоторой таблицы до мллиона? И чем это координально хуже увеличения числа строк в той же таблице? Только тем что существующие промышленные СУБД не расчитаны на такой сценарий? Тогда, извините, модель данных бизнес процесса в полном порядке. Это не у бизнес логики проблемы а у текущей реализации СУБД. То что грамотному разработчику для какой то конкретной СУБД придется извращаться, чтоб реализовать этот нестандартный сценарий учитывая текущие ограничения этой конкретной СУБД к теме данного топика имеет весьма отдаленное отношение. Всеже окажите любезность и озвучте чем плоха структура данных предполагающая миллион колонок в таблице ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.09.2006, 19:40 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
> самое слабое место в системе Если честно, я не очень понимаю, почему. Может, Вы расскажете, какие задачи должно решать описанное Вами приложение? > против всех остальных, которые считают себя специалистами-предметниками? А зачем? Каждый должен заниматься своим делом: специалист предметной области - формулировать то, что он хочет видеть, разработчик - проектировать. Никак не вместе и не наоборот. > Без классификации эта куча атрибутов была бы просто нереализуема При чем здесь опять классификация? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.09.2006, 20:54 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
> в чем вы оцениваете плохость и хорошесть структуры данных? Ни в чем не оцениваю. Нет таких единиц. Либо структура данных приемлема для конкретной задачи, либо нет. > И на основании чего вешаете на одну структуру ярлык плохой, а на другую - хорошей? На основании формального описания задачи, разумеется. Никто ничего другого пока не придумал. С телепатическими способностями у меня - никак, к сожалению. > чем плоха структура данных, предполагающая увеличение числа колонок некоторой таблицы до мллиона? В принципе нет ни одного повода считать это решением вообще. Ни с точки зрения проектирования, ни с точки зрения здравого смысла. > существующие промышленные СУБД не расчитаны на такой сценарий? Это неправильно заданный вопрос. Не "СУБД не расчитаны", а СУБД предполагают наличие хотя бы минимальных знаний у того, кто занимается проектированием. Вы готовы привести пример сущности с миллионом независимых имеющих смысл атрибутов, которые можно регистрировать? > озвучте чем плоха структура данных предполагающая миллион колонок в таблице Дружище, Ваш вопрос не имеет смысла. Это не структура данных. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.09.2006, 20:54 |
|
||
|
Многокритериальный поиск в очень-очень большой базе
|
|||
|---|---|---|---|
|
#18+
guest_20040621> чем плоха структура данных, предполагающая увеличение числа колонок некоторой таблицы до мллиона? В принципе нет ни одного повода считать это решением вообще. Ни с точки зрения проектирования, ни с точки зрения здравого смысла. Однако до сих пор от вас я не услышал и ни одного довода для того чтобы не считать это решением, кроме guest_20040621Вы готовы привести пример сущности с миллионом независимых имеющих смысл атрибутов, которые можно регистрировать? А кто вам сказал, что в одном списке(таблице) обязательно хранить только одинаковые сущности? Опять же только текущие ограничения текущих реализаций и стереотипное мышление ;) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.09.2006, 21:06 |
|
||
|
|

start [/forum/topic.php?fid=32&msg=33966671&tid=1545033]: |
0ms |
get settings: |
9ms |
get forum list: |
15ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
162ms |
get topic data: |
10ms |
get forum data: |
3ms |
get page messages: |
70ms |
get tp. blocked users: |
1ms |
| others: | 205ms |
| total: | 481ms |

| 0 / 0 |
