Здравствуйте. Не могли бы вы подсказать алгоритм, который бы позволил решить следующую задачу:
Имеется список(множество) объектов-записей с различными полями, который находится на диске в виде одного или нескольких очень больших файлов. Каждое поле записи является ключем. Необходимо организовать поиск так, чтобы в результате получить подмножество, содержащее записи, у которых первое поле попадает в свой заданный интервал значений, второе — в свой и т.д. Причем, необходим такой алгоритм, чтобы при одном обращении либо находилась следующая из записей по определенному порядку(допустим, по алфавиту в нескольких полях, если это текст), либо сообщалось, что больше подходящих записей нет. Решение, которое использует сначала поиски по каждому из полей, а потом сравнение результатов поисков с целью нахождения пересечения этих множеств, не годится, т.к. эти множества предполагаются большими, и в оперативную память не помещающимися.

пример приведи

Здравствуйте, trump-card, Вы писали:

Решение: Загрузить данные в реляционную СУБД, создать необходимые индексы, запросы формировать на языке SQL.

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

R_X>пример приведи

Пример — простейший: запись cостоит из двух полей. Вот сама таблица — 2.1; 3.2; 4.5; 3.13; 8.12; 1.2; 3.6; 3.3; 8.1; 5.6; 11.25; 15.11; 12.13; 9.10
Теперь нужно найти такие записи, которые в первом поле содержат числа из интервала 4-10, а во втором — из интервала 11-15.
Находим записи удовлетворяющие первому условию (это быстрая операция): 4.5; 8.1; 5.6; 9.10;8.12
Второму условию: 15.11;12.13;3.13;8.12 Видно, что ответ это 8.12, но для того, чтобы его получить программно нужен двойной цикл; можно ,конечно, упростить до одного цикла, но это все равно перебор, а значит время! Как решить такую задачу, избежав перебора? Может какой-нибудь дополнительный индекс нужен или особая организация самой таблицы? Ответы типа — Загнать в стандартную базу, составить SQL и курить бамбук — не подходят . Мне нужен алгоритм, идея как сократить время такого поиска!

Здравствуйте, trump-card, Вы писали:

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

R_X>>пример приведи

TC>Пример — простейший: запись cостоит из двух полей. Вот сама таблица — 2.1; 3.2; 4.5; 3.13; 8.12; 1.2; 3.6; 3.3; 8.1; 5.6; 11.25; 15.11; 12.13; 9.10
TC>Теперь нужно найти такие записи, которые в первом поле содержат числа из интервала 4-10, а во втором — из интервала 11-15.
TC>Находим записи удовлетворяющие первому условию (это быстрая операция): 4.5; 8.1; 5.6; 9.10;8.12
TC>Второму условию: 15.11;12.13;3.13;8.12 Видно, что ответ это 8.12, но для того, чтобы его получить программно нужен двойной цикл; можно ,конечно, упростить до одного цикла, но это все равно перебор, а значит время! Как решить такую задачу, избежав перебора? Может какой-нибудь дополнительный индекс нужен или особая организация самой таблицы? Ответы типа — Загнать в стандартную базу, составить SQL и курить бамбук — не подходят . Мне нужен алгоритм, идея как сократить время такого поиска!

Если отсортировать записи по первому полю, а записи с одинаковым значением первого поля по второму, то поиск будет только один. Если не происходит удаления/добавления записей, то выполняется просто двоичный поиск в упорядоченной последовательности. Если надо поддерживать операции удаления/добавления, тогда необходимо построить поисковое дерево, b-tree, например, подходит для таких целей.

Здравствуйте, trump-card, Вы писали:

TC>Здравствуйте. Не могли бы вы подсказать алгоритм, который бы позволил решить следующую задачу:
TC>Имеется список(множество) объектов-записей с различными полями, который находится на диске в виде одного или нескольких очень больших файлов. Каждое поле записи является ключем. Необходимо организовать поиск так, чтобы в результате получить подмножество, содержащее записи, у которых первое поле попадает в свой заданный интервал значений, второе — в свой и т.д. Причем, необходим такой алгоритм, чтобы при одном обращении либо находилась следующая из записей по определенному порядку(допустим, по алфавиту в нескольких полях, если это текст), либо сообщалось, что больше подходящих записей нет. Решение, которое использует сначала поиски по каждому из полей, а потом сравнение результатов поисков с целью нахождения пересечения этих множеств, не годится, т.к. эти множества предполагаются большими, и в оперативную память не помещающимися.

