Эффективная структура данных для представления отношений между районами -> штатами -> нацией - PullRequest
Новая
       18

Эффективная структура данных для представления отношений между районами -> штатами -> нацией

0 голосов
/ 02 июня 2009

Я ищу эффективный способ для представления и получения географических отношений, например. districts-> states-> США. Это должно соответствовать любому уровню иерархии, например. район-> регион-> штаты-> большой регион (восток / запад / юг / север) -> США.

Мои требования

  1. Я в основном работаю на самом низком уровне - поэтому быстрое получение их всех должно быть первым приоритетом. Постоянное время является предпочтительным.
  2. Затем я хочу выполнить агрегацию, например, данные по районным бинарным округам на уровне штатов (чтобы получить все дочерние элементы для узла) - это второй критерий.
  3. Порядок на уровне не имеет значения, например. Что касается NC, я не против, если я впервые получу Роли или Фейетвилл.

Как вы уже догадались, структура данных Tree логически поддается решению проблемы. Но я не мог найти способ получить все листья эффективно. Я могу проверить, является ли узел листом O (log n), но я должен проверить каждый из узлов для этого.

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

У меня такое чувство, что для этого должны быть эффективные решения, потому что - Windows или любая файловая система делает это. Файлы-> Папки-> Большие папки-> C -> Мой компьютер. Кроме того, такого рода вычисления должны быть выполнены в интеллектуальном анализе данных, скажем, для кластеризации (я помню, что читал что-то подобное)

Будут благодарны любые выводы в этом направлении.

Спасибо

Ответы [ 2 ]

1 голос
/ 02 июня 2009

Вы говорите о получении n уникальных элементов, соответствующих заданному критерию (в данном случае все на определенном уровне в иерархии под данным узлом). Вы не можете получить n уникальных элементов из структуры данных за постоянное время, если вы предварительно не вычислили все возможные критерии. По крайней мере, вам придется перебирать эти n элементы.

Существует множество структур данных и комбинаций структур данных, которые можно использовать для повышения эффективности различных видов использования. Вы правы, что B и B + деревья хорошо работают в этой ситуации, поэтому я собираюсь предложить вам использовать реляционную базу данных для этого приложения, поскольку они являются лучшими и наиболее надежными реализациями B-деревьев, которые вы сможете найти. Соответствие конечных узлов и вычислительных агрегатов - это почти то, для чего они нужны. Если у вас нет особых причин не использовать подсистему РСУБД, это, вероятно, ваш лучший выбор.

0 голосов
/ 15 июня 2010

Создайте дерево узлов, где каждый узел содержит:

  • Указатель на родительский узел (или нулевой для корневого узла)
  • Коллекция (например, HashMap или ArrayList в Java) дочерних узлов
  • Любая полезная нагрузка данных, связанная с узлом (например, географические координаты, позволяющие выполнять поиск по расстоянию)

Если хотите, вы можете дополнить это индексом String -> Node для доступа к узлам на основе HashMap для доступа к узлам. Но для этой проблемы я бы не стал беспокоиться о стоимости поиска по дереву, поскольку у вас вряд ли будет максимум 5-10 уровней.

...