Thread: Re: [pgsql-ru-general] индексирование по расстоянию
2014-05-09 13:42 GMT-07:00 Dmitry E. Oboukhov <unera@debian.org>: > Сейчас залез копаться в GIST-индексы и расширения на C, но возник > вопрос, может быть уже что-то готовое есть на тему решения подобных > задач? > то есть если у нас есть функция возвращающая дистанцию между двумя > объектами, то может быть можно просто (без C-программирования) > построить индекс отвечающий на > вопрос "дай мне ближайшие объекты к заданному"? Есть кое-какие наработки в этом направлении: http://www.postgresql.org/message-id/flat/9E07E159-E405-41E2-9889-A04F534FC257@gmail.com# А какая предметная область, если не секрет, что за данные и для чего дистанция? Возможно есть проще решение. -- Kind regards, Sergey Konoplev PostgreSQL Consultant and DBA http://www.linkedin.com/in/grayhemp +1 (415) 867-9984, +7 (499) 346-7196, +7 (988) 888-1979 gray.ru@gmail.com
>> Сейчас залез копаться в GIST-индексы и расширения на C, но возник >> вопрос, может быть уже что-то готовое есть на тему решения подобных >> задач? >> то есть если у нас есть функция возвращающая дистанцию между двумя >> объектами, то может быть можно просто (без C-программирования) >> построить индекс отвечающий на >> вопрос "дай мне ближайшие объекты к заданному"? > Есть кое-какие наработки в этом направлении: > http://www.postgresql.org/message-id/flat/9E07E159-E405-41E2-9889-A04F534FC257@gmail.com# А я чет почитал про этот kNN но не понял как совместить его с моей задачей. у меня на входе текстовые сопоставления и координатные. и итоговое сопоставление опирается на оба сопоставления сразу > А какая предметная область, если не секрет, что за данные и для чего > дистанция? Возможно есть проще решение. предметная область - объекты с текстовыми характеристиками в пространстве (на глобусе). То есть объект имеет: - название - текстовое описание - lon - lat Пользователь отчасти помнит название (или текстовое описание) объекта и начинает его вводить в поисковом поле. Мы хотим налету подсказывать ему объекты в виде автокомплит-списка. сперва сделали чисто подсказки по тексту - получилось довольно неплохо, но автокомплит комплитит и сильно далекие точки от юзера. далее попробовали совмещать комплит с географией. но получается если сперва текстовый индекс поюзать, а потом сортировать по удаленности, то получаются большие накладные расходы, если например юзер вводит популярное название объекта. далее если наоборот - сперва выбирать ближайшие объекты в заданном радиусе, а потом отфильтровывать их по текстовой похожести, то получаются большие накладные расходы если юзер ищет объект в скоплении других объектов (например улицу в Москве). ну и вот далее хочется совместить оба критерия в один индекс: и текстовую близость и близость по расстоянию причем текстовую близость мы считаем по своим критериям. -- . ''`. Dmitry E. Oboukhov : :’ : email: unera@debian.org jabber://UNera@uvw.ru `. `~’ GPGKey: 1024D / F8E26537 2006-11-21 `- 1B23 D4F8 8EC0 D902 0555 E438 AB8C 00CF F8E2 6537
Attachment
2014-05-09 14:34 GMT-07:00 Dmitry E. Oboukhov <unera@debian.org>: >>> то есть если у нас есть функция возвращающая дистанцию между двумя >>> объектами, то может быть можно просто (без C-программирования) >>> построить индекс отвечающий на >>> вопрос "дай мне ближайшие объекты к заданному"? > >> Есть кое-какие наработки в этом направлении: > >> http://www.postgresql.org/message-id/flat/9E07E159-E405-41E2-9889-A04F534FC257@gmail.com# > > А я чет почитал про этот kNN но не понял как совместить его с моей > задачей. у меня на входе текстовые сопоставления и координатные. > и итоговое сопоставление опирается на оба сопоставления сразу Да, я не заметил в постановке задачи текст упоминается. >> А какая предметная область, если не секрет, что за данные и для чего >> дистанция? Возможно есть проще решение. > > предметная область - объекты с текстовыми характеристиками в > пространстве (на глобусе). > > То есть объект имеет: > - название > - текстовое описание > - lon > - lat [...] > ну и вот далее хочется > совместить оба критерия в один индекс: и текстовую близость и близость > по расстоянию > > причем текстовую близость мы считаем по своим критериям. Каким образом? -- Kind regards, Sergey Konoplev PostgreSQL Consultant and DBA http://www.linkedin.com/in/grayhemp +1 (415) 867-9984, +7 (499) 346-7196, +7 (988) 888-1979 gray.ru@gmail.com
>>>> то есть если у нас есть функция возвращающая дистанцию между двумя >>>> объектами, то может быть можно просто (без C-программирования) >>>> построить индекс отвечающий на >>>> вопрос "дай мне ближайшие объекты к заданному"? >> >>> Есть кое-какие наработки в этом направлении: >> >>> http://www.postgresql.org/message-id/flat/9E07E159-E405-41E2-9889-A04F534FC257@gmail.com# >> >> А я чет почитал про этот kNN но не понял как совместить его с моей >> задачей. у меня на входе текстовые сопоставления и координатные. >> и итоговое сопоставление опирается на оба сопоставления сразу > Да, я не заметил в постановке задачи текст упоминается. в постановке задачи - просто обобщенный вес вычисляется >>> А какая предметная область, если не секрет, что за данные и для чего >>> дистанция? Возможно есть проще решение. >> >> предметная область - объекты с текстовыми характеристиками в >> пространстве (на глобусе). >> >> То есть объект имеет: >> - название >> - текстовое описание >> - lon >> - lat > [...] >> ну и вот далее хочется >> совместить оба критерия в один индекс: и текстовую близость и близость >> по расстоянию >> >> причем текстовую близость мы считаем по своим критериям. > Каким образом? по сути расстояние Левенштейна но с тем отличием что веса операций считаются нелинейно: в зависимости от категории + положения в слове (ближе к началу или концу) + положения слова в тексте -- . ''`. Dmitry E. Oboukhov : :’ : email: unera@debian.org jabber://UNera@uvw.ru `. `~’ GPGKey: 1024D / F8E26537 2006-11-21 `- 1B23 D4F8 8EC0 D902 0555 E438 AB8C 00CF F8E2 6537
Attachment
2014-05-09 22:37 GMT-07:00 Dmitry E. Oboukhov <unera@debian.org>: >>> причем текстовую близость мы считаем по своим критериям. > >> Каким образом? > > по сути расстояние Левенштейна но с тем отличием что веса операций > считаются нелинейно: в зависимости от категории + положения в слове > (ближе к началу или концу) + положения слова в тексте Хм, интересно, а как вы это индексируете? -- Kind regards, Sergey Konoplev PostgreSQL Consultant and DBA http://www.linkedin.com/in/grayhemp +1 (415) 867-9984, +7 (499) 346-7196, +7 (988) 888-1979 gray.ru@gmail.com
надо писать функцию расстояния на Си, высоким уровнем НЕ обойтись, там сигнатура с internal.
пример можно посмотреть, например, в контрибе earthdistance, ну и где найдете function 8 для гиста реализованную. но там много кодить везде, хотя может вам и не трудно будет.
у меня в 92 это есть в OPERATOR CLASS point_ops DEFAULT FOR TYPE point USING gist
FUNCTION 8 gist_point_distance(internal, point, integer, oid)
и
OPERATOR CLASS gist_int8_ops DEFAULT FOR TYPE int8 USING gist AS
FUNCTION 8 gbt_int8_distance(internal, bigint, smallint, oid),
последнее - контриб btree_gist
Михаил
DBA