Можно использовать kd-tree, адаптировав его для эффективной работы с файлами.

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

_DA>Здравствуйте, trump-card, Вы писали:

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

R_X>>>пример приведи

TC>>Пример — простейший: запись cостоит из двух полей. Вот сама таблица — 2.1; 3.2; 4.5; 3.13; 8.12; 1.2; 3.6; 3.3; 8.1; 5.6; 11.25; 15.11; 12.13; 9.10
TC>>Теперь нужно найти такие записи, которые в первом поле содержат числа из интервала 4-10, а во втором — из интервала 11-15.
TC>>Находим записи удовлетворяющие первому условию (это быстрая операция): 4.5; 8.1; 5.6; 9.10;8.12
TC>>Второму условию: 15.11;12.13;3.13;8.12 Видно, что ответ это 8.12, но для того, чтобы его получить программно нужен двойной цикл; можно ,конечно, упростить до одного цикла, но это все равно перебор, а значит время! Как решить такую задачу, избежав перебора? Может какой-нибудь дополнительный индекс нужен или особая организация самой таблицы? Ответы типа — Загнать в стандартную базу, составить SQL и курить бамбук — не подходят . Мне нужен алгоритм, идея как сократить время такого поиска!

_DA>Если отсортировать записи по первому полю, а записи с одинаковым значением первого поля по второму, то поиск будет только один. Если не происходит удаления/добавления записей, то выполняется просто двоичный поиск в упорядоченной последовательности. Если надо поддерживать операции удаления/добавления, тогда необходимо построить поисковое дерево, b-tree, например, подходит для таких целей.
Я попробовал — вот отсортированная таблица: 1.2; 3.2; 3.3; 3.6; 3.13; 4.5; 5.6; 8.1; 8.12; 9.10; 11.25;13.13;15.11. Теперь вы предлагаете искать от 4.11 до 10.15. Хорошо — вот результат: 5.6; 8.1; 8.12;9.10. Действительно 5.6 больше 4.11, а 9.10 меньше 10.15 .Но верный ответ все-таки только 8.12!Но ответ этот неверный. Так что не могу с этим алгоритмом согласиться.

Здравствуйте, trump-card, Вы писали:

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

_DA>>Здравствуйте, trump-card, Вы писали:


_DA>>Если отсортировать записи по первому полю, а записи с одинаковым значением первого поля по второму, то поиск будет только один. Если не происходит удаления/добавления записей, то выполняется просто двоичный поиск в упорядоченной последовательности. Если надо поддерживать операции удаления/добавления, тогда необходимо построить поисковое дерево, b-tree, например, подходит для таких целей.
TC>Я попробовал — вот отсортированная таблица: 1.2; 3.2; 3.3; 3.6; 3.13; 4.5; 5.6; 8.1; 8.12; 9.10; 11.25;13.13;15.11. Теперь вы предлагаете искать от 4.11 до 10.15. Хорошо — вот результат: 5.6; 8.1; 8.12;9.10. Действительно 5.6 больше 4.11, а 9.10 меньше 10.15 .Но верный ответ все-таки только 8.12!Но ответ этот неверный. Так что не могу с этим алгоритмом согласиться.

Согласен. Извиняюсь
Тут ниже уже упомянули kd-дерево. Можно попробовать применить его. В данном случае k будет 2 (вспоминается анекдот про камерный оркестр). То есть находится медиана всего множества записей по первому полю, множество разбивается пополам, затем каждое их них так же разбивается по медиане по второму полю, затем опять по первому и т.д.

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

_DA>Здравствуйте, trump-card, Вы писали:

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

_DA>>>Здравствуйте, trump-card, Вы писали:


_DA>>>Если отсортировать записи по первому полю, а записи с одинаковым значением первого поля по второму, то поиск будет только один. Если не происходит удаления/добавления записей, то выполняется просто двоичный поиск в упорядоченной последовательности. Если надо поддерживать операции удаления/добавления, тогда необходимо построить поисковое дерево, b-tree, например, подходит для таких целей.
TC>>Я попробовал — вот отсортированная таблица: 1.2; 3.2; 3.3; 3.6; 3.13; 4.5; 5.6; 8.1; 8.12; 9.10; 11.25;13.13;15.11. Теперь вы предлагаете искать от 4.11 до 10.15. Хорошо — вот результат: 5.6; 8.1; 8.12;9.10. Действительно 5.6 больше 4.11, а 9.10 меньше 10.15 .Но верный ответ все-таки только 8.12!Но ответ этот неверный. Так что не могу с этим алгоритмом согласиться.

_DA>Согласен. Извиняюсь
_DA>Тут ниже уже упомянули kd-дерево. Можно попробовать применить его. В данном случае k будет 2 (вспоминается анекдот про камерный оркестр). То есть находится медиана всего множества записей по первому полю, множество разбивается пополам, затем каждое их них так же разбивается по медиане по второму полю, затем опять по первому и т.д.
Возможно это и выход, но дело в том что kd-tree нужно организовать в памяти, а как я уже говорил выборки могут быть настолько большими, что что не влезут в оперативку. Что делать тогда?

Здравствуйте, trump-card, Вы писали:

TC>Возможно это и выход, но дело в том что kd-tree нужно организовать в памяти, а как я уже говорил выборки могут быть настолько большими, что что не влезут в оперативку. Что делать тогда?
1. Можно в качестве листьев kd-дерева оставлять не одиночные записи, а целые группы записей на диске. Внутри такой группы на диске просматривать все записи.
2. Можно объединять узлы в кластеры, которые хранятся на диске и кэшируются в памяти. Например, так (три уровня объединены в один кластер, реально нужно объединять намного больше):

                      +-------------+
                      |0     *      |
                      |     * *     |
                      |    12 34    |
                      +-------------+
+-------------++-------------++-------------++-------------+
|1     *      ||2     *      ||3     *      ||4     *      |
|     * *     ||     * *     ||     * *     ||     * *     |
|    56 78    ||  9 10 11 12 || 13 14 15 16 || 17 18 19 20 |
+-------------++-------------++-------------++-------------+

Кстати, ещё можно почиать третий том Кнута.

TC>Пример — простейший: запись cостоит из двух полей. Вот сама таблица — 2.1; 3.2; 4.5; 3.13; 8.12; 1.2; 3.6; 3.3; 8.1; 5.6; 11.25; 15.11; 12.13; 9.10

Каковы диапазоны допустимых значений для 1-го и 2-го полей?

Здравствуйте, What, Вы писали:
W>Здравствуйте, trump-card, Вы писали:
W>Кстати, ещё можно почиать третий том Кнута.

И даже очень нужно.
А потом подумать такую мысль: "В движке СУБД как раз и реализованы описанные Кнутом алгоритмы и структуры, причем заточенные именно под внешнюю память и большие объемы."

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

W>>Кстати, ещё можно почиать третий том Кнута.

W>И даже очень нужно.
W>А потом подумать такую мысль: "В движке СУБД как раз и реализованы описанные Кнутом алгоритмы и структуры, причем заточенные именно под внешнюю память и большие объемы."

Это не факт. Не уверен, что движки СУБД оптимизированы под пространственные запросы.
По крайней мере, я смотрел, как SQL сервер 2000 проводит выборки.
Для запроса (0 < X < 10) AND (0 < Y < 10)
он находит множества {(0 < X < 10)} и {(0 < Y < 10)}, а потом выполняет пересечение. Это, естественно, далеко не оптимально.
Так что в ряде случаев специальные структуры данных для пространственных выборок могут сильно обгонять СУБД.

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

W>Это не факт. Не уверен, что движки СУБД оптимизированы под пространственные запросы.
Конечно не оптимизированы сами по себе. Но они могут оптимизировать запросы разных типов. А кроме того, есть специализированные движки и надстройки над реляционными СУБД для работы с пространственными данными.

W>По крайней мере, я смотрел, как SQL сервер 2000 проводит выборки.
W>Для запроса (0 < X < 10) AND (0 < Y < 10)
W>он находит множества {(0 < X < 10)} и {(0 < Y < 10)}, а потом выполняет пересечение. Это, естественно, далеко не оптимально.
Это проблема не SQL сервера, а того, кто проектировал базу.

W>Так что в ряде случаев специальные структуры данных для пространственных выборок могут сильно обгонять СУБД.
Согласен.

Здравствуйте, trump-card, Вы писали:

TC>Здравствуйте. Не могли бы вы подсказать алгоритм, который бы позволил решить следующую задачу:
TC>Имеется список(множество) объектов-записей с различными полями, который находится на диске в виде одного или нескольких очень больших файлов. Каждое поле записи является ключем. Необходимо организовать поиск так, чтобы в результате получить подмножество, содержащее записи, у которых первое поле попадает в свой заданный интервал значений, второе — в свой и т.д. Причем, необходим такой алгоритм, чтобы при одном обращении либо находилась следующая из записей по определенному порядку(допустим, по алфавиту в нескольких полях, если это текст), либо сообщалось, что больше подходящих записей нет. Решение, которое использует сначала поиски по каждому из полей, а потом сравнение результатов поисков с целью нахождения пересечения этих множеств, не годится, т.к. эти множества предполагаются большими, и в оперативную память не помещающимися.
Ну, во-первых, ты можешь применить линейный индекс. Тебе уже предложили отсортировать сначала по одному полю, а потом по другому. При этом нужно сначала сортировать по тому полю, селективность запросов по которому выше.
Рассмотрим твой пример:

 2  1
 3  2
 4  5
 3 13
 8 12
 1  2
 3  6
 3  3
 8  1
 5  6
11 25
15 11
12 13
 9 10

Мы делаем запрос на (4..10, 11..15). Под первое условие попадают 5 записей, под второе — тоже 5. Предположим, что у нас есть древовидный индекс по ключу (X, Y). Нам надо найти подмножество ключей из диапазона (4,11)..(10, 15). Вот записи, отсортированные в порядке индекса:

 1  2
 2  1
 3  2
 3  3
 3  6
 3 13
 4  5
 5  6
 8  1
 8 12
 9 10
11 25
15 11
12 13

За O(log(N)) получаем первую запись из диапазона (4, ...) — (10, ...). Это (3, 13). Ее придется проверить на предикат по Y и убедиться, что она подходит. Это выполняется за O(1), как и переход к следующей записи в индексе. Таким образом, нам придется перебрать все пять записей с X в [4, 10]. Итого, затраты пропорциональны O(LogN) + O(K), где К — количество записей, отобранных первым предикатом. Если K/N достаточно невелико, то производительность запроса будет приемлемой. Но это смотря по сравнению с чем. K записей являются всего лишь кандидатами. В нашем случае в финальный результат попадут только три из пяти. Это еще достаточно неплохо. Для геосистем типично примерное соответствие K/N ~ R/K, где R — это количество записей результата.
Дальнейшее сокращение времени поиска возможно только при отказе от одномерности индекса. Эта тема до сих пор находится в стадии исследований; есть R-tree — специальные деревья, заточенные под многомерный поиск. У них проблема в том, что они плохо балансируются (по сравнению с B-деревьями, рулящими для одномерных индексов). Если данные меняются редко, то такие деревья вполне можно применять. Если же данные часто удаляются/изменяются, то надо поискать более совершенные способы индексирования. Я как-то натыкался на статью про многомерные индексы, которые вроде как сохряняют логарифмичность всех операций, и при этом имеют гарантированный филл-фактор в 1/(M+1), где M — количество измерений индекса.
В общем, погугли по multidimensional indexing